Area Efficient Twiddle Factor Design for NTT/INTT Hardware Implementation

Efficient polynomial multiplication is essential for lattice-based quantum-resistant cryptographic algorithms such as CRYSTALS-Kyber. Therefore, this paper presents an area- efficient twiddle factor design for Number Theoretic Transform (NTT) and inverse NTT (INTT) that significantly reduces on- chip memory utilization. The NTT is widely used for polynomial multiplication in cryptographic operations. The core of NTT is the butterfly unit that performs the modular operations with precomputed twiddle factors (roots of unity). This paper proposes a twiddle factor design based on two- and four-fold techniques. The total number of precomputed values required during the NTT/INTT process is 254 (127 values for NTT and 127 for INTT). Our design reduces the number of values required to be stored in read-only memory (ROM) to 148(+4) and 106(+4) for two-fold and four-fold techniques, respectively. The design reduces memory utilization by <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathbf{4 0. 1 6 \%}$</tex> for the two-fold unit and 56.69% for the four-fold unit compared to the conventional design. We implemented the proposed design using Kyber-digital signal processing (K-DSP) as a modular multiplication unit. The resource consumption by the proposed design on the Artix-7 FPGA platform are presented as follows: 113 LUTs, 97 FFs, 301 SLICEs for twofold computation unit, and 220 LUTs, 111 FFs, 473 SLICEs for four-fold computation units.