Falcon is a
post-quantum
Post-quantum cryptography (PQC), sometimes referred to as quantum-proof, quantum-safe, or quantum-resistant, is the development of cryptographic algorithms (usually public-key algorithms) that are currently thought to be secure against a cryptan ...
signature scheme selected by the
NIST
The National Institute of Standards and Technology (NIST) is an agency of the United States Department of Commerce whose mission is to promote American innovation and industrial competitiveness. NIST's activities are organized into physical s ...
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.
It relies on the hash-and-sign technique over the
Gentry
Gentry (from Old French , from ) are "well-born, genteel and well-bred people" of high social class, especially in the past. ''Gentry'', in its widest connotation, refers to people of good social position connected to Landed property, landed es ...
, Peikert, and
Vaikuntanathan framework over
NTRU
NTRU is an open-source public-key cryptosystem that uses lattice-based cryptography to encrypt and decrypt data. It consists of two algorithms: NTRUEncrypt, which is used for encryption, and NTRUSign, which is used for digital signatures. Unlike ...
lattices. The name ''Falcon'' is an
acronym
An acronym is a type of abbreviation consisting of a phrase whose only pronounced elements are the initial letters or initial sounds of words inside that phrase. Acronyms are often spelled with the initial Letter (alphabet), letter of each wor ...
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
In cryptography, a random oracle is an oracle (a theoretical black box) that responds to every ''unique query'' with a (truly) random response chosen uniformly from its output domain. If a query is repeated, it responds the same way every tim ...
.
Implementations
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 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.
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.
Use
Falcon signature was used since 2022 by Algorand and Crypnut
blockchains.
See also
*
Post-quantum cryptography
Post-quantum cryptography (PQC), sometimes referred to as quantum-proof, quantum-safe, or quantum-resistant, is the development of cryptographic algorithms (usually public-key algorithms) that are currently thought to be secure against a crypt ...
*
Lattice-based cryptography
Lattice-based cryptography is the generic term for constructions of cryptographic primitives that involve lattices, either in the construction itself or in the security proof. Lattice-based constructions support important standards of post-quant ...
*
NTRU
NTRU is an open-source public-key cryptosystem that uses lattice-based cryptography to encrypt and decrypt data. It consists of two algorithms: NTRUEncrypt, which is used for encryption, and NTRUSign, which is used for digital signatures. Unlike ...
*
NIST Post-Quantum Cryptography Standardization
Post-Quantum Cryptography Standardization is a program and competition by NIST to update their standards to include post-quantum cryptography. It was announced at PQCrypto 2016. 23 signature schemes and 59 encryption/ KEM schemes were submitted by ...
References
{{crypto-stub
Asymmetric-key algorithms
Digital signature schemes
Lattice-based cryptography