Post-Quantum Cryptography

Cryptography is built on computational problems that are believed to be hard, like breaking a candidate PRP, factoring large integers, calculating discrete logarithms in elliptic curves, to name a few. But quantum computers can solve some problems faster than classical computers; they change the landscape of hard problems. It is therefore important to understand their consequences on cryptography.

Quantum vs. post-quantum: There are two ways quantum computers can affect cryptography:

• We can imagine designing and deploying new cryptography that requires a quantum computer. Think of Alice and Bob sending entangled photons to each other. This kind of cryptography is called quantum cryptography; it is extremely limited and requires specialized hardware.

• We can imagine cryptography that runs on traditional, classical computers, but is designed to be secure even against adversaries who have access to a quantum computer. This kind of cryptography is called post-quantum cryptography.

This chapter discusses only post-quantum cryptography.

Urgency: Scalable quantum computers that pose a serious threat to cryptography do not yet exist, and may not exist for many decades. Still, they are plausible enough to warrant serious attention now, because data encrypted and stored today could be decrypted by a future quantum adversary.

Fortunately, paranoia is a virtue in cryptography, and cryptographers like to prepare for the worst-case scenario. Since 2017, NIST has been organizing a process to develop and select new post-quantum cryptographic standards. In 2022, four algorithms (one KEM and three signature schemes) were chosen as future standards. Section 20.3 describes some greatly simplified aspects of the winning KEM design.

20.1. Capabilities of quantum computing

Which problems are easier to solve on a quantum computer? This section summarizes known results that are relevant to cryptography. I will not attempt to describe how quantum computers work, or how these algorithms work; that is well beyond the scope of this book.

20.1.1. Attacking symmetric-key cryptography

Quantum computers can speed up brute-force searches from $2^n$ time to $2^{n/2}$ time, using a method called Grover's algorithm:

You can think of Grover's algorithm as a faster method for finding needles in haystacks. The haystack is $\bits^n$, and the needle is the special input $X$ that causes $F$ to output 1. Grover's algorithm can be used to attack symmetric-key cryptography by applying it to a suitable needle-identification function $F$.

For example, a quantum computer can break an SKE scheme in the following way: First, obtain a few ciphertexts with known plaintexts:

There need to be enough samples $m$ so that, with high probability, only one value of $\key$ is consistent with them all. Usually a very small value of $m$ is sufficient. Next, define the following function $F$:

This function checks whether a candidate $\key$ is consistent with all of the $(\ptxt_i,\ctxt_i)$ pairs, which are hard-coded as constants into the algorithm's description. By design, there is likely only one value of $\key$ that causes $F$ to output 1, and Grover's algorithm can find it in time $O(2^{\secpar/2})$.

Grover's algorithm speeds up brute-force attacks, but they remain exponential-time. Additionally, Grover's algorithm is inherently sequential — it cannot be obviously parallelized like a classical brute-force search. The threat of Grover's algorithm can be neutralized by simply doubling the length of the keys. To ensure that quantum brute-force attacks require $2^\secpar$ effort, we can choose keys that are $2\secpar$ bits long. Of course, this defense helps only if brute-force attacks are the best possible attack. For many symmetric-key primitives, this is assumed to be case; however, it is not true for asymmetric-key primitives.

20.1.2. Breaking asymmetric-key cryptography

In 1994, Peter Shor struck fear into the hearts of cryptographers everywhere by demonstrating that quantum computers could break most asymmetric-key cryptography in polynomial time:

All of the public-key cryptography that you've seen so far relies on either the hardness of factoring (as in RSA) or the discrete logarithm problem (as in Diffie-Hellman, El Gamal, Schnorr signatures). A quantum computer of reasonable size could break all of these schemes. New techniques are needed for post-quantum secure public-key cryptography.

20.2. The learning-with-errors problem

If you were asked to solve for the unknown $s_i$'s in the following system of equations, your task would be relatively easy:

You can write these as a single matrix equation, then solve it by inverting the square matrix that appears:

This problem is not made any harder by increasing the number of constraints (the height of this matrix), although in this case not every left-hand-side will have a solution. These systems of linear equations can also be solved modulo $\qmod$, as long as the matrix is invertible mod $\qmod$.

Now suppose you are asked to solve a system of approximate equations:

Here, $\approx$ means that the two sides differ by only a very small amount – say, $\{-1,0,1\}$. Such a system of approximate equations is much harder to solve.

We can rewrite these approximate equations as exact equations by introducing an error vector:

Here, the error vector is $\vec{e} = (e_1, e_2, e_3, \ldots)$, whose entries are known to be “small” (say, from $\{-1,0,+1\}$) but are otherwise unknown.

Equations like the one above are useful for cryptography because of the following dichotomy:

• When the number of approximate equations is high (the matrix is tall), there is generally at most one possible solution in the unknown $s_i$'s and $e_i$'s.

• On the other hand, it appears to be very hard to find that solution or to even determine whether one exists. All known algorithms for this problem, even quantum algorithms, require exponential time.

Learning With Errors: Learning with errors (LWE) is a cryptographic problem based on approximate linear equations of this kind. An adversary is given a matrix $\mat M$ and a vector $\vec x = \mat M \vec s + \vec e$, where $\vec s$ is sampled uniformly and $\vec e$ is sampled from a distribution of “small” values. All arithmetic is performed modulo $\qmod$.

An output of this LWE process is “close” (within a small error vector) of a vector of the form $\mat M \vec s$. If $\mat M$ is much taller than it is wide, not every $\vec x$ is close to a vector of the form $\mat M \vec s$, so not every $\vec x$ is a possible LWE output. However, it is believed to be hard to determine whether a $\vec x$ has this property. Thus, the LWE assumption is that $\vec x$ is indistinguishable from a uniformly distributed vector.

The vector $\vec e$ in LWE is called the noise vector. Each component of $\vec e$ is sampled independently from a distribution on “small” values, so we call vectors from this distribution “short.” Since we are working mod $\qmod$, instead of thinking about “small” values, think “close to 0,” in either direction. For example, $\qmod-1$ is “small” because $\qmod-1 \equiv -1$. In general, for the purposes of LWE it is helpful to think of $\Z_\qmod$ not as $\{0,1, \ldots, \qmod-1\}$ but as $\{ -\lfloor \frac{\qmod-1}2 \rfloor, \ldots, 0, \ldots, \lceil \frac{\qmod-1}2 \rceil \}$.

The LWE problem is not particularly sensitive to the precise distribution of noise elements; two common choices are a [discretized] Gaussian distribution (normal distribution) and a uniform distribution over $\{-c, \ldots, c\}$ for some small $c$.

Why “learning” with errors? The secret vector $\vec s$ defines a function $\vec m \mapsto \vec m^\top \vec s$. The adversary learns input/output samples of this function, one for each row of $\mat M$ and $\vec x$, but with added errors/noise.

LWE Security and Parameters: The security of LWE depends on a reasonable choice of the parameters listed above. The choice of these parameters is not as straightforward as it is for, say, RSA. There is not a one-size-fits-all recommendation, because different LWE-based constructions require matrices of different sizes, and are affected differently by the LWE noise. However, the following suggestions can give you a rough sense for the size of the numbers involved, for basic applications of LWE:

• The secret length $n$ should be the security parameter $\secpar$.

• The modulus $\qmod$ should be approximately $\secpar^2$.

• The noise distribution $\mathcal E$ should produce outputs bounded in magnitude by approximately $\sqrt{\secpar}$.

Using these parameters, the LWE assumption is believed to hold for any parameter $m$ (polynomial in the security parameter), even against quantum adversaries!

LWE With Short Secrets: The primary secret $\vec s$ in LWE is a uniformly sampled vector. Interestingly, the hardness of LWE does not change if $\vec s$ is instead sampled from the noise distribution:

20.3. Key exchange from LWE

In this section we discuss how LWE can be used for key exchange. The goal is not to show a realistic protocol (as you will see, the protocol we construct is impractical), but rather to merely provide some basic intuition for applying LWE to public-key cryptography.

Big Picture: Inspired By Diffie-Hellman: The heart of Diffie-Hellman KE is that there are two ways to compute the expression $g^{ab}$:

Additionally, Alice can send $g^a$, and Bob can send $g^b$, because these values “hide” $a$ and $b$ from an eavesdropper in some way.

LWE-based key exchange is motivated by two different ways to compute a vector-matrix-vector product:

Here, $\mat G$ is a public matrix, and $\vec a$ and $\vec b$ are vectors, so that the product $\vec a^\top \mat G \vec b$ a single scalar. The names are chosen to be suggestive of Diffie-Hellman. Suppose Alice and Bob sample secret vectors $\vec a$ and $\vec b$, then Alice sends $\vec a^\top \mat G$ and Bob sends $\mat G \vec b$. Both users could compute the common value $\vec a^\top \mat G \vec b$ in their own way, using the observation above. Would the resulting KE protocol be secure?

Unfortunately not: The protocol messages $\vec a^\top \mat G$ and $\mat G \vec b$ do not hide the secret vectors $\vec a$ and $\vec b$ in the same way that $g^a$ and $g^b$ hide exponents $a$ and $b$ in DHKE. However, the LWE assumption suggests that Alice and Bob can hide $\vec a$ and $\vec b$ by adding noise!

Adding noise: If both Alice and Bob add standard LWE noise to their protocol messages, we obtain the following KE protocol:

“Short” vectors sampled from the noise distribution are drawn here as shaded boxes. Thanks to lemma 20.2.2, it is safe for both users to sample their secret LWE vectors ($\vec a$ and $\vec b$) from the noise distribution. We use this fact later.

The two protocol messages each have the form of an LWE vector, which suggests that they hide $\vec a$ and $\vec b$. Keep in mind that Alice's protocol message is simply the transpose of a standard LWE vector (using $\mat G^\top$ as the LWE matrix):

Although noise is vital for security, it undermines the agreement aspect of key exchange. Alice will compute output:

whereas Bob will compute output:

Their outputs differ by an error amount:

Each vector in this expression ($\vec a$, $\vec b$, $\vec e_1$, $\vec e_2$) is a short vector, sampled from the noise distribution. It is possible to choose secure parameters for the noise distribution, to ensure that $\epsilon$ is sufficiently small: Say, $\PR{ \epsilon > q/4 }$ is negligible. The quantitative analysis is tedious, and beyond the scope of this book. But the conclusion is that Alice and Bob compute values that may not be identical, but are certainly close.

Reconciliation: Alice and Bob now hold values in $\Z_q$ that are within distance $q/4$. You can visualize the situation as follows, where we list the elements of $\Z_q$ in a circle, like the face of a clock.

Call Alice's value $\key$ and Bob's $\key'$. In the diagram above, Alice doesn't know Bob's $\key'$ but she knows that it is always in the shaded region.

To convert their approximately equal values into truly equal values, Alice can uniformly sample a bit $\alpha$ and send the message $R = K + \alpha \lfloor q/2 \rfloor \pct q$ to Bob. In other words, if $\alpha=0$, then Alice sends $K$, which is very close to Bob's $K'$; If $\alpha=1$ then Alice sends a value that is diametrically opposite $K$ in the $\Z_q$ circle, and therefore more than $q/4$ away from Bob's $K'$. Bob can easily distinguish these two cases, and thereby learn $\alpha$. Finally, Alice and Bob can agree on a common value! But an eavesdropper will not learn $\alpha$ because, as we will show, $K$ is pseudorandom to an eavesdropper, and acts as a one-time pad to mask $\alpha$.

Careful readers will have noticed that Alice and Bob have gone to all this work only to agree on a single bit! This is true, and this is what makes the protocol impractical. In principle, Alice and Bob could run $\secpar$ parallel instances of this protocol, to agree on a $\secpar$-bit key, but this would be incredibly expensive. Real-world LWE-based KE protocols are much more efficient, and we will briefly discuss them later. Still, they are based on the core ideas from this simplified protocol.

The protocol that results from this discussion is presented below. For reasons that shall become clear in the security analysis, Alice must add a noise term to her value of $K$.

LWE-based key exchange in practice: This KE protocol has been presented as a glimpse into the general techniques of post-quantum cryptography. As you saw, it is far from practical and requires considerable effort to agree on just a single bit.

In 2024, NIST standardized a new post-quantum PKE/KEM scheme called ML-KEM. It is based on the LWE approach described in this chapter but offers better performance through a few techniques:

• Our simple KE protocol has throughput of one bit because it is based on a vector-matrix-vector multiplication expression that results in a single scalar value. However, it is also possible to design a KE protocol based on matrix-matrix-matrix multiplication, which will allow Alice and Bob to (approximately) agree on an entire matrix of values. Exercises 20.4 and 20.7 give a roadmap to such a construction.

• Standard LWE involves a uniformly chosen matrix, but there exist LWE variants in which the matrix has some additional algebraic structure. For example, in the ring LWE variant, the matrix is not arbitrary but is built from $n \times n$ blocks, where each block has the special form:

  $\begin{bmatrix} a_1 & a_2 & a_3 & \cdots & a_n \\ -a_n & a_1 & a_2 & \cdots & a_{n-1} \\ -a_{n-1} & -a_n & a_1 & \cdots & a_{n-2} \\ & \vdots & & \ddots & \vdots \\ -a_2 & -a_3 & -a_4 & \cdots & a_1 \end{bmatrix}$

  Matrices of this form offer a few benefits: First, each $n \times n$ block is entirely determined by its first row, meaning that it is $n$ times cheaper to communicate these kinds of matrices in a protocol. Second, there are more efficient algorithms for multiplying these special kinds of matrices.

Exercises

1. Explain how to break a PRG $G : \bits^\secpar \to \bits^{\secpar+\ell}$ in time $O(2^{\secpar/2})$ on a quantum computer. Clearly describe an attack and analyze its distinguishing advantage.

2. This exercise develops a quantum algorithm for finding collisions in a hash function.

   1. Using an analysis similar to lemma 4.5.5, show that the following program has at least a 50 percent chance of outputting $\texttt{collision}$ when $m = 2^{n/3}$:

      for $i=1$ to $m$:

      $X \gets \bits^n$

      if $X \in \mathcal{X}$:

      output $\texttt{collision}$

      $\mathcal{X} := \mathcal{X} \cup \{X\}$

      for $i=1$ to $m^2$:

      $Y \gets \bits^n$

      if $Y \in \mathcal{X}$:

      output $\texttt{collision}$

      output $\texttt{fail}$

   2. Let $\ro$ be a random oracle with $n$ output bits. We will write inputs to $\ro$ as integers rather than strings. Consider the following quantum algorithm for finding a collision in $\ro$. What is the probability that it successfully finds a collision, and what is its running time?

      $m := 2^{n/3}$

      for $i=1$ to $m$:

      $X := \ro(i)$

      if $P[X]$ defined:

      output “$\texttt{collision}$: $i$ and $P[X]$”

      $P[X] := i$

      // define the following function $F$, whose

      // input domain is $\{ m+1, \ldots, m+m^2 \}$,

      // that has $P[\cdot]$ (from above) hard-coded:

      $F(i)$:

      $Y := \ro(i)$

      if $P[Y]$ defined: return $\bit1$

      else: return $\bit0$

      use Grover's algorithm to find $i^*$ such that $F(i^*) = 1$

      if Grover's algorithm fails: output $\texttt{fail}$

      otherwise: output “$\texttt{collision}$: $i^*$ and $P[\ro(i^*)]$”

3. Let $n,m,\qmod$ be parameters for the LWE problem. Suppose for the sake of simplicity that the error distribution $\mathcal E$ outputs values from the range $\{-d, \ldots, d\}$.

   1. With these parameters, how many outputs are possible from lwe.sample in $\lib{lwe-real}^{n,m,\qmod}$? (definition 20.2.1)

   2. With these parameters, how many outputs are possible from lwe.sample in $\lib{lwe-rand}^{n,m,\qmod}$?

   3. Suppose we use the suggested parameters $n = \secpar$, $\qmod = \secpar^2$, and $d = \sqrt{\secpar}$. How do your answers to (a) and (b) scale with $m$ and $\secpar$, especially when $m$ is much larger than $n$?

4. In this exercise, we extend LWE secrets from vectors to matrices. Prove that if the LWE assumption is true for parameters $n,m,\qmod$, then for any parameter $\ell$ the following two libraries are indistinguishable:

   $\lib{lwe-multi-real}^{n,m,\ell,\qmod}$

   $\subname{lwe.multi.sample}(\,)$:

   $\mat{M} \gets (\Z_\qmod)^{m \times n}$

   $\mat{S} \gets (\Z_\qmod)^{n \times \ell}$

   $\mat{E} \gets \mathcal{E}^{m \times \ell}$

   $\mat{X} = \mat{M} \cdot \mat{S} + \mat{E}$

   return $(\mat{M},\mat{X})$

   $\indist$

   $\lib{lwe-multi-rand}^{n,m,\ell,\qmod}$

   $\subname{lwe.multi.sample}(\,)$:

   $\mat{M} \gets (\Z_\qmod)^{m \times n}$

   $\mat{X} \gets (\Z_\qmod)^{m \times \ell}$

   return $(\mat{M},\mat{X})$

5. Formally show that the warmup protocol shown in the first figure in section 20.3 is not a passively secure KE protocol.

6. In construction 20.3.1, Alice and Bob exchange a single scalar $R = K + \alpha \lfloor q/2 \rfloor$ that helps them agree on an output bit $\alpha$. Consider the following approach that works when $q$ is a multiple of 4, and the noise (difference between $K$ and $K'$) is bounded by $q/8$. Alice sends a only single bit, indicating whether her value of $K$ is in the shaded region below; both users output a bit indicating whether Alice's $K$ is left or right of the dashed line.

   

   1. Explain/prove why the bit sent by Alice leaks nothing about the output bit.

   2. Explain how Bob can output the same secret bit as Alice.

7. Using exercise 20.4 as inspiration, design a KE protocol in which the two parties agree on $n^2$ bits, after exchanging $O(n^2)$ elements of $\Z_q$ ($n$ is the LWE parameter). Prove that your protocol is secure.

8. Propose a PKE scheme based on construction 20.3.1 and prove that it is CPA-secure under the LWE assumption. Your scheme can support single-bit plaintexts.

9. $\star$ There are variants of LWE that are unconditionally secure. For example, if the matrix is sufficiently wide ($n \ge 2m \log q$) and the secret vector is sampled not from $(\Z_q)^n$ but from $\{0,1\}^n$, then the resulting LWE variant is secure, without any noise! In other words, the following two libraries are indistinguishable:

   $\lib{lhl-real}^{n,m,q}$

   $\subname{lwe.sample}(\,)$:

   $\mat M \gets (\Z_q)^{m \times n}$

   $\vec s \gets \hl{\{0,1\}^n}$

   $\vec x = \mat{M} \vec{s}$

   return $(\mat M,\vec x)$

   $\indist$

   $\lib{lhl-rand}^{n,m,q}$

   $\subname{lwe.sample}(\,)$:

   $\mat M \gets (\Z_q)^{m \times n}$

   $\vec x \gets (\Z_q)^{m}$

   return $(\mat M,\vec x)$

   In section 20.3 we develop a KE protocol starting from the idea that $(\vec a^\top \mat G) \vec b = \vec a^\top (\mat G \vec b)$, but where both users add LWE noise to their vectors.

   1. Design a KE protocol in which one participant adds noise, but the other uses this noiseless LWE variant. Identify the error term (difference between users' approximately-equal $\Z_q$ values), and prove that your protocol is secure.

   2. Propose two different PKE schemes based on this KE protocol, and prove that they are CPA-secure. The participants in the KE protocol have asymmetric roles, and the two PKE schemes arise by assigning different participants to the roles of ciphertext and public key.

Chapter Notes

For an accessible and nontechnical summary of limitations of quantum (not post-quantum) cryptography, see the recent report from several European government agencies [103].

Grover's algorithm is named for its creator, Lov Grover [117]. The collision-finding algorithm in exercise 20.2 is due to Brassard, Høyer, and Tapp [54]. There is debate as to whether this quantum algorithm could ever be more efficient than the classical birthday attack (see Bernstein [36]).

Shor's algorithm is named after its creator, Peter Shor [202].

The learning with errors assumption was introduced by Regev [188]. Claim 20.2.2 is due to Applebaum, Cash, Peikert, and Sahai [6]. For a comprehensive overview of LWE and lattice-based cryptography in general, see the retrospective article by Peikert [179].

The ML-KEM standard is based on the Kyber KEM, of Avanzi, Bos, Ducas, Kiltz, Lepoint, Lyubashevsky, Schanck, Schwabe, Seiler, and Stehlé [8].

Construction 20.3.1 is based on the PKE schemes of Lyubashevsky, Palacio, and Segev [151] and Lindner and Peikert [148]. The two approaches suggested in exercise 20.9 give rise to well-known PKE schemes: the one proposed by Regev in the paper that introduced the LWE assumption [188] and the “dual-Regev” scheme proposed by Gentry, Peikert, and Vaikuntanathan [109]. These use a noiseless variant of LWE based on a result called the leftover hash lemma, which is due to Impagliazzo and Zuckerman [125]. The noise-reconciliation method of exercise 20.6 is due to Peikert [178].

1. Previous Chapter19. Zero-Knowledge Proofs