Hardware implementation of the post-quantum cryptography algorithm falcon

Abstract

The emergence of quantum computing poses a significant threat to classical cryptographic systems, as it undermines the hardness assumptions on which widely used public-key schemes such as RSA and ECC are based. In response to this evolving threat landscape, the National Institute of Standards and Technology (NIST) launched a multi-year, open international process in 2016 to identify and standardize post-quantum cryptographic (PQC) algorithms that are secure against quantum adversaries. This initiative has involved extensive evaluation of submissions based on their security, efficiency, and suitability for practical deployment. Among the algorithms submitted and assessed throughout NIST's multi-round selection process, FALCON (Fast Fourier Lattice-based Compact Signatures over NTRU) emerged as one of the selected candidates for digital signature standardization. FALCON is a lattice-based digital signature scheme, and leverages several techniques and methods for efficient polynomial arithmetic, offering significant performance improvements over conventional lattice-based schemes. The novel Fast Fourier Sampling method, that is developed by the creators of FALCON, is a central component of this efficiency. This method is employed alongside various other algorithms, including the Fast Fourier Transform (FFT) and floating-point arithmetic, to compose the complete algorithm in three parts: key generation, signature generation and verification. This study aims to analyze FALCON in detail and identify key components for hardware acceleration. The goal is to design accelerator cores to enhance the speed of the major algorithmic parts, and to form a System-on-Chip (SoC) that includes the accelerator cores, a RISC-V processor, and a special Direct Memory Access (DMA) module, to improve the overall efficiency of the signature generation and verification processes. The initial phase involved a comprehensive analysis of the FALCON algorithm, utilizing reference documentation and the official C implementation. A C profiler was used to measure the execution time distribution across various sub-functions. This profiling revealed the computational structure of the algorithm, identified performance bottlenecks, and highlighted operations most suitable for acceleration. To enable hardware-software integration, the reference C code was modified for compatibility with a RISC-V environment. And to establish a baseline, compiled codes for the signature generation and verification of FALCON was employed on a actual FPGA implementation of a RISC-V core, VexRiscv, and the clock cycles required by each major sub-function were measured. Following this analysis, a design methodology was adopted that focuses on implementing selected components of the algorithm in their entirety. Rather than developing generalized cores for basic operations—intended for reuse across multiple sub-functions—this approach targets the direct hardware realization of specific, high-impact sub-functions as dedicated accelerator cores. This methodology significantly reduces the communication overhead between the software and hardware domains, which is often a bottleneck in hybrid implementations. Although this approach may incur higher resource consumption, it enables maximum performance by minimizing latency and maximizing data locality, thereby achieving the highest possible execution speed. Results from both profiling and baseline implementation were used in the selection process of the parts that will be realized on accelerator cores, following the explained design methodology. The design process began with a detailed examination of the selected functions. Following the functional analysis, a dedicated hardware circuit for the selected sub-functions was developed. In the signature generation process, the majority of operations involve floating-point arithmetic, as the polynomials being processed reside in the FFT domain, where their elements are represented as floating-point complex numbers. Consequently, the accelerator cores for signature generation were designed using configurable floating-point IP cores provided by Xilinx, complemented by data flow control components such as internal memory blocks and First-In First-Out (FIFO) buffers. On the other hand, the most time consuming part of the algorithm was determined to be polynomial multiplication for the verification part, where the Number Theoretic Transform (NTT) method is used in the reference implementation. Therefore, accelerator cores that carry out NTT and Inverse-NTT operations were constructed for improving the overall performance of the part. Each core was then individually implemented and verified using test vectors generated from the reference C code, covering both the signature generation and verification components. The maximum achievable clock frequency for each circuit was measured, and necessary optimizations and modifications were applied to obtain the highest-performing versions of the cores. With all of the components ready, the SoC was formed using the designed accelerators connected to the special DMA, together with the VexRiscv processor and a block RAM for data and instructions. The software responsible for managing the algorithmic flow and controlling the accelerator cores was developed in the C programming language. Core control is handled through dedicated driver code, which provides the accelerators with appropriate configuration parameters and input data sourced from memory via the DMA. Similarly, the drivers manage the transfer of computed outputs from the cores back to designated memory locations. The system then was implemented on a Zynq-7000 FPGA, after the designed accelerator cores were prepared as IPs to be used in a block design. Implemented system was evaluated for its execution time and resource usage. Performance was prioritized over other considerations initially. Nonetheless, the design serves as both a proof of concept and a viable FPGA-based implementation. The results demonstrate that the proposed implementation achieves an approximate 375× and 70× speed-up for the signature generation and verification, respectively, over the baseline RISC-V implementation. And compared to the related work, results from the system are remarkable, making the design methodology a viable solution for implementing FALCON. The current implementation represents a first iteration of the system design. Simulation and performance analysis have revealed opportunities for further optimization for a number of accelerators, including parallelization and the design of custom floating-point units to improve area efficiency. Future work will aim to refine the design to balance speed, area, and power consumption. This study not only provided a deep understanding of FALCON, particularly the signature generation and verification, but also highlighted the critical points for the both parts. The proposed hardware accelerators demonstrates a substantial improvement in execution speed. While this work prioritizes speed, future research may focus on achieving a more balanced trade-off between performance and hardware resource utilization.