Falcon (signature scheme)

Falcon is a post-quantum signature scheme selected by the NIST at the fourth round of the post-quantum standardisation process. 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.^[1][2][3] It relies on the hash-and-sign technique over the Gentry, Peikert, and Vaikuntanathan framework^[4] over NTRU lattices. The name Falcon is an acronym for Fast Fourier lattice-based compact signatures over NTRU.

The design rationale of Falcon takes advantage of multiple tools to ensure compactness and efficiency with provable security. To achieve this goal, the use of a NTRU lattice allows the size of the signatures and public-key to be relatively small, while fast Fourier sampling permits efficient signature computations.^[5]

From a security point of view, the Gentry, Peikert, and Vaikuntanathan framework enjoys a security reduction in the Quantum Random Oracle Model.^[6]

All computations are done modulo a monic polynomial called ${\displaystyle \phi }$ of the form ${\displaystyle x^{n}+1}$ for some ${\displaystyle n}$ that is either 512 for Falcon-512 or 1024 for Falcon-1024. Polynomials are sometimes treated as ${\displaystyle n\times n}$ square matricies whose ${\displaystyle i}$th row is ${\displaystyle x^{i}f{\pmod {\phi }}}$.^[1]: 21

The public key consists of a lattice of dimension ${\displaystyle 2n}$ that is described by the ${\displaystyle 2n\times 2n}$ matrix

${\displaystyle \left[{\begin{array}{c|c}-{\frac {h}{qI_{n}}}&I_{n}\\\hline qI_{n}&O_{n}\end{array}}\right]}$

where ${\displaystyle I_{n}}$ is the identity matrix of dimension ${\displaystyle n}$, ${\displaystyle O_{n}}$ is a zero matrix of the same dimension, ${\displaystyle h}$ is a polynomial modulo ${\displaystyle \phi }$ that is treated as a submatrix as described before. The coefficients of ${\displaystyle h}$ are reduced modulo ${\displaystyle q=12289}$.^[1]: 21

The corresponding private key that generates the same lattice is:^[1]: 21

${\displaystyle \left[{\begin{array}{c|c}g&-f\\\hline G&-F\end{array}}\right]}$

Due to Falcon using a NTRU lattice, the following two equations have to hold:^[1]: 21

${\displaystyle {\begin{aligned}h&={\frac {g}{f}}{\pmod {\phi }}{\pmod {q}}\\fG-gF&=q{\pmod {\phi }}\end{aligned}}}$

In order to generate a key pair, one has to generate two polynomials ${\displaystyle f}$ and ${\displaystyle g}$ that yield short vectors and solve the second equation to derive ${\displaystyle F}$ and ${\displaystyle G}$. The public key can then be derived from calculating ${\displaystyle h}$.^[1]: 22

In order to sign a message, the message is first hashed with a random nonce into a polynomial ${\displaystyle c}$ modulo ${\displaystyle \phi }$, whose coefficients are between ${\displaystyle 0}$ and ${\displaystyle q-1}$. The signer then uses the private key that represents the secret lattice basis to produce two short polynomials ${\displaystyle s_{1}}$ and ${\displaystyle s_{2}}$ that satisfy ${\displaystyle s_{1}=c-s_{2}h{\pmod {\phi }}{\pmod {q}}}$. The signature is ${\displaystyle s_{2}}$ as ${\displaystyle s_{1}}$ can be recovered.^[1]: 22

Finding ${\displaystyle s_{1}}$ and ${\displaystyle 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.^[1]: 22

The signature verification consists of calculating ${\displaystyle c}$ from the message, recovering ${\displaystyle s_{1}}$ and confirming that ${\displaystyle (s_{1},s_{2})}$ have a small enough Euclidean norm compared to a parameter ${\displaystyle \beta }$ such that ${\displaystyle ||(s_{1},s_{2})||^{2}\leq \lfloor \beta ^{2}\rfloor }$ holds.^[1]: 45 For Falcon-512, ${\displaystyle \lfloor \beta ^{2}\rfloor }$ is ${\displaystyle 34034726}$, while it is ${\displaystyle 70265242}$ for Falcon-1024.^[1]: 51

The signature verification can be done entirely using integers modulo ${\displaystyle q}$.^[1]: 22 Contrarily, the signature generation uses 64 bit floats to represent calculations using complex numbers.^[1]: 26

Since ${\displaystyle s_{2}}$ consists of many coefficients close to ${\displaystyle 0}$, the signature stores a compressed version alongside the nonce, leading to a variable length signature if it is not padded.^[1]: 46,50

The authors of Falcon provide a reference implementation in C^[7] as required by the NIST^[8] and one in Python for simplicity.

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.^[1]

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.^[1]

Falcon signature was used since 2022 by Algorand^[9] and Crypnut^[10] blockchains.

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

• Official website