HyperNTT: A Fast and Accurate NTT/INTT Accelerator with Multi-Level Pipelining and an Improved K2-RED Module

Post-quantum cryptography is advancing rapidly to counteract the potential threats posed by upcoming quantum computers, with lattice-based algorithms playing a key role. In these algorithms, polynomial multiplication using the number theoretic transform (NTT) presents a significant computational challenge, affecting performance. Existing NTT architectures face challenges in achieving high performance and low area, and the K2-RED module within the NTT is prone to bit overflow errors. Therefore, this paper introduces HyperNTT with three innovative ideas to achieve high throughput, low area consumption, and error-free polynomial multiplication. First, HyperNTT utilizes a multi-stage pipeline with NTT cores that incorporate a fully-pipelined butterfly unit (FPBU) design, reducing the workload per stage by one-third compared to conventional methods. Second, simplified modular reduction modules are recommended to substitute multiplication with shifts and additions, thereby optimizing pipeline efficiency for high-speed performance. Third, a DSP-free HyperNTT with the new K2-RED architecture is proposed to mitigate error cases and balance execution time, area, and energy efficiency. The HyperNTT architectures have been implemented at the System-on-Chip (SoC) level for correctness verification. Besides, FPGA evaluations demonstrate that Hyper-NTT outperforms previous works by 1.2 to 6 times in area-delay product, while the ASIC experiment shows its superiority by at least 2.84 times in area-delay product and power-delay product.