Paper 2024/1769

A Closer Look at Falcon

Phillip Gajland, Max Planck Institute for Security and Privacy, Ruhr University Bochum, IBM Research - Zurich
Jonas Janneck, Ruhr University Bochum
Eike Kiltz, Ruhr University Bochum
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, 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 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. This work takes a closer look at Falcon and demonstrates that introducing a few minor, conservative modifications allows for the first formal proof of the scheme in the random oracle model. 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. Furthermore, we obtain a provable version of the GPV framework over NTRU rings. Both these tools may be of independent interest. 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. As such we recommend revisiting falcon and its parameters.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
SignaturesFalconGPVRenyi
Contact author(s)
phillip gajland @ rub de
jonas janneck @ rub de
eike kiltz @ rub de
History
2024-10-30: approved
2024-10-30: received
See all versions
Short URL
https://ia.cr/2024/1769
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/1769,
      author = {Phillip Gajland and Jonas Janneck and Eike Kiltz},
      title = {A Closer Look at Falcon},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1769},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1769}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.