An Area-Efficient, Conflict-Free, and Configurable Architecture for Accelerating NTT/INTT

The Number Theoretic Transform (NTT) is a widely adopted method for accelerating polynomial multiplication in lattice-based cryptosystems. Consequently, numerous hardware accelerators have been developed to enhance the speed of the NTT algorithm. Area-Time Product (ATP) and configurability are critical metrics for evaluating these accelerators. ATP measures efficiency, while configurability ensures adaptability to various algorithm parameters and hardware limitations. In this article, we propose an area-efficient, conflict-free, and configurable architecture for accelerating NTT/inverse NTT (INTT). The proposed architecture demonstrates adaptability to various parameter settings while maintaining a consistently low ATP, even under a high level of parallelism. Moreover, our architecture supports polynomials of different degrees after compilation, further enhancing its versatility. To minimize latency, we adopt the existing merged Constant-Geometry (CG) NTT and INTT algorithm to combine preprocessing and postprocessing and further eliminate the bit-reverse operation in the algorithm. Building upon this foundation, we propose low-complexity memory access patterns for polynomial coefficients and twiddle factors, which contribute to high area efficiency and configurability in our architecture. The implementation results on FPGA substantiate that the proposed architecture exhibits remarkable superiority over existing works in terms of configurability and area efficiency.

I. Introduction

Lattice-based cryptography (LBC) is a prominent branch of modern cryptography, which utilizes mathematical lattice structures to ensure the security of information. Due to its high level of security, LBC has become an important research direction in post-quantum cryptography. Its applications are experiencing a significant increase in traditional security problems, such as public key encryption [1], [2], [3], and digital signature [4], [5]. Additionally, emerging security challenges, including homomorphic encryption [6], [7] and identity-based encryption [8], are also being addressed using LBC. However, the practical application of LBC is still limited by computational speed, especially for polynomial multiplication, which requires significant computing resources. The Number Theoretic Transform (NTT) algorithm is commonly used to address this issue. NTT is a number theory-based fast Fourier transform (FFT) algorithm that can reduce the computational complexity of polynomial multiplication from to , where refers to the degree of the polynomial. This significant reduction in complexity greatly enhances the speed of polynomial multiplication, making NTT an essential component in the implementation of lattice cryptosystems.