Falcon (signature scheme)

Falcon is a post-quantum signature scheme selected by the NIST at the fourth round of the post-quantum standardisation process. It was designed by Thomas Prest, Pierre-Alain Fouque, Jeffrey Hoffstein, Paul Kirchner, Vadim Lyubashevsky, Thomas Pornin, Thomas Ricosset, Gregor Seiler, William Whyte, and Zhenfei Zhang.^[1][2][3] It relies on the hash-and-sign technique over the Gentry, Peikert, and Vaikuntanathan framework^[4] over NTRU lattices. The name Falcon is an acronym for Fast Fourier lattice-based compact signatures over NTRU.

The design rationale of Falcon takes advantage of multiple tools to ensure compactness and efficiency with provable security. To achieve this goal, the use of a NTRU lattice allows the size of the signatures and public-key to be relatively small, while fast Fourier sampling permits efficient signature computations.^[5]

From a security point of view, the Gentry, Peikert, and Vaikuntanathan framework enjoys a security reduction in the Quantum Random Oracle Model.^[6]

The authors of Falcon provide a reference implementation in C^[7] as required by the NIST^[8] and one in Python for simplicity.^[9]

The set of parameters suggested by Falcon imply signatures of size 666 bytes for the NIST security level 1 (security comparable to breaking AES-128 bits). The key generation can be performed in 8.64 ms with a throughput of approximately 6,000 signature per second and 28,000 verifications per second.^[10]

On the other hand, the NIST security level 5 (comparable to breaking AES-256) requires signature of 1,280 bytes, a key generation under 28 ms, and a throughput of 2,900 signatures per second and 13,650 verifications per second.^[11]

• Post-quantum cryptography
• Lattice-based cryptography
• NTRU
• NIST Post-Quantum Cryptography Standardization

1.^ Thomas Prest; Pierre-Alain Fouque; Jeffrey Hoffstein; Paul Kirchner; Vadim Lyubashevsky; Thomas Pornin; Thomas Ricosset; Gregor Seiler; William Whyte; Zhenfei Zhang, Falcon: Fast-Fourier Lattice-based Compact Signatures over NTRU (PDF)

2.^ Falcon official website

3.^ List of NIST PQC selected candidates

4.^ Craig Gentry; Chris Peikert; Vinod Vaikuntanathan (2008). Trapdoors for Hard Lattices and New Cryptographic Constructions. STOC.

5.^ Dan Boneh; Özgür Dagdelen; Marc Fischlin; Anja Lehmann; Christian Schaffner; Mark Zhandry (2011). Random Oracles in a Quantum World. Asiacrypt.

6.^ Reference implementation of Falcon in C

7.^ Implementation of Falcon in Python

8.^ NIST Post-Quantum Cryptography Call for Proposals

This cryptography-related article is a stub. You can help Wikipedia by expanding it.

• v
• t
• e