Rethinking Parallel Memory Access Pattern in Number Theoretic Transform Design

Number theoretic transform (NTT) is widely applied as a fundamental component of next-generation cryptosystems. This brief introduces a novel high-low interactive memory access pattern for an out-of-place NTT design, which can be configurable in degree of parallelism. To achieve high area efficiency, the memory component of the proposed pattern is flexibly selected referring to the design parameters. Then for the first time, we present a quantitative analysis about the relevance between the degree of parallelism and the number of computing cycles. More importantly, we put forward a universal method of avoiding the memory conflict and obtaining the minimal number of computing cycles in a configurable NTT design. Based on the above optimization techniques, we develop the first parameterized out-of-place NTT architecture. Experimental results on FPGA show that our design can achieve higher efficiency in LUTs and BRAMs compared with previous works.