The Math Behind PQC: Learning With Errors

27 Mar 2023

Introduction

Some of the cryptographic schemes that emerged as winners of the NIST standardization process and belong to the lattice-based cryptography family are built upon a problem known as Learning With Errors (LWE). Given a system of random linear equations describing a secret, the Learning With Errors problem is based on the idea of hiding the value of the secret by adding noise (or error) to the system. Introduced in 2005 by the Israeli-American computer scientist and theoretical mathematician Oded Regev, LWE has had a significant impact on post-quantum cryptography from the very beginning, earning Regev the Gödel Prize in 2018, a prestigious award in the field of theoretical computer science.

Learning With Errors

Despite its strong connection to lattice problems, somewhat surprisingly, LWE is not itself a problem defined on lattices, but rather an algebraic problem. The core idea behind Learning With Errors is to make a system of random equations hard to solve by introducing small errors into it. For a better problem understanding, first consider the following linear system

$\begin{cases} 3s_1+3s_2=6 \\ 2s_1+5s_2=7 \\ 4s_1+s_2=5 \\ \end{cases}$

that can be also written in terms of matrices as

$\begin{pmatrix} 3 & 3 \\ 2 & 5 \\ 4 & 1 \end{pmatrix} \mathbf{s} = \begin{pmatrix} 6 \\ 7 \\ 5 \end{pmatrix}$

where $\mathbf{s} = \begin{pmatrix} s_1 \\ s_2 \end{pmatrix}$ is the secret. In this system, finding $s$ is computationally easy, since Gaussian elimination can be applied. However, if an error $e= \begin{pmatrix} e_1 \\ e_2 \\ e_3 \end{pmatrix}$ , with $e_i$ ‘s “small”, is included into the system, solving

$\begin{pmatrix} 3 & 3 \\ 2 & 5 \\ 4 & 1 \end{pmatrix} \mathbf{s} + \begin{pmatrix} e_1 \\ e_2 \\ e_3 \end{pmatrix} = \begin{pmatrix} 4 \\ 6 \\ 6 \end{pmatrix}$

becomes much difficult. In cryptography, arithmetic is usually restricted to integer modulo $q$ , where the operations can be efficiently implemented. Formally, let $q$ be a positive integer and $\mathbb{Z}_q=\{0,\dots,q-1\}$ , consider $m$ public vectors $a_1,\dots,a_m\in \mathbb{Z}_q^k$ with $\mathbf{a}_{i}=(a_{i,1},\dots,a_{i,k})$ , a secret $\mathbf{s}=(s_1,\dots,s_k)\in \mathbb{Z}_q^k$ and $m$ small values $e_1,\dots,e_m\in \mathbb{Z}_q$ , the system of equations

$\begin{cases} \langle \mathbf{a}_1,\mathbf{s}\rangle+e_1=b_1 \pmod{q} \\ \langle \mathbf{a}_2,\mathbf{s}\rangle+e_2=b_2 \pmod{q} \\ \vdots \\ \langle \mathbf{a}_m,\mathbf{s}\rangle+e_m=b_m \pmod{q}. \end{cases}$

can be rewritten in matrix form as

$\begin{pmatrix} a_{1,1} & \cdots & a_{1,k} \\ a_{2,1} & \cdots & a_{2,k} \\ \vdots & \ddots & \vdots \\ a_{m,1} & \cdots & a_{m,k} \end{pmatrix} \cdot \begin{pmatrix} s_1 \\ \vdots \\ s_k \end{pmatrix} + \begin{pmatrix} e_1 \\ e_2 \\ \vdots \\ e_m \end{pmatrix} = \begin{pmatrix} b_1 \\ b_2 \\ \vdots \\ b_m \end{pmatrix} \pmod{q},$

or $\mathbf{A}\mathbf{s} + \mathbf{e} = \mathbf{b} \pmod{q}$ for short. The LWE problem consists of the following: given a pair $(\mathbf{A}, \mathbf{b})$ , where $\mathbf{A}$ is sampled uniformly and $\mathbf{e}$ is sampled according to a certain probability distribution (typically a Gaussian distribution) over $\mathbb{Z}_q$ , the goal is to find $\mathbf{s}$ . More precisely, the formulation just described corresponds to the search version of LWE (Search-LWE), which has been proven equivalent to the decision version (Decision-LWE). In the latter, the objective is, given a pair $(\mathbf{A}, \mathbf{b})$ , to determine whether it has the structure described above or is uniformly random. Observe that, as in the previous example, the presence of the error term $\mathbf{e}$ makes the system hard to solve (for instance, it is no longer possible to recover $\mathbf{s}$ using Gaussian elimination). This hardness is also the foundation of public-key cryptosystems built from LWE, where the public key is $(\mathbf{A}, \mathbf{b})$ and the private key is $\mathbf{s}$ .

LWE hardness

The LWE problem admits a worst-case to average-case reduction from certain lattice problems, which are believed to be hard for both classical and quantum computers. In other words, the security of LWE, for appropriate parameter choices, is guaranteed unless one can show that it is always possible to efficiently solve an instance of a lattice problem—an assumption that appears unrealistic given the computational cost of the algorithms currently used to find solutions. The hardness of the problem can be formally established and also intuitively understood by relating it to a lattice problem known as Bounded Distance Decoding (BDD). BDD is a variant of the Closest Vector Problem (CVP) which, given a lattice and a vector (called the target) that is sufficiently close to it in the ambient space, consists of finding the unique lattice point closest to the target. Formally, given a lattice $\mathcal{L}$ and a target $\mathbf{t} \in \mathbb{R}^k$ at small distance $d$ from $\mathcal{L}$ , that is, $\min_{x \in \mathcal{L}} \lVert t - x \rVert < d$ , the goal is to find $\mathbf{x} \in \mathcal{L}$ such that $\lVert t - x \rVert < d$ . ********placeholder “bdd.png” BDD, like the other lattice problems (SVP and CVP) described in the previous article in this series, becomes computationally hard to solve in high-dimensional lattices, and to date no classical or quantum algorithm is known that can solve these problems in polynomial time. There are several theoretical results showing that solving an LWE instance $(\mathbf{A}, \mathbf{b})$ is equivalent to solving BDD for the lattice defined by the basis $\mathbf{A}$ and target $\mathbf{b}$ . A simple intuition can be given by the following diagram. ********placeholder “lwe-bdd.png” Indeed, let $(\mathbf{A},\mathbf{b}=\mathbf{As}+\mathbf{e}$ be an LWE instance and consider the lattice

$\mathcal{L}(\mathbf{A}):=\{\mathbf{Av}:\mathbf{v}\in\mathbb{Z}_q^{k}\}.$

Since $\mathbf{e}$ is small, $\mathbf{A}\mathbf{s}$ (from which $\mathbf{s}$ can be easily recovered) is the lattice point in $\mathcal{L}(\mathbf{A})$ closest to $\mathbf{b}$ . This yields an instance of the Bounded Distance Decoding problem.

LWE in post-quantum schemes

LWE-based cryptographic schemes, in order to be secure, require large public keys, typically of size $(k \times m) \sim m^2$ , corresponding to the size of the matrix $\mathbf{A}$ . This means that as the security parameters increase, the size of the matrix $\mathbf{A}$ —and thus of the public key—grows quadratically. From an efficiency standpoint, however, it is highly desirable to reduce the size of the public key to a value that grows at most linearly with the security parameters. A natural approach to achieve this goal is to introduce additional structure into the public matrix $\mathbf{A}$ , so that it can be represented using a limited amount of information, thereby reducing the space required for its storage. To this end, the Ring-LWE and Module-LWE variants have been proposed. In these settings, the sampled elements are no longer taken from $\mathbb{Z}_q$ , as in the basic LWE formulation, but from $R_q = \mathbb{Z}_q/(X^n + 1)$ , the ring of polynomials in $X$ with coefficients in $\mathbb{Z}_q$ , subject to the relation $X^n = -1$ . The security of the Kyber scheme, a Key Encapsulation Mechanism (KEM) winner of the NIST competition, is based on the latter. An instance of Module-LWE is given by $(\mathbf{A}, \mathbf{b}) \in R_q^{m \times k} \times R_q^{m}$ , where $a_{i,j}(X) \in R_q$ , $s_j(X) \in R_q$ , and $e_i \in R_q$ for every $i \in {0, \dots, m}$ and every $j \in {0, \dots, k}$ . For a clearer understanding, consider the example where $n = 2$ , $m = 2$ , and $k = 3$ . The system is then defined in terms of $R_q$ as

$\begin{pmatrix} a(X) & c(X) & d(X) \\ f(X) & g(X) & h(X) \\ \end{pmatrix} \begin{pmatrix} s_1(X) \\ s_2(X) \\ s_3(X) \end{pmatrix} + \begin{pmatrix} e_1(X) \\ e_2(X) \end{pmatrix} = \begin{pmatrix} b_1(X) \\ b_2(X) \\ \end{pmatrix}\in R_{q}^{2}\\$

or in terms of $\mathbb{Z}_q$ as

$\left( \begin{array}{c c | c c | c c} a_0 & -a_1 & c_0 & -c_1 & d_0 & -d_1 \\ a_1 & a_0 & c_1 & c_0 & d_1 & d_0 \\ \hline f_0 & -f_1 & g_0 & -g_1 & h_0 & -h_1 \\ f_1 & f_0 & g_1 & g_0 & h_1 & h_0 \end{array} \right) \cdot \left( \begin{array}{c} s_{1,0} \\ s_{1,1} \\ \hline s_{2,0} \\ s_{2,1} \\ \hline s_{3,0} \\ s_{3,1} \end{array} \right) + \left( \begin{array} {c } e_{1,0} \\ e_{1,1} \\ \hline e_{2,0} \\ e_{2,1} \end{array} \right) = \left( \begin{array}{c} b_{1,0} \\ b_{1,1} \\ \hline b_{2,0} \\ b_{2,1} \end{array} \right) \in \mathbb{Z}_{q}^{2\cdot 2}.$

For each of these problems, there also exists a derandomized version, where errors are introduced through a rescaling and rounding operation. This leads to the Learning With Rounding (LWR) problem, as well as its Ring-LWR and Module-LWR variants. The latter underlies the security of Saber, a KEM that was excluded from the NIST competition at the end of the third round in favor of Kyber. Beyond its widespread use in lattice-based cryptography, LWE also enables the construction of a wide range of cryptographic primitives, including Fully Homomorphic Encryption (FHE) schemes. In the next articles of this series, we will explore in more detail the KEM Kyber and the digital signature scheme Dilithium, winners of the first phase of the NIST standardization process, both based on variants of LWE.

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.

Francesco Stocco, a master’s degree in Mathematics at the University of Padua and the Université de Bordeaux attending the course of study “Algebra Geometry And Number Theory” (ALGANT), joined the Telsy research group in Cryptography at end of 2020 focusing in particular on issues related to quantum technologies.