Flexible GPU-Based Implementation of Number Theoretic Transform for Homomorphic Encryption
Phap Duong-Ngoc, Thang Xuan Pham, Hanho Lee, Tuy Tan Nguyen · 2022 19th International SoC Design Conference (ISOCC) · 2022
This paper proposes a flexible implementation of Number Theoretic Transform (NTT) on GPU platforms. The proposed method introduces an adjustable number (i.e.,$NTT_{core}$) of butterfly units that are simultaneously implemented in each NTT computational stage. The NTT implementation of a large polynomial was experimented on an NVIDIA GeForce RTX 3070 GPU card and showed at least 21× acceleration compared with that on the CPU. The proposed approach is worthy to parallelize NTT computations of multiple polynomials in expensive homomorphic functions with high circuit depth.