Welcome to the resource topic for 2018/1073
Title:
Faster Homomorphic Discrete Fourier Transforms and Improved FHE Bootstrapping
Authors: Jung Hee Cheon, Kyoohyung Han, Minki Hhan
Abstract: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.
ePrint: https://eprint.iacr.org/2018/1073
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .