Falcon: NTRU-based digital signature

31 Jul 2023

[latexpage]

Introduction

The Post-Quantum Cryptography NIST standardization process has identified two digital signature schemes based on lattice theory CRYSTALS-Dilithium and Falcon. In modern cryptographic protocols, these solutions are set to replace the currently used digital signature schemes that are vulnerable to quantum computer attacks. Even though Dilithium has been selected as the primary solution, Falcon may be more suitable in specific application scenarios, as noted by NIST. Indeed, an interesting Falcon feature is its ability to produce a signature fitting into a single IP packet, avoiding fragmentation-related issues. On the other hand, Falcon’s design is complex to understand and implement. Its construction is based on three main ingredients: the NTRU mathematical problem, the GPV framework for lattice hash-and-sign digital signatures and the Fast Fourier Sampling.

NTRU Problem

Let $n$ be a power of $2$ and $q$ be a prime number, a set of $\text{NTRU}$ secrets is constructed via four small polynomials [1] \[ f,g,F,G\in\mathbb{Z}[X]/(X^n+1) \] such that \[ fG-gF=q\mod{X^n+1} \] and $f$ is invertible modulo $q$. In this setting, the secret key consists of $(f,g,F,G)$ while the public one of the polynomial \[ h = g\cdot f^{-1}\mod q. \] The $\text{NTRU}$ problem is considered to be hard even for a quantum computer and consists of identifying two small polynomials $f’$, $g’$ such that $h$ coincides with $g’f’^{-1}$ modulo $q$. This problem is strictly related to lattice theory, since the best known cryptanalytic algorithm requires solving a Shortest Vector Problem (SVP) instance in the lattice generated by the $2n \times 2n$ integer matrix \[ \begin{bmatrix} 1&h\\ 0&q\\ \end{bmatrix} := \left(\begin{array}{c c c c | c c c c} 1&0&\cdots&0&h_0&h_1&\cdots&h_{n-1}\\ 0&1&\cdots&0&-h_{n-1}&h_0&\cdots&h_{n-2}\\ \vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\ddots&\vdots\\ 0&0&\cdots&1&-h_1&-h_2&\cdots&h_0\\ \hline 0 & 0 & \cdots & 0 & q & 0 & \cdots & 0 \\ 0 & 0 & \cdots & 0 & 0 & q & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 0 & 0 & 0 & \cdots & q \end{array}\right), \] where $h=h_0+h_1X+\cdots+h_{n-1}X^{n-1}$.

The GPV Framework

The GPV framework, proposed by Gentry, Peikert and Vaikuntanathan in 2008, provides a guideline to realize a secure digital signature scheme based on lattices and the hash-and-sign [2] paradigm. At a high level, the framework features a public key given by a full-rank matrix \[ \mathbf{A}\in\mathbb{Z}_{q}^{n\times k}, k>n \] and a private key given by \[ \mathbf{B}\in\mathbb{Z}_{q}^{k\times k}\text{ such that }\mathbf{BA}^{T}=\mathbf{0}. \] Given the hash function $\text{H}:\{0,1\}^{*}\rightarrow\mathbb{Z}_q^n$, the signature of a given message $m$ consists of a small vector $\mathbf{s}$ in $\mathbb{Z}_q^k$ such that \[ \mathbf{sA}^{T}=\text{H}(m). \] Even though the verification process is smooth, it is enough to check that the previous equality holds and that $\mathbf{s}$ is small, the signature process is more challenging. Finding an element in $\mathbb{Z}_q^k$ satisfying the equation is easy via linear algebra, while ensuring this element is short requires the knowledge of the secret information included in matrix $\mathbf{B}$ and working with the generated lattice.

Falcon as a GPV instance

Falcon instantiates the GPV framework using the mathematical objects of the NTRU problem, with the following parameters: \begin{align*} \mathbf{A}&=\begin{bmatrix}1&h^{\star}\end{bmatrix}\in\mathbb{Z}_q^{n\times2n},\\ \mathbf{B}&=\begin{bmatrix}g&-f\\G&-F\end{bmatrix}\in\mathbb{Z}_q^{2n\times2n}, \end{align*} where $h^{\star}=h_0+h_{n-1}X+h_{n-2}X^2+\cdots+h_1X^{n-1}$ and it can be verified that [3] \[ \mathbf{BA}^{\star}= \begin{bmatrix}g&-f\\G&-F\end{bmatrix}\begin{bmatrix}1\\h\end{bmatrix} = \mathbf{0}\mod q. \] The signature of message $m$ consists of a salt $r$ and a pair of polynomials $(s_1,s_2)$ [4] such that $s_1+s_2h=\text{H}(r||m)$, where $\text{H}$ is instantiated as SHAKE-256. The randomization through $r$ is introduced for security reasons. Indeed, publishing two distinct signatures for the same $\text{H}(m)$ would jeopardize the security proofs underlying the GPV framework. The sampling mechanism of $(s_1,s_2)$ is called Fast Fourier Sampling and is a particular case of the so-called trapdoor sampling. A proper discussion of this topic can be found in the Falcon documentation [5]. Moreover, observe that the particular shape of the prime \[ q=c\cdot 2n+1, \] for a certain constant $c$, enables the use of the Number Theoretic Transform (NTT), optimizing polynomial operations. Specifically, just as in the key encapsulation mechanism Kyber and in the digital signature scheme Dilithium, the NTT strongly simplifies polynomial multiplications.

Performance

Among the candidates of the NIST standardization process, Falcon is the one that has proposed an optimal (hence minimal) solution in terms of the size of the public key-signature pair, transmitted together with each message. Minimizing the size of these two elements is therefore crucial in order not to excessively impact the transmission costs of the scheme. As shown by the following histogram, Falcon is also notably efficient in the signing and verification algorithms. On the other hand, the key generation phase turns out to be considerably slower, at least when compared with Dilithium.

Furthermore, in terms of RAM usage, Falcon is much more demanding than Dilithium, impacting potential implementations on constrained devices such as smart cards. Finally, a further consideration that makes a secure implementation of Falcon non-trivial is the need to rely on floating-point arithmetic. Indeed, in order to use the Fast Fourier Sampling technique, it is not possible to limit oneself to integer numbers, and the execution/protection of operations on real numbers is challenging, especially at the hardware level. [1] Polynomials with small coefficients. [2] Also known as hash-then-sign. [3] See the Falcon documentation [5] for the transition from transposition $\cdot^T$ to adjunction $\cdot^\star$. [4] To optimize signature size, only $r$ and $s_2$ are transmitted, since $s_1$ is easily derived from them. [5] P.A. Fouque, J. Hoffstein, P. Kirchner, V. Lyubashevsky, T. Pornin, T. Prest, T. Ricosset, G. Seiler, W. Whyte and Z. Zhang. FALCON: Fast-Fourier Lattice-based Compact Signatures over NTRU. 2020

This article belongs to a series of contributions, edited by the Telsy Cryptography Research Group, devoted to quantum computing and its implications on Cryptography. For reference to other articles, please refer to the index.

For other articles related to Quantum and Cryptography topics, please refer to the related categories in the blog.

The author

Francesco Stocco, a master’s degree in Mathematics from the University of Padua and the Université de Bordeaux attending the Algebra Geometry And Number Theory (ALGANT) program, joined the Telsy Cryptography Research Group in late 2020.