PipeNTT: A Pipelined Number Theoretic Transform Architecture

Polynomial multiplication is the key and time-consuming operation among various operators in Post-Quantum Cryptography (PQC), which aims to find quantum-resistant algorithms to prevent attacks launched by quantum computers. Number Theoretic Transform (NTT) is an efficient algorithm that can accelerate the polynomial multiplication from O(n²) to O(nlog(n)). In this paper, we present a pipelined NTT (PipeNTT) hardware architecture in FPGA to achieve high throughput with fewer hardware resources. The dataflow and the butterfly unit are optimized to minimize the latency. To fulfil the proposed dataflow, a Block RAM (BRAM) based reordering unit is designed to further reduce the hardware resource. Moreover, our architecture can also be applied to Inverse-NTT (INTT). Compared to state-of-the-art parallel designs, our design achieves a 30% lower area-time product with 3x less memory space requirement.