# Low-Latency FFT/iFFT RTL Implementation for the FALCON Post-Quantum Signature Algorithm

Alexandre Ortega, Lilian Bossuet, Brice Colombier

► To cite this version:

Alexandre Ortega, Lilian Bossuet, Brice Colombier. Low-Latency FFT/iFFT RTL Implementation for the FALCON Post-Quantum Signature Algorithm. Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM), May 2025, Fayetteville, Arkansas, United States. hal-05072821

HAL Id: hal-05072821

https://hal.science/hal-05072821v1

Submitted on 19 May 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Low-Latency FFT/iFFT RTL Implementation for the FALCON Post-Quantum Signature Algorithm

Alexandre Ortega, Lilian Bossuet and Brice Colombier

Université Jean Monnet Saint-Etienne, CNRS, Institut d'Optique Graduate School, Laboratoire Hubert Curien UMR 5516, F-42023, SAINT-ETIENNE, France

`{alexandre.ortega; lilian.bossuet; b.colombier}@univ-st-etienne.fr`

## I. INTRODUCTION

FALCON [1] is one of the three post-quantum digital signature schemes that have been recently standardized by NIST due to the future threat that quantum computers pose to classical cryptographic schemes. Despite this, there is currently no full hardware register-transfer level (RTL) implementation of FALCON. One possible explanation is the rather unusual requirement for a double-precision floating-point Fast Fourier Transform (FFT) [2], which is used in FALCON to speed up polynomial multiplication. In this work, we propose a full RTL constant-time implementation of the FFT and its inverse (iFFT), on FPGA, tailored for the specific context of FALCON. Section II presents the FFT in the context of FALCON before Section III describes the proposed architecture. Section IV concludes.

## II. THE FAST FOURIER TRANSFORM IN FALCON

In FALCON, the FFT over the ring $Q[x]/(\phi)$ is used with $\phi = x^N + 1$ and $N = 2^k$ a power of two. $N$ is a security parameter of FALCON that can be equal to either 512 or 1024. Due to FALCON security requirements, IEEE-754 compliant double-precision floating-point arithmetic is being used [1]. Using the fact that FALCON polynomials are in $Z[x]/(\phi)$, as well as the roots of unity symmetry in $Z[x]/(\phi)$, the storage requirements can be halved and more than half of the computations can be omitted [1].

## III. DESCRIPTION OF THE PROPOSED HARDWARE ARCHITECTURE

The proposed hardware architecture is divided in three main blocks.

1) The butterfly unit: Made with three complex double-precision floating-point operators, an adder as well as a subtractor and a multiplier, it can be reconfigured dynamically to perform either the radix-2 decimation-in-time FFT or the radix-2 decimation-in-frequency iFFT.

2) The Polynomial coefficients storage unit: Two true dual port RAMs are used to store the polynomial coefficients.

3) The Polynomial Coefficient Addresses and Root of Unity Values Storage Unit: Four single-port ROMs and one dual-port ROM are used to store the pre-computed coefficient addresses in RAM and root of unity values.

The proposed hardware implementation is described using VHDL and synthetised using AMD-Xilinx Vivado 2023.2.

<table><caption>TABLE I
(1)FFT-512/(1)FFT-1024 IMPLEMENTATION RESULTS</caption><thead><tr><th rowspan="2"></th><th colspan="2">This work</th><th colspan="2">[3]</th><th colspan="2">Vivado 2023.2</th></tr><tr><th colspan="2">Double</th><th colspan="2">Double</th><th colspan="2">Single</th></tr></thead><tbody><tr><th>Floating-point precision</th><td colspan="2">Double</td><td colspan="2">Double</td><td colspan="2">Single</td></tr><tr><th>FFT length</th><td>512</td><td>1024</td><td>512</td><td>512</td><td>512</td><td>1024</td></tr><tr><th>LUT</th><td>9658</td><td>9677</td><td>8396</td><td>1741</td><td>1793</td><td>1793</td></tr><tr><th>FF</th><td>369</td><td>374</td><td>2526</td><td>3468</td><td>3508</td><td>3508</td></tr><tr><th>DSP</th><td>36</td><td>36</td><td>9</td><td>10</td><td>10</td><td>10</td></tr><tr><th>BRAM</th><td>8</td><td>11</td><td>9.5</td><td>4</td><td>5</td><td>5</td></tr><tr><th>Latency (cycles)</th><td>3074</td><td>6658</td><td>19800</td><td>4589</td><td>9474</td><td>9474</td></tr></tbody></table>

Table I reports the implementation results of the proposed design and compares it with Vivado 2023.2 FFT/iFFT IP, and a co-design implementation of FALCON FFT/iFFT for the security parameter $N = 512$ [3]. The FPGA targetted, in all the reported results in Table I, is the AMD-Xilinx ZCU104+(xczu7ev-ffvc1156-2-e) FPGA. The fairest comparison is with Mandal et al. design as both design use double-precision. The proposed design and this design have similar metrics for the LUTs and the BRAMs. The proposed design uses $4 \times$ more DSP blocks but around $6.5 \times$ less FFs and clock cycles. As expected when comparing the proposed design to Vivado's IP, which uses single-precision, it uses around $2 \times$ more BRAMs, more LUTs and DSPs. However, the proposed design uses around $10 \times$ less FFs and achieves a lower latency.

## IV. CONCLUSION

A low-latency full hardware constant-time RTL implementation of the FFT/iFFT, tailored for FALCON parameters, was presented. It achieves the best latency of the literature among FPGA-based implementations.

**Acknowledgment:** This work received funding from the France 2030 program, managed by the French National Research Agency under grant agreement No. ANR-22-PETQ-0008 PQ-TLS

## REFERENCES

[1] P.-A. Fouque, J. Hoffstein, P. Kirchner, V. Lyubashevsky, T. Pornin, T. Prest, T. Ricosset, G. Seiler, W. Whyte, Z. Zhang, et al., "Falcon: Fast-Fourier lattice-based compact signatures over NTRU," *Submission to the NIST's post-quantum cryptography standardization process*, vol. 36, no. 5, pp. 1-75, 2018.

[2] L. Beckwith, D. T. Nguyen, and K. Gaj, "High-Performance Hardware Implementation of Lattice-Based Digital Signatures." Cryptology ePrint Archive, Paper 2022/217, 2022.

[3] S. Mandal and D. Roy, "Design of a Lightweight Fast Fourier Transformation for FALCON using Hardware-Software Co-Design," in *GLSVLSI'24 Proceedings*, pp. 228-232, 06 2024.