Paper 2018/1073

Faster Homomorphic Discrete Fourier Transforms and Improved FHE Bootstrapping

Jung Hee Cheon, Kyoohyung Han, and Minki Hhan


In this work, we propose a faster homomorphic linear transform algorithm for structured matrices such as the discrete Fourier transform (DFT) and linear transformations in bootstrapping. First, we proposed new method to evaluate the DFT homomorphically for a given packed ciphertext from the Cooley-Tukey fast Fourier transform algorithm. While the previous method requires $O(\sqrt n)$ rotations and $O(n)$ constant vector multiplications, our method only needs $O(\log n)$ rotations/multiplications by consuming $O(\log n)$ depth for the length of input vector $n$. Second, we apply the same method to the linear transform of bootstrapping for $\textsf{HEAAN}$. To achieve this, we construct a recursive relation of matrices in those linear transformations. Accordingly, we can highly accelerate the linear transformation part of bootstrapping: the number of homomorphic operations becomes logarithmic to the number of slots, as in homomorphic DFT. We also implement both algorithms. Our homomorphic DFT with length $2^{14}$ only takes about 8 seconds which is about 150 times faster result than previous one. The bootstrapping for $\textsf{HEAAN}$ with our linear transform algorithm takes about 2 minutes for $\mathbb{C}^{32768}$ plaintext space with 8 bit precision, which takes 26 hours using the previous method.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
Discrete Fourier TransformHomomorphic EncryptionBootstrapping
Contact author(s)
satanigh @ snu ac kr
2018-11-09: received
Short URL
Creative Commons Attribution


      author = {Jung Hee Cheon and Kyoohyung Han and Minki Hhan},
      title = {Faster Homomorphic Discrete Fourier Transforms and Improved FHE Bootstrapping},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1073},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.