Falcon (signature scheme)

☆ Save On Wikipedia ↗

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.[1][2][3] 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 ϕ {\displaystyle \phi } {\displaystyle \phi } of the form x n + 1 {\displaystyle x^{n}+1} {\displaystyle x^{n}+1} for some n {\displaystyle n} {\displaystyle n} that is either 512 for Falcon-512 or 1024 for Falcon-1024. Polynomials are sometimes treated as n × n {\displaystyle n\times n} {\displaystyle n\times n} square matricies whose i {\displaystyle i} {\displaystyle i}th row is x i f ( mod ϕ ) {\displaystyle x^{i}f{\pmod {\phi }}} {\displaystyle x^{i}f{\pmod {\phi }}}.[1]: 21 

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

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

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

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

[ g − f G − F ] {\displaystyle \left[{\begin{array}{c|c}g&-f\\\hline G&-F\end{array}}\right]} {\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 

h = g f ( mod ϕ ) ( mod q ) f G − g F = q ( mod ϕ ) {\displaystyle {\begin{aligned}h&={\frac {g}{f}}{\pmod {\phi }}{\pmod {q}}\\fG-gF&=q{\pmod {\phi }}\end{aligned}}} {\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 f {\displaystyle f} {\displaystyle f} and g {\displaystyle g} {\displaystyle g} that yield short vectors and solve the second equation to derive F {\displaystyle F} {\displaystyle F} and G {\displaystyle G} {\displaystyle G}. The public key can then be derived from calculating h {\displaystyle h} {\displaystyle h}.[1]: 22 

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

Finding s 1 {\displaystyle s_{1}} {\displaystyle s_{1}} and s 2 {\displaystyle s_{2}} {\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 c {\displaystyle c} {\displaystyle c} from the message, recovering s 1 {\displaystyle s_{1}} {\displaystyle s_{1}} and confirming that ( s 1 , s 2 ) {\displaystyle (s_{1},s_{2})} {\displaystyle (s_{1},s_{2})} have a small enough Euclidean norm compared to a parameter β {\displaystyle \beta } {\displaystyle \beta } such that | | ( s 1 , s 2 ) | | 2 ≤ ⌊ β 2 ⌋ {\displaystyle ||(s_{1},s_{2})||^{2}\leq \lfloor \beta ^{2}\rfloor } {\displaystyle ||(s_{1},s_{2})||^{2}\leq \lfloor \beta ^{2}\rfloor } holds.[1]: 45  For Falcon-512, ⌊ β 2 ⌋ {\displaystyle \lfloor \beta ^{2}\rfloor } {\displaystyle \lfloor \beta ^{2}\rfloor } is 34034726 {\displaystyle 34034726} {\displaystyle 34034726}, while it is 70265242 {\displaystyle 70265242} {\displaystyle 70265242} for Falcon-1024.[1]: 51 

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

Since s 2 {\displaystyle s_{2}} {\displaystyle s_{2}} consists of many coefficients close to 0 {\displaystyle 0} {\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 

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

See also

References

  1. Thomas Prest; Pierre-Alain Fouque; Jeffrey Hoffstein; Paul Kirchner; Vadim Lyubashevsky; Thomas Pornin; Thomas Ricosset; Gregor Seiler; William Whyte; Zhenfei Zhang, Falcon: Fast-Fourier Lattice-based Compact Signatures over NTRU (PDF)
  2. Falcon official website
  3. List of NIST PQC selected candidates