Invited Paper: Efficient Design of FHEW/TFHE Bootstrapping Implementation with Scalable Parameters

Fully Homomorphic Encryption (FHE) is vital for computing over encrypted data, thereby enabling numerous privacy-preserving applications. This work focuses on the third generation FHE schemes (e.g., FHEW and TFHE), known for their fast bootstrapping, small FHE parameters, and robust security built on milder assumptions. Our goal is to improve the efficiency of implementation for scalable parameters. Notably, scaling up FHE parameters moderately, such as the plaintext space, extends the applicability of third-generation FHEs to a broader range of practical scenarios. However, prevailing state-of-the-art libraries such as OpenFHE and TFHE either lack support for extensive FHE parameters beyond 64-bit integers or suffer significant performance slowdowns on widely used 64-bit architectures. To tackle this challenge, we propose a novel FFT-based multiplication implementation, which decomposes large numbers (e.g., 128-bit integers) into multiple doubles (64-bit floating points). To optimize the performance, we refine the error analysis in FFT-based FHEW/TFHE computation with the decomposition for the optimal balance between efficiency and decryption failure probability. We evaluate our approach through comprehensive experiments, showing a 5-7x speedup using 64-bit architecture over 128-bit in core operations compared to existing libraries. Our implementation is particularly conducive to parallelization, making it well-suited for hardware acceleration, such as GPUs.