A Low-Complexity, Conflict-Free Memory Access Scheme for Flexible NTT /INTT Architecture

Number Theoretic Transform (NTT) and inverse NTT (INTT) are widely used to accelerate polynomial multi-plications in lattice-based cryptosystems. This paper proposes a low-complexity coefficient memory access pattern for an in-place NTT/INTT design. It simplifies the data path between the processing elements (PEs) and the memory banks. Moreover, to avoid read-after-write conflicts and achieve minimal (I)NTT computing cycles, we present a strategy that dynamically calculates and inserts necessary idle cycles during (I)NTT processing. Based on the proposed low-complexity and conflict-free memory access scheme, we develop a flexible NTT/INTT unified architecture. Our design allows the configuration of various parameter sets and parallelism setups at compile-time, while supporting polynomials of multiple degrees and moduli of different sizes at run-time. Experimental results on FPGA show that our design achieves better area efficiency and flexibility compared with previous works.