Paper 2026/2902
Bounds of Falcon's Fast Fourier Sampler with Fixed-Point Arithmetic
Abstract
Falcon was selected by NIST for standardization as FN-DSA in the forthcoming FIPS 206, and its signature generation is driven by the fast Fourier sampler, defined over the complex numbers. This report bounds the Rényi divergence between the sampler in real arithmetic and its fixed-point implementation, on the tail-cut event, where every sample stays within a fixed number of standard deviations of its center. For a reference bit security λ = 128 at n = 512 and λ = 256 at n = 1024 over 2^64 signatures, the bound keeps 126.28 and 248.78 bits at the plain center, and 126.70 and 253.53 bits at the fractional center, for every key the key generation accepts. The floating-point signer's analysis is left open: it stopped at a numerical contradiction while closing its hypotheses. We propose four changes to the fixed-point implementation. (i) The one-dimensional sampler SamplerZ rejects a candidate at a saturated shift instead of saturating the shift. (ii) The key generation runs three new checks on the tree: it bounds the largest relative deviation of a leaf standard deviation, the multiplicative perturbation of the tree map, and the largest remainder on the tail-cut event. The first two changes carry the proof: dropping (i) costs the saturated leaves' term, and dropping (ii) leaves no security level at any number of signatures for our proof. (iii) The root node is computed with the NTRU identity, and (iv) an inversion followed by a multiplication becomes a division; these two simplify the proofs. The bits rest on machine-checked proofs and on three code-alignment hypotheses. The sampler's kernels and its recursion are proved in CryptoLine on the aarch64 objects of the C code, compiled at -O3 and traced under QEMU's Cortex-A72, and composed in Lean. The analysis is carried in Lean where its model reaches, every proof line it does not reach recorded as such, and the Lean theorems take the summability of their series as a hypothesis. The bound samples nothing. This report was written with agents under the human author's detailed guidance, a blend of formal verification of machine code, the Rényi divergence argument of lattice sampling, and the engineering of an agent harness; the tree map's perturbation is a multiplicative one, in the sense of relative perturbation theory. The compiled objects have known timing side channels: in the key generation's arithmetic the compiler turned constant-time C into key-dependent branches in the Cortex-A72 build, so that arithmetic is verified on the object compiled for the Apple M1, which selects, and a branchless assembly reference is future work with the agents.
Metadata
- Available format(s)
-
PDF
- Category
- Implementation
- Publication info
- Preprint.
- Keywords
- Falconfast Fourier samplingRényi divergenceformal verificationlattice-based signaturesAI agents
- Contact author(s)
- vincentvbh7 @ gmail com
- History
- 2026-11-19: approved
- 2026-11-15: received
- See all versions
- Short URL
- https://ia.cr/2026/2902
- License
-
CC0
BibTeX
@misc{cryptoeprint:2026/2902,
author = {Vincent Hwang},
title = {Bounds of Falcon's Fast Fourier Sampler with Fixed-Point Arithmetic},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/2902},
year = {2026},
url = {https://eprint.iacr.org/2026/2902}
}