Falcon: A Post-Quantum Signature Scheme
In December 2016, The National Institute of Standards and Technology (NIST)
officially called for proposals of algorithms that would be resistent to quantum
computers. It is estimated that a sufficiently large quantum computer would
cut the effective key length of public-key schemes in half.
This paper will serve as a case study on one such submission,
Falcon, designed by
Pierrre-Alain Fouque, Jeffrey Hoffstein, Paul Kirchner, Vadim Lyubashevsky,
Thomas Pornin, Thomas Ricosset, Gregor Seiler, William Whyte, and Zhengfei Zhang.
Falcon is a signature scheme that takes advantage of lattice-based cryptography
and the short integer solution (SIS) problem.
- NIST call for proposals and requirements
- Falcon overview
- Lattice-based cryptography
- Short integer solution problem
- Falcon specifics
- Signature generation
- Signature verification
- Performance measures
- Lattice: the set of all integer linear combinations, described by an n-dimensional set of linearly independent vectors
- NTRU: a public key cryptosystem that uses lattice-based cryptography. Falcon uses lattices from this system
- Short Integer Solution Problem: SIS is a lattice problem that is hard on the average case. It involves
finding a linearly independent set of short vectors that form a basis of the lattice.