NTTFusion: Efficient Number Theoretic Transform Acceleration on GPUs
Zhiwei Wang, Peinan Li, Rui Hou, Dan Meng · 2023
Fully homomorphic encryption (FHE) holds great promise as an encryption technology for safeguarding privacy by enabling computations directly on encrypted data. However, FHE encounters significant performance bottlenecks due to the extensive utilization of number theoretic transform (NTT) and its inverse (INTT). Therefore, it is crucial to accelerate NTT to enhance the efficiency of FHE. Conventional NTT implementations rely on mandatory synchronization to maintain data consistency, which leads to two critical problems: excessive synchronizations and unexplored synchronization switching points. This paper presents NTTFusion, an efficient GPU-based NTT acceleration design that focuses on boosting the performance of NTT. (i) To reduce the number of synchronizations, we propose two types of stage fusion methods specifically designed for different polynomial lengths. For small polynomial lengths, we employ the butterfly decomposition approach, while for large polynomial lengths, we leverage the thread aggregation method. (ii) To explore the optimal synchronization switching point, we propose an SM-aware synchronization combination strategy to balance synchronization overhead and hardware utilization. Finally, we conduct experiments on a realistic NVIDIA GPU server and demonstrate that the butterfly decomposition method achieves up to 1.37× speedup compared to the state-of-the-art implementation. Furthermore, the thread aggregation method can yield up to 1.32× speedup for larger polynomial lengths. The optimal synchronization switching point-based NTT, which incorporates thread aggregation, can produce a maximum 1.6× performance boost under a typical large polynomial length.