Chapter 8: The LWE problem

The learning with errors problem, LWE, is a linear system over $\mathbb{Z}_q$ with a single catch. The solver is given a matrix $A$ and the vector $b = A s + e$, where $s$ is the unknown secret and $e$ is a small random perturbation. Without the perturbation, Gaussian elimination recovers $s$ in $O(m n^2)$ field operations, and the problem is a first-week linear algebra exercise. With the perturbation, the same algorithm fails loudly on almost every input. The noise is the source of hardness in the LWE family. ML-KEM rests on the related structured Module-LWE problem: its K-PKE component publishes noisy module equations of the form $(A, A s + e)$ over $R_q^k$, with small secrets and errors sampled from centered binomial distributions (National Institute of Standards and Technology, 2024; Regev, 2009).

A simple linear system, with a catch

Fix $q = 17$, the secret $s = (4, 7) \in \mathbb{Z}_{17}^2$, and the sample matrix

$$A = \begin{pmatrix} 3 & 5 \\ 2 & 1 \\ 7 & 4 \end{pmatrix}.$$

Computing $A s$ in ordinary integer arithmetic gives $(47, 15, 56)$, which reduces modulo $17$ to $b_{\text{clean}} = (13, 15, 5)$. An adversary who sees the pair $(A, b_{\text{clean}})$ can recover $s$ by picking any two rows of $A$ whose resulting $2 \times 2$ submatrix is invertible modulo $17$ and inverting that block. The first two rows give the submatrix

$$\begin{pmatrix} 3 & 5 \\ 2 & 1 \end{pmatrix}$$

with determinant $3 \cdot 1 - 5 \cdot 2 = -7 \equiv 10 \pmod{17}$ and inverse determinant $10^{-1} = 12 \pmod{17}$ (because $10 \cdot 12 = 120 = 7 \cdot 17 + 1$). Applying the $2 \times 2$ adjugate to the top two entries of $b_{\text{clean}}$ recovers the secret exactly, and the third row of the system holds as a redundant check.

import numpy as np

q = 17
A = np.array([[3, 5], [2, 1], [7, 4]], dtype=np.int64)
s_true = np.array([4, 7], dtype=np.int64)
b_clean = (A @ s_true) % q

def solve_2x2_mod_q(A_top, b_top, q):
    a, b, c, d = (
        int(A_top[0, 0]), int(A_top[0, 1]),
        int(A_top[1, 0]), int(A_top[1, 1]),
    )
    det = (a * d - b * c) % q
    det_inv = pow(det, -1, q)
    adj = np.array([[d, -b], [-c, a]], dtype=np.int64)
    return (det_inv * (adj @ b_top)) % q

s_recovered = solve_2x2_mod_q(A[:2], b_clean[:2], q)
row3_residual = int((A[2] @ s_recovered - b_clean[2]) % q)

print("b_clean =", b_clean.tolist())
# ==> b_clean = [13, 15, 5]
print("s_recovered (clean) =", s_recovered.tolist())
# ==> s_recovered (clean) = [4, 7]
print("row 3 residual =", row3_residual)
# ==> row 3 residual = 0

Every Python block this chapter prints is also a standalone file in the companion repository, under chapter-code/ch08/, one file per block. Appendix C covers the clone and the environment they run on.

Now introduce the catch. Replace $b_{\text{clean}}$ with $b = b_{\text{clean}} + e$, where $e = (1, 0, -2)$ is a small error vector. The modified right-hand side is $b = (14, 15, 3)$, with each entry shifted by at most two units from the clean value in symmetric representatives. The adversary, who does not know $e$, runs the same $2 \times 2$ inversion procedure on the first two rows. The arithmetic is identical except for one entry of the input, and the output is a vector in $\mathbb{Z}_{17}^2$. The recovered secret is $(16, 0)$, which is not $(4, 7)$, and the third row’s residual is no longer zero.

import numpy as np

q = 17
A = np.array([[3, 5], [2, 1], [7, 4]], dtype=np.int64)
s_true = np.array([4, 7], dtype=np.int64)
b_clean = (A @ s_true) % q
e = np.array([1, 0, -2], dtype=np.int64)
b_noisy = (b_clean + e) % q

def solve_2x2_mod_q(A_top, b_top, q):
    a, b, c, d = (
        int(A_top[0, 0]), int(A_top[0, 1]),
        int(A_top[1, 0]), int(A_top[1, 1]),
    )
    det = (a * d - b * c) % q
    det_inv = pow(det, -1, q)
    adj = np.array([[d, -b], [-c, a]], dtype=np.int64)
    return (det_inv * (adj @ b_top)) % q

s_recovered = solve_2x2_mod_q(A[:2], b_noisy[:2], q)
row3_residual = int((A[2] @ s_recovered - b_noisy[2]) % q)

print("b_noisy =", b_noisy.tolist())
# ==> b_noisy = [14, 15, 3]
print("s_recovered (noisy) =", s_recovered.tolist())
# ==> s_recovered (noisy) = [16, 0]
print("row 3 residual =", row3_residual)
# ==> row 3 residual = 7

Two things about this failure mode carry over to the general problem. First, the recovered secret is not close to the true one: $(16, 0)$ and $(4, 7)$ disagree on both coordinates and the distance is not a function of the error. Second, the third row’s residual is no longer forced to be zero. The error propagates through the $2 \times 2$ inversion as a scrambled projection that has no structural reason to vanish, and on a larger random instance the residual behaves like an unstructured projection of the error to this linear solver. Both observations are what makes LWE with $m > n$ unsolvable by linear algebra alone.

Search LWE and decisional LWE

An LWE instance is determined by a parameter tuple $(n, q, m, \chi)$. The integer $n \geq 1$ is the secret dimension, $q \geq 2$ is the modulus, $m \geq n$ is the number of samples, and $\chi$ is a distribution over $\mathbb{Z}$ whose samples are small integers called the error or noise. Throughout this chapter, $\chi$ is the uniform distribution on $\{-B, -B+1, \ldots, B\}$ for a nonnegative integer noise bound $B$.

Three error distributions recur in the LWE literature, and all three play the same conceptual role: they produce small errors.

Error distribution	Where it appears
$\bar\Psi_\alpha$, a continuous Gaussian over the torus discretized modulo $q$	Regev’s original construction, and the worst-case reduction stated later in this chapter (Regev, 2009)
Centered binomial	ML-KEM, specified in FIPS 203 and efficient to sample in constant time; Chapter 11 builds the sampler (National Institute of Standards and Technology, 2024)
Uniform on $\{-B, \ldots, B\}$	This chapter’s toy code, where the small support makes each error readable by eye

They are not theorem-level interchangeable. Regev’s worst-case reduction is stated for the Gaussian-derived error distribution, and ML-KEM’s IND-CPA argument uses the centered binomial. Concrete-attack estimates and the formal reductions carry distribution-specific constants.

Search LWE. Fix the parameter tuple $(n, q, m, \chi)$ and draw three things independently: $A \in \mathbb{Z}_q^{m \times n}$ uniform, $s \in \mathbb{Z}_q^n$ uniform, and $e \in \mathbb{Z}_q^m$ with every entry drawn from $\chi$ and reduced modulo $q$. Set $b = A s + e \pmod q$. The search LWE problem is to recover $s$ given only $(A, b)$ (Regev, 2009).

The adversary’s input is $(A, b)$ and the parameters; the secret $s$ and the error $e$ are hidden. The advantage of a solver is the probability that it outputs the true $s$, taken over the random choices of $A$, $s$, and $e$. The problem is believed hard when $m$ and $q$ are both polynomial in $n$, against the best known classical and quantum attacks covered in Chapter 13. The noise $\chi$ must be wide enough to defeat linear algebra yet narrow enough that the honest decrypter in a scheme built on LWE still recovers the secret message (Regev, 2009).

Why this chapter fixes a finite number of samples

The restriction $m \geq n$ is not part of every abstract definition of LWE, which is often phrased as a sample-oracle problem with unbounded $m$. This chapter fixes a finite overdetermined sample matrix because the q-ary lattice $\Lambda_q(A)$ in the section “LWE on a lattice” below is constructed from $A$ directly.

Decisional LWE. Given the same parameter tuple, the decisional LWE problem presents the solver with a pair $(A, b)$ drawn from one of two distributions, with equal probability. On the LWE side, $b = A s + e \pmod q$ with $A$, $s$, and $e$ drawn as in search LWE. On the uniform side, $b$ is a uniformly random element of $\mathbb{Z}_q^m$ independent of $A$. The solver must decide which (Regev, 2009).

Decisional LWE is the distinguishing game at the heart of cryptographic security. An IND-CPA-secure encryption scheme built on LWE cannot leak more than a negligible advantage in the distinguishing game. Any distinguishing attack on the scheme implies a distinguishing attack on the underlying problem. The two formulations turn out to be equivalent when $q$ is prime and polynomial in $n$, via a reduction walked in the “Why noise makes it hard” section below (Regev, 2009).

One detail about the error distribution matters for the rest of the chapter. When the error $e$ is reduced modulo $q$ into the canonical range $[0, q)$, a small entry of $\chi$ can look large in raw value. For example, with $q = 97$ and noise bound $B = 1$, the entry $e_i = -1$ is stored as $96$ in the canonical representatives. For odd $q$ the solver can pass to symmetric representatives $\{-(q-1)/2, \ldots, (q-1)/2\}$ to recover the short form; more generally, any centered interval of length $q$ works. Every statement below that says “the error is short” refers to the symmetric representative.

Sampling LWE instances in Python

Fix the toy parameters $(n, q, m, B) = (4, 97, 8, 1)$. The modulus is prime so that every nonzero element of $\mathbb{Z}_q$ is invertible. The dimensions $n$ and $m$ are small enough that every operation completes in microseconds. The noise bound $B = 1$ keeps the error distribution to three values $\{-1, 0, 1\}$ that the reader can track by hand. The full package is at solutions/ch08-lwe/. The snippets below show the core idea of each sampling operation in numpy and match the package up to the signature of the random number generator.

The secret is a uniform vector in $\mathbb{Z}_q^n$:

import numpy as np

n, q = 4, 97
rng = np.random.default_rng(seed=0)
s = rng.integers(low=0, high=q, size=n, dtype=np.int64)
print("s =", s.tolist())
# ==> s = [82, 61, 49, 26]

The error vector is drawn coordinate-wise from the uniform distribution on $\{-B, -B + 1, \ldots, B\}$. Reducing modulo $q$ puts the entries into the canonical range $[0, q)$. With $B = 1$ the reduced entries are in $\{0, 1, q - 1\} = \{0, 1, 96\}$, and the reader can spot the error coordinates by looking for a $1$ or a $96$:

import numpy as np

q, m, B = 97, 8, 1
rng = np.random.default_rng(seed=1)
raw = rng.integers(low=-B, high=B + 1, size=m, dtype=np.int64)
e = raw % q
print("raw error       =", raw.tolist())
# ==> raw error       = [0, 0, 1, 1, -1, -1, 1, 1]
print("reduced mod q =", e.tolist())
# ==> reduced mod q = [0, 0, 1, 1, 96, 96, 1, 1]

A full LWE instance combines the two. The sample matrix $A$ is uniform over $\mathbb{Z}_q^{m \times n}$, and the observation vector is $b = A s + e \pmod q$. One block sets a seed, draws everything, and prints the result:

import numpy as np

n, q, m, B = 4, 97, 8, 1
rng = np.random.default_rng(seed=0)

s = rng.integers(low=0, high=q, size=n, dtype=np.int64)
A = rng.integers(low=0, high=q, size=(m, n), dtype=np.int64)
e = rng.integers(low=-B, high=B + 1, size=m, dtype=np.int64)
b = (A @ s + e) % q

print("s =", s.tolist())
# ==> s = [82, 61, 49, 26]
print("e =", e.tolist())
# ==> e = [-1, -1, 0, 0, 0, -1, -1, -1]
print("b =", b.tolist())
# ==> b = [19, 31, 29, 65, 48, 86, 53, 87]

The decisional side of the distinguishing game draws a uniformly random $u \in \mathbb{Z}_q^m$ independent of $A$, so the adversary’s input is $(A, u)$ with the same shape as the search instance. Numerically the search and uniform instances are almost indistinguishable by eye: every entry is in $[0, q)$, every value occurs with roughly the same frequency, and the coordinate means are close:

import numpy as np

n, q, m, B = 4, 97, 8, 1

# Search instance with secret s and small error e.
rng = np.random.default_rng(seed=0)
s = rng.integers(low=0, high=q, size=n, dtype=np.int64)
A = rng.integers(low=0, high=q, size=(m, n), dtype=np.int64)
e = rng.integers(low=-B, high=B + 1, size=m, dtype=np.int64)
b_lwe = (A @ s + e) % q

# Decisional "uniform" side: same A, random u.
rng2 = np.random.default_rng(seed=7)
u_rand = rng2.integers(low=0, high=q, size=m, dtype=np.int64)

print("b_lwe  =", b_lwe.tolist())
# ==> b_lwe  = [19, 31, 29, 65, 48, 86, 53, 87]
print("u_rand =", u_rand.tolist())
# ==> u_rand = [91, 60, 66, 87, 56, 75, 80, 21]

Telling them apart requires either exploiting the short error $e$ or brute-forcing the secret. For plain LWE with a uniform secret the brute-force cost is $q^n$. ML-KEM is not this exact problem: its K-PKE component is Module-LWE over $R_q^k$ with modulus $q = 3329$, ring degree $256$, and module rank $k \in \{2, 3, 4\}$ for the three NIST categories, with small centered-binomial secrets (National Institute of Standards and Technology, 2024). The flat-LWE attack dimension is $k \cdot 256$ (so $512$ for ML-KEM-512), and the operational attacks use lattice reduction rather than exhaustive search. Chapter 13 develops the cost curve. The next section walks the cheap attack on the toy plain-LWE instance above and explains why it is cheap.

Why noise makes it hard

The noise-free LWE instance $(A, A s)$ is a determined linear system over $\mathbb{Z}_q$ as soon as $m \geq n$ and $A$ has full column rank. Gaussian elimination in $O(m n^2)$ field operations recovers $s$ exactly. The algorithm is the same one that solves real-valued linear systems, with one substitution: where the real version divides by a pivot, the $\mathbb{Z}_q$ version multiplies by a modular inverse, which exists for every nonzero element when $q$ is prime. The forward pass zeroes out the first $n$ columns of the extended matrix $[A \mid b]$ row by row. The back substitution reads $s$ out of the reduced form.

The following block implements exactly that algorithm in pure numpy. It is a pedagogical slice of gaussian_eliminate_mod_q in the ch08-lwe package under solutions/, with the error handling and assertions stripped down. The interface takes $A$, $b$, and $q$, and returns either the recovered $s$ or None. The None result signals that the rows below row $n-1$ of the reduced system contain a nonzero right-hand side. That situation never arises in the noise-free case and almost always arises in the noisy case:

import numpy as np

def solve_mod_q(A, b, q):
    A = np.array(A, dtype=np.int64) % q
    b = np.array(b, dtype=np.int64) % q
    m, n = A.shape
    for c in range(n):
        pivot = next((r for r in range(c, m) if A[r, c] != 0), None)
        assert pivot is not None, "rank deficient"
        A[[c, pivot]] = A[[pivot, c]]
        b[c], b[pivot] = int(b[pivot]), int(b[c])
        inv = pow(int(A[c, c]), -1, q)
        A[c] = (A[c] * inv) % q
        b[c] = (int(b[c]) * inv) % q
        for r in range(m):
            if r != c and A[r, c] != 0:
                f = int(A[r, c])
                A[r] = (A[r] - f * A[c]) % q
                b[r] = (int(b[r]) - f * int(b[c])) % q
    for r in range(n, m):
        if int(b[r]) % q != 0:
            return None
    return b[:n].copy()

n, q, m, B = 4, 97, 8, 1
rng = np.random.default_rng(seed=0)
s_true = rng.integers(0, q, size=n, dtype=np.int64)
A = rng.integers(0, q, size=(m, n), dtype=np.int64)
e = rng.integers(-B, B + 1, size=m, dtype=np.int64)
b_clean = (A @ s_true) % q
b_noisy = (A @ s_true + e) % q

s_clean = solve_mod_q(A, b_clean, q)
s_noisy = solve_mod_q(A, b_noisy, q)

print("s_true          =", s_true.tolist())
# ==> s_true          = [82, 61, 49, 26]
print("recovered clean =", s_clean.tolist())
# ==> recovered clean = [82, 61, 49, 26]
print("recovered noisy =", s_noisy)
# ==> recovered noisy = None

On the noise-free input the algorithm recovers $s$ exactly, with no residual. On the noisy input it returns None, which is the function’s signal that the forward-elimination residual on the last $m - n$ rows of the reduced system is nonzero. Concretely: the first $n$ rows of the reduced system determine a candidate $s'$, and the remaining $m - n$ rows must be consistent with that candidate for the output to be valid. In the clean case the candidate equals the true $s$ and every remaining row is the identity $0 = 0$. In the noisy case the candidate is a scrambled vector, and the remaining rows project the error through the forward pass in a way that almost never leaves a zero residual.

The None path depends on having strictly more samples than unknowns: when $m = n$ there are no consistency rows, and the solver returns a plausible-looking but wrong secret without signalling failure. The toy instance uses $m = 8 > n = 4$, so the check fires. Chapter 13 develops this failure into a concrete cryptanalytic cost model for the primal LWE attack.

Complexity of the noise-free case. Noise-free LWE recovery is dominated by the forward elimination, which touches every entry of the $m \times (n + 1)$ augmented matrix a constant number of times per pivot column. With $n$ pivot columns and $m$ rows of elimination, the total count is $O(m n^2)$ $\mathbb{Z}_q$ operations. For the small moduli used in this chapter each operation is a machine-word step. Asymptotically, the bit complexity carries an additional $\log q$ factor. For the toy parameters $n = 4$, $m = 8$, $q = 97$ this is in the hundreds of multiplications. A 2024-era laptop runs it in microseconds.

ML-KEM-512 uses Module-LWE over the ring $\mathbb{Z}_{3329}[x]/(x^{256} + 1)$ with module rank $2$, which looks like a flat LWE instance of effective dimension $512$ (National Institute of Standards and Technology, 2024). Treated as flat LWE, the same Gaussian elimination would run in a fraction of a second if the problem were noise-free. The noise is what keeps the LWE-based security argument alive.

Regev’s search-to-decision reduction. The two formulations of LWE are equivalent when $q$ is prime and polynomial in $n$. Any decisional-LWE distinguisher with non-negligible advantage yields a search LWE solver with polynomial overhead (Regev, 2009). The reduction recovers the secret one coordinate at a time by rerandomizing a fresh LWE sample. To pin down $s_i$, the solver iterates over candidates $k \in \mathbb{Z}_q$. Each iteration draws a fresh LWE sample $(a, c)$ and a uniform $r \in \mathbb{Z}_q$, then forms $(a', c') = (a + r \cdot e_i, c + k \cdot r)$. Drawing a fresh sample on every iteration ensures the distinguisher sees an independent input on every guess.

The arithmetic gives $c' = a' \cdot s + x + r (k - s_i)$, where $x$ is the original error. When $k = s_i$, the correction $r(k - s_i)$ vanishes and the pair is distributed as a fresh LWE sample with the same secret. When $k \neq s_i$, the quantity $r(k - s_i)$ is uniform on $\mathbb{Z}_q$ because $q$ is prime and $k - s_i$ is a unit, so $(a', c')$ is statistically uniform on $\mathbb{Z}_q^n \times \mathbb{Z}_q$. The correct candidate therefore preserves the LWE distribution and the incorrect candidates map it to uniform, so the distinguisher’s acceptance probability separates the two cases after the standard advantage-amplification step.

Running the procedure over every $k$ and every coordinate pins down $s$ in $O(n q)$ calls to the amplified distinguisher, polynomial when $q$ is polynomial in $n$. The full reduction first amplifies the distinguisher from non-negligible advantage to high probability, at a further polynomial cost in calls to the original one. Regev 2009 §4 covers the details (Regev, 2009).

The reverse direction, decisional LWE reducing to search LWE, is straightforward at this level: run the search solver on the input to obtain a candidate $s$, then check whether $b - A s$ is short in symmetric representatives. On true LWE samples the residual is short with the solver’s success probability; on uniform samples the residual is short only with negligible probability for the usual parameters. So the two formulations stand or fall together under the stated parameter regime.

LWE on a lattice

The noise-makes-it-hard demonstration above treated LWE as a linear algebra problem. The next observation reframes LWE as a lattice problem. That reframing is what Regev’s worst-case-to-average-case reduction operates on, and it is the source of LWE’s security advantage over assumptions (such as syndrome decoding) that lack a worst-case guarantee. Every LWE instance $(A, b)$ sits naturally on two companion q-ary lattices built from the sample matrix $A$, and search LWE becomes a bounded-distance decoding (BDD) instance on one of them.

The q-ary lattice $\Lambda_q^\perp(A)$. Given $A \in \mathbb{Z}_q^{m \times n}$ with $m \geq n$, define

$$\Lambda_q^\perp(A) = \{x \in \mathbb{Z}^m : A^\top x \equiv 0 \pmod q\}.$$

This is an integer lattice of dimension $m$: it contains the full sublattice $q \mathbb{Z}^m$ (because $A^\top (q x) = q (A^\top x) \equiv 0 \pmod q$ for every $x \in \mathbb{Z}^m$), and $q \mathbb{Z}^m$ already has rank $m$. When $A$ has full column rank modulo $q$, a standard rank-nullity count over $\mathbb{Z}_q$ gives the determinant of $\Lambda_q^\perp(A)$ as $q^n$. The index of $\Lambda_q^\perp(A)$ inside $\mathbb{Z}^m$ equals the order of the image of the map $\mathbb{Z}^m \to \mathbb{Z}_q^n$ defined by $x \mapsto A^\top x \pmod q$, which is $q^n$ when the map is surjective (Micciancio & Regev, 2009, sec. 3).

The following block constructs a basis for $\Lambda_q^\perp(A)$ on a tiny instance with $m = 3$, $n = 1$, $q = 11$, and verifies both the determinant identity and the defining condition that every basis vector annihilates $A^\top$ modulo $q$:

import numpy as np

q = 11
A = np.array([[3], [5], [2]], dtype=np.int64)
m, n = A.shape

# With n = 1, A is a column vector and A[0] = 3 is a unit mod 11.
# Use row 0 as the pivot and construct a basis directly.
inv = pow(int(A[0, 0]), -1, q)
B = np.array([
    [q,                                 0, 0],
    [(-int(A[1, 0]) * inv) % q,         1, 0],
    [(-int(A[2, 0]) * inv) % q,         0, 1],
], dtype=np.int64)

print("basis B =")
# ==> basis B =
print(B)
# ==> [[11  0  0]
# ==>  [ 2  1  0]
# ==>  [ 3  0  1]]

det_B = int(round(np.linalg.det(B.astype(float))))
print("|det B| =", abs(det_B))
# ==> |det B| = 11
print("q^n     =", q ** n)
# ==> q^n     = 11

for i, row in enumerate(B):
    r = (A.T @ row) % q
    print(f"A^T @ B[{i}] mod q = {int(r[0])}")
# ==> A^T @ B[0] mod q = 0
# ==> A^T @ B[1] mod q = 0
# ==> A^T @ B[2] mod q = 0

The basis has three rows (matching $m = 3$), the absolute determinant equals $q^n = 11$, and every row annihilates $A^\top$ modulo $q$. The function qary_lattice_basis in the ch08-lwe package under solutions/ implements the same construction for arbitrary $A$ by selecting an invertible set of $n$ rows of $A$ (equivalently $n$ pivot columns of $A^\top$) when the first $n$ rows do not already form one.

The primal companion $\Lambda_q(A)$. A second lattice built from $A$ is

$$\Lambda_q(A) = \{y \in \mathbb{Z}^m : y \equiv A s \pmod q \text{ for some } s \in \mathbb{Z}^n\} = A \mathbb{Z}^n + q \mathbb{Z}^m.$$

This one is also a full-rank integer lattice of dimension $m$, and its determinant is $q^{m - n}$ when $A$ has full column rank modulo $q$. The two lattices are related by a $q$-scaled duality: the geometric dual of $\Lambda_q(A)$ is $\Lambda_q(A)^* = (1/q) \cdot \Lambda_q^\perp(A)$, equivalently $\Lambda_q^\perp(A) = q \cdot \Lambda_q(A)^*$ (Micciancio & Regev, 2009, sec. 2). A direct check: a vector $y = x/q$ with $x \in \mathbb{Z}^m$ satisfies $\langle y, A s\rangle = (1/q) (A^\top x)^\top s$. This inner product lands in $\mathbb{Z}$ for every $s \in \mathbb{Z}^n$ iff $A^\top x \equiv 0 \pmod q$, iff $x \in \Lambda_q^\perp(A)$. The determinants obey $\det \Lambda_q(A) \cdot \det \Lambda_q^\perp(A) = q^{m - n} \cdot q^n = q^m$, matching the index of $q \mathbb{Z}^m$ in $\mathbb{Z}^m$.

Search LWE is BDD on $\Lambda_q(A)$. For any clean LWE vector $A s$ computed in $\mathbb{Z}^m$ (no mod-$q$ reduction), the result is an element of $\Lambda_q(A)$ by definition. The observation $b$ is the mod-$q$ reduction of $A s + e$. As integer vectors there is some $k \in \mathbb{Z}^m$ with $b = A s + e + q k$, where $k$ collects the per-coordinate wraparound that carries $A s + e$ into $[0, q)^m$. Because $\Lambda_q(A)$ contains $q \mathbb{Z}^m$, the point $A s + q k$ is itself a lattice vector, and $b$ sits at Euclidean displacement $\|e\|$ from it. The uniform noise on $\{-B, \ldots, B\}$ gives $\|e\| \leq \sqrt{m} \cdot B$.

Now suppose the noise bound $B$ is small enough that the minimum distance of $\Lambda_q(A)$ exceeds $2 \sqrt{m} \cdot B$. Then the closest lattice vector to $b$ is unique. Any solver for the closest vector problem on $\Lambda_q(A)$ recovers $A s \bmod q$, and the recovered $s$ follows by inverting $A$ modulo $q$ (a full-column-rank $A$ has a unique preimage in $\mathbb{Z}_q^n$) (Regev, 2009). This is bounded-distance decoding: a special case of CVP where the target is promised to be within a fraction of the minimum distance (Lyubashevsky & Micciancio, 2009, sec. 1). The promise makes BDD no harder than CVP, and the algorithms Regev’s paper surveys for LWE, which is BDD on this lattice, run in time $2^{O(n)}$ (Regev, 2009, sec. 1). Chapter 13 walks the best known BDD algorithms on q-ary lattices and places the three ML-KEM parameter sets of FIPS 203 §8 (National Institute of Standards and Technology, 2024) on the resulting cost curve.

Figure 8.1 shows the geometric picture of search LWE as BDD on a q-ary lattice. The lattice $\Lambda_q(A)$ is drawn in two dimensions with its points on a regular grid. The clean lattice vector $A s$ is highlighted. The noisy observation $b = A s + e$ sits slightly off the lattice, and a small arrow shows the error $e$. The shaded circle around $A s$ is the ball of radius $\sqrt{m} \cdot B$ that contains every possible noisy observation for the given noise bound $B$. Any bounded-distance decoder that can find the nearest lattice vector to any target inside that ball solves search LWE.

Figure 8.1. Search LWE as bounded-distance decoding on $\Lambda_q(A)$. The clean lattice vector $A s$ (large amber dot) sits in the q-ary lattice. The noisy observation $b = A s + e$ (smaller dot) is displaced by the short error $e$ into the surrounding ball of radius $\sqrt{m} \cdot B$ (faint amber disc).

Figure 8.1 compresses two facts into one drawing. The first fact is that the LWE equation defines a geometric displacement: the observation $b$ is literally the lattice vector $A s$ plus a short integer perturbation. The second fact is that the BDD ball is the promise under which the closest vector is unique. Concretely, as long as $2 \sqrt{m} \cdot B$ is strictly less than the minimum distance of $\Lambda_q(A)$, the lattice point $A s$ is the unique closest vector to $b$ in the whole lattice. The cryptographer’s job is to pick $B$ narrow enough that the scheme’s legitimate decrypter succeeds and wide enough that no BDD solver runs in polynomial time. ML-KEM’s parameter sets reflect that tradeoff at each NIST security category: enough dimension and noise to resist the known primal and dual attacks, while remaining efficient and correct enough for deployment (National Institute of Standards and Technology, 2024).

The dual attack on $\Lambda_q^\perp(A)$. The companion lattice $\Lambda_q^\perp(A)$ is the natural object for distinguishing LWE from uniform. A short vector $w \in \Lambda_q^\perp(A)$ satisfies $A^\top w \equiv 0 \pmod q$, so for a true LWE pair $(A, b)$ with $b = A s + e$,

$$w^\top b = w^\top (A s + e) = (A^\top w)^\top s + w^\top e \equiv w^\top e \pmod q,$$

which has much smaller spread than uniform modulo $q$ when $\|w\|$ times the error standard deviation is small relative to $q$. For a uniform pair $(A, u)$ and any $w \not\equiv 0 \pmod q$, the inner product $w^\top u$ is uniform modulo $q$. The nonzero-mod-$q$ condition matters: a vector such as $q e_i$ lies in $\Lambda_q^\perp(A)$ and forces $w^\top u \equiv 0$ regardless of $u$. A sufficiently short nonzero-mod-$q$ vector $w$ therefore gives a decisional-LWE distinguisher. Finding such a short $w$ is the shortest vector problem on $\Lambda_q^\perp(A)$ and is the driver of the dual attack family. Chapter 13 prices ML-KEM-512, ML-KEM-768, and ML-KEM-1024 against the best known dual attacks, where the answer turns on whether memory access is charged.

Regev’s worst-case reduction. The load-bearing hardness result is Regev’s 2009 theorem. Fix a modulus $q$, $m$ polynomial in $n$, and the Gaussian-derived LWE error distribution of width about $\alpha q$, with $\alpha q > 2 \sqrt{n}$. Under these parameters, an efficient algorithm for average-case LWE yields an efficient quantum algorithm for a discrete Gaussian sampling problem on arbitrary $n$-dimensional lattices. Standard reductions then imply quantum worst-case algorithms for approximating $\mathrm{SIVP}$ and $\mathrm{GapSVP}$ within factors on the order of $n/\alpha$, up to formulation-dependent logarithmic factors (Regev, 2009).

The modulus does not have to be prime for this theorem, which is worth stating because the previous section’s reduction did need a prime. Regev assumes a prime modulus only in the decision-to-search lemma and records that everywhere else, the main theorem included, the modulus may be an arbitrary integer (Regev, 2009). Primality therefore belongs to the search-to-decision equivalence, which is also how this statement transfers to decisional LWE.

Two consequences shape the rest of Part II. First, the LWE family has worst-case-to-average-case foundations: plain LWE through Regev’s theorem above, and the structured variants Ring-LWE and Module-LWE through related ring- and module-lattice assumptions. This foundation supports the schemes built in Part II, from Regev encryption in Chapter 10 to ML-KEM in Chapter 11. Concrete security still depends on the exact structured parameter set and attack model. Second, Regev’s original reduction is quantum. The theorem therefore bases LWE hardness on the assumed hardness of worst-case lattice problems against quantum algorithms, rather than giving a purely classical worst-case foundation. Classical reductions for important parameter regimes were later developed by Brakerski, Langlois, Peikert, Regev, and Stehlé (Brakerski et al., 2013). Chapter 13 does not reprove either reduction. It takes the hardness assumption as given and prices the best known concrete attacks, placing BKZ’s block size on the resulting cost curve.

Tradeoffs inside Part II

Chapter 9 lifts LWE from $\mathbb{Z}_q^n$ to the polynomial ring $\mathbb{Z}_q[x] / (x^n + 1)$, where the structured variants Ring-LWE and Module-LWE live. The structured form replaces a large unstructured scalar matrix with a small number of ring or module elements. Each ring element packs $n$ scalar coefficients, and multiplication is implemented efficiently with the number-theoretic transform.

Chapter 10 builds Regev encryption from LWE samples and proves IND-CPA security under decisional LWE: a bit is hidden by adding roughly $\lfloor q/2 \rceil$ times the bit to a noisy inner product, and decryption rounds back to the nearer half of the modulus. Chapter 11 replaces the $\mathbb{Z}_q$ secret with a Module-LWE secret, adds the Fujisaki-Okamoto transform from Chapter 5, and arrives at ML-KEM (National Institute of Standards and Technology, 2024). Chapter 13 walks the primal and dual attack families on the q-ary lattices introduced here, and positions the three ML-KEM parameter sets of FIPS 203 §8 (National Institute of Standards and Technology, 2024) on the current best cost curve.

The worst-case reduction is what separates the lattice families from the other assumption families in this book. Each rests on a different kind of evidence.

Family	Underlying assumption	Kind of evidence
Lattice (Part II)	LWE / Module-LWE, SIS / Module-SIS	Worst-case-to-average-case reductions from well-studied lattice problems
Hash-based signatures (Chapter 17)	Preimage resistance	A one-parameter assumption with no worst-case backing
Code-based KEM (Chapter 21, HQC)	Quasi-cyclic syndrome decoding	An NP-complete parent problem, but no average-case reduction from the worst case
Isogeny-based signature (Chapter 23, SQIsign)	The endomorphism ring problem on supersingular elliptic curves	New enough that its cryptanalytic surface is still being explored

NIST standardized a lattice-based KEM (ML-KEM, FIPS 203), a lattice-based signature (ML-DSA, FIPS 204) and the hash-based signature SLH-DSA (FIPS 205) (National Institute of Standards and Technology, 2024a, 2024b, 2024c). The positioning comes from the release announcement rather than the standards, which say nothing about it. NIST presents the two lattice schemes as the primary standards for general encryption and for signatures. SLH-DSA is the backup, resting on a different mathematical approach should ML-DSA prove vulnerable (National Institute of Standards and Technology, 2024d). The worst-case reduction is one stated part of the lattice schemes’ security justification, alongside performance, implementability, and attack-surface arguments that Chapter 13 walks in detail.

Chapter 9 is the immediate next step: it keeps the noisy linear equation $b = A s + e$ built here and changes only the algebra its terms live in.

Exercises

Exercise 1. Widen the noise and ask whether the failure is gradual. Modify the $(n, q, m, B) = (4, 97, 8, 1)$ instance above so that the noise bound is $B = 3$, $B = 10$, or $B = 30$. Run the solve_mod_q function on the noisy instance at each width and report the fraction of seeds for which it returns None versus a wrong secret versus (by accident) the true secret. State whether widening $B$ changes the failure behavior at all, and describe how the residual distribution on the last $m - n$ rows changes as the noise widens. Then run a second experiment that leaves $B = 1$ and sets $m = n$, removing the consistency rows, and say which of the two changes is the one that produces a consistent but wrong secret. Explain why this consistency check is not by itself an LWE attack.

Exercise 2. Brute-force decisional distinguisher. Implement a decisional-LWE distinguisher that, given a pair $(A, b)$, tries every $s \in \mathbb{Z}_q^n$ and reports the $s$ minimizing $\|A s - b\|_\infty$ in symmetric representatives. If the minimum is at most the noise bound $B$, output “LWE”; otherwise output “uniform”. Run it on a search instance and a uniform instance with the toy parameters $(n, q, m, B) = (4, 97, 8, 1)$ and report the running time as a function of $q^n$. Explain why this attack is polynomial in $q$ when $n$ is fixed, but exponential in $n$ when $q$ is fixed.

Exercise 3. q-ary orthogonality check. Take a random $A \in \mathbb{Z}_{97}^{8 \times 4}$ with seed zero, call qary_lattice_basis(A, 97) from the ch08-lwe package under solutions/, and verify two properties of the returned basis $B \in \mathbb{Z}^{8 \times 8}$. First, the absolute determinant equals $97^4 = 88\,529\,281$. Second, every row $v$ of $B$ satisfies $A^\top v \equiv 0 \pmod{97}$. For each row print the residual vector. Every entry must be zero. Explain in one sentence what property of $A$ (full column rank modulo $q$) the construction depends on.

Worked solutions and editorial notes for these exercises are in Appendix D, Chapter 8. A separate track, for rebuilding rather than reading: the package exercises/ch08-lwe has every function the chapter teaches replaced by a stub. Run PQC_IMPL=exercises pytest tests/ch08 to grade your version against the suite that proves the reference one.

References

Brakerski, Z., Langlois, A., Peikert, C., Regev, O., & Stehlé, D. (2013). Classical hardness of learning with errors. Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC), 575–584. https://doi.org/10.1145/2488608.2488680

Lyubashevsky, V., & Micciancio, D. (2009). On bounded distance decoding, unique shortest vectors, and the minimum distance problem. In S. Halevi (Ed.), Advances in Cryptology – CRYPTO 2009 (Vol. 5677, pp. 577–594). Springer. https://doi.org/10.1007/978-3-642-03356-8_34

Micciancio, D., & Regev, O. (2009). Lattice-based cryptography. In D. J. Bernstein, J. Buchmann, & E. Dahmen (Eds.), Post-Quantum Cryptography (pp. 147–191). Springer. https://doi.org/10.1007/978-3-540-88702-7_5

National Institute of Standards and Technology. (2024a). FIPS 203: Module-Lattice-Based Key-Encapsulation Mechanism Standard. Federal Information Processing Standards Publication. https://doi.org/10.6028/NIST.FIPS.203

National Institute of Standards and Technology. (2024b). FIPS 204: Module-Lattice-Based Digital Signature Standard. Federal Information Processing Standards Publication. https://doi.org/10.6028/NIST.FIPS.204

National Institute of Standards and Technology. (2024c). FIPS 205: Stateless Hash-Based Digital Signature Standard. Federal Information Processing Standards Publication. https://doi.org/10.6028/NIST.FIPS.205

National Institute of Standards and Technology. (2024d). NIST Releases First 3 Finalized Post-Quantum Encryption Standards. NIST news release. https://www.nist.gov/news-events/news/2024/08/nist-releases-first-3-finalized-post-quantum-encryption-standards

Regev, O. (2009). On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM, 56(6), 34:1-34:40. https://doi.org/10.1145/1568318.1568324