Falcon: Fast-Fourier Lattice-based Compact Signatures over NTRU

About Falcon

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.

Algorithm Highlights

Falcon offers the following features:


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 laptop computer (Intel Core i7-6567U at 3.3 GHz, up to 3.6 GHz with Turbo Boost), the reference implementation of Falcon achieves the following performance:

variant keygen (ms) keygen (RAM) sign/s verify/s pub size sig size
Falcon-512 7.26 14336 7692.9 44424.7 897 657.38
Falcon-1024 21.63 28672 3818.5 22416.5 1793 1273.31

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 twice 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 laptop on which these measures were taken, OpenSSL's thoroughly optimized assembly implementation achieves about 1500 signatures per second; thus, Falcon's reference implementation is five times faster, and it scales better to larger sizes (for long-term security).


Notice (2019-09-18): An implementation published on this site on 2019-08-02 was using an incorrect sampler, leading to weakened signatures and artificially inflated performance. The bugs have been fixed and the benchmarks and links above have been adjusted. Details about the issues have been added to the report on the new Falcon implementation.