In a significant development for post-quantum cryptography, a new research report authored by Vincent Hwang has established rigorous mathematical bounds for the fast Fourier sampler of Falcon—the lattice-based digital signature scheme selected by the National Institute of Standards and Technology (NIST) for standardization as FN-DSA in the forthcoming FIPS 206 standard. The paper, titled "Bounds of Falcon’s Fast Fourier Sampler with Fixed-Point Arithmetic" and cataloged on the Cryptology ePrint Archive as Paper 2026/2902, addresses critical security considerations in implementing Falcon’s signature generation, which traditionally relies on complex numbers.
Falcon’s signature generation is fundamentally driven by the fast Fourier sampler. Hwang’s report focuses on bounding the Rényi divergence between this sampler when executed in real arithmetic and its practical fixed-point implementation. This analysis is conducted specifically on the tail-cut event, a scenario where every sample remains strictly within a fixed number of standard deviations of its center.
To evaluate the security implications, the research targets reference bit security levels of $lambda = 128$ at dimension $n = 512$ and $lambda = 256$ at dimension $n = 1024$ over a total of $2^64$ signatures. The newly derived bounds demonstrate robust security retention. Specifically, the analysis reveals that the bounds maintain 126.28 and 248.78 bits at the plain center, and 126.70 and 253.53 bits at the fractional center, applicable for every key that the key generation algorithm accepts. Meanwhile, the corresponding analysis for a floating-point signer remains an open question in the field, having previously encountered a numerical contradiction while attempting to close its underlying hypotheses.
To achieve these rigorous guarantees, the report proposes four distinct changes to the fixed-point implementation of the algorithm. First, the one-dimensional sampler, known as SamplerZ, is modified to reject a candidate at a saturated shift instead of merely saturating the shift itself. Second, the key generation process introduces three new checks on the tree structure: it bounds the largest relative deviation of a leaf standard deviation, evaluates the multiplicative perturbation of the tree map, and calculates the largest remainder on the tail-cut event.
According to the author’s findings, these first two modifications are essential for carrying the mathematical proof through. Dropping the first modification would incur an untracked cost from the saturated leaves’ term, while dropping the second modification would leave the system with no provable security level at any number of signatures under the proposed proof framework. The third and fourth modifications further streamline the mathematics: the root node is computed using the NTRU identity, and an inversion followed by a multiplication is streamlined into a single division operation. These adjustments successfully simplify the overall proofs.
The security bits established in this work rest upon a combination of machine-checked proofs and three code-alignment hypotheses. The sampler’s computational kernels and its recursive structures are formally proved using CryptoLine on the aarch64 object code compiled at optimization level -O3 and traced under QEMU running on a Cortex-A72 processor. These proofs are then composed within the Lean theorem prover. The broader mathematical analysis is likewise carried out in Lean as far as its automated model can reach, with every individual proof line that falls outside this reach explicitly recorded as such, while the Lean theorems take the summability of their underlying series as an explicit hypothesis. Notably, the bound itself samples nothing, relying purely on analytical guarantees.
The creation of this research report also reflects modern cryptographic engineering methodologies. It was written with artificial intelligence agents operating under the detailed, hands-on guidance of the human author, representing a unique blend of formal verification of compiled machine code, the Rényi divergence argument common to lattice-based sampling, and the engineering of specialized agent harnesses. Within this context, the tree map’s perturbation is analyzed specifically as a multiplicative perturbation in the sense of relative perturbation theory.
The report also addresses vital hardware-level implementation realities, noting that the compiled object files exhibit known timing side channels. Specifically, during key generation arithmetic, the compiler inadvertently transformed constant-time C code into key-dependent branches within the Cortex-A72 build. Consequently, that arithmetic is verified instead on the object compiled for the Apple M1 processor, which handles the operations cleanly. Developing a fully branchless assembly reference remains a designated avenue for future work by the author and the agent harness.

