Falcon – A Post-Quantum Signature Scheme

This blog note is an introduction to Falcon, our post-quantum signature scheme. Falcon is a joint work between researchers from PQShield, Algorand, Brown University, IBM, NCC Group, Qualcomm, Thales and Université Rennes I. It is one of the few remaining candidates to NIST’s standardization process, and as such it targets both high efficiency and long-term security. In this note, I will present the key ideas underlying Falcon and explain how they all fit together.

DIGITAL SIGNATURES

Just like their physical counterparts, digital signatures are meant to prove that a document is issued or approved by someone. Along with encryption schemes, they play a vital role in the security of electronic communications. Since everything can be replicated in the digital world, digital signatures cannot leverage the same principles as physical ones; instead, they rely on the hardness of mathematical problems.

The signer keeps to himself a private key, which he uses each time he computes a signature. To this private key is associated a public key, which he can publicly send to anyone. Each time the signer needs to sign a message, he uses his private key to solve some mathematical hard problem which depends only on the message and the public key; the solution will be the signature. On the other hand, the verifier generates the same problem (since it only depends on public elements), and uses his public key to verify that the signature is indeed a solution of the problem. However, the public key does not help the verifier to solve the problem himself. If all this may seem a bit abstract, the next section shows how to pull this off concretely with a simple but pre-quantum example.

RABIN’S SCHEME: AN EXAMPLE BASED ON FACTORISATION

It is known that the problem of factorisation is hard: given two very large integers p and q (of, say, 1000 digits each), a computer can compute their product N = p × q instantly, but recovering (p, q) given N is out of reach for current computers. There are problems which are hard to solve knowing only N, but easy to solve given its factorisation (p, q). Consider for example the problem of computing a square root: given an integer y, we want to find a an integer x such that x²= y mod N. If we know only N, this is a hard problem on a classical computer (at the very least, there is no known efficient method to solve it), but checking whether x is a valid solution is easy: just verify that x² = y mod N. However, if we know the decomposition N = p × q , then this problem is easily solved using this algorithm:

1. Compute square roots of y modulo p and q. There are many ways to do that, for example, the Tonelli-Shanks algorithm.
2. Use the Chinese remainder theorem to combine these square roots modulo p and q in a square root modulo N.

This example highlights how there are problems (here, computing a square root) which are:

1. Easy to verify, hard to solve with a public key N.
2. Easy to solve with a private key (p, q).

Public-key cryptography takes advantage of the asymmetry between what a public key and a private key can achieve. For example, Rabin’s signature scheme is based on the exact problem exposed above. This scheme works as follows:

1. The signer signs a message $\text{msg}$ by first sending it to a random-looking target y (using a hash function, a type of function which sends inputs to random-looking outputs). Then he uses his private key (p, q) to compute a square root of y mod N: this solution x will serve as the signature of $\text{msg}$.
2. The verifier uses the public key N to convince himself that check that x is a valid signature of $\text{msg}$, by checking that x² = H($\text{msg}$) mod N.

Interestingly, one can show that computing square roots and factorisation are equivalent problems: if computing square roots modulo N is hard, then so is factoring N, and reciprocally. Rabin’s scheme follows the hash-then-sign paradigm: the message is first hashed to a target challenge, and the solution to this challenge is the signature. Falcon follows the same paradigm, but uses lattice problems instead of integer factorisation.

A PRIMER ON LATTICES

Rabin’s scheme is not post-quantum. Indeed, its underlying problem, factorisation, could be solved quickly by a large scale quantum computer. However, its high-level ideas can be adapted to work over lattices problems which are conjectured to resist quantum attackers. This section introduces lattices, and the next one explains how we use them to build our signature scheme, Falcon.

A lattice is essentially an infinite number of points arranged in a grid fashion. For example, the picture below displays a two-dimensional lattice. In general, a lattice may exist in any positive number of dimensions.

A lattice has an infinite number of points, which of course raises practicality issues: do we have to store an infinite number of points? Of course, the answer is no, we can be more efficient than that. A first step towards practicality is to work only with q-ary lattices; these are lattices whose points coordinates are integer and “wrap around” some integer q, that is, if we reduce modulo q the coordinates of a lattice point, the result will still be a point of the lattice. To illustrate this with our previous example, we draw a grid and restrict the lattice to the points having coordinates between 0 and q = 19. One can see that it is indeed a q-ary lattice.

A second step is to have a compact representation of the lattice. Let us consider the lattice points ${\mathrm{b1}}^{}=(5,1)$ and b₂=(1,4). Every lattice point can be expressed as a linear combination (with integer coefficients) of ${\mathrm{b1}}^{}$ and ${\mathrm{b2}}^{}$, and this representation is unique; for example, the top rightmost point can be expressed as $(19,19)=(3\cdot 5,3\cdot 1)+(4\cdot 1,4\cdot 4)=3\cdot {\mathrm{b1}}^{}+4\cdot {\mathrm{b2}}^{}$. We say that the set $B=\{{\mathrm{b1}}^{},{\mathrm{b2}}^{}\}$ is a basis of the lattice, and this lattice is said to be of dimension two because its basis has two elements. A basis is an unambiguous and compact way of representing a lattice. Any lattice (of dimension at least 2) has an infinity of bases. For example, the set $C=\left\{\right(7,9),(8,13\left)\right\}$ is also a basis of this lattice.

All bases are not equal when it comes to their capabilities. Let us consider the following problem: “given a random target point on the grid, find a lattice point close to the target”. In the example below, the target is $(9,8)$. A simple way to find such a lattice point with a basis (say, $B$) is through this algorithm, known as Babai’s rounding algorithm:

1. Express the target as a linear combination of the basis. With our example and the basis $B$, we have $(9,8)=\frac{\mathrm{28/}}{19}\cdot {\mathrm{b1}}^{}+\frac{\mathrm{31/}}{19}\cdot {\mathrm{b2}}^{}$.
2. Round each coefficient of the linear combination, multiply the value obtained by the corresponding vector and sum all the results. For our example, this would give $\lfloor \frac{\mathrm{28/}}{19}\rceil \cdot {\mathrm{b1}}^{}+\lfloor \frac{\mathrm{31/}}{19}\rceil \cdot {\mathrm{b2}}^{}=1\cdot {\mathrm{b1}}^{}+2\cdot {\mathrm{b2}}^{}=(7,9)$, which is the green point in the left illustration below.

It is proven that Babai’s rounding algorithm will always find a lattice point somewhat close to the target, in the sense that it will be contained into a parallelepiped centred on the target, whose form is dictated by the basis used (on the figure, it is the green parallelogram). Used with the basis $B$, this algorithm performs reasonably well. On our example, the output $(9,8)$is actually the lattice point closest to our target! However, if one uses $C$ as a basis instead, then the result can be much further from the target. This dramatic difference is visible on the right illustration above: the algorithm then outputs $(13,14)$, which is rather far from the target. However, note that the long basis $C$ still allows verifying that $(7,9)$ is a valid solution to our problem, by checking that: 1) it is close to the target, 2) it is a linear combination of the vectors of $C$.

This illustrates an asymmetry between what we do with a short basis and a long basis: for the problem of finding a lattice point close to a target, the short basis allows solving the problem, whereas the long basis only allows verifying that a solution is valid.

HOW TO MAKE A FALCON

Now that we have a basic understanding of the mathematics of lattices, we will see how to leverage them to build a signature scheme.

THE HIGH-LEVEL RECIPE: THE GPV FRAMEWORK

Falcon follows a framework introduced in 2008 by Gentry, Peikert, and Vaikuntanathan, which we call the GPV framework for short. The details of their work can be quite technical, but the high-level idea is the following:

1. The public key is a long basis of a q-ary lattice.
2. The private key is (essentially) a short basis of the same lattice.
3. In the signing procedure, the signer:
   1. generates a random value $\text{salt;}$
   2. computes a target $c=H\left(\text{msg||}\text{salt}\right)$, where $H$ is a hash function sending an input to a random-looking point (on the grid);
   3. uses his knowledge of a short basis to compute a lattice point $v$ close to the target $\mathrm{c;}$
   4. outputs $(\text{salt},s)$, where $s=c-\mathrm{v.}$
4. The verifier accepts the signature $(\text{salt},s)$ if and only if:
   1. the vector $s$ is short;
   2. $H\left(\text{msg||}\text{salt}\right)-s$ is a point on the lattice generated by his public key.

The way we described it, this framework is quite abstract. Which kind of lattice should we take? What form should their short and long bases have? How do we realise step 3.3, is it secure to use Babai’s rounding algorithm? We figure out these details in the rest of this blog post.

INGREDIENT #1: NTRU LATTICES

The first step to instantiate the GPV framework is to select a class of cryptographically hard lattices: we should be able to build a short and a long basis for the same lattice, such that it will be intractable for anyone with the long basis to find close vectors with as much accuracy than with the short basis. For didactic purposes, our example took a lattice of dimension n = 2. However, in practice this dimension is insufficient to assert security: in low dimensions, lattice reduction algorithms such as LLL can quickly recover a short basis (in our example, $B$) from a long basis (in our example, $C$). Just as RSA requires numbers of a few thousand bits to be secure against classical computers, lattice-based cryptosystems typically require dimensions in the order of magnitude of n = 1024 to be secure against classical and quantum computers.

Storing bases of such high dimensions can be costly: the resulting public key can easily be more than a megabyte. To circumvent this issue, it is typical to work with structured lattices, where a whole basis can be obtained by rotating the coefficients of a few initial basis vectors. This drastically reduces the storage size of a basis. Falcon uses NTRU lattices, which is a class of such structured lattices. Their use allows to reduce the public key size down to less than 1.8 kilobytes. Since their inception more than 20 years, NTRU lattices have successfully endured extensive scrutiny.

INGREDIENT #2: FAST FOURIER SAMPLING

The second step is to select an algorithm for computing close lattice vectors in step 3.3 of our signature scheme. While Babai’s rounding algorithm is a very efficient one, it is known that it should not be used here. Indeed, the output of Babai’s algorithm is always in a parallelepiped having the form of the basis used, therefore using it would slowly leak the private key. Instead, In their framework Gentry and his co-authors recommend to work with a modification of Babai’s algorithm, where:

• Each coefficient is rounded in a randomised way. This ensures that no information about the private key is leaked.
• Each rounding takes into account the previous ones. This allows sampling of closer vectors than with a naive rounding.

The resulting algorithm, often called the GPV sampler, is both safer and better than Babai’s rounding algorithm. As an additional improvement, Falcon leverages the structure of NTRU lattices to make the GPV sampler faster by two orders of magnitude. Our algorithm, called Fast Fourier sampling, can be seen as a hybrid between the GPV sampler and the fast Fourier transform, which use is widespread in signal processing.

PUTTING EVERYTHING TOGETHER

In a nutshell, Falcon uses a high-level recipe (the GPV framework) with two ingredients (NTRU lattices and fast Fourier sampling). The integer modulus is always the same, q = 12289. The public key is a single vector of n integers between 0 and q – 1, and similarly for each signature. Falcon comes in two variants, for either n = 512 or n = 1024. They target high efficiency and high security, respectively. The table below details the performances of Falcon. {Op}/s denotes the number of {Op} operations per second (timings are measured on an Intel Core i7-6567U at 3.3 GHz). |pk| And |sig| denote the sizes of the public key and the signature, respectively.

Additional resources about Falcon, including its full specification, the reference implementation, etc., can be found on its dedicated website:

https://falcon-sign.info/