A Unified FFT/NTT Design for Efficient NTRU Equation Solving in FALCON Cryptography

Post-Quantum Cryptography has garnered significant attention with the rapid development of quantum computing. FALCON, a lattice-based quantum-resistant digital signature scheme, has been standardized. During the key pair generation process, solving the NTRU equation based on Galois theory is required. The simultaneous use of two distinct algebraic structures, $\mathbb{Q}[x]/\left( {{x^n} + 1} \right)$ and $\mathbb{Z}[x]/\left( {{x^n} + 1} \right)$, where n is a power of 2, presents challenges in hardware design. This paper proposes a hardware accelerator specifically customized for FFT/IFFT and NTT/INTT operations on rings under different point numbers. The design incorporates conflict-free scheduling for memory access and the selection of twiddle factors across various radices. The proposed design occupies an area of 0.54 mm<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> and operates at a frequency of 333 MHz based on the synthesis results using 40nm technology. Compared to existing FFT/IFFT design on rings, the proposed one reduces the area requirement of processing elements by 33% without increasing the overall execution time. Moreover, our design supports both 64-bit radix-4 and 128-bit radix-2 NTT/INTT. This solution effectively addresses the two transformations required for key pair generation in FALCON.