Improved Homomorphic Discrete Fourier Transforms and FHE Bootstrapping

Homomorphic encryption (HE), which enables computation on ciphertexts without any leakage, rise as a most promising solution for privacy-preserving data processing, including secure machine learning and secure out-sourcing computation. Despite the extensive applicability of HE, the current constructions are sometimes considered as impractical due to its inefficiency. In this paper, we propose improvements on the linear transformation in bootstrapping, a technique allowing the infinite number of operation for HE, and homomorphic discrete Fourier transformation (DFT) using batch homomorphic encryption. We observe that the multiplication of a sparse diagonal matrix and ciphertext of a vector can be done within O(1) homomorphic computations. This observation induces the faster algorithm for linear transformation in bootstrapping and homomorphic DFT. To achieve this, we use Cooley-Tukey matrix factorization and construct a new recursive factorization of the linear transformation in bootstrapping. Our method with radix r only requires O(r log r n) constant vector multiplication and O(√r log r n) rotations by consuming O(log r n) depth when the input vector size is n. The previous method used in the library, a library that implements homomorphic encryption for approximate computation, requires O(n) and O(√n), respectively. To show the performance improvement, we implement our method on top of the library. Our implementation, along with further few techniques, of these algorithms show the significant improvements compared to the previous algorithm. New homomorphic DFT with length 2 14 only takes about 8s which results 150 times faster than the previous method. Furthermore, the bootstrapping takes about 2 minutes for ℂ 32768 plaintext space with 8-bit precision, which takes 26 hours with same bit precision using the previous method.