Falcon is a post-quantum signature scheme selected by the NIST at the fourth round of the post-quantum standardisation process. It has been designed by Thomas Prest, Pierre-Alain Fouque, Jeffrey Hoffstein, Paul Kirchner, Vadim Lyubashevsky, Thomas Pornin, Thomas Ricosset, Gregor Seiler, William Whyte and Zhenfei Zhang. It relies on the hash-and-sign technique over the Gentry, Peikert and Vaikuntanathan framework over NTRU lattices. The name Falcon is an acronym for Fast Fourier lattice-based compact signatures over NTRU.
Properties
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.
From a security point of view, the Gentry, Peikert and Vaikuntanathan framework enjoys a security reduction in the Quantum Random Oracle Model.
Implementations and Performances
The authors of Falcon provide a reference implementation in C as required by the NIST and one in Python for simplicity.
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 approximatively 6,000 signature per second and 28,000 verifications per second.
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.
See also
References
- 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