Falcon (signature scheme)

Template:Primary sources Falcon is a post-quantum signature scheme. It was designed by Thomas Prest, Pierre-Alain Fouque, Jeffrey Hoffstein, Paul Kirchner, Vadim Lyubashevsky, Thomas Pornin, Thomas Ricosset, Gregor Seiler, William Whyte, and Zhenfei Zhang. The name Falcon is an acronym for Fast Fourier lattice-based compact signatures over NTRU. It was selected by the NIST at the fourth round of the post-quantum standardisation process.

Details

All computations are done modulo a monic polynomial called $\varphi$ of the form $x^n+1$ for some $n$ that is either 512 for Falcon-512 or 1024 for Falcon-1024. Polynomials are sometimes treated as $n\times n$ square matricies whose $i$th row is $x^{i}f(\mathrm{mod}\varphi )$.Template:R

The public key consists of a lattice of dimension $2n$ that is described by the $2n\times 2n$ matrix Template:Center where $I_n$ is the identity matrix of dimension $n$, $O_n$ is a zero matrix of the same dimension, $h$ is a polynomial modulo $\varphi$ that is treated as a submatrix as described before. The coefficients of $h$ are reduced modulo $q=12289$.Template:R

The corresponding private key that generates the same lattice is:Template:R Template:Center

Due to Falcon using a NTRU lattice, the following two equations have to hold:Template:R Template:Center

In order to generate a key pair, one has to generate two polynomials $f$ and $g$ that yield short vectors and solve the second equation to derive $F$ and $G$. The public key can then be derived from calculating $h$.Template:R

In order to sign a message, the message is first hashed with a random nonce into a polynomial $c$ modulo $\varphi$, whose coefficients are between $0$ and $q-1$. The signer then uses the private key that represents the secret lattice basis to produce two short polynomials $s_1$ and $s_2$ that satisfy $s_1=c-s_{2}h(\mathrm{mod}\varphi )(\mathrm{mod}q)$. The signature is $s_2$ as $s_1$ can be recovered.Template:R

Finding $s_1$ and $s_2$ without the secret basis is generally hard. Falcon uses a divide and conquer approach similar to the Fast Fourier transform with some added noise to find the two polynomials without leaking too much information about the secret basis, hence the name.Template:R

The signature verification consists of calculating $c$ from the message, recovering $s_1$ and confirming that $(s_1,s_2)$ have a small enough Euclidean norm compared to a parameter $\beta$ such that $||(s_1,s_2)|{|}^2\le \lfloor {\beta }^2\rfloor$ holds.Template:R For Falcon-512, $\lfloor {\beta }^2\rfloor$ is $34034726$, while it is $70265242$ for Falcon-1024.Template:R

The signature verification can be done entirely using integers modulo $q$.Template:R Contrarily, the signature generation uses 64 bit floats to represent calculations using complex numbers.Template:R

Since $s_2$ consists of many coefficients close to $0$, the signature stores a compressed version alongside the nonce, leading to a variable length signature if it is not padded.Template:R

Implementations

The set of parameters suggested by Falcon imply a signature size of 666 bytes and a public key size of 897 bytes for the NIST security level 1 (security comparable to breaking AES-128 bits). The key generation can be performed in 8.64 ms with a throughput of approximately 6,000 signature per second and 28,000 verifications per second.

On the other hand, the NIST security level 5 (comparable to breaking AES-256) requires a signature size of 1,280 bytes and a public key size of 1793 bytes, a key generation under 28 ms, and a throughput of 2,900 signatures per second and 13,650 verifications per second.

See also

• Post-quantum cryptography
• Lattice-based cryptography
• NTRU
• NIST Post-Quantum Cryptography Standardization

External links

• Official website