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

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

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]

See also

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

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