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

Abstract

Falcon is a lattice-based signature scheme. It stands for the following acronym: Fast Fourier lattice-based compact signatures over NTRU The high-level design of Falcon is simple: we instantiate the theoretical framework described by Gentry, Peikert and Vaikuntanathan [GPV08] for constructing hash-and-sign lattice-based signature schemes. This framework requires two ingredients: • A class of cryptographic lattices. We chose the class of NTRU lattices. • A trapdoor sampler. We rely on a new technique which we call fast Fourier sampling. In a nutshell, the Falcon signature scheme may therefore be described as follows: Falcon = GPV framework + NTRU lattices + Fast Fourier sampling This document is the supporting documentation of Falcon. It is organized as follows. Chapter 2 explains the overall design of Falcon and its rationale. Chapter 3 is a complete specification of Falcon. Chapter 4 discusses implementation issues and possible optimizations, and described measured performance.