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]