Fast Estimation of NTT/INTT Accelerator Costs for RNS-Based Homomorphic Encryption

Abstract

This paper proposes a hardware estimator for accelerating number theoretic transform (NTT) for fast polynomial operations in the ring learning with error (RLWE) based homomorphic encryption (HE). By modifying the number of unit processing elements, modulus bit-width, and residue number system (RNS) parameters, we present a systematic way for rapidly calculating the hardware complexity without realizing the target accelerator. Compared with the actual synthesis results in 28nm CMOS technology, experimental results show that the proposed work successfully estimates the NTT accelerator area even under the large-valued parameters with acceptable errors, greatly relaxing the overheads for the design space exploration. Homomorphic encryption, residue number system, hardware accelerator