Falcon is a cryptographic signature algorithm submitted to NIST Post-Quantum Cryptography Project on November 30th, 2017. It has been designed by: Pierre-Alain Fouque, Jeffrey Hoffstein, Paul Kirchner, Vadim Lyubashevsky, Thomas Pornin, Thomas Prest, Thomas Ricosset, Gregor Seiler, William Whyte, Zhenfei Zhang.

The point of a post-quantum cryptographic algorithm is to keep on ensuring its security characteristics even faced with quantum computers. Quantum computers are deemed feasible, according to our current understanding of the laws of physics, but some significant technological issues remain to be solved in order to build a fully operational unit. Such a quantum computer would very efficiently break the usual asymmetric encryption and digitial signature algorithms based on number theory (RSA, DSA, Diffie-Hellman, ElGamal, and their elliptic curve variants).

Falcon is based on the theoretical framework of Gentry, Peikert and Vaikuntanathan for lattice-based signature schemes. We instantiate that framework over NTRU lattices, with a trapdoor sampler called "fast Fourier sampling". The underlying hard problem is the short integer solution problem (SIS) over NTRU lattices, for which no efficient solving algorithm is currently known in the general case, even with the help of quantum computers.

Falcon offers the following features:

**Security:**a true Gaussian sampler is used internally, which guarantees negligible leakage of information on the secret key up to a practically infinite number of signatures (more than 2^{64}).**Compactness:**thanks to the use of NTRU lattices, signatures are substantially shorter than in any lattice-based signature scheme with the same security guarantees, while the public keys are around the same size.**Speed:**use of fast Fourier sampling allows for very fast implementations, in the thousands of signatures per second on a common computer; verification is five to ten times faster.**Scalability:**operations have cost*O(n*log*n)*for degree*n*, allowing the use of very long-term security parameters at moderate cost.**RAM Economy:**the enhanced key generation algorithm of Falcon uses less than 30 kilobytes of RAM, a hundredfold improvement over previous designs such as NTRUSign. Falcon is compatible with small, memory-constrained embedded devices.

While resistance to quantum computers is the main drive for the design and development of Falcon, the algorithm may achieve significant adoption only if it is also reasonably efficient in our current world, where quantum computers do not really exist. Using the reference implementation on a common desktop computer (Intel® Core® i5-8259U at 2.3 GHz, TurboBoost disabled), Falcon achieves the following performance:

variant | keygen (ms) | keygen (RAM) | sign/s | verify/s | pub size | sig size |
---|---|---|---|---|---|---|

Falcon-512 | 8.64 | 14336 | 5948.1 | 27933.0 | 897 | 666 |

Falcon-1024 | 27.45 | 28672 | 2913.0 | 13650.0 | 1793 | 1280 |

Sizes (key generation RAM usage, public key size, signature size) are expressed in bytes. Key generation time is given in milliseconds. Private key size (not listed above) is about three times that of a signature, and it could be theoretically compressed down to a small PRNG seed (say, 32 bytes), if the signer accepts to run the key generation algorithm every time the key must be loaded.

To give a point of comparison, Falcon-512 is roughly equivalent, in classical security terms, to RSA-2048, whose signatures and public keys use 256 bytes each. On the specific system on which these measures were taken, OpenSSL's thoroughly optimized assembly implementation achieves about 1140 signatures per second; thus, Falcon's reference implementation, which is portable and uses no inline assembly on x86 CPUs, is already more than five times faster, and it scales better to larger sizes (for long-term security).

**Warning (2021-11-01):** an issue in the external API
was detected by David Lazar and Chris Peikert (of Algorand, Inc.): the
functions `shake256_init_prng_from_seed()`

and
`shake256_init_prng_from_system()`

were not behaving
properly. The NIST API, test vectors and benchmarks used as part of the
NIST PQC standardization project are *not* affected; neither are
the implementations of Falcon in the
PQClean and
pqm4 libraries. The reference
source code linked below (both the Zip archive and the browsable
version) have been fixed.

- Falcon submission package [zip] (specification, source code, scripts and test vectors)
- Falcon specification [pdf]
- Falcon reference implementation:
- An implementation in Python [html]
- For reference, submission packages for previous rounds: Round 1 [zip] and Round 2 [zip]
- Presentations at the NIST PQC Standardization Conferences: Round 1 [pdf] and Round 2 [pdf]

- Thomas Pornin and Thomas Prest

*More Efficient Algorithms for the NTRU Key Generation using the Field Norm*[pdf] - Xingye Lu, Man Ho Au and Zhenfei Zhang

*Raptor: A Practical Lattice-Based (Linkable) Ring Signature*[pdf] - Thomas Pornin

*New Efficient, Constant-Time Implementations of Falcon*[pdf] - Pierre-Alain Fouque, Paul Kirchner, Mehdi Tibouchi, Alexandre Wallet and Yang Yu

*Key Recovery from Gram-Schmidt Norm Leakage in Hash-and-Sign Signatures over NTRU Lattices*[pdf] - James Howe, Thomas Prest, Thomas Ricosset and Mélissa Rossi

*Isochronous Gaussian Sampling: From Inception to Implementation*[pdf]