Faster Homomorphic Discrete Fourier Transforms and Improved FHE Bootstrapping

Jung Hee Cheon, Kyoohyung Han, Minki HhanIACR ePrint 2018

TL;DR

This paper introduces a significantly faster method for computing homomorphic Discrete Fourier Transforms (DFT) and a corresponding improvement in the bootstrapping process for Fully Homomorphic Encryption (FHE). By exploiting the sparse structure of DFT matrices, they achieve a dramatic speedup, making complex computations on encrypted data much more practical.

What Problem Does This Paper Address?

Fully Homomorphic Encryption (FHE) allows computations on encrypted data without decryption, but it's computationally expensive. A key bottleneck is the "bootstrapping" process, which is necessary to refresh the noise in ciphertexts and enable deeper computations. Bootstrapping relies heavily on linear transformations, particularly the Discrete Fourier Transform (DFT), which is used in various signal processing and data analysis tasks. Existing methods for homomorphic DFT and bootstrapping are slow, often requiring a large number of operations and significant computational depth. This paper addresses the need for more efficient homomorphic evaluation of these critical linear transformations to make FHE more practical.

Methods

The core innovation lies in exploiting the inherent structure of the DFT matrix. The authors propose a new method for homomorphic DFT evaluation by factorizing the DFT matrix into sparse diagonal matrices, inspired by the Cooley-Tukey fast Fourier transform algorithm. This factorization allows them to perform the homomorphic DFT using a logarithmic number of operations (rotations and constant vector multiplications) with a logarithmic depth, a significant improvement over previous methods that required square-root or linear numbers of operations.

They then apply this same matrix decomposition strategy to the linear transformations used in bootstrapping for the HEAAN (Homomorphic Encryption for Approximate Number) scheme. By recursively decomposing the matrices involved, they achieve a similar logarithmic complexity for these transformations, drastically reducing the computational burden of bootstrapping. The paper also introduces a "hybrid method" that combines their approach with the baby-step giant-step algorithm, offering a trade-off between depth and complexity.

Datasets

Not discussed in the paper. The paper focuses on algorithmic improvements and theoretical analysis, with experimental validation on simulated data.

Key Insights and Ideas

  • Exploiting Sparsity is Key: The paper highlights that the overlooked sparse structure within DFT and bootstrapping matrices is the critical factor for achieving efficiency.
  • Logarithmic Complexity is Achievable: By decomposing matrices into sparse diagonal forms, they demonstrate that homomorphic DFT and linear transformations in bootstrapping can be performed with logarithmic complexity in terms of operations and depth.
  • Bootstrapping Bottleneck Addressed: The significant speedup in linear transformations directly translates to a much faster bootstrapping process, a crucial step for enabling complex computations in FHE.
  • Trade-offs for Practicality: The introduction of a hybrid method and the concept of "radix" allow for flexible trade-offs between computational depth and the number of operations, catering to different FHE application needs.

Key Results

  • Homomorphic DFT Speedup: Their homomorphic DFT algorithm with length $2^{14}$ takes approximately 8 seconds, which is about 150 times faster than previous methods.
  • Bootstrapping Speedup: The bootstrapping procedure for HEAAN with their improved linear transformation algorithm takes about 2 minutes for a $C^{32768}$ plaintext space with 8-bit precision. This is a dramatic improvement compared to the previous method, which took 26 hours for the same setting.
  • Reduced Key Size: The proposed method significantly reduces the size of public keys required for operations, from 800GB in previous methods to 7GB in their implementation for a large plaintext space.

Limitations and Future Work

  • Focus on Power-of-Two Dimensions: The paper primarily focuses on DFT with power-of-two dimensions, although they mention that the method can be generalized to other prime dimensions.
  • Approximate Homomorphic Encryption: The work is based on approximate homomorphic encryption schemes (like HEAAN), which introduce small errors. The paper notes that they can reduce this difference between encrypted and un-encrypted states by using larger scaling factors.
  • Future Work: The authors suggest that their technique can be applied to other linear transformations and potentially to bootstrapping for sparsely packed ciphertexts. They also imply that further optimizations might be possible by exploring dynamic radices for recursive steps.

Summary updated

BibTeX
@article{cheon2018faster,
  author = {Jung Hee Cheon and Kyoohyung Han and Minki Hhan},
  title = {{Faster Homomorphic Discrete Fourier Transforms and Improved FHE Bootstrapping}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2018},
}
Figure