Falcon: A Post-Quantum Signature Scheme

Abstract

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.

Outline

  1. NIST call for proposals and requirements
  2. Falcon overview
  3. Lattice-based cryptography
  4. Short integer solution problem
  5. Falcon specifics
    • Signature generation
    • Signature verification
    • Performance measures
  6. Conclusions

Definitions

Final Submission

Slides
Paper

References


Home