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.
Properties
[edit]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]
Implementations and Performances
[edit]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 a signature size of 666 bytes and a public key size of 897 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 a signature size of 1,280 bytes and a public key size of 1793 bytes, a key generation under 28 ms, and a throughput of 2,900 signatures per second and 13,650 verifications per second.[11]
See also
[edit]- Post-quantum cryptography
- Lattice-based cryptography
- NTRU
- NIST Post-Quantum Cryptography Standardization
References
[edit]- 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. |