Chapter 13: Lattice cryptanalysis

Lattice reduction finds short vectors. Concrete LWE security is a statement about that search: the primal attack builds a lattice from the LWE sample in which the secret and the error form one short vector, and the parameters are set so that lattice reduction does not reach it inside the attacker’s time budget. Regev’s reduction is the worst-case foundation the problem family rests on, and it gives no concrete cost (Regev, 2009). The Kyber Round 3 submission’s security table (Table 4) makes that concrete claim precise for Module-LWE at the ML-KEM parameter sets. FIPS 203 standardizes the ML-KEM parameter sets and states the category claims for ML-KEM-512, ML-KEM-768, and ML-KEM-1024 (Avanzi et al., 2021; National Institute of Standards and Technology, 2024). The reimplementation at solutions/ch13-lattice-cryptanalysis/ reproduces the Kyber Round 3 submission’s Table 4 block sizes for all three parameter sets within five block sizes. It uses only equation 9 of the submission, the Chen 2013 root-Hermite factor, and the Becker-Ducas-Gama-Laarhoven 2016 sieving exponents.

A toy primal attack that actually runs

The parameter regime where lattice reduction wins is tiny. A flat-LWE instance with $n = 4$ unknowns, $q = 97$, and $m = 8$ samples fits in a thirteen-dimensional lattice and LLL recovers the secret in milliseconds. The same construction scaled up to the ML-KEM-768 parameter set gives a lattice of dimension $d = 1419$. On that lattice the core-SVP model gives a conservative estimate of roughly $2^{182}$ classical operations; the Kyber Round 3 Table 4 core-SVP figure is $2^{183}$ (Avanzi et al., 2021).

Fix a specific instance. Sample the matrix $A \in \mathbb{Z}_{97}^{8 \times 4}$ and the secret $\mathbf{s} \in \{-1, 0, 1\}^4$ and the error $\mathbf{e} \in \{-1, 0, 1\}^8$ from a seeded numpy generator, and set $\mathbf{b} = A \mathbf{s} + \mathbf{e} \bmod 97$. The secret distribution is the simplest possible small-secret analogue of the centered binomial used in ML-KEM (National Institute of Standards and Technology, 2024). The error distribution matches the Chapter 8 toy instance. The concrete secret and error drop out of the numpy seed: the secret is $\mathbf{s} = (-1, 1, -1, 0)$ and the error is $\mathbf{e} = (-1, -1, 0, 0, 0, -1, -1, -1)$.

The primal embedding lifts the LWE sample into a lattice that contains $(\mathbf{e}, -\mathbf{s}, 1)$ as one of its vectors, the unique-SVP instance the Kyber Round 3 submission’s primal attack builds (Avanzi et al., 2021, sec. 5.1.2). The construction: stack three block rows inside a $(m + n + 1) \times (m + n + 1)$ integer matrix. The top $m$ rows are $q$ times the identity, which forces the first $m$ coordinates to live in $q \mathbb{Z}^m$. The middle $n$ rows pair $A^{\top}$ (in the first $m$ columns) with $I_n$ (in the next $n$ columns), which tells the lattice that any integer combination of secret coordinates contributes the corresponding $A$-column combination to the first block. The bottom row places $\mathbf{b}$ in the first $m$ columns and a single $1$ in the last column, which plants the target.

A vector of the form $(\mathbf{e}, -\mathbf{s}, 1)$ is always in the lattice by construction. Take one copy of the bottom row. Subtract $s_j$ copies of the $j$-th middle row for each $j$. Add the right multiple of each top row. The first block becomes $\mathbf{b} - A \mathbf{s} = \mathbf{e}$. The middle block becomes $-\mathbf{s}$. The last coordinate is $1$. The norm is $\sqrt{\|\mathbf{e}\|^2 + \|\mathbf{s}\|^2 + 1} = \sqrt{5 + 3 + 1} = 3$ on the seeded instance. A random lattice of the same dimension $d = 13$ and determinant $V = q^8$ has a shortest vector of norm approximately $\sqrt{d / (2 \pi e)} \cdot V^{1/d} \approx 14.6$ under the Gaussian heuristic (Gama & Nguyen, 2008). So $(\mathbf{e}, -\mathbf{s}, 1)$ is far shorter than the generic expectation, and LLL finds it directly (Lenstra et al., 1982).

The block below defines a toy LLL (the swap-and-size-reduce loop from the 1982 Lenstra-Lenstra-Lovász paper at the standard parameter $\delta = 3/4$) and runs it on the Kannan embedding.

import numpy as np


def lll(basis, delta=0.75):
    """Toy educational LLL: the standard size-reduce / swap loop at parameter delta."""
    B = basis.astype(float).copy()
    dim = B.shape[0]

    def gso():
        Q = np.zeros_like(B)
        mu = np.zeros((dim, dim))
        for i in range(dim):
            Q[i] = B[i].copy()
            for j in range(i):
                mu[i, j] = B[i] @ Q[j] / (Q[j] @ Q[j])
                Q[i] = Q[i] - mu[i, j] * Q[j]
        return Q, mu

    k = 1
    while k < dim:
        Q, mu = gso()
        for j in range(k - 1, -1, -1):
            if abs(mu[k, j]) > 0.5:
                B[k] = B[k] - round(mu[k, j]) * B[j]
                Q, mu = gso()
        if Q[k] @ Q[k] >= (delta - mu[k, k - 1] ** 2) * (Q[k - 1] @ Q[k - 1]):
            k += 1
        else:
            B[[k, k - 1]] = B[[k - 1, k]]
            k = max(k - 1, 1)
    return B.astype(int)


rng = np.random.default_rng(0)
n, m, q = 4, 8, 97
A = rng.integers(0, q, size=(m, n))
s = rng.integers(-1, 2, size=n)
e = rng.integers(-1, 2, size=m)
b = (A @ s + e) % q

# Kannan primal embedding of dimension m + n + 1 = 13.
d = m + n + 1
basis = np.zeros((d, d), dtype=int)
basis[:m, :m] = q * np.eye(m, dtype=int)
basis[m:m + n, :m] = A.T
basis[m:m + n, m:m + n] = np.eye(n, dtype=int)
basis[m + n, :m] = b
basis[m + n, m + n] = 1

planted = np.concatenate([e, -s, [1]])
print(f"planted secret s = {s.tolist()}")
# ==> planted secret s = [-1, 1, -1, 0]
print(f"planted error  e = {e.tolist()}")
# ==> planted error  e = [-1, -1, 0, 0, 0, -1, -1, -1]
print(f"planted (e || -s || 1) norm = {float(np.linalg.norm(planted)):.4f}")
# ==> planted (e || -s || 1) norm = 3.0000

reduced = lll(basis)
shortest = reduced[0]
print(f"LLL shortest row norm      = {float(np.linalg.norm(shortest)):.4f}")
# ==> LLL shortest row norm      = 3.0000
print(f"equals planted vector ?    {np.array_equal(shortest, planted) or np.array_equal(shortest, -planted)}")
# ==> equals planted vector ?    True

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

LLL recovers the planted vector on the first reduced row. The recovered middle block is $-\mathbf{s}$ and the recovered first block is $\mathbf{e}$. Normalizing by the last coordinate recovers the sign, since LLL may return the negated planted vector. The attack terminates at dimension thirteen.

The instance scales unpleasantly. ML-KEM-768 has $k = 3$ module rows over a polynomial ring of degree $256$, which gives an effective LWE dimension of $kn = 768$ (National Institute of Standards and Technology, 2024). The Kannan embedding at the published optimal number of samples has dimension $d = 1419$ (Avanzi et al., 2021). LLL alone cannot handle dimension 1419. The rest of the chapter quantifies the gap between “LLL works at $d = 13$” and “the core-SVP model gives a conservative estimate of roughly $2^{182}$ classical operations at $d = 1419$”.

The four problems and the two tools

Chapter 7 stated SVP, CVP, and $\mathrm{GapSVP}_\gamma$ precisely (Micciancio & Goldwasser, 2002). Module-LWE’s attack analysis also depends on two relaxations of those problems. Bounded Distance Decoding (BDD) is the promise-version of CVP where the target is guaranteed close to the lattice. Unique-SVP is the promise-version of SVP where the shortest vector is much shorter than every lattice vector linearly independent of it. Both relaxations are easier than the full problem in principle. Both are what LWE reduces to in practice.

Bounded distance decoding (BDD). The BDD input is a basis $B$ of a lattice $L \subset \mathbb{R}^d$, a target $\mathbf{t} \in \mathbb{R}^d$, and a promise that $\mathrm{dist}(\mathbf{t}, L) < \lambda_1(L) / (2 \gamma)$ for some slack factor $\gamma \geq 1$. The output is the lattice point closest to $\mathbf{t}$, which is $\mathrm{BDD}_{1/(2\gamma)}$ in the Lyubashevsky-Micciancio notation (Definition 2 in Lyubashevsky & Micciancio, 2009). The promise that the target is strictly within half the minimum distance guarantees uniqueness. Babai’s nearest-plane algorithm solves BDD in polynomial time whenever the reduced basis is good enough (Babai, 1986), and the Lindner-Peikert decoding attack on LWE is a widened nearest-planes search on a BKZ-reduced basis of the LWE lattice (Lindner & Peikert, 2011, sec. 4). LWE is a BDD instance. The public LWE sample $(A, \mathbf{b})$ corresponds to a target $\mathbf{b}$ near the lattice spanned by the columns of $A$ modulo $q$. The error $\mathbf{e}$ is the promise that the target is close.

Unique-SVP. The uSVP input is a basis $B$ of a lattice $L$ and a promise that $\lambda_2(L) > \gamma \lambda_1(L)$. The output is a shortest nonzero vector (Definition 1 in Lyubashevsky & Micciancio, 2009). The promise is a gap. Here $\lambda_2$ is the second successive minimum from Chapter 7, so the promise says that every lattice vector not a multiple of the shortest one is more than $\gamma$ times longer than it. The shortest vector’s own multiples do not count. The larger the gap, the easier the instance. The Kannan embedding from the previous section turns an LWE sample into a unique-SVP instance. The primal attack solves that instance by running BKZ at a block size large enough to bring the GSO of the shortest vector below the gap.

The primal attack’s success condition rests on two pieces: a function $\delta(\beta)$ that says how short BKZ output vectors are at a given block size, and a cost model that prices one SVP oracle call at block size $\beta$.

LLL. The Lenstra-Lenstra-Lovász algorithm from 1982 is the polynomial-time baseline (Lenstra et al., 1982). Given a basis $B$ of a lattice $L$ of rank $d$, LLL at the standard parameter $\delta = 3/4$ outputs a reduced basis whose first vector satisfies $\|b_1\| \leq 2^{(d - 1)/2} \cdot \lambda_1(L)$ (Lenstra et al., 1982). More generally the approximation factor is $\alpha^{(d-1)/2}$ with $\alpha = 1/(\delta - 1/4)$, exponential in $d$, which is the only point needed here. The running time is polynomial in $d$ and in the bit length of the input. LLL is strong enough to solve the toy problem from the previous section. It is weak enough to be useless against ML-KEM directly. The approximation factor grows exponentially in $d$. At $d \approx 1419$ the factor $2^{(d-1)/2}$ is roughly $2^{709}$. That is many orders of magnitude larger than the ML-KEM-768 unique-SVP gap that the primal attack has to see, so LLL has no chance.

BKZ. The Block Korkine-Zolotarev algorithm parameterizes lattice reduction by a block size $\beta$ (Schnorr & Euchner, 1994). For $\beta = 2$, BKZ collapses to LLL. For $\beta = d$, BKZ collapses to a single call of an exact SVP oracle on the whole lattice. For intermediate $\beta$, BKZ iterates an SVP oracle over rank-$\beta$ sub-bases until the full basis is reduced. The output quality is quantified by the root-Hermite factor $\delta(\beta)$, and the closed-form approximation

$$\delta(\beta) = \left( \frac{(\pi \beta)^{1/\beta} \cdot \beta}{2 \pi e} \right)^{\!1 / (2 (\beta - 1))}$$

is valid for $\beta \gtrsim 50$ and is the one the Kyber Round 3 submission uses, citing Chen’s 2013 thesis and the Albrecht-Player-Scott estimator for it (Albrecht et al., 2015; Avanzi et al., 2021; Chen, 2013). The practical refinements that make BKZ run at these block sizes, early abort and pruned enumeration among them, come from BKZ 2.0 (Chen & Nguyen, 2011). At $\beta = 100$, $\delta \approx 1.0093$. At $\beta = 500$, $\delta \approx 1.0034$. At small $\beta$ the asymptotic formula is not a useful root-Hermite factor, and the empirical value observed on LLL-reduced bases in dimensions of cryptographic interest is $\delta \approx 1.0219$ (Gama & Nguyen, 2008). BKZ’s first Gram-Schmidt (GSO) vector on a lattice of dimension $d$ and determinant $V$ has norm approximately $\delta(\beta)^{d - 1} \cdot V^{1/d}$, which is how the primal attack’s success condition will drop out.

Core-SVP cost. Inside the rank-$\beta$ SVP oracle that BKZ calls, the best known algorithm is a sieve (Becker et al., 2016). The classical sieving complexity is $2^{0.292 \beta + o(\beta)}$ operations. Applying the Laarhoven quantum speedup to the nearest-neighbor search at the heart of the sieve brings the classical exponent down to $2^{0.265 \beta + o(\beta)}$ for a quantum attacker (Laarhoven, 2015; Laarhoven et al., 2015). The core-SVP methodology was introduced by the NewHope team for their Round 1 NIST PQC submission (Alkim et al., 2016). It takes the cost of one SVP oracle call at the block size where the primal attack succeeds, and reports that cost as the attack’s bit-security. The methodology deliberately ignores the $o(\beta)$ sub-exponential factor and the number of SVP oracle calls that BKZ makes (a polynomial factor). The Kyber team’s own account of the omitted term is that the costs hidden in it were positive in the experiments that preceded the dimensions-for-free technique, and that this sub-exponential speedup makes it unclear whether the total $o(\beta)$ term is positive or negative, asymptotically and concretely (Avanzi et al., 2021, sec. 5.2). The omitted factors can move the estimate in either direction. The result is a conservative baseline for the attacker’s work, not a formal lower bound. Its unit is not a gate count either. The Kyber specification states the core-SVP figure as $2^{0.292 \beta}$ CPU cycles and keeps it in its own rows of Table 4 ($118$, $183$, and $256$ classical bits), separate from the refined estimate it reports as $\log_2$ gates ($151.5$, $215.1$, and $287.3$), which prices the sieve as an explicit circuit, adds the progressive-sieving overhead and the dimensions-for-free saving, and is the number the specification holds against AES (Table 4 in Avanzi et al., 2021, sec. 4.4, with the costing in §5.2 and §5.2.1). The NIST category floors in the next subsection are AES-derived gate-count reference costs (National Institute of Standards and Technology, 2016). Holding a core-SVP number against them is a comparison of proxy bits with gates, and the specification says the core-SVP estimates come out smaller than the AES gate counts for classical attacks (Avanzi et al., 2021, sec. 4.4). A quantitative comparison needs a circuit-cost model, and the refined row is what supplies one.

Every block size $\beta$ the rest of the chapter computes translates directly into $0.292 \beta$ bits of classical security and $0.265 \beta$ bits of quantum security via these two exponents.

Step-by-step cryptanalysis of ML-KEM

The primal embedding

The Kyber Round 3 submission states the primal attack’s success condition as equation 9 of Section 5.1.2 (Avanzi et al., 2021). Start with a Module-LWE instance with module rank $k$, polynomial degree $n$, modulus $q$, and secret-error coefficient standard deviation $\sigma$. The attacker chooses a number of samples $m \in [1, (k + 1) n]$, builds a lattice of dimension $d = m + kn + 1$ and volume $q^m$, and runs BKZ-$\beta$. The attack succeeds iff the projection of the planted short vector onto the last $\beta$ Gram-Schmidt vectors is shorter than the last Gram-Schmidt vector BKZ-$\beta$ produces. The planted vector’s projection onto a $\beta$-dimensional subspace has expected norm $\sigma \sqrt{\beta}$. The last Gram-Schmidt vector has length $\delta(\beta)^{2 \beta - d - 1} \cdot q^{m / d}$ under the geometric series assumption.

Combining the two gives equation 9:

$$\sigma \sqrt{\beta} \; \leq \; \delta(\beta)^{2 \beta - d - 1} \cdot q^{m / d}.$$

The attacker picks the smallest $\beta$ for which some $m$ satisfies the inequality. A larger $m$ gives more samples and a larger lattice dimension. A larger $d$ shifts the exponent $2 \beta - d - 1$ down, which is bad for the attacker. A larger $d$ also lets $q^{m/d}$ absorb more of the modulus, which is good for the attacker. The two effects trade, and there is a unique optimum the estimator searches for. The Kyber Round 3 submission reports its minimum $\beta$ at specific $m$ values ($m = 486, 650, 860$ for the three parameter sets). The estimator below picks slightly different $m$ for ML-KEM-768 and ML-KEM-1024, which is part of the reproduction-gap story in the estimator subsection below (Avanzi et al., 2021).

For ML-KEM the secret-error coefficient standard deviation is $\sigma = \sqrt{\eta_1 / 2}$, where $\eta_1$ is the centered binomial parameter of the key-generation noise (National Institute of Standards and Technology, 2024). At ML-KEM-768 we have $\eta_1 = 2$, so $\sigma = 1$.

import math


def delta_beta(beta):
    """Chen 2013 root-Hermite factor approximation."""
    numerator = ((math.pi * beta) ** (1.0 / beta)) * beta
    return (numerator / (2.0 * math.pi * math.e)) ** (1.0 / (2.0 * (beta - 1)))


def primal_succeeds(beta, d, q, m, sigma):
    """Kyber Round 3 submission equation 9."""
    log_lhs = math.log(sigma * math.sqrt(beta))
    log_rhs = (2 * beta - d - 1) * math.log(delta_beta(beta)) + (m / d) * math.log(q)
    return log_lhs <= log_rhs


# ML-KEM-768: k = 3, n = 256, q = 3329, eta_1 = 2, sigma = 1.
k, n, q, sigma = 3, 256, 3329, 1.0
# Try the attack at the published optimal number of samples m = 650 (d = 1419).
m = 650
d = m + k * n + 1
print(f"ML-KEM-768 lattice dimension d = {d}")
# ==> ML-KEM-768 lattice dimension d = 1419
print(f"primal succeeds at beta = 500 ? {primal_succeeds(500, d, q, m, sigma)}")
# ==> primal succeeds at beta = 500 ? False
print(f"primal succeeds at beta = 700 ? {primal_succeeds(700, d, q, m, sigma)}")
# ==> primal succeeds at beta = 700 ? True

The inequality fails at $\beta = 500$ and holds at $\beta = 700$. The actual threshold lies somewhere between those two block sizes. The next subsection finds it by linear search.

The dual distinguisher

The dual attack works in an extended dual lattice. Its plain-LWE form finds short vectors in the scaled dual of the LWE lattice and uses them to distinguish (Albrecht et al., 2015, sec. 5.3). Start with a Module-LWE sample $(A, \mathbf{b})$ with $A \in \mathbb{Z}_q^{m \times k n}$ and $\mathbf{b} = A \mathbf{s} + \mathbf{e} \bmod q$. The Kyber Round 3 submission uses the lattice of integer pairs $\Lambda' = \{(\mathbf{x}, \mathbf{y}) \in \mathbb{Z}^m \times \mathbb{Z}^{kn} : A^{\top} \mathbf{x} \equiv \mathbf{y} \bmod q\}$, which has dimension $d = m + kn$ and volume $q^{kn}$ (Avanzi et al., 2021, sec. 5.1.3). The attacker runs BKZ on $\Lambda'$ to find a short vector $\mathbf{w} = (\mathbf{x}, \mathbf{y})$ of length $\ell = \|\mathbf{w}\|$, then computes $\mathbf{x}^{\top} \mathbf{b} \bmod q$ on each fresh sample.

If $\mathbf{b}$ is uniformly random, $\mathbf{x}^{\top} \mathbf{b}$ is uniform on $\mathbb{Z}_q$. If $\mathbf{b}$ is an LWE sample, $\mathbf{x}^{\top} \mathbf{b} = \mathbf{y}^{\top} \mathbf{s} + \mathbf{x}^{\top} \mathbf{e} \bmod q$ because $A^{\top} \mathbf{x} \equiv \mathbf{y}$. Both $\mathbf{y}^{\top} \mathbf{s}$ and $\mathbf{x}^{\top} \mathbf{e}$ are small because $(\mathbf{x}, \mathbf{y})$ is a short lattice vector and $\mathbf{s}, \mathbf{e}$ have small coefficients. So $\mathbf{x}^{\top} \mathbf{b}$ is distributed approximately as a centered Gaussian of standard deviation $\ell \sigma$, where $\sigma$ is the secret-error coefficient standard deviation. The difference between that Gaussian and the uniform distribution on $\mathbb{Z}_q$ is what the distinguisher sees.

The Kyber Round 3 submission bounds the distinguishing advantage from above (Section 5.1.3): the LWE and uniform distributions of the inner product have maximal variation distance at most (Albrecht et al., 2015; Avanzi et al., 2021)

$$\varepsilon \;\leq\; 4 \exp\!\left( -2 \pi^2 \tau^2 \right), \qquad \tau = \frac{\|\mathbf{w}\| \sigma}{q}.$$

Here $\mathbf{x}$ and $\mathbf{b}$ are integer vectors. The inner product $\mathbf{x}^{\top} \mathbf{b}$ is taken over $\mathbb{Z}$ and then reduced modulo $q$. Shorter $\mathbf{w}$ means a larger bound, and the bound collapses superexponentially in $\tau^2$. BKZ at block size $\beta$ produces a vector of length $\ell \approx \delta(\beta)^{d - 1} \cdot q^{kn/d}$ on $\Lambda'$ ($d = m + kn$) under the GSA. This is the dual-lattice first-vector length estimate, a different success condition from the primal embedding, which instead compares the planted vector against the last Gram-Schmidt vectors. The dual attack’s cost is then the cost of running BKZ at the block size whose dual vector drives $\tau$ small enough to make the advantage usable. For core-SVP purposes, that $\beta$ comes out to roughly the same value as the primal attack for Kyber-scale parameters (Avanzi et al., 2021).

import math


def dual_advantage(w_norm, sigma, q):
    """Kyber Round 3 submission, Section 5.1.3 distinguishing bound."""
    tau = (w_norm * sigma) / q
    return 4.0 * math.exp(-2.0 * math.pi * math.pi * tau * tau)


# At ML-KEM-768 parameters (sigma = 1) the bound depends only on the
# ratio of the dual vector norm to the modulus q = 3329. The bound is
# meaningful only when below 1; a much shorter vector saturates it.
print(f"w norm 1000: advantage <= {dual_advantage(1000, 1.0, 3329):.4f}")
# ==> w norm 1000: advantage <= 0.6738
print(f"w norm 1500: advantage <= {dual_advantage(1500, 1.0, 3329):.6f}")
# ==> w norm 1500: advantage <= 0.072708
print(f"w norm q = 3329: advantage <= {dual_advantage(3329, 1.0, 3329):.3e}")
# ==> w norm q = 3329: advantage <= 1.070e-08

A dual vector at the modulus length drives the bound to roughly $10^{-8}$, which is negligible. When $\|\mathbf{w}\| \sigma$ is a small fraction of $q$ the raw expression exceeds $1$. The advantage is then capped at $1$ and the bound stops being a meaningful quantitative estimate. The useful regime for estimates is where the expression is below $1$ but not vanishingly small. Because the KEM hashes the agreed key, a small per-sample $\varepsilon$ is not directly exploitable. The attacker amplifies it by collecting many short dual vectors and combining their distinguishing signals (Albrecht et al., 2015; Avanzi et al., 2021). The Round 3 submission’s analysis places the dual $\beta$ within a few block sizes of the primal $\beta$ for every Kyber parameter set (Avanzi et al., 2021).

In the Kyber Round 3 refined gate-count analysis the dual attack is significantly more expensive than the primal attack against Kyber. The dual analysis assumes exponentially many equally short sieve vectors, which is incompatible with the dimensions-for-free technique the primal attack exploits (Avanzi et al., 2021). Later refined dual attacks changed the RAM-model picture, as the refinement pass below describes. The chapter uses the primal attack as the canonical one for the rest of the step-by-step.

A core-SVP estimator in Python

The success condition plus the core-SVP cost model plus a linear search over $\beta$ is the whole estimator. The implementation is a handful of lines on top of delta_beta and primal_succeeds from before. The core-SVP side needs no numpy at all. The following block searches for the smallest $\beta$ that works at some valid $m$, and prints the three-row ML-KEM table.

import math


def delta_beta(beta):
    numerator = ((math.pi * beta) ** (1.0 / beta)) * beta
    return (numerator / (2.0 * math.pi * math.e)) ** (1.0 / (2.0 * (beta - 1)))


def primal_succeeds(beta, d, q, m, sigma):
    log_lhs = math.log(sigma * math.sqrt(beta))
    log_rhs = (2 * beta - d - 1) * math.log(delta_beta(beta)) + (m / d) * math.log(q)
    return log_lhs <= log_rhs


def core_svp_beta(k, n, q, sigma):
    for beta in range(50, 1200):
        for m in range(1, (k + 1) * n + 1):
            d = m + k * n + 1
            if primal_succeeds(beta, d, q, m, sigma):
                return beta
    raise AssertionError("no beta in range")


parameter_sets = [
    ("ML-KEM-512",  2, 256, 3329, 3),
    ("ML-KEM-768",  3, 256, 3329, 2),
    ("ML-KEM-1024", 4, 256, 3329, 2),
]

print(f"{'name':<12} {'beta':>5} {'classical':>10} {'quantum':>8}")
# ==> name          beta  classical  quantum
for name, k, n, q, eta_1 in parameter_sets:
    sigma = math.sqrt(eta_1 / 2.0)
    beta = core_svp_beta(k, n, q, sigma)
    print(f"{name:<12} {beta:>5} {int(0.292 * beta):>10} {int(0.265 * beta):>8}")
# ==> ML-KEM-512     406        118      107
# ==> ML-KEM-768     624        182      165
# ==> ML-KEM-1024    874        255      231

Interactive demo

An interactive version of this estimator is at the core-SVP estimator demo. Pick an ML-KEM parameter set, slide the block size $\beta$, and scrub the sample count $m$. The primal-success inequality $\sigma\sqrt{\beta} \le \delta(\beta)^{2\beta-d-1}\cdot q^{m/d}$ evaluates in log space and, at the optimal sample count, the flag turns from red to green the moment $\beta$ reaches the threshold $\beta^{*}$ the estimator reports. At any other $m$ the inequality at that $m$ decides.

Compare against Table 4, page 21 of the CRYSTALS-Kyber Round 3 submission (Avanzi et al., 2021). For the primal attack under the core-SVP methodology, Table 4 reports block sizes $\beta = 406$, $626$, and $878$ at lattice attack dimensions $d = 999$, $1419$, and $1885$. The estimator’s free search returns $406$, $624$, and $874$, and the difference splits into exactly two causes.

Set	Published $\beta$	Published $(m, d)$	Estimator $\beta$	Estimator $(m, d)$	From $m$	From shape
ML-KEM-512	406	(486, 999)	406	(486, 999)	0	0
ML-KEM-768	626	(650, 1419)	624	(658, 1427)	1	1
ML-KEM-1024	878	(860, 1885)	874	(842, 1867)	0	4

The first cause is the estimator’s free search over the number of samples $m$. The Kyber team fixes $m$ per parameter set; the estimator does not. At ML-KEM-768 it finds $m = 658$, which buys one block size over the published $m = 650$ under the same success condition. At ML-KEM-1024 it picks a smaller $m$ than the published one and lands on the same $\beta$, so the free search buys nothing there.

The second cause is the basis shape, and it is not the $\delta(\beta)$ approximation it looks like. Running the chapter’s own success condition at the published $(m, d)$ pairs gives $\beta = 625$ for ML-KEM-768 and $874$ for ML-KEM-1024, leaving $1$ and $4$ block sizes unaccounted for. The Kyber team’s security script computes $\delta(\beta)$ from the same closed form this chapter does, so the residual is not an error in that formula (Avanzi et al., 2021). What differs is the basis the two models reduce. Equation 9 lays a single geometric-series line across the whole basis. The script instead builds the $q$-ary shape the embedding actually has, a flat block at $\log q$, the geometric-series slope only in the middle, and a flat block at $0$, then slides that shape until its volume matches. Run at the published $(m, d)$ pairs, the script returns $406$, $626$, and $878$, which is the entire residual.

The four-block gap at ML-KEM-1024 translates to $0.292 \times 4 \approx 1.2$ classical bits before flooring, which is inside the gap between the coarse core-SVP estimate and the refined Kyber estimates, walked in the “How the estimator oversimplifies” section below. A separate one-bit effect is the rounding of the sieve exponents. The chapter uses the headline $0.292$ and $0.265$ that the submission states for its first-pass core-SVP analysis. Flooring the unrounded $\log_2 \sqrt{3/2} \approx 0.29248$ and $\log_2 \sqrt{13/9} \approx 0.26526$ reproduces Table 4’s classical $183$ and quantum $166$ at ML-KEM-768, one bit above the chapter’s $182$ / $165$ (Avanzi et al., 2021; Becker et al., 2016; Laarhoven et al., 2015). That reproduction does not identify the submission’s own arithmetic. Rounding the headline products to nearest reaches the same pair, since $0.292 \times 626 = 182.79$ and $0.265 \times 626 = 165.89$, and the submission states the exponents without saying how the table’s integers were taken from them.

The ch13-lattice-cryptanalysis package under solutions/ factors the same logic into core_svp, primal, and dual modules, plus an estimator entry point that returns a frozen dataclass record per parameter set. The package’s primal_success swaps the argument order of the inline primal_succeeds and computes $d$ internally from $k$ and $n$. The two are numerically equivalent. The pytest suite at tests/ch13/ asserts the reproduction gap is at most five block sizes for every ML-KEM parameter set, which is the contract the package commits to.

From block size to NIST security category

FIPS 203 states that ML-KEM-512, ML-KEM-768, and ML-KEM-1024 are claimed to be in NIST security categories 1, 3, and 5 respectively (National Institute of Standards and Technology, 2024). The NIST Call for Proposals defines category 1 as the classical-and-quantum cost of key recovery against AES-128, category 3 as the AES-192 version, and category 5 as the AES-256 version (National Institute of Standards and Technology, 2016). Section 4.A.5 then prices those reference attacks directly, and the classical and quantum columns behave differently. The classical costs are fixed numbers: $2^{143}$ gates for AES-128, $2^{207}$ for AES-192, and $2^{272}$ for AES-256. The quantum costs are not, because the call restricts a quantum attack to a fixed circuit depth MAXDEPTH and quotes them as $2^{170} / \mathrm{MAXDEPTH}$, $2^{233} / \mathrm{MAXDEPTH}$, and $2^{298} / \mathrm{MAXDEPTH}$ gates. So it is the classical column that gives the floor: $143$, $207$, and $272$ bits (National Institute of Standards and Technology, 2016). A core-SVP bit count held against it is a proxy held against a gate count, as the core-SVP cost definition in “The four problems and the two tools” said. The comparison below is the Kyber team’s own: the coarse baseline is shown against the floor, and the refined gate count is the number that clears it.

The ML-KEM estimator numbers above sit below those floors on the core-SVP model: $118$ classical bits for ML-KEM-512, $182$ for ML-KEM-768, $255$ for ML-KEM-1024. The gap is intentional. The core-SVP model is a deliberately coarse baseline. The refined gate-count model the Kyber team used for the final parameter choice gives larger counts: $151.5$, $215.1$, and $287.3$ classical bits for the three sets (Avanzi et al., 2021). Those clear the NIST floors of $143$, $207$, and $272$ by $8$, $8$, and $15$ bits. That margin is not unconditional. The refined dual attacks of Guo-Johansson 2021 and the MATZOV group 2022 lowered the RAM-model estimates (Guo & Johansson, 2021; MATZOV, 2022). The NIST third-round status report concludes that all three Kyber parameter sets fall slightly below their category targets when memory-access cost is not charged. They are expected to meet the targets in realistic cost models that charge for large-memory access (Alagic et al., 2022).

import math


def core_svp_classical(beta):
    return int(0.292 * beta)


def core_svp_quantum(beta):
    return int(0.265 * beta)


rows = [
    ("ML-KEM-512",  406, 1),
    ("ML-KEM-768",  624, 3),
    ("ML-KEM-1024", 874, 5),
]
nist_floor_classical = {1: 143, 3: 207, 5: 272}

print(f"{'name':<12} {'beta':>5} {'classical':>10} {'NIST cat':>9} {'floor':>6}")
# ==> name          beta  classical  NIST cat  floor
for name, beta, cat in rows:
    classical = core_svp_classical(beta)
    floor = nist_floor_classical[cat]
    print(f"{name:<12} {beta:>5} {classical:>10} {cat:>9} {floor:>6}")
# ==> ML-KEM-512     406        118         1    143
# ==> ML-KEM-768     624        182         3    207
# ==> ML-KEM-1024    874        255         5    272

The classical core-SVP cost is below the NIST floor for every category. The gap is the distance between a deliberately coarse core-SVP estimate and the refined Kyber estimates, not a single calibrated margin. The “How the estimator oversimplifies” section below describes those refinements and the conditions under which the FIPS 203 parameters clear the NIST category floors.

Figure 13.1. The right panel plots core-SVP cost (classical 0.292 beta, quantum 0.265 beta) against block size beta. Horizontal dashed lines mark NIST category floors at 143, 207, and 272 classical bits. ML-KEM-512 sits at beta 406, ML-KEM-768 at beta 626, and ML-KEM-1024 at beta 878. The Table 4 classical core-SVP costs are 118, 183, and 256 bits. The chapter's estimator reproduces these block sizes at beta 406, 624, and 874 (classical 118, 182, 255 under the rounded 0.292 constant). The floors are gate counts and the curves are core-SVP proxy bits, so the distance between a dot and a line is not a margin in either unit. The refined gate counts of 151.5, 215.1, and 287.3 are what clear the floors. The operator decision is which parameter set meets which NIST category, and at what block-size beta a lattice-reduction adversary must run to break it.

The same estimator against ML-DSA

Part II builds two flagship schemes, and everything above prices one of them. ML-DSA (Chapter 12) rests on Module-LWE too, so the estimator already written applies to it without a new success condition (National Institute of Standards and Technology, 2024b). Two things about the instance differ, and both change the arithmetic rather than the model.

The module is not square. ML-KEM’s public key is $\mathbf{A} \in R_q^{k \times k}$, so unknowns and samples both scale with $k$. ML-DSA publishes $\mathbf{t} = \mathbf{A}\mathbf{s}_1 + \mathbf{s}_2$ with $\mathbf{A} \in R_q^{k \times \ell}$ and $k \neq \ell$ at two of the three parameter sets. The unknowns are $\mathbf{s}_1$, which is $\ell$ ring elements, and the samples are the $k$ rows of $\mathbf{t}$, so the embedding dimension is $m + \ell n + 1$ with $m$ capped at $kn$ rather than $(k+1)n$.

The secret is uniform rather than centered binomial. FIPS 204 draws every coefficient of $\mathbf{s}_1$ and $\mathbf{s}_2$ uniformly from $[-\eta, \eta]$ (National Institute of Standards and Technology, 2024b). A uniform coefficient on that range has variance $\eta(\eta+1)/3$, so $\sigma = \sqrt{\eta(\eta+1)/3}$ replaces ML-KEM’s $\sqrt{\eta_1 / 2}$. At ML-DSA-65, $\eta = 4$ gives $\sigma \approx 2.58$, well above any ML-KEM value. Neither that nor the much larger modulus $q = 8380417$ is a hardness comparison on its own. In the success condition above, $q$ enters the right-hand side as $q^{m/d}$, so raising it at fixed dimensions and noise makes the condition easier to satisfy rather than harder. Modulus, module dimensions and noise distribution decide the estimated cost together, and the block sizes below are what the estimator returns for the standardized parameter set.

import math


def delta_beta(beta):
    numerator = ((math.pi * beta) ** (1.0 / beta)) * beta
    return (numerator / (2.0 * math.pi * math.e)) ** (1.0 / (2.0 * (beta - 1)))


def primal_succeeds(beta, d, q, m, sigma):
    log_lhs = math.log(sigma * math.sqrt(beta))
    log_rhs = (2 * beta - d - 1) * math.log(delta_beta(beta)) + (m / d) * math.log(q)
    return log_lhs <= log_rhs


def mldsa_beta(k, ell, n, q, eta):
    # The unknowns are s_1, which is ell ring elements. The samples are
    # the k rows of t = A s_1 + s_2. A coefficient uniform on
    # [-eta, eta] has variance eta (eta + 1) / 3.
    sigma = math.sqrt(eta * (eta + 1) / 3.0)
    for beta in range(50, 1200):
        for m in range(1, k * n + 1):
            if primal_succeeds(beta, m + ell * n + 1, q, m, sigma):
                return beta
    raise AssertionError("no beta in range")


# ML-DSA parameter sets from FIPS 204 Table 1; q = 2**23 - 2**13 + 1.
q_dsa = 8380417
parameter_sets = [
    ("ML-DSA-44", 4, 4, 2, 2),
    ("ML-DSA-65", 6, 5, 4, 3),
    ("ML-DSA-87", 8, 7, 2, 5),
]

print(f"{'name':<11} {'beta':>5} {'classical':>10} {'quantum':>8} {'cat':>4}")
# ==> name         beta  classical  quantum  cat
for name, k, ell, eta, cat in parameter_sets:
    beta = mldsa_beta(k, ell, 256, q_dsa, eta)
    print(f"{name:<11} {beta:>5} {int(0.292 * beta):>10} {int(0.265 * beta):>8} {cat:>4}")
# ==> ML-DSA-44     424        123      112    2
# ==> ML-DSA-65     624        182      165    3
# ==> ML-DSA-87     863        251      228    5

The Dilithium Round 3 submission’s security table reports its Module-LWE block sizes on a row labelled “BKZ block-size $b$ (GSA)”: $423$, $624$, and $863$, with classical core-SVP costs $123$, $182$, and $252$ (Bai et al., 2021). The estimator lands within one block size on all three, and exactly on two of them. That is a tighter reproduction than the ML-KEM side managed, and the label is the reason. The Dilithium team publishes the pure geometric-series row, which is the model equation 9 states; the Kyber team publishes the row its security script produces, which is the basis-shape model of the “A core-SVP estimator in Python” section above. Comparing like with like removes the residual.

ML-DSA-65 lands at $\beta = 624$, the same block size as ML-KEM-768. Two schemes with different rings, different moduli, different secret distributions and different jobs are calibrated to the same lattice-reduction effort, because both are aiming at NIST category 3. The estimator is the thing that makes that visible.

The category floors do not carry across unchanged, though. ML-DSA-44 claims category 2, and categories 2 and 4 are hash-collision reference problems rather than AES key search: the Call for Proposals prices SHA3-256 collisions at $2^{146}$ classical gates, not $2^{143}$ (National Institute of Standards and Technology, 2016). The pattern from the ML-KEM table repeats regardless. Core-SVP puts all three sets below their floors, at $123$, $182$, and $251$ against $146$, $207$, and $272$, and the Dilithium team’s refined gate counts of $159$, $217$, and $285$ are what clear them (Bai et al., 2021).

What this section does not price

ML-DSA rests on two assumptions, and this is one of them. Key recovery is Module-LWE, which is what the estimator above attacks. Forgery rests on Module-SIS, in the SelfTargetMSIS variant FIPS 204 names, and that needs a different success condition: not a unique short vector planted in a Kannan embedding, but any lattice vector below a given norm bound. The Dilithium submission’s own Module-SIS core-SVP row reads $423$, $638$, and $909$ against the Module-LWE row’s $423$, $624$, and $863$ (Bai et al., 2021). So Module-LWE is the binding constraint at every ML-DSA parameter set, or tied at ML-DSA-44, and the numbers above are the ones that set the parameters. That is why the omission is survivable, not why it is unimportant.

How the estimator oversimplifies

Core-SVP is a deliberately coarse baseline. Three refinements push the estimate upward, and two push it downward. The balance matters for the FIPS 203 parameter choice (National Institute of Standards and Technology, 2024a).

Dimensions for free. Ducas 2018 observed that the last few Gram-Schmidt vectors of a BKZ-reduced basis are good enough for a shortcut (Ducas, 2018). The SVP oracle at the head of the block can be replaced with a smaller-dimensional SVP oracle, with a Babai nearest-plane lift completing the rest of the shortest-vector recovery (Babai, 1986). The saving is roughly $f(\beta) = \beta \cdot \ln(4/3) / \ln(\beta / (2 \pi e))$ dimensions at block size $\beta$ (Ducas, 2018). At ML-KEM-768 ($\beta \approx 624$) this saves about $50$ dimensions, which drops the classical sieving exponent from $0.292 \beta$ to roughly $0.292 (\beta - 50) \approx 168$ bits (Avanzi et al., 2021). The refinement moves in the attacker’s favor.

Progressive BKZ. Actual BKZ implementations run over increasing block sizes rather than one fixed $\beta$. The Kyber Round 3 refined estimate models the cumulative cost as $C \cdot (n - b)$ times the cost of the final sieve in dimension $b$ (Avanzi et al., 2021). Here $C = 1 / (1 - 2^{-0.292}) \approx 5.46$ and $n$ is the full lattice dimension. For Kyber512 ($n = 1025$, $b = 413$) that overhead is roughly $3340$ times the final SVP cost. The refinement moves in the defender’s favor and is of the same order as the dimensions-for-free saving in that worked estimate, not negligible against it.

Refined dual attacks. Guo and Johansson 2021 (Guo & Johansson, 2021) and the MATZOV group 2022 (MATZOV, 2022) published refined dual attacks that cut the cost of the dual distinguisher against Kyber by exploiting modulus-switching and the specific structure of centered binomial noise. The refinements prompted a NIST re-review in 2022. The NIST third-round status report concluded that the improvements lower the RAM-model estimates enough that all three Kyber sets fall slightly below their targeted categories when memory-access cost is ignored. They are still expected to meet those categories in realistic cost models that charge for large-memory access (Alagic et al., 2022). The refinement moves in the attacker’s favor.

The 2022 conclusion was disputed, then re-established

Ducas and Pulles showed that the independence heuristic both refinements rest on contradicts established results in the regimes where it can be checked (Ducas & Pulles, 2023). NIST’s December 2023 Kyber-512 FAQ records the position that followed: the MATZOV result had been called into question, and no rescue of it had been demonstrated (National Institute of Standards and Technology, 2023). Carrier, Meyer-Hilfiger, Shen, and Tillich later supplied one. Their coded dual attack replaces modulus switching with a decoder built from polar codes generalized over $\mathbb{Z}_q$, drops the disputed independence assumptions, and is backed by experiment. It prices Kyber-512, Kyber-768, and Kyber-1024 at $139.5$, $195.1$, and $259.7$ classical bits against floors of $143$, $207$, and $272$ (Carrier et al., 2025). Those figures sit in the same nearest-neighbor circuit model as the Kyber submission and MATZOV, with memory access uncharged and a coarser gate-level accounting. The result confirms MATZOV’s ballpark rather than beating it: at Kyber-512 its $139.5$ is marginally above MATZOV’s claimed $139.2$. What changed is the footing, not the number.

Rounding noise (Module-LWER). The actual noise distribution inside ML-KEM is not pure Module-LWE. Ciphertext compression introduces an additional rounding error that Chapter 11 walked into at the noise-budget level (National Institute of Standards and Technology, 2024a). For analysis purposes the Kyber team defines Module-LWER, the rounding-error variant, and the six core-SVP bits at stake run in the direction a reader would not guess. Bounding Module-LWER by Module-LWE at the smaller ciphertext noise parameter $\eta_2$ would put ML-KEM-512 at $112$ classical core-SVP bits rather than $118$, dropping the refined gate count from $151.5$ to roughly $145$. The Kyber team rejects that bound because it discards the compression error, whose per-coefficient variance carries the total above the key-generation noise’s $\eta_1 / 2 = 3/2$. They therefore treat ML-KEM-512 as at least as hard as Module-LWE at $\eta_1$, which is what the published numbers assume (Avanzi et al., 2021). The refinement moves in the defender’s favor, and the six bits are what ignoring it costs rather than what counting it adds.

Memory costs. Core-SVP assumes the attacker has enough RAM to hold $2^{0.208 \beta}$ lattice vectors in memory. At ML-KEM-768 that is roughly $2^{130}$ vectors, which is beyond any physically realizable storage. The RAM model is a generous assumption. What a real sieve pays instead depends on the physical model and on the algorithm. Jaques puts processors, memory, and wire in constant proportion, charges the routing between them, and modifies the sieve to amortize that routing. Asymptotically the area-time cost is $2^{0.3113 d + o(d)}$ for a computer laid out in two spatial dimensions and returns to the RAM-model $2^{0.2925 d + o(d)}$ in three or more, which is the paper’s title (Jaques, 2024). The concrete pricing takes the two-dimensional case with a fixed memory-access constant, changes only the sieving step inside the primal attack’s core-SVP subroutine, and leaves every other aspect of the attack as the Kyber submission had it. Under those assumptions the published Table 1 puts the primal attack against the three ML-KEM parameter sets at $154.5$, $223.6$, and $310.2$ bits, which is $10.1$, $15.9$, and $30.6$ above the RAM-model estimator that already carries the MATZOV refinement, and $3.0$, $8.5$, and $22.9$ above the submission’s own gate counts, because MATZOV’s saving and the memory charge nearly cancel at ML-KEM-512 (Jaques, 2024). The ePrint revision of April 2024 carried $158.7$ and $229.9$ for the first two sets, and the journal version revised them. The author reads the result as an upper bound on the overhead of memory in sieving rather than a settled cost, and it is a costing of one primal attack under one memory model, not of the coded dual attack or of any other. The ML-KEM-512 figure sits inside the $2^{140}$ to $2^{180}$ range NIST gives around its own estimate of about $2^{160}$ (National Institute of Standards and Technology, 2023). Zhao, Ding, and Yang make the algorithmic half of the point: a BGJ sieve organized around streaming memory access, with buckets that shrink by orders of magnitude at each filtering layer, needs only $2^{0.2075 n + o(n)}$ non-random main-memory accesses, so which sieve is run, and how it touches memory, is part of any memory-cost claim (Zhao et al., 2025). The refinement moves in the defender’s favor.

The net balance. The FIPS 203 final parameters land the three ML-KEM variants at refined gate-count estimates of $151.5$, $215.1$, and $287.3$ classical bits, above the NIST category floors of $143$, $207$, and $272$ (Avanzi et al., 2021). The post-2021 refined dual attacks pulled the RAM-model estimates down far enough that the NIST third-round report places all three sets slightly below their targets when memory access is treated as free (Alagic et al., 2022; Guo & Johansson, 2021; MATZOV, 2022). The peer-reviewed 2025 coded dual attack reaches the same place without the disputed independence assumptions, at $139.5$, $195.1$, and $259.7$ bits (Carrier et al., 2025). They are still expected to meet the targets in realistic cost models that charge for large-memory access (Alagic et al., 2022). The one concrete pricing of that kind is Jaques’s, and it prices the primal attack under its own memory model at $154.5$, $223.6$, and $310.2$ bits (Jaques, 2024). It does not reprice the coded dual attack or the ring-aware dual attack, so the expectation that memory costs restore the margin is an inference from one attack’s repricing, and raising the cost of one attack bounds nothing about the cheapest. Core-SVP’s $182$ bits for ML-KEM-768 is the coarse-baseline figure; $215.1$ is the gate-count estimate; the realistic-memory caveat is why the margin is expected to hold rather than proven.

A concrete chosen-ciphertext attack on K-PKE. Chapter 11 promised one concrete decryption-oracle attack that the Fujisaki-Okamoto wrapper closes. Consider a small-secret variant of the Chapter 10 flat Regev PKE at Kyber-like toy parameters. Chapter 10 draws $\mathbf{s}$ uniformly from $\mathbb{Z}_q^n$. Here it is drawn from $\{-1, 0, 1\}^n$ instead, the toy analogue of ML-KEM’s centered-binomial secret and the same change the primal-attack instance at the top of this chapter made. The error is $\mathbf{e} \in \{-1, 0, 1\}^m$ and the noise budget inequality is $2 m B < \lfloor q / 2 \rfloor$ at $B = 1$. The encryption of a message bit $\mu$ produces a ciphertext $(\mathbf{c}_1, c_2) = (A^{\top} \mathbf{r}, \mathbf{b}^{\top} \mathbf{r} + \lfloor q / 2 \rfloor \mu)$ under fresh randomness $\mathbf{r} \in \{0, 1\}^m$. Decryption computes $c_2 - \mathbf{c}_1^{\top} \mathbf{s}$ and rounds to the nearer of $0$ or $\lfloor q / 2 \rfloor$.

Fluhrer 2016 observed that a decryption oracle lets an attacker read secret coordinates one at a time via carefully chosen boundary queries (Fluhrer, 2016). Pick an index $j \in \{1, \ldots, n\}$ and a small positive scalar $\tau \in \mathbb{Z}_q$. Set $\mathbf{c}_1 = \tau \cdot \mathbf{u}_j$ where $\mathbf{u}_j \in \mathbb{Z}_q^n$ is the $j$-th standard basis vector, and set $c_2 = \lfloor q / 4 \rfloor$. The decryption value is

$$v = c_2 - \mathbf{c}_1^{\top} \mathbf{s} = \lfloor q / 4 \rfloor - \tau s_j \bmod q.$$

The decoder rounds $v$ to bit $0$ when $v \in [-\lfloor q/4 \rfloor, \lfloor q/4 \rfloor]$ and bit $1$ otherwise. At $q = 3329$ the FIPS 203 Compress_1 rule gives dec(832) = 0 and dec(833) = 1, so $832$ is the last bit-$0$ value and $833$ the first bit-$1$ value (National Institute of Standards and Technology, 2024a). Chapter 10’s decrypt formula ((2 * v + half_q) // q) % 2 produces the same midpoint-to-bit-0 tie-break used here, matching Ch 11’s K-PKE.Decrypt toy block. At $s_j = -1$, $v = \lfloor q/4 \rfloor + \tau$, which crosses into the bit-$1$ branch. At $s_j = 0$, $v = \lfloor q/4 \rfloor$, which lies on the inclusive boundary and decodes to bit-$0$. At $s_j = +1$, $v = \lfloor q/4 \rfloor - \tau$, which stays inside the bit-$0$ region. A single query with $\mathbf{c}_1 = \tau \mathbf{u}_j$ therefore distinguishes $s_j = -1$ (bit-$1$) from $s_j \in \{0, +1\}$ (bit-$0$), but it cannot tell $0$ and $+1$ apart (Fluhrer, 2016). A second query with $\mathbf{c}_1 = -\tau \mathbf{u}_j$ (same $c_2$) flips the sign in the $\tau s_j$ term and now distinguishes $s_j = +1$ from $s_j \in \{0, -1\}$. The pair of responses uniquely determines $s_j \in \{-1, 0, +1\}$ in two queries per coordinate.

The attack recovers one ternary coordinate per pair of oracle calls, so the full secret of this small-secret toy (entries in $\{-1, 0, 1\}$) comes out in $2 n$ calls. ML-KEM’s K-PKE does not have a ternary secret: its key-generation secret is sampled from a centered binomial $\mathrm{CBD}_{\eta_1}$ with support $[-\eta_1, \eta_1]$ ($\eta_1 = 2$ or $3$), so each coordinate needs more than two threshold queries to pin down. FIPS 203 specifies K-PKE only as an internal component that must not be exposed as a standalone decryption oracle (National Institute of Standards and Technology, 2024a). The attacker never runs BKZ. The decryption-oracle game is easier than the primal attack by orders of magnitude whenever raw K-PKE decryption is reachable, which is exactly what the wrapper below prevents.

The Fujisaki-Okamoto wrapper from Chapter 11 closes the oracle. Every tampered ciphertext $c \neq c'$ returns the pseudorandom rejection value $J(z \mathbin\Vert c)$ (Hofheinz et al., 2017; National Institute of Standards and Technology, 2024a). That value depends on the per-key rejection seed $z$ and the ciphertext bytes $c$ but has no algebraic dependence on $\mathbf{s}$. An attacker who submits the Fluhrer-style chosen-ciphertext query gets back a random function of $c$ and learns nothing about any coordinate of $\mathbf{s}$. The Hofheinz-Hovelmanns-Kiltz theorem formalizes the argument. Starting from an OW-CPA, $\delta$-correct K-PKE, derandomizing it with $G$ so that the result is rigid (a decrypted ciphertext re-encrypts to itself or is rejected), the FO transform produces an IND-CCA2 KEM with a concrete security bound in the random oracle model (Hofheinz et al., 2017). The QROM bound is looser and is established by follow-up work outside the scope of this chapter. The wrapper is the reason the decoder-boundary attacks above do not touch ML-KEM.

Tradeoffs inside Part II

Where does Module-LWE at rank $k$ over $\mathbb{Z}_{3329}[x]/(x^{256}+1)$ sit in the lattice family?

• Module-LWE and the subfield attack family (Albrecht, Bai, and Ducas 2016). The subfield attack reduces an overstretched NTRU instance to a lower-dimensional problem in a subfield of a power-of-two cyclotomic (Albrecht et al., 2016). It is an attack on overstretched NTRU, not on ML-KEM’s Module-LWE instance. The Ducas-van Woerden 2021 ternary-NTRU fatigue point $q \approx 0.004 \, n^{2.484}$ is a statement about the NTRU key distribution, not ML-KEM’s Module-LWE public key, so its numeric threshold should not be carried across (Ducas & van Woerden, 2021). At $n = 256$ that point is near $q \approx 3800$, close to ML-KEM’s $q = 3329$, which is exactly why the cross-comparison is brittle. The narrower safe takeaway: the known overstretched-NTRU subfield and fatigue attacks are not direct attacks on ML-KEM’s Module-LWE instance over $\mathbb{Z}_{3329}[x]/(x^{256}+1)$. The Langlois-Stehlé 2015 worst-case to average-case reduction is the foundation of the Module-LWE family the chapter inherits from Chapter 9, under its own hypotheses: an elliptical Gaussian error family in the canonical embedding and, for the direct search-to-decision route, a prime modulus that splits completely in the ring. Its Theorem 4.8 reaches other moduli by modulus switching at enlarged Gaussian noise. ML-KEM’s centered-binomial noise is not that family on either route, so the reduction certifies the problem family and not this instance (Langlois & Stehlé, 2015, sec. 4.1). The power-of-two cyclotomic and the Module-LWE public-key distribution are what keep the specific subfield attack family out.

• Module-LWE and flat-LWE Regev from Chapter 10. A direct Regev-style unstructured-LWE construction at a security level matching Kyber pushes the public key into the megabyte range, because the flat public key carries an $m \times n$ matrix over $\mathbb{Z}_q$. The secret key is the $n$-entry vector $\mathbf{s}$ and is a kilobyte or two. A more key-exchange-amenable unstructured-LWE design brings the public key and ciphertext down to roughly $11$ KB each, still about ten times larger and slower than Kyber-scale Module-LWE (Avanzi et al., 2021). ML-KEM’s ring structure cuts the public key to $1184$ bytes by amortizing $256$ coefficients into each matrix entry. The primal attack is analyzed the same way in every case: flatten the instance and run the primal embedding against the resulting lattice. What changes is the number of bytes the defender ships over the wire, plus a small correction the flattening misses. Hou, Jiang, and Ogilvie show that negacyclic rotations in $\mathbb{Z}_{3329}[x]/(x^{256}+1)$ let a hybrid attacker reuse one expensive preprocessing across many rotated secrets, which the published paper’s Table 9 prices in its “MLWE vs. LWE contribution” column at $0.0$ to $0.5$ bits for ML-KEM-512, $0.3$ to $0.9$ for ML-KEM-768, and $0.5$ to $1.3$ for ML-KEM-1024, the three values per set being its core-SVP, classical-circuit, and classical-query cost models, around one bit in the paper’s own summary (Hou et al., 2026). The table’s total gap over the prior estimator is larger, $0.1$ to $2.8$ bits, because it also includes a corrected search over the number of guesses, and that part is not a ring effect. Hou and Jiang’s half of the merged paper, the enhanced hybrid decoding attack, gains nothing over the primal attack at ML-KEM’s non-sparse secrets, where the plain uSVP estimate still dominates. The large effect is on the sparse secrets used in homomorphic encryption, up to 14.2 bits below the corresponding flat-LWE estimate.

• Module-LWE and Ring-LWE at $k = 1$ from Chapter 9. Ring-LWE at rank one gives a smaller public key at the same security level than Module-LWE at rank $k \geq 2$, but pays for it with a harder parameter-scaling story. Scaling security in Ring-LWE means changing $n$, which changes the ring, the NTT, and the structural attack surface. Scaling security in Module-LWE means changing $k$, which keeps the ring fixed and just adds matrix rows. The three ML-KEM parameter sets use the same ring $\mathbb{Z}_{3329}[x]/(x^{256}+1)$ and the same NTT. They differ in module rank $k$, the key-generation noise parameter $\eta_1$ ($3$ at ML-KEM-512, $2$ at ML-KEM-768 and ML-KEM-1024), and, for ML-KEM-1024, the ciphertext compression parameters $(d_u, d_v) = (11, 5)$ versus $(10, 4)$ (National Institute of Standards and Technology, 2024a).

Where Part II ends and Part III picks up

Part II has now built two schemes from scratch and priced the assumption underneath both. ML-KEM (Chapter 11) and ML-DSA (Chapter 12) share a ring family and a single hardness assumption for key recovery, and this chapter has shown what that assumption costs an attacker: a BKZ run at $\beta = 624$ for either of the category-3 sets, which the core-SVP model prices at $2^{182}$ classical operations. ML-DSA’s forgery side rests on Module-SIS, and the note above puts its published core-SVP row at or above the Module-LWE one at every parameter set. Everything in the Part rests on that lattice reduction improving slowly.

That is also the Part’s weakness, and it is why the book does not stop here. A single family means a single failure. Parts III and IV build the alternatives from different mathematics. Part III uses hash-based signatures, where security rests on the preimage resistance of a hash function and a few related properties rather than on any algebraic structure. Part IV uses code-based encryption and isogenies, where the hard problems are syndrome decoding and finding paths in isogeny graphs. Neither family is touched by the lattice reduction this chapter has spent its length on.

The three Parts after those change the question. Part V is migration and deployment, where the constraint stops being hardness and becomes inventory, protocol negotiation, and the size of the certificates a handshake has to carry. Part VI is post-quantum zero-knowledge, which is where the lattice assumptions of this Part reappear in a different role. Part VII applies all of it to blockchains, where key exposure is public by construction and no single authority can compel every participant to migrate, which is why Chapter 41 makes distributed coordination its own subject.

Chapter 14 starts the hash-based track from one-time signatures, which need no algebraic structure at all.

Exercises

1. Core-SVP bit costs across a block-size sweep. Compute $0.292 \beta$ and $0.265 \beta$ for $\beta \in \{100, 200, 400, 600, 800, 1000\}$ and tabulate the resulting classical and quantum bit counts. Verify the monotonicity the Kyber Round 3 submission relies on, and locate the ML-KEM-768 Table 4 block size $\beta = 626$ between two rows of your table (Avanzi et al., 2021).

2. Where the estimator starts saying something. Hold $q = 3329$ and $\sigma = 1$ fixed and sweep the number of unknowns $n$ over $\{50, 100, 200, 300, 400, 512, 640, 768\}$, allowing up to $2n$ samples. For each $n$, find the smallest $\beta$ satisfying primal_succeeds above, searching from $\beta = 50$ upward as core_svp_beta does. Tabulate $\beta$ against $n$ and confirm the last row reproduces ML-KEM-768’s $\beta = 624$. Two rows come out equal. Explain what that tells you about the estimator rather than about those two instances, and say why searching below $\beta = 50$ would not fix it.

3. Subfield-attack sketch at an overstretched cyclotomic. The Albrecht-Bai-Ducas attack on overstretched NTRU works at a power-of-two cyclotomic of degree $512$ with $q = 2^{40}$ (Albrecht et al., 2016). Explain in one paragraph why this attack should not be read as a direct attack on ML-KEM’s Module-LWE instance, discussing both the much smaller ML-KEM modulus and, more importantly, the different public-key distribution. Then say what the Langlois-Stehlé 2015 reduction does and does not certify about that instance (Langlois & Stehlé, 2015).

4. Decoder-boundary oracle on flat Regev. Implement the Fluhrer-2016 chosen-ciphertext attack walked above (Fluhrer, 2016). Target the Chapter 10 flat Regev PKE at $(n, q, m) = (4, 97, 8)$ with its key generation changed to draw the secret from $\{-1, 0, 1\}^n$, as in the walkthrough. Construct two queries per secret coordinate: one with $\mathbf{c}_1 = \tau \mathbf{u}_j$ and one with $\mathbf{c}_1 = -\tau \mathbf{u}_j$, both at $c_2 = \lfloor q/4 \rfloor$ and small positive $\tau$. Verify that the pair of decoder responses uniquely identifies $s_j \in \{-1, 0, +1\}$, and count $2 n$ total oracle calls to recover the full secret.

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

References

Alagic, G., Apon, D., Cooper, D., Dang, Q., Dang, T., Kelsey, J., Lichtinger, J., Miller, C., Moody, D., Peralta, R., Perlner, R., Robinson, A., Smith-Tone, D., & Liu, Y.-K. (2022). Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process (Internal Report NIST IR 8413 (updated 2022-09-26)). National Institute of Standards and Technology. https://doi.org/10.6028/NIST.IR.8413-upd1

Albrecht, M. R., Bai, S., & Ducas, L. (2016). A subfield lattice attack on overstretched NTRU assumptions: Cryptanalysis of some FHE and graded encoding schemes. Advances in Cryptology – CRYPTO 2016, 9814, 153–178. https://doi.org/10.1007/978-3-662-53018-4_6

Albrecht, M. R., Player, R., & Scott, S. (2015). On the concrete hardness of Learning with Errors. Journal of Mathematical Cryptology, 9(3), 169–203. https://doi.org/10.1515/jmc-2015-0016

Alkim, E., Ducas, L., Pöppelmann, T., & Schwabe, P. (2016). Post-quantum key exchange – a new hope. Proceedings of the 25th USENIX Security Symposium, 327–343. https://www.usenix.org/conference/usenixsecurity16/technical-sessions/presentation/alkim

Avanzi, R., Bos, J., Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schanck, J. M., Schwabe, P., Seiler, G., & Stehlé, D. (2021). CRYSTALS-Kyber Algorithm Specifications and Supporting Documentation (Version 3.02). NIST Post-Quantum Cryptography Project, Round 3 submission package. https://pq-crystals.org/kyber/data/kyber-specification-round3-20210804.pdf

Babai, L. (1986). On Lovász’ lattice reduction and the nearest lattice point problem. Combinatorica, 6(1), 1–13. https://doi.org/10.1007/BF02579403

Bai, S., Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schwabe, P., Seiler, G., & Stehlé, D. (2021). CRYSTALS-Dilithium Algorithm Specifications and Supporting Documentation (Version 3.1). NIST Post-Quantum Cryptography Project, Round 3 submission package. https://pq-crystals.org/dilithium/data/dilithium-specification-round3-20210208.pdf

Becker, A., Ducas, L., Gama, N., & Laarhoven, T. (2016). New directions in nearest neighbor searching with applications to lattice sieving. Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 10–24. https://doi.org/10.1137/1.9781611974331.ch2

Carrier, K., Meyer-Hilfiger, V., Shen, Y., & Tillich, J.-P. (2025). Assessing the Impact of a Variant of MATZOV’s Dual Attack on Kyber. Advances in Cryptology – CRYPTO 2025. https://doi.org/10.1007/978-3-032-01855-7_15

Chen, Y. (2013). Lattice reduction and concrete security of fully homomorphic encryption [Phdthesis, Université Paris Diderot]. https://theses.fr/2013PA077242

Chen, Y., & Nguyen, P. Q. (2011). BKZ 2.0: better lattice security estimates. In D. H. Lee & X. Wang (Eds.), Advances in Cryptology – ASIACRYPT 2011 (Vol. 7073, pp. 1–20). Springer. https://doi.org/10.1007/978-3-642-25385-0_1

Ducas, L. (2018). Shortest vector from lattice sieving: a few dimensions for free. In J. B. Nielsen & V. Rijmen (Eds.), Advances in Cryptology – EUROCRYPT 2018 (Vol. 10820, pp. 125–145). Springer. https://doi.org/10.1007/978-3-319-78381-9_5

Ducas, L., & Pulles, L. N. (2023). Does the Dual-Sieve Attack on Learning with Errors Even Work? Advances in Cryptology – CRYPTO 2023, 14083, 37–69. https://doi.org/10.1007/978-3-031-38548-3_2

Ducas, L., & van Woerden, W. (2021). NTRU Fatigue: How Stretched is Overstretched? Advances in Cryptology – ASIACRYPT 2021; IACR ePrint 2021/999. https://eprint.iacr.org/2021/999

Fluhrer, S. (2016). Cryptanalysis of ring-LWE based key exchange with key share reuse. IACR Cryptology ePrint Archive, Report 2016/085. https://eprint.iacr.org/2016/085

Gama, N., & Nguyen, P. Q. (2008). Predicting lattice reduction. In N. P. Smart (Ed.), Advances in Cryptology – EUROCRYPT 2008 (Vol. 4965, pp. 31–51). Springer. https://doi.org/10.1007/978-3-540-78967-3_3

Guo, Q., & Johansson, T. (2021). Faster dual lattice attacks for solving LWE with applications to CRYSTALS. In M. Tibouchi & H. Wang (Eds.), Advances in Cryptology – ASIACRYPT 2021 (Vol. 13093, pp. 33–62). Springer. https://doi.org/10.1007/978-3-030-92068-5_2

Hofheinz, D., Hövelmanns, K., & Kiltz, E. (2017). A modular analysis of the Fujisaki-Okamoto transformation. Theory of Cryptography – TCC 2017, Part I, 10677, 341–371. https://doi.org/10.1007/978-3-319-70500-2_12

Hou, J., Jiang, H., & Ogilvie, T. (2026). Careful with the Ring! Concrete Hardness Gaps Between LWE and MLWE. Advances in Cryptology – CRYPTO 2026. https://doi.org/10.1007/978-3-032-35377-1_15

Jaques, S. (2024). Memory Adds No Cost to Lattice Sieving for Computers in 3 or More Spatial Dimensions. IACR Communications in Cryptology, 1(3). https://doi.org/10.62056/ay4fbn2hd

Laarhoven, T. (2015). Search Problems in Cryptography: From Fingerprinting to Lattice Sieving [Phdthesis, Eindhoven University of Technology]. https://research.tue.nl/en/publications/search-problems-in-cryptography-from-fingerprinting-to-lattice-si/

Laarhoven, T., Mosca, M., & van de Pol, J. (2015). Finding Shortest Lattice Vectors Faster Using Quantum Search. Designs, Codes and Cryptography, 77(2), 375–400. https://doi.org/10.1007/s10623-015-0067-5

Langlois, A., & Stehlé, D. (2015). Worst-case to average-case reductions for module lattices. Designs, Codes and Cryptography, 75(3), 565–599. https://doi.org/10.1007/s10623-014-9938-4

Lenstra, A. K., H. W. Lenstra, Jr., & Lovász, L. (1982). Factoring polynomials with rational coefficients. Mathematische Annalen, 261(4), 515–534. https://doi.org/10.1007/BF01457454

Lindner, R., & Peikert, C. (2011). Better key sizes (and attacks) for LWE-based encryption. In A. Kiayias (Ed.), Topics in Cryptology – CT-RSA 2011 (Vol. 6558, pp. 319–339). Springer. https://doi.org/10.1007/978-3-642-19074-2_21

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

MATZOV. (2022). Report on the Security of LWE: Improved Dual Lattice Attack. Zenodo. https://doi.org/10.5281/zenodo.6412486

Micciancio, D., & Goldwasser, S. (2002). Complexity of Lattice Problems: A Cryptographic Perspective (Vol. 671). Kluwer Academic Publishers. https://link.springer.com/book/10.1007/978-1-4615-0897-7

National Institute of Standards and Technology. (2016). Submission Requirements and Evaluation Criteria for the Post-Quantum Cryptography Standardization Process. Call for Proposals, Section 4.A.5 (Security Strength Categories). https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/call-for-proposals-final-dec-2016.pdf

National Institute of Standards and Technology. (2023). FAQ on Kyber512. NIST Post-Quantum Cryptography Project. https://csrc.nist.gov/csrc/media/Projects/post-quantum-cryptography/documents/faq/Kyber-512-FAQ.pdf

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

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

Schnorr, C. P., & Euchner, M. (1994). Lattice basis reduction: improved practical algorithms and solving subset sum problems. Mathematical Programming, 66, 181–199. https://doi.org/10.1007/BF01581144

Zhao, Z., Ding, J., & Yang, B.-Y. (2025). Sieving with Streaming Memory Access. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2025(2), 362–384. https://doi.org/10.46586/tches.v2025.i2.362-384