Compact FALCON FFT/NTT Accelerator for Post-Quantum Cryptography

FALCON is one of four algorithms selected by NIST to standardize post-quantum cryptography standards. FALCON is a digital signature algorithm based on NTRU lattice with difficulty based on the short vector problem. While Kyber and Dilithium algorithms are only based on NTT operations, FALCON uses both NTT and FFT, which is a barrier to Falcon’s hardware implementation. This paper proposes a compact architecture that supports FFT and NTT for the FALCON algorithm. First, we propose an architecture that executes floating-point and complex number operations with theoretic speed and low area requirements. Then, we design a processing element that performs FFT with complex number operations. Finally, we propose an NTT architecture that reuses the resources used for FFT execution with high parallelism. The FPGA implementation results show that the FFT execution takes 2.048k CCs and 4.608k CCs for the 512-point and 1024-point FFT/IFFT, respectively. The NTT/INTT operation takes 288 CCs for FALCON-512 and 640 CCs for FALCON-1024. The speedup improves from 3× to 9.6× for FFT and up to 18× for NTT implementations compared to previous studies.