An Acceleration Architecture of Polynomial Multiplication based on NTT for CKKS Homomorphic Evaluation

The Number Theoretic Transform (NTT) is currently widely used to accelerate polynomial multiplication in finite fields, which is the computational bottleneck of lattice-based fully homomorphic encryption schemes. The key challenge of NTT hardware structure implementation lies in the large amount of data storage and the complex pattern of data access. This paper proposes an efficient data access pattern of NTT algorithm. Benefiting from the specific pattern optimization of different stages of NTT, the use of hardware resource can be reduced by 46%~80%, and the performance based on FPGA is increased up to 4.9x compared with state-of-the-art NTT implementation. Furthermore, we apply the proposed hardware structure to realize the homomorphic evaluation of the CKKS homomorphic scheme, whose performance is improved by 7300x compared with software implementation.