Paper 2024/1769

A Closer Look at Falcon

Abstract

Falcon is a winner of NIST’s six-year post-quantum cryptography standardisation competition. Based on the celebrated full-domain-hash framework of Gentry, Peikert and Vaikuntanathan (GPV) (STOC’08), Falcon leverages NTRU lattices to achieve the most compact signatures among lattice-based schemes. Its security hinges on a Rényi divergence-based argument for Gaussian samplers. However, the GPV proof, which uses statistical distance to argue closeness of distributions, fails when applied naively to Falcon due to parameter choices resulting in statistical distances as large as $2^{−34}$. Additional implementation-driven deviations from the GPV framework further invalidate the original proof, leaving Falcon without a security proof despite its selection for standardisation. In this work, we provide the first formal security proof of Falcon in the random oracle model, achieved through a few conservative modifications, now incorporated into the forthcoming standard. At the heart of our analysis lies an adaptation of the GPV framework to work with the Rényi divergence, along with an optimised method for parameter selection under this measure. We also analyse the FFO Sampler that is used in Falcon. Further, we prove the equivalence of plain unforgeability to a multi-target inhomogeneous SIS problem, and strong unforgeability to a second-preimage version of this problem, providing clear targets for cryptanalysis. Assuming these problems are as hard as standard SIS, we demonstrate that Falcon-512 barely satisfies the claimed 120-bit security target, while Falcon-1024 achieves the claimed security level.

Note: Improved the strong unforgeability result using a new assumption, added an analysis of the FFO sampler with contributions from two new coauthors, and fixed notation in the preliminaries.