The mathematics behind PQC: lattices

15 Feb 2023

Introduction

A large number of post-quantum cryptographic schemes are based on a mathematical structure known as a lattice. Within this framework, it is possible to define problems that are believed to remain hard even in the presence of quantum computers. Cryptosystems in this class, collectively referred to as lattice-based cryptography, derive their security from computational problems that have been studied for several decades and are conjectured to be intractable for both classical and quantum computers. During the process of NIST standardization, aimed at identifying new quantum-resistant schemes in the field of public-key cryptography, numerous lattice-based proposals were submitted. Owing to their strong security and remarkable efficiency, many of these schemes advanced to the later stages of the selection process. Among the four final winners, three are lattice-based: the KEM (Key Encapsulation Mechanism) Kyber, and the digital signature schemes Dilithium and Falcon.

Lattices

Lattices are geometric objects that can be intuitively described as a regular grid. Formally, given a set of linearly independent vectors $B = {b_1,\dots ,b_r}$ in $\mathbb{R}^n$ , the lattice $\mathcal{L}(B)$ is defined as the set of all integer linear combinations of the vectors in $B$ . In other words, $\mathcal{L}=\{x_1 b_1 + x_2 b_2 + \dots + x_r b_r \mid x_1,\dots,x_r \in \mathbb{Z}\}$ . For simplicity, a lattice can be viewed as a set of points in $n$ -dimensional space with a periodic structure. The figure below illustrates the case of a lattice in two-dimensional space (with $r = 2$ ) and one in three-dimensional space (with $r = 3$ ).

Lattice problems

As mentioned earlier, several computational problems can be defined on lattices, and the security of lattice-based cryptographic schemes relies on the difficulty of solving them. Two of the most prominent examples are the Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP).

The Shortest Vector Problem consists of finding a nonzero lattice vector with minimum distance from the origin. Formally, given a lattice $\mathcal{L} \subset \mathbb{R}^n$ , the goal is to find $x \in \mathcal{L}$ such that

$\| x \| = \min_{t \in \mathcal{L}\setminus \{0\}} \| t \|.$

svp Telsy

The second computational problem on which many cryptosystems are based is the so-called Closest Vector Problem (CVP), whose goal is to find the lattice point closest to a given vector in the space where the lattice is defined.

Formally, given a lattice $\mathcal{L} \subset \mathbb{R}^n$ and a vector $t \in \mathbb{R}^n$ that does not belong to $\mathcal{L}$ , the task is to find an element $x \in \mathcal{L}$ such that

$\lVert x - t \rVert = \min_{a \in \mathcal{L}} \lVert a - t \rVert.$

cvp Telsy

For both CVP and SVP, it is also possible to define approximate versions ( $\gamma$ -CVP and $\gamma$ -SVP), in which the goal is to find a solution within a factor $\gamma$ , which typically depends on the dimension of the lattice itself. The exact versions of these problems belong to a class of extremely hard computational problems (known as NP-complete problems), which, however, are of limited practical relevance in cryptography. For this reason, the security of lattice-based cryptographic schemes is typically reduced to the hardness of the approximate versions of SVP and CVP for suitable approximation factors.

Problems hardness

Although several algorithms have been developed to solve SVP and CVP, these problems become computationally hard when dealing with high-dimensional lattices. By analyzing the computational cost of such algorithms, it is possible to assess the difficulty of solving SVP and CVP, and thus estimate the security of lattice-based cryptographic schemes built upon them. Among the most well-known algorithms for solving SVP and CVP are LLL (Lenstra–Lenstra–Lovász), proposed in 1982, and its generalization BKZ (introduced by Schnorr and Euchner), which is more widely used today. However, these algorithms can solve only approximate versions of SVP in polynomial time, and only for values of $\gamma$ that are too large to be useful in practical attacks against lattice-based schemes. We can also mention the algorithms proposed by Kannan (1983) and Babai (1986), which are likewise capable of solving approximate versions of CVP in polynomial time, but only for approximation factors that are exponential in the lattice dimension. Algorithms that achieve polynomial approximation factors (the regime relevant for lattice-based cryptography) require exponential time in the lattice dimension. As a result, no efficient attacks against current lattice-based schemes are known.

Lattices at the base of PQC

Supporting the security of lattice-based cryptography is a notable theoretical result that links the average-case complexity of cryptographic schemes to the worst-case complexity of certain lattice problems. By average-case complexity, we refer to classes of problems for which a random choice of parameters does not affect their complexity on average. Such problems are of interest in public-key cryptography, since each key generation implicitly corresponds to a random instance of a problem, whose security must not depend on the choice of that instance. On the other hand, the notion of worst-case complexity—according to which a problem is considered hard provided that at least one instance is computationally intractable—is more intuitive and easier to analyze, but is not directly relevant for cryptographic purposes. In 1996, the Hungarian mathematician Miklos Ajtai proved a worst-case to average-case reduction, through which it is possible to define certain constructions (on which the security of lattice-based cryptosystems is based) that are hard unless all instances of some lattice problems (for example SVP and CVP) are easy to solve. This result, although theoretical in nature and not immediately applicable to current schemes, strengthens confidence in the design of lattice-based cryptographic constructions.

Indeed, the security of these schemes, for appropriate parameters, is guaranteed unless it can be shown that it is always possible to efficiently solve an instance of SVP or CVP—something that does not appear realistic given the computational cost of the algorithms currently used to solve these problems. Moreover, despite numerous attempts since the 1990s, no quantum algorithms have been proposed that solve CVP and SVP with significantly better performance than the classical algorithms mentioned above. This supports the widespread belief in the mathematical community that these computational problems can provide a suitable foundation for developing cryptographic schemes resistant to attacks by quantum computers, and on which the future of public-key cryptography may rely. As further evidence, one can observe the predominance of lattice-based schemes in the standardization process initiated by NIST: in the first round of the competition, 26 out of 64 schemes were lattice-based; in the second round, 12 out of 26; and in the third round, 7 out of 15. In the next articles of this series, we will examine in more detail the three lattice-based winners of the first phase of the NIST standardization process: Kyber, Dilithium, and Falcon.

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 authors

Veronica Cristiano, a bachelor’s degree in Mathematics from the University of Pisa and a master’s degree in Mathematics with a specialization in Cryptography at the University of Trento, joined the Telsy Cryptography research group in mid-2021.

Marco Rinaudo, a bachelor’s degree in Mathematics from the University of Turin and a master’s degree with a specialization in Cryptography from the University of Trento. Following a 2022 curricular internship at Telsy, he has been part of the Cryptography Research Group since January 2023.