Organizer: Jérôme Govinden

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 Renyi divergence-based argument for Gaussian samplers, a core element of the scheme. However, the GPV proof, which uses statistical distance to argue closeness of distributions, fails when applied naively to Falcon. 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 talk, I will give an overview of our results which demonstrate that introducing a few minor, conservative modifications allows for the first formal proof of the scheme in the random oracle model. These modifications were already applied to the latest Falcon implementation. Unfortunately, our analysis shows that despite our modification of Falcon-512 and Falcon-1024 we do not achieve strong unforgeability for either scheme. For plain unforgeability we are able to show that our modifications to Falcon-512 barely satisfy the claimed 120-bit security target and for Falcon-1024 we confirm the claimed security level.

Speaker Bio

Jonas Janneck is a third-year Ph.D. student under the supervision of Eike Kiltz at Ruhr University Bochum (RUB), Germany. His research focuses on the design and analysis of cryptographic protocols. In particular, he is interested in the concrete security of signature schemes and authenticated KEMs.