Falcon (signature scheme)

Falcon is a digital signature scheme designed to stay secure even against attackers who have a large quantum computer. Its name stands for Fast Fourier lattice-based compact signatures over NTRU, and it was designed by a team that includes Thomas Prest, Pierre-Alain Fouque, Jeffrey Hoffstein, Paul Kirchner, Vadim Lyubashevsky, Thomas Pornin, Thomas Ricosset, Gregor Seiler, William Whyte and Zhenfei Zhang. NIST selected it in the fourth round of its post-quantum standardisation process. The scheme works on an NTRU lattice, with all arithmetic done modulo a polynomial of degree 512 or 1024. To sign, the message is hashed together with a random nonce into a polynomial, and the signer uses a secret short basis of the lattice to produce a short signature polynomial. Verification only needs integer arithmetic modulo a small prime, while signing uses 64 bit floating point numbers. The smallest parameter set gives a signature of 666 bytes and a public key of 897 bytes.