Fast FHE on GPGPU

Fully Homomorphic Encryption (FHE) is experiencing a surge in interest due to its com- pelling features in secure data processing, making the exploration of its optimization more pertinent than ever. This study presents an in-depth analysis and optimization of all critical components of the FHE bootstrapping process, with a particular focus on GPU acceler- ation. Our research explores the intrinsic parallel nature of FHE operations, where we have managed to parallelize polynomial multiplication using Karatsuba, Number Theo- retic Transform (NTT), and Fast Fourier Transform (FFT) methods. The study elucidates the design considerations and implementation techniques for mapping these computa- tions effectively onto GPU architectures. We report significant performance gains over existing state-of-the-art CPU and GPU implementations, achieving up to a 28x speedup for certain operations. These results underline the potential for substantial performance enhancements in FHE through careful algorithmic design and effective use of the parallel processing capabilities of modern GPUs. 3

Lecture files: