Jump to content

Falcon (signature scheme)

From Wikipedia, the free encyclopedia
(Redirected from Falcon (Signature))

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 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

[edit]

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