SHP-FsNTT: A Scalable and High-Performance NTT Accelerator Based on the Four-step Algorithm

Lattice-Based Cryptography (LBC) emerges as a powerful cryptographic primitive, offering a solution for post-quantum security. Within LBC schemes, one of the most computationally intensive tasks is polynomial multiplication, which can be accelerated through the Number Theoretic Transform (NTT). This paper proposes SHP-FsNTT, a scalable, dynamically configurable and high-performance hardware accelerator based on four-step NTT algorithm to support both NTT and inverse NTT (INTT). SHP-FsNTT leverages pipeline parallelism and data parallelism, and optimizes the memory access pattern to avoid the implementation of a matrix transposition unit for the four-step algorithm. The proposed design achieves remarkable area-time efficiency improvement compared with state-of-the-art works on FPGA.