A Timing-Constrained Design Methodology for Radix- 2 ^<i>k</i> NTT in Polynomial Arithmetic

Polynomial modular multiplication is the most complex and costly operation in homomorphic encryption (HE) and post-quantum cryptography (PQC). Using the Number Theoretic Transform (NTT) helps reduce the complexity of multiplication to quasi-linear O(<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$N\,\textup{log}_{2}N$</tex-math></inline-formula>). Although NTT significantly impacts the performance of HE and PQC, existing NTT-based multipliers often fall short due to inefficient data movement and large memory overhead. Notably, deploying low-latency cryptosystems incurs more significant costs with reduced acceleration gains. To overcome these constraints, we introduce a pioneering methodology called timing-constrained NTT (TCO-NTT). We propose an innovative time-controlled memory (TCM) structure that re-orders and stores coefficients within each stage of the NTT. Then, we employ the divide-and-conquer strategy, allowing freely configurable parallelism levels. Besides, our proposed methodology can generalize to radix-2<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><i>k</i></sup> NTT and supports any arbitrary polynomial degree <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</i> and scale factor <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p</i> values. We evaluate the proposed TCO-NTT on typical HE and PQC parameter sets across multiple levels of parallelism and radix-2<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><i>k</i></sup> NTT configurations. FPGA implementation results demonstrate that our TCO-NTT achieves minimal hardware cost while consistently executing the NTT in a near-theoretical execution time. Our area-time product (ATP) reports about LUT-ATP (LATP), FF-ATP (FATP), and BRAM-ATP (BATP) surpass the reported-to-date NTT designs by up to 10.2×, 17.8× and 47.2×. The proposed TCO-NTT sets new records for NTT-based multiplier efficiency, laying the foundation for implementing HE and PQC in real-time applications.