Fast Fourier Transform and Gaussian Sampling Instructions Designed for FALCON Digital Signature
摘要
FALCON is one of the signature schemes selected for standardization in the post-quantum cryptography project posted by the National Institute of Standards and Technology (NIST). To ensure signature security and randomness, discrete Gaussian sampling requires high-precision calculations, especially in high-dimensional spaces, where its computational complexity increases significantly. As a result, discrete Gaussian sampling is a performance bottleneck when implementing the FALCON algorithm on embedded devices or devices constrained by resources. FALCON uses the Fast Fourier Transform (FFT) for polynomial operations, which is crucial for optimizing Gaussian sampling. However, FFT is another performance bottleneck in the implementation of FALCON. Moreover, the computational complexity of FFT increases with the growth of the coefficients’ number. This paper proposes a hardware-software co-design to accelerate FALCON’s discrete Gaussian sampling and FFT. First, we design and implement the hardware architecture for discrete Gaussian sampling and FFT. Next, we embed these hardware accelerators into the RISC-V-based IBEX core and design the corresponding RISC-V instructions. Finally, we adopt customized instructions to implement FALCON and measure clock cycles and hardware consumption. Compared to the reference software implementation, our hardware-software implementation accelerates the signature scheme by \(2\times \) and the key generation by about \(30\%\) , with some additional hardware circuit consumption.