Chapter 11: ML-KEM (FIPS 203) from scratch

ML-KEM can be read as the Regev-style encryption pattern from Chapter 10, moved to the Module-LWE setting from Chapter 9 (National Institute of Standards and Technology, 2024). The noise distribution switches from the toy uniform distribution used in Chapter 10 to the centered binomial $\text{CBD}_\eta$. The ciphertext is compressed to shave bytes. The specific compression map was introduced in the Kyber NIST PQC submission and standardized by FIPS 203. The whole thing is wrapped in the Fujisaki-Okamoto transform to lift it from IND-CPA to IND-CCA2. The underlying decryption identity is the same one from Chapter 10: $c_2 - s^\top c_1$ recovers $\text{Decompress}_1(\mu) \in \{0, 1665\}$ plus a bounded noise term. Here $1665 = \lceil q/2 \rceil$ is FIPS 203’s round-half-up image of message bit $1$ at $q = 3329$. What changes is the algebra the secret lives in, the distribution the noise is drawn from, and how the ciphertext is packaged and verified on decapsulation.

The chapter builds the whole construction at the ML-KEM-768 parameter set $(n, q, k) = (256, 3329, 3)$ specified in FIPS 203 (National Institute of Standards and Technology, 2024), and it matches the NIST Automated Cryptographic Validation Protocol (ACVP) test vectors byte-for-byte. That second claim is an implementation result rather than anything the standard reports, and tests/ch11/test_vectors.py is what checks it. Chapter 13 handles the primal and dual lattice attacks that set the three standardized parameter sets.

K-PKE as Module-Regev with compression

K-PKE is the public-key encryption component underlying ML-KEM (National Institute of Standards and Technology, 2024). It inherits Regev’s secret-cancellation identity from Chapter 10 and changes four things. First, the secret lives in $R_q^k$ rather than $\mathbb{Z}_q^n$. Second, the noise distribution is $\text{CBD}_\eta$ rather than the toy uniform distribution from Chapter 10. Third, the ciphertext is compressed to $d_u$ and $d_v$ bits per coordinate to shave transmission bytes. Fourth, every polynomial multiplication runs in the NTT domain because $R_q$ admits a specialized transform at $\zeta = 17$.

The FO wrapper does not touch the K-PKE internals (Fujisaki & Okamoto, 1999). It sits around K-PKE, deriving the encryption randomness from a hash of the message and re-encrypting on decapsulation to detect tampered ciphertexts. When the re-encryption check fails, the decapsulator returns a pseudorandom value derived from a per-key rejection seed so that adversarial ciphertexts cannot probe the secret through an error oracle (Hofheinz et al., 2017).

A concrete ML-KEM-768 parameter and seed derivation

ML-KEM-768 works with module rank $k = 3$ and noise widths $(\eta_1, \eta_2) = (2, 2)$, compression widths $(d_u, d_v) = (10, 4)$, at NIST security category 3 (National Institute of Standards and Technology, 2024). The encapsulation key is $1184$ bytes, the decapsulation key is $2400$ bytes, the ciphertext is $1088$ bytes, and the shared secret is $32$ bytes. The byte lengths are fixed by the parameter set and computed in the code below from FIPS 203 §8 Table 3 (byte lengths) and the K-PKE and ML-KEM algorithms in §5–§7.

The other two sets differ from ML-KEM-768 in four numbers and agree with it in everything else. All three fix $n = 256$, $q = 3329$, and $\eta_2 = 2$, and all three return a $32$-byte shared secret.

Set	$k$	$\eta_1$	$(d_u, d_v)$	Category	$\text{ek}$	$\text{dk}$	$c$
ML-KEM-512	2	3	(10, 4)	1	800	1632	768
ML-KEM-768	3	2	(10, 4)	3	1184	2400	1088
ML-KEM-1024	4	2	(11, 5)	5	1568	3168	1568

Sizes are in bytes. The parameter columns are FIPS 203 §8 Table 2, the size columns are §8 Table 3, and the category column is the surrounding §8 text rather than either table (National Institute of Standards and Technology, 2024).

A concrete parameter instantiation at NIST ACVP test-case 26 fixes the seeds and reproduces the exact byte lengths. This block derives $(\rho, \sigma)$ and the fixed byte lengths; it does not run a full encapsulation, which the step-by-step construction below builds up to.

import hashlib

# ML-KEM-768 parameter constants from FIPS 203 Section 8 Table 2.
n, q, k = 256, 3329, 3
eta_1, eta_2 = 2, 2
d_u, d_v = 10, 4

# Derived byte lengths from FIPS 203 Section 8 Table 3 and the K-PKE/ML-KEM algorithms.
ek_len = 384 * k + 32
dk_pke_len = 384 * k
dk_len = dk_pke_len + ek_len + 32 + 32
ct_len = 32 * (d_u * k + d_v)
ss_len = 32

# NIST ACVP test case ML-KEM-768 tcId = 26 seeds.
d_hex = "A2B4BCA315A6EA4600B4A316E09A2578AA1E8BCE919C8DF3A96C71C843F5B38B"
z_hex = "D6BF055CB7B375E3271ED131F1BA31F83FEF533A239878A71074578B891265D1"
d = bytes.fromhex(d_hex)
z = bytes.fromhex(z_hex)

# The K-PKE seed derivation: G(d || k) splits SHA3-512 into (rho, sigma).
rho_sigma = hashlib.sha3_512(d + bytes([k])).digest()
rho = rho_sigma[:32]
sigma = rho_sigma[32:]

print("ek_len =", ek_len)
print("dk_len =", dk_len)
print("ct_len =", ct_len)
print("ss_len =", ss_len)
print("rho[:8]   =", rho[:8].hex())
print("sigma[:8] =", sigma[:8].hex())
# ==> ek_len = 1184
# ==> dk_len = 2400
# ==> ct_len = 1088
# ==> ss_len = 32
# ==> rho[:8]   = e2212400769de8e1
# ==> sigma[:8] = ea2f872a82cc0c20

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

The key generator takes the $32$-byte seed $d$ and applies $G = \text{SHA3-512}$ to the concatenation $d \mathbin\Vert k$, where the byte $k$ is a domain separator equal to the module rank. The two $32$-byte halves of $G(d \mathbin\Vert k)$ become the matrix seed $\rho$ and the noise seed $\sigma$. FIPS 203 fixes the exact byte order so two implementations hashing the same $d$ produce identical derived seeds (National Institute of Standards and Technology, 2024). K-PKE.KeyGen and the ML-KEM wrapper are verified against the NIST test vectors by pytest tests/ch11/test_vectors.py. The committed fixture files live at tests/ch11/vectors/ml_kem_{512,768,1024}_acvp.json. The fixtures are vendored from the NIST ACVP server. The FIPS-validation program that consumes those vectors is the Cryptographic Algorithm Validation Program (CAVP), which is the name used in the standard for the testing scope referenced by FIPS 203 §6 (National Institute of Standards and Technology, 2024).

The ML-KEM math preliminaries

Four objects show up repeatedly: the ring $R_q$ and its partial NTT, the Module-LWE problem at rank $k$, the centered binomial distribution $\text{CBD}_\eta$, and the compression and decompression maps on $\mathbb{Z}_q$.

The ring $R_q$ at $(n, q) = (256, 3329)$. The ring is $R_q = \mathbb{Z}_{3329}[x] / (x^{256} + 1)$. The integer $q = 3329$ is prime. The integer $256$ divides $q - 1 = 3328 = 256 \cdot 13$, so $\mathbb{Z}_q$ has a primitive $256$-th root of unity. The integer $512$ does not divide $q - 1$, so $\mathbb{Z}_q$ has no primitive $512$-th root (National Institute of Standards and Technology, 2024). There are $\phi(256) = 128$ primitive $256$-th roots in $\mathbb{Z}_q^\times$. FIPS 203 fixes $\zeta = 17$ as the specific one used by ML-KEM and notes that $\zeta^{128} = -1 \pmod q$, which can be verified directly.

The polynomial $x^{256} + 1$ factors over $\mathbb{Z}_q$ into $128$ quadratic polynomials rather than into $256$ linear polynomials, because only a primitive $256$-th root of unity is available. The factorization is

$$x^{256} + 1 = \prod_{i=0}^{127} \bigl(x^2 - \zeta^{2\,\text{BitRev}_7(i) + 1}\bigr) \pmod q,$$

where $\text{BitRev}_7$ reverses the seven-bit binary representation of $i$. The NTT on $R_q$ is therefore a partial NTT: it splits $R_q$ into a product of $128$ quadratic extensions $\mathbb{Z}_q[X] / (X^2 - \gamma_i)$ rather than into $256$ copies of $\mathbb{Z}_q$. Multiplication in the NTT domain is not pointwise: each adjacent pair of coefficients represents a degree-$1$ polynomial in a different quadratic extension, and the base-case multiply takes two such pairs to a new pair. The section on the specialized partial NTT below gives the full definition. FIPS 203 §4.3 and Algorithms 9, 10, 11, and 12 formalize it (National Institute of Standards and Technology, 2024).

Module-LWE at rank $k$. Chapter 9 introduced Module-LWE as the intermediate problem between Ring-LWE and flat LWE (Langlois & Stehlé, 2015). A general Module-LWE instance at rank $k$ with $m$ samples draws a secret $\mathbf{s} \in R_q^k$, a matrix $\mathbf{A} \in R_q^{m \times k}$, and an error $\mathbf{e} \in R_q^m$. The instance emits the sample $(\mathbf{A}, \mathbf{t} = \mathbf{A} \mathbf{s} + \mathbf{e})$ with $\mathbf{t} \in R_q^m$. In K-PKE the number of rows is set equal to the module rank, so $\mathbf{A} \in R_q^{k \times k}$ and $\mathbf{t} \in R_q^k$. The three ML-KEM parameter sets instantiate this at $k \in \{2, 3, 4\}$ corresponding to ML-KEM-$512$, ML-KEM-$768$, and ML-KEM-$1024$. The ring and modulus are fixed at $(n, q) = (256, 3329)$ across all three, so scaling security is done by raising $k$, not by enlarging the ring.

The centered binomial distribution. ML-KEM draws secret and error polynomials from $\text{CBD}_\eta$, a discrete distribution with support $\{-\eta, -\eta + 1, \ldots, \eta\}$ (National Institute of Standards and Technology, 2024). The definition is

$$\text{CBD}_\eta = \sum_{i=1}^{\eta} (a_i - b_i),$$

where each $a_i$ and $b_i$ is an independent fair coin flip. At $\eta = 2$ the support is $\{-2, -1, 0, 1, 2\}$ with probabilities $(1/16, 4/16, 6/16, 4/16, 1/16)$. At $\eta = 3$ the support is $\{-3, \ldots, 3\}$ with the corresponding binomial weights. The distribution is symmetric and has mean zero and variance $\eta / 2$, so $\text{CBD}_2$ has variance $1$ and $\text{CBD}_3$ has variance $1.5$. FIPS 203 §4.2.2 uses $\text{CBD}_\eta$ in place of the toy uniform noise from Chapter 10’s pedagogical Regev (National Institute of Standards and Technology, 2024) (Regev’s original paper used discrete Gaussians, not uniform: the uniform sampler in Chapter 10 was a teaching simplification).

Compression and decompression. A $\text{Compress}_d$ map takes $x \in \mathbb{Z}_q$ and returns the index in $\{0, 1, \ldots, 2^d - 1\}$ of the nearest multiple of $q / 2^d$ on the cycle:

$$\text{Compress}_d(x) = \left\lfloor \frac{2^d \cdot x}{q} \right\rceil \bmod 2^d,$$

where $\lfloor \cdot \rceil$ is round-half-up to the nearest integer (National Institute of Standards and Technology, 2024). The inverse $\text{Decompress}_d(y) = \lfloor q \cdot y / 2^d \rceil$ maps back into $\mathbb{Z}_q$. Compression is lossy. The round-trip error is bounded by the nearest-multiple half-width:

$$\bigl|\text{Decompress}_d\bigl(\text{Compress}_d(x)\bigr) - x\bigr| \leq \left\lceil \frac{q}{2^{d+1}} \right\rceil,$$

where the absolute value is taken in symmetric representatives on $\mathbb{Z}_q$. At $q = 3329$ and $d = 10$ the bound is $2$. At $d = 4$ the bound is $105$. These two numbers feed directly into the K-PKE noise budget, which has to cover the Module-LWE error on top of the compression error. The special case $d = 1$ governs message encoding: $\text{Decompress}_1(0) = 0$ and $\text{Decompress}_1(1) = \lceil q/2 \rceil = 1665$ at $q = 3329$, by round-half-up at the midpoint $q/2 = 1664.5$. The encoded message therefore lives in $\{0, 1665\}^n$ rather than $\{0, 1664\}^n$ (National Institute of Standards and Technology, 2024).

The extended noise budget. K-PKE decrypts correctly whenever the total symmetric-representative distance between the decoder input and the encoded message (which equals $\text{Decompress}_1(\text{ByteDecode}_1(m))$, an element of $\{0, 1665\}^n$) stays below $q/4$ in each coordinate. The decoder input is $\tilde v - \mathbf{s}^\top \tilde{\mathbf u}$, where $\tilde{\mathbf u}$ and $\tilde v$ are the decompressed ciphertext parts. The compressed ciphertext $(\mathbf u, v)$ decompresses to $(\tilde{\mathbf u}, \tilde v) = (\mathbf u + \delta_u, v + \delta_v)$, so expanding with the secret-cancellation identity from Chapter 10 gives

$$\tilde v - \mathbf{s}^\top \tilde{\mathbf u} = \text{Decompress}_1(\text{ByteDecode}_1(m)) + \mathbf{e}^\top \mathbf{y} - \mathbf{s}^\top \mathbf{e}_1 + e_2 + \delta_v - \mathbf{s}^\top \delta_u,$$

where $\mathbf{y}$ is the encryption ephemeral vector (FIPS 203 Algorithm 14’s name, and the chapter reserves $r$ for the $32$-byte coin seed), and $\delta_u$, $\delta_v$ are the compression errors on $\mathbf u$ and $v$ respectively. The compression error on $\mathbf{u}$ enters the decoder multiplied by the secret, as $-\mathbf{s}^\top \delta_u$, not as a bare $+\delta_u$, because the decompressed ciphertext is $\mathbf{u} + \delta_u$ and the inner product with $\mathbf{s}$ propagates the $\delta_u$ term through.

The two Module-LWE inner-product terms $\mathbf{e}^\top \mathbf{y}$ and $\mathbf{s}^\top \mathbf{e}_1$ each combine $k$ ring multiplications of $\text{CBD}_\eta$-distributed polynomials, so each output coefficient is itself a signed sum of $k n$ products of CBD samples under negacyclic convolution. The scalar term $e_2$ is a single $\text{CBD}_{\eta_2}$-sampled polynomial in $R_q$ with no convolution. The secret-multiplied compression term $\mathbf{s}^\top \delta_u$ inherits the same $k$-ring-product structure as $\mathbf{s}^\top \mathbf{e}_1$, with the role of $\mathbf{e}_1$ played by the per-coefficient compression error bounded by $\lceil q/2^{d_u + 1} \rceil$. That asymmetry between $\delta_u$ and $\delta_v$ is why FIPS 203 spends the finer compression width on $\mathbf u$: $\delta_v$ reaches the decoder bare, while $\delta_u$ arrives amplified through $kn$ products with the secret.

The aggregate concentrates around its typical value by sub-Gaussian arguments. Correctness requires the coefficient error to stay within the $q/4$-sized decoding region around the encoded value in each coordinate. Because FIPS 203 rounds half-integers up and bit $1$ encodes to $\lceil q/2 \rceil = 1665$, the exact decode boundary is asymmetric by one integer. Errors of $-832$ through $+832$ decode correctly around $0$, but only $-832$ through $+831$ around $1665$. The chapter treats $\lfloor q/4 \rfloor = 832$ as the conceptual noise-budget threshold and relies on the FIPS 203 decapsulation-failure analysis for the exact rate.

FIPS 203 chooses $(k, \eta_1, \eta_2, d_u, d_v)$ so the probability that any coordinate leaves the decoding region, the decryption failure rate $\delta$, is cryptographically negligible across all three parameter sets. FIPS 203 §3.2 Table 1 lists the decapsulation failure rates as $2^{-138.8}$ for ML-KEM-512, $2^{-164.8}$ for ML-KEM-768, and $2^{-174.8}$ for ML-KEM-1024 (National Institute of Standards and Technology, 2024).

Step-by-step construction

The construction walks from the byte-level primitives outward to K-PKE and the ML-KEM wrapper. Inline blocks use numpy and hashlib only so they run standalone. The full implementation is at solutions/ch11-mlkem/.

Serialization: ByteEncode and ByteDecode

FIPS 203 §4.2.1 (Algorithms 5 and 6) specifies bit-packed serialization of polynomials via ByteEncode_d and ByteDecode_d (National Institute of Standards and Technology, 2024). A length-$256$ polynomial with coefficients in $[0, 2^d)$ (or $[0, q)$ for $d = 12$) packs into exactly $32 d$ bytes using $d$ bits per coefficient. The encoding is little-endian within each $d$-bit field and little-endian across fields. ByteEncode_d and ByteDecode_d are inverses when the input coefficients fit in $d$ bits. For $d = 12$ the decoder reduces modulo $q$ so malformed $12$-bit values get canonicalized.

The direct-integer form is short. Treat the $256$ coefficients as digits of a large integer in base $2^d$ and let int.to_bytes emit the little-endian byte string. The decoder reverses the packing with int.from_bytes and a bit mask.

import numpy as np

Q = 3329
N = 256


def byte_encode_d(f, d):
    assert f.shape == (N,)
    # Precondition: for d < 12 the coefficients are already reduced
    # modulo 2^d; for d = 12 they are reduced modulo q. FIPS ByteEncode
    # does not itself mask, so assert the range rather than rely on it.
    if d == 12:
        assert bool(np.all((0 <= f) & (f < Q)))
    else:
        assert bool(np.all((0 <= f) & (f < (1 << d))))
    mask = (1 << d) - 1
    big = 0
    for i in range(N):
        big |= (int(f[i]) & mask) << (i * d)
    return big.to_bytes(32 * d, "little")


def byte_decode_d(B, d):
    assert len(B) == 32 * d
    mask = (1 << d) - 1
    big = int.from_bytes(B, "little")
    f = np.zeros(N, dtype=np.int64)
    for i in range(N):
        coeff = (big >> (i * d)) & mask
        if d == 12:
            coeff %= Q
        f[i] = coeff
    return f


rng = np.random.default_rng(seed=20260411)
f = rng.integers(0, Q, size=N, dtype=np.int64)
encoded = byte_encode_d(f, 12)
decoded = byte_decode_d(encoded, 12)
print("encoded length =", len(encoded))
print("round trip equal =", bool(np.array_equal(decoded, f)))
# ==> encoded length = 384
# ==> round trip equal = True

Every polynomial in $R_q$ serializes into $384$ bytes at $d = 12$, and every compressed polynomial serializes into $32 d$ bytes. A vector in $R_q^k$ just concatenates $k$ such byte strings. ML-KEM-768 encodes the public vector $\mathbf{t}$ at $d = 12$, producing $3 \cdot 384 = 1152$ bytes, and appends the $32$-byte matrix seed $\rho$, giving the $1184$-byte encapsulation key computed earlier. The byte layer is the contract with the NIST test vectors: any implementation that matches test vectors must produce identical bytes at this layer.

Hash primitives: H, G, PRF, XOF, J

ML-KEM uses five hash primitives, all built from the Keccak permutation exposed by Python’s hashlib, and all fixed by FIPS 203 §4.1 (National Institute of Standards and Technology, 2024).

Function	Instantiation	Absorbs	Squeezes	Used for
$H$	SHA3-256	any byte string	$32$ bytes	hashing $\text{ek}$, into $\text{dk}$ and into $G$‘s input
$G$	SHA3-512	any byte string	$64$ bytes, split in two	$(\rho, \sigma)$ in KeyGen, $(K, r)$ in Encaps
$\text{PRF}_\eta$	SHAKE-256	$32$-byte seed, one-byte nonce	$64 \eta$ bytes	the CBD sampler
$\text{XOF}$	SHAKE-128	$32$-byte seed, two index bytes	streamed	the rejection sampler for $\hat{\mathbf{A}}$
$J$	SHAKE-256	any byte string	$32$ bytes	the implicit-rejection value in Decaps

$G$ is called at two sites with two different labelings for its two halves. The K-PKE KeyGen construction below labels the split $(\rho, \sigma)$, the two seeds for $\mathbf{A}$ and for CBD noise; the KEM’s encapsulation and decapsulation paths label it $(K, r)$, the shared-secret half and the re-encryption randomness. The two labelings name the same 64-byte-into-two-32-byte-halves pattern applied in different call sites.

From-scratch Keccak lives elsewhere. The construction below treats SHA-3 and SHAKE as opaque oracles.

import hashlib


def H(data):
    return hashlib.sha3_256(data).digest()


def G(data):
    digest = hashlib.sha3_512(data).digest()
    return digest[:32], digest[32:]


def PRF(eta, seed, nonce):
    assert eta in (2, 3)
    shake = hashlib.shake_256()
    shake.update(seed + bytes([nonce]))
    return shake.digest(64 * eta)


def XOF(shake_input, outlen):
    shake = hashlib.shake_128()
    shake.update(shake_input)
    return shake.digest(outlen)


def J(data):
    return hashlib.shake_256(data).digest(32)


# A sanity check: G applied to the empty byte string is SHA3-512 of
# the empty byte string split into two 32-byte halves. Compare the
# concatenation against the canonical FIPS 202 digest.
k_half, r_half = G(b"")
full = k_half + r_half
expected = bytes.fromhex(
    "a69f73cca23a9ac5c8b567dc185a756e97c982164fe25859e0d1dcc1475c80a6"
    "15b2123af1f5f94c11e3e9402c3ac558f500199d95b6d3e301758586281dcd26"
)
print("H len =", len(H(b"abc")))
print("PRF(2) len =", len(PRF(2, b"\x00" * 32, 0)))
print("J len =", len(J(b"")))
print("G matches SHA3-512 on empty input =", full == expected)
# ==> H len = 32
# ==> PRF(2) len = 128
# ==> J len = 32
# ==> G matches SHA3-512 on empty input = True

The nonce in PRF(eta, seed, nonce) is a one-byte domain separator. K-PKE.KeyGen uses nonces $0, 1, \ldots, k - 1$ for the secret $\mathbf{s}$ and nonces $k, k + 1, \ldots, 2k - 1$ for the error $\mathbf{e}$, so the same $\sigma$ seed produces independent-looking output for different rows. K-PKE.Encrypt uses nonces $0, \ldots, k - 1$ for the ephemeral vector $\mathbf{y}$, nonces $k, \ldots, 2k - 1$ for $\mathbf{e}_1$, and nonce $2k$ for the scalar $e_2$. The nonce discipline is fixed by FIPS 203 so two implementations produce identical derived randomness.

Sampling: CBD_eta and rejection-sampled uniform

Two distinct samplers feed K-PKE. The first is $\text{CBD}_\eta$ (FIPS 203 Algorithm 8), which takes a $64 \eta$-byte string from the PRF and produces a polynomial with coefficients drawn from the centered binomial distribution. The second is the uniform-NTT sampler (FIPS 203 Algorithm 7), which rejection-samples bytes from the XOF stream until it has $256$ coefficients strictly less than $q = 3329$. The uniform sampler is used to expand the matrix $\hat{\mathbf{A}}$ directly in the NTT domain from a $32$-byte seed $\rho$.

import hashlib
import numpy as np

Q = 3329
N = 256


def _bytes_to_bits(b):
    bits = []
    for byte in b:
        for j in range(8):
            bits.append((byte >> j) & 1)
    return bits


def cbd_eta(byte_string, eta):
    assert len(byte_string) == 64 * eta
    bits = _bytes_to_bits(byte_string)
    f = np.zeros(N, dtype=np.int64)
    for i in range(N):
        x = sum(bits[2 * i * eta + j] for j in range(eta))
        y = sum(bits[2 * i * eta + eta + j] for j in range(eta))
        f[i] = (x - y) % Q
    return f


def sample_ntt(shake_input):
    shake = hashlib.shake_128()
    shake.update(shake_input)
    bytes_requested = 168 * 5
    raw = shake.digest(bytes_requested)
    idx = 0
    out = np.zeros(N, dtype=np.int64)
    j = 0
    while j < N:
        if idx + 3 > len(raw):
            bytes_requested += 168
            raw = shake.digest(bytes_requested)
        b0, b1, b2 = raw[idx], raw[idx + 1], raw[idx + 2]
        idx += 3
        d1 = b0 | ((b1 & 0x0F) << 8)
        d2 = (b1 >> 4) | (b2 << 4)
        if d1 < Q:
            out[j] = d1
            j += 1
        if j < N and d2 < Q:
            out[j] = d2
            j += 1
    return out


# An all-zero CBD input at eta=2, standing in for PRF output, produces
# the zero polynomial because every paired-bit x = y = 0 gives f[i] = 0.
# Other inputs produce coefficients in {-2, -1, 0, 1, 2} in Z_q.
f_zero = cbd_eta(b"\x00" * 128, 2)
print("CBD(0 bytes, eta=2) sums =", int(f_zero.sum()))

# The rejection sampler consumes bytes until it has accepted 256
# coefficients below q.
# Two distinct seeds produce distinct polynomials with overwhelming
# probability.
a = sample_ntt(b"\x00" * 34)
b = sample_ntt(b"\x01" * 34)
print("sample_ntt output length =", int(a.shape[0]))
print("distinct seeds distinct output =", bool(not np.array_equal(a, b)))
# ==> CBD(0 bytes, eta=2) sums = 0
# ==> sample_ntt output length = 256
# ==> distinct seeds distinct output = True

The CBD sampler reads the $512\eta$ bits in consecutive blocks of $2\eta$, one block per coefficient. The coefficient is the number of ones in the block’s first $\eta$ bits minus the number of ones in its last $\eta$ bits (FIPS 203 Algorithm 8: $f[i] = \sum_{j<\eta} b[2i\eta + j] - \sum_{j<\eta} b[2i\eta + \eta + j]$). At $\eta = 2$ the result is an integer in $\{-2, -1, 0, 1, 2\}$. The sampler reduces modulo $q$ to keep outputs in the canonical range $[0, q)$, so negative samples appear as values close to $q - 1$.

The rejection sampler interprets the SHAKE-128 byte stream in groups of three, reading each group as two $12$-bit candidates. A candidate in $[0, q)$ is accepted; a candidate in $[q, 2^{12})$ is rejected. The rejection rate is $(2^{12} - q) / 2^{12} = 767 / 4096 \approx 0.187$, so roughly one in five candidates is dropped and $256$ accepted coefficients typically need fewer than $500$ bytes of SHAKE output. The sampler requests $840$ bytes up front as headroom and squeezes more if the rare unlucky stream runs out.

The specialized partial NTT at (256, 3329)

FIPS 203 §4.3 defines a specialized NTT on $R_q$ (National Institute of Standards and Technology, 2024). The map is not the full negacyclic NTT from Chapter 9 because $\mathbb{Z}_{3329}$ has a primitive $256$-th root of unity ($\zeta = 17$) but not a primitive $512$-th root. The ring therefore splits into $128$ quadratic extensions rather than $256$ copies of $\mathbb{Z}_q$. The forward NTT runs an iterative Cooley-Tukey butterfly scheme (FIPS 203 Algorithm 9) with bit-reversed twiddle factors. The inverse (Algorithm 10) runs Gentleman-Sande butterflies and scales by $128^{-1} = 3303 \pmod q$ at the end. Multiplication in the NTT domain is not pointwise: FIPS 203 Algorithm 11 runs BaseCaseMultiply over $128$ pairs of adjacent coefficients, each representing a degree-$1$ polynomial in a different $\mathbb{Z}_q[X] / (X^2 - \gamma_i)$ factor. The gamma values are $\gamma_i = \zeta^{2\,\text{BitRev}_7(i) + 1}$.

The NTT is the only primitive in the chapter that is long enough to warrant a dedicated code block. The inline block below defines bit_rev_7, the zeta tables, the forward and inverse NTT, and the multiply_ntts routine that runs BaseCaseMultiply over the $128$ slots. A self-consistency check verifies that the round-trip inverse_ntt(multiply_ntts(ntt(f), ntt(g))) equals an independent schoolbook polynomial multiplication in $R_q$.

import numpy as np

Q = 3329
N = 256
ZETA = 17
INV_128 = pow(128, -1, Q)  # 3303


def bit_rev_7(i):
    out = 0
    for _ in range(7):
        out = (out << 1) | (i & 1)
        i >>= 1
    return out


ZETAS_NTT = [pow(ZETA, bit_rev_7(k), Q) for k in range(128)]
ZETAS_MUL = [pow(ZETA, 2 * bit_rev_7(k) + 1, Q) for k in range(128)]


def ntt(f):
    f_hat = np.asarray(f, dtype=np.int64).copy() % Q
    i = 1
    length = 128
    while length >= 2:
        start = 0
        while start < N:
            zeta = ZETAS_NTT[i]
            i += 1
            for j in range(start, start + length):
                t = (zeta * int(f_hat[j + length])) % Q
                f_hat[j + length] = (int(f_hat[j]) - t) % Q
                f_hat[j] = (int(f_hat[j]) + t) % Q
            start += 2 * length
        length //= 2
    return f_hat


def inverse_ntt(f_hat):
    f = np.asarray(f_hat, dtype=np.int64).copy() % Q
    i = 127
    length = 2
    while length <= 128:
        start = 0
        while start < N:
            zeta = ZETAS_NTT[i]
            i -= 1
            for j in range(start, start + length):
                t = int(f[j])
                f[j] = (t + int(f[j + length])) % Q
                f[j + length] = (zeta * (int(f[j + length]) - t)) % Q
            start += 2 * length
        length *= 2
    return (f * INV_128) % Q


def multiply_ntts(f_hat, g_hat):
    out = np.zeros(N, dtype=np.int64)
    for i in range(128):
        gamma = ZETAS_MUL[i]
        a0, a1 = int(f_hat[2 * i]), int(f_hat[2 * i + 1])
        b0, b1 = int(g_hat[2 * i]), int(g_hat[2 * i + 1])
        out[2 * i] = (a0 * b0 + a1 * b1 * gamma) % Q
        out[2 * i + 1] = (a0 * b1 + a1 * b0) % Q
    return out


# Self-consistency check: the NTT product equals schoolbook convolution
# in R_q, for a random polynomial pair.
def schoolbook(f, g):
    h = np.zeros(N, dtype=np.int64)
    for i in range(N):
        fi = int(f[i])
        for j in range(N):
            k = i + j
            term = (fi * int(g[j])) % Q
            if k < N:
                h[k] = (int(h[k]) + term) % Q
            else:
                h[k - N] = (int(h[k - N]) - term) % Q
    return h


rng = np.random.default_rng(seed=20260411)
f = rng.integers(0, Q, size=N, dtype=np.int64)
g = rng.integers(0, Q, size=N, dtype=np.int64)
h_ntt = inverse_ntt(multiply_ntts(ntt(f), ntt(g)))
h_school = schoolbook(f, g)
print("NTT product equals schoolbook =", bool(np.array_equal(h_ntt, h_school)))
print("ZETAS_NTT[1] =", ZETAS_NTT[1])
# ==> NTT product equals schoolbook = True
# ==> ZETAS_NTT[1] = 1729

The check passes because the forward NTT, the inverse NTT, the bit-reversed zeta table, and the slot-wise BaseCaseMultiply are all correct by construction. The value $\text{ZETAS\_NTT}[1] = 1729$ is the first non-trivial twiddle and appears in FIPS 203 Appendix A (National Institute of Standards and Technology, 2024). It is a useful landmark rather than a complete test. A wrong primitive root changes it, and so does any bit-reversal error that touches index 1. A permutation error confined to positions the block does not print leaves it standing. The schoolbook cross-check is the independent computation path. Tautological checks like ntt(f) == ntt(f) would not catch bugs in the NTT implementation itself.

K-PKE.KeyGen

K-PKE.KeyGen takes a $32$-byte seed $d$ and emits the K-PKE public key $\text{ek}_\text{PKE}$ and secret key $\text{dk}_\text{PKE}$. The derivation starts at $G(d \mathbin\Vert k) = (\rho, \sigma)$, which splits the SHA3-512 digest into a matrix seed and a noise seed. The matrix $\hat{\mathbf{A}} \in R_q^{k \times k}$ is expanded directly in the NTT domain from $\rho$ via the rejection sampler, with one call per entry. FIPS 203 specifies the XOF input for entry $[i][j]$ as $\rho \mathbin\Vert j \mathbin\Vert i$ (column byte first, row byte second) so that two implementations reading the same $\rho$ produce identical matrix entries (National Institute of Standards and Technology, 2024).

The secret vector $\mathbf{s}$ and error vector $\mathbf{e}$ are sampled from $\text{CBD}_{\eta_1}$ using $\text{PRF}_{\eta_1}(\sigma, \text{nonce})$. K-PKE.KeyGen uses nonces $0, 1, \ldots, k - 1$ for $\mathbf{s}$ and nonces $k, k + 1, \ldots, 2k - 1$ for $\mathbf{e}$, so the same $\sigma$ seed produces independent-looking output for different rows and the two vectors never collide. Both vectors are then transformed into the NTT domain: $\hat{\mathbf{s}} = \text{NTT}(\mathbf{s})$ and $\hat{\mathbf{e}} = \text{NTT}(\mathbf{e})$.

The public vector is $\hat{\mathbf{t}} = \hat{\mathbf{A}} \hat{\mathbf{s}} + \hat{\mathbf{e}}$, all multiplications in the NTT domain. The encapsulation key is $\text{ek}_\text{PKE} = \text{ByteEncode}_{12}(\hat{\mathbf{t}}) \mathbin\Vert \rho$, which has length $384 k + 32$. The decryption key is $\text{dk}_\text{PKE} = \text{ByteEncode}_{12}(\hat{\mathbf{s}})$, of length $384 k$. Both are stored in the NTT domain, not in the coefficient domain, because every subsequent multiplication will happen in NTT space.

A short inline block reproduces the first eight secret and error samples for ML-KEM-768 at the NIST tcId=26 seeds, using the noise seed $\sigma$ derived above.

import hashlib
import numpy as np


def PRF(eta, seed, nonce):
    shake = hashlib.shake_256()
    shake.update(seed + bytes([nonce]))
    return shake.digest(64 * eta)


def cbd_eta(byte_string, eta):
    bits = []
    for byte in byte_string:
        for j in range(8):
            bits.append((byte >> j) & 1)
    f = np.zeros(256, dtype=np.int64)
    for i in range(256):
        x = sum(bits[2 * i * eta + j] for j in range(eta))
        y = sum(bits[2 * i * eta + eta + j] for j in range(eta))
        f[i] = (x - y) % 3329
    return f


# Reconstruct sigma from the NIST tcId=26 d seed.
d = bytes.fromhex(
    "A2B4BCA315A6EA4600B4A316E09A2578AA1E8BCE919C8DF3A96C71C843F5B38B"
)
k = 3
sigma = hashlib.sha3_512(d + bytes([k])).digest()[32:]

# Sample s row 0 (nonce 0) and e row 0 (nonce k = 3) with eta_1 = 2.
s_row_0 = cbd_eta(PRF(2, sigma, 0), 2)
e_row_0 = cbd_eta(PRF(2, sigma, k), 2)

# Put the outputs into symmetric representatives for inspection.
def sym(f):
    return [int(x) - 3329 if int(x) > 1664 else int(x) for x in f]


print("s_row_0[:8] =", sym(s_row_0[:8]))
print("e_row_0[:8] =", sym(e_row_0[:8]))
print("nonce 0 vs nonce 3 distinct =",
      bool(not np.array_equal(s_row_0, e_row_0)))
# ==> s_row_0[:8] = [0, 0, -1, 0, 2, 0, 1, -1]
# ==> e_row_0[:8] = [0, 0, 0, -1, 1, 0, 0, 0]
# ==> nonce 0 vs nonce 3 distinct = True

The coefficients are in $\{-2, -1, 0, 1, 2\}$, the support of $\text{CBD}_2$. The printed check establishes only that the two rows differ. Independence is a property of the PRF: under FIPS 203 the nonce is a domain separator, so $\mathbf{s}$ and $\mathbf{e}$ derived from the same $\sigma$ under different nonces are computationally indistinguishable from independently sampled polynomials, and an array comparison cannot verify that. A bug in the nonce scheme (for example, reusing nonce $0$ for both $\mathbf{s}$ and $\mathbf{e}$) collapses the error into the secret and silently breaks the security reduction. Such a bug passes every round-trip test that runs the same implementation on both sides, because key generation, encryption and decryption stay mutually consistent, and nothing fails until an adversary exploits it. The byte-for-byte match against the NIST test vectors catches it at once, by comparing the resulting $\hat{\mathbf{t}}$ and $\text{ek}_\text{PKE}$ bytes to the standard.

K-PKE.Encrypt

K-PKE.Encrypt takes the $\text{ek}_\text{PKE}$ bytes, a $32$-byte message $m$, and a $32$-byte coin seed $r$, and produces the compressed ciphertext $c$. The first step decodes $\hat{\mathbf{t}}$ and the matrix seed $\rho$ from $\text{ek}_\text{PKE}$. FIPS 203 Algorithm 14 re-expands $\hat{\mathbf{A}}$ with the same byte order as KeyGen, $\rho \mathbin\Vert j \mathbin\Vert i$, and then uses $\hat{\mathbf{A}}^\top$ algebraically (line 19 of Algorithm 14 writes $\hat{\mathbf{A}}^\top$ explicitly). The flagship code in solutions/ch11-mlkem/ exposes a transpose=True flag on sample_matrix_ntt that swaps the two suffix bytes to $\rho \mathbin\Vert i \mathbin\Vert j$ and materializes the transposed view directly. The row-wise product $\sum_j \hat{\mathbf{A}}[i][j] \cdot \hat{\mathbf{y}}[j]$ inside Encrypt therefore evaluates to $\hat{\mathbf{A}}_\text{KeyGen}^\top \mathbf{y}$ without an explicit transpose operation. The byte-order swap is an implementation convenience, not a different FIPS matrix definition.

The encryption ephemeral randomness $\mathbf{y}, \mathbf{e}_1, e_2$ is sampled from the coin seed $r$. The discipline uses $\text{CBD}_{\eta_1}$ with nonces $0, \ldots, k - 1$ for $\mathbf{y}$. It uses $\text{CBD}_{\eta_2}$ with nonces $k, \ldots, 2k - 1$ for $\mathbf{e}_1$. The scalar $e_2$ uses $\text{CBD}_{\eta_2}$ with nonce $2k$. The NTT brings $\mathbf{y}$ into transform space. The ciphertext parts are

$$\mathbf{u} = \text{NTT}^{-1}(\hat{\mathbf{A}}^\top \hat{\mathbf{y}}) + \mathbf{e}_1,$$ $$v = \text{NTT}^{-1}(\hat{\mathbf{t}}^\top \hat{\mathbf{y}}) + e_2 + \text{Decompress}_1(\text{ByteDecode}_1(m)),$$

where $\hat{\mathbf{t}}^\top \hat{\mathbf{y}}$ is the dot product in the module and $\text{ByteDecode}_1$ reads the $256$ bits of $m$ into a polynomial with coefficients in $\{0, 1\}$. Here $\text{Decompress}_1$ maps $1 \mapsto \lceil q/2 \rceil = 1665$ and $0 \mapsto 0$ at $q = 3329$.

The ciphertext is $c = \text{ByteEncode}_{d_u}(\text{Compress}_{d_u}(\mathbf{u})) \mathbin\Vert \text{ByteEncode}_{d_v}(\text{Compress}_{d_v}(v))$, total length $32 (d_u k + d_v)$. At ML-KEM-768 the two parts are $960 + 128 = 1088$ bytes.

The derandomization from the coin seed $r$ means the same message under the same public key with the same coin seed produces the same ciphertext. K-PKE.Encrypt is therefore a deterministic function of its three inputs, which is essential for the FO re-encryption check inside Decaps to work.

K-PKE.Decrypt

K-PKE.Decrypt takes $\text{dk}_\text{PKE}$ and $c$ and recovers the message. The ciphertext splits into $c_1$ (the compressed $\mathbf{u}$) and $c_2$ (the compressed $v$). Decompression undoes the rounding to produce approximations $\tilde{\mathbf{u}}$ and $\tilde{v}$ in $\mathbb{Z}_q$ with residual error bounded by the compression noise formula from the preliminaries.

The decryption identity is the secret-cancellation from Chapter 10 with the extra compression and Module-LWE noise terms accounted for:

$$w = \tilde{v} - \text{NTT}^{-1}\!\left(\hat{\mathbf{s}}^\top \text{NTT}(\tilde{\mathbf{u}})\right) = \text{Decompress}_1(\text{ByteDecode}_1(m)) + (\text{noise}),$$

where $\hat{\mathbf{s}}$ is decoded from $\text{dk}_\text{PKE}$ (FIPS 203 Algorithm 15 line 6: the decoder brings $\tilde{\mathbf{u}}$ into the NTT domain with ntt, runs multiply_ntts slot-wise, sums, and returns to the coefficient domain with inverse_ntt). The recovered message is $\text{Compress}_1(w)$, which reads $1$ for coefficients closer to $\lceil q/2 \rceil = 1665$ and $0$ for coefficients closer to $0$.

A tiny Module-LWE round-trip at $k = 2$ and $q = 97$ demonstrates the secret-cancellation identity in the module setting without invoking the full ML-KEM NTT machinery. The parameters are Chapter 10’s flat-Regev toy at $q = 97$ but with a module rank $k = 2$ instead of a secret dimension $n = 4$. Each ring element is a single integer in $\mathbb{Z}_{97}$, because at $n = 1$ the ring is just $\mathbb{Z}_q$.

import numpy as np

q = 97
k = 2

rng = np.random.default_rng(seed=0)

# Module-Regev at k = 2, n = 1: secret and error live in Z_q^k,
# matrix lives in Z_q^{k x k}, public vector is a Z_q^k column.
s = rng.integers(-1, 2, size=k, dtype=np.int64) % q
A = rng.integers(0, q, size=(k, k), dtype=np.int64)
e = rng.integers(-1, 2, size=k, dtype=np.int64) % q
t = (A @ s + e) % q

# Encryption: r, e1 in Z_q^k, e2 scalar. mu is the message bit.
mu = 1
r = rng.integers(-1, 2, size=k, dtype=np.int64) % q
e1 = rng.integers(-1, 2, size=k, dtype=np.int64) % q
e2 = int(rng.integers(-1, 2, dtype=np.int64)) % q
u = (A.T @ r + e1) % q
v = int((t @ r + e2 + ((q + 1) // 2) * mu) % q)

# Decryption: w = v - s^T u. Round to nearer of 0 or (q+1)//2 using
# the same decode formula as Chapter 10 (midpoint -> 0).
w = (v - int(s @ u)) % q
half_q = q // 2
decoded = ((2 * w + half_q) // q) % 2
print("(q + 1) // 2 =", (q + 1) // 2)
print("w =", w)
print("decoded mu =", decoded, "expected =", mu)
# ==> (q + 1) // 2 = 49
# ==> w = 49
# ==> decoded mu = 1 expected = 1

The encoding multiplier is $\lceil q/2 \rceil = (q+1)/2 = 49$ to mirror FIPS 203’s round-half-up convention at the prime modulus $q = 97$, rather than the symmetric $\lfloor q/2 \rfloor = 48$. The decrypted value $w = 49$ lands exactly on $\lceil q/2 \rceil = 49$, so the decoder formula returns the expected bit $1$. The noise at this tiny instance happens to cancel perfectly at seed $0$. Other seeds give non-zero values inside the decoding half-width $q/4 \approx 24$. The toy omits CBD noise, compression, and the NTT. Only the module structure and the secret-cancellation identity are preserved. The real ML-KEM-768 case is the same identity at $(k, n, q) = (3, 256, 3329)$ with CBD noise and compression, and the FIPS 203 noise budget absorbs both.

The Fujisaki-Okamoto wrapper

The K-PKE scheme above is IND-CPA, not IND-CCA2. If an attacker were given a useful decryption oracle on malformed ciphertexts, decoder-boundary behavior could leak information about the secret $\mathbf{s}$. The exact attack and query complexity depend on the chosen-ciphertext construction, which Chapter 13 treats in detail. FIPS 203 is explicit that K-PKE is not IND-CCA2-secure, must not be used standalone, and is approved only as a component inside ML-KEM (National Institute of Standards and Technology, 2024). The Fujisaki-Okamoto-style transform is designed to remove this useful oracle signal by making the encryptor’s randomness a deterministic function of the message and the public key. On decapsulation the decapsulator re-runs the encryptor and verifies the ciphertext against the re-encryption (Fujisaki & Okamoto, 1999; Hofheinz et al., 2017).

ML-KEM.KeyGen internally takes two $32$-byte seeds, $d$ and $z$. The seed $d$ feeds K-PKE.KeyGen, and $z$ is the implicit-rejection seed, stored inside $\text{dk}$ for use only by the decapsulator. The decapsulation key is $\text{dk} = \text{dk}_\text{PKE} \mathbin\Vert \text{ek} \mathbin\Vert H(\text{ek}) \mathbin\Vert z$. The hash $H(\text{ek})$ is precomputed so decapsulation does not rehash the public key on every call, and the rejection seed $z$ rides along.

ML-KEM.Encaps takes the public key $\text{ek}$ and a $32$-byte message $m$. The “internal” form with an explicit $m$ is the one that matches NIST test vectors; the external form draws $m$ uniformly at random. Encaps computes $(K, r) = G(m \mathbin\Vert H(\text{ek}))$, runs K-PKE.Encrypt with the derandomized coin seed $r$, and returns $(K, c)$. The shared secret $K$ is a hash of the message and the public-key commitment. The coin seed $r$ is the other half of the same hash.

ML-KEM.Decaps takes $\text{dk}$ and $c$. It runs K-PKE.Decrypt to recover a candidate message $m'$, then recomputes $(K', r') = G(m' \mathbin\Vert H(\text{ek}))$. It re-runs K-PKE.Encrypt to produce $c' = \text{K-PKE.Encrypt}(\text{ek}, m', r')$ and compares $c$ against $c'$. On a match the shared secret is $K'$. On a mismatch the shared secret is the pseudorandom rejection value $\bar{K} = J(z \mathbin\Vert c)$, where $J = \text{SHAKE-256}$ truncated to $32$ bytes. The rejection branch returns the same $\bar{K}$ for the same $(z, c)$ pair. Flipping any byte of $c$ gives a different $\bar{K}$. An adversary tampering with the ciphertext cannot extract information through this oracle, because the returned $K$ is independent of the secret except through the hash.

Figure 11.1. The ML-KEM Encaps and Decaps call graph, showing the Fujisaki-Okamoto re-encryption check. Encaps is one forward pass from m to c. Decaps recovers m', re-runs the pipeline to get c', and returns K' on match or the pseudorandom rejection value J(z || c) on mismatch.

The diagram makes the FO wrapper shape visible. The decapsulator runs K-PKE.Encrypt a second time, which is the costly operation. The equality check at the end is cheap. The rejection branch has no algebraic dependence on the K-PKE secret $\mathbf{s}$. That structural property is what the FO-style wrapper relies on to argue that no useful decryption-oracle signal leaks under the ROM (or QROM) idealization of $G$, $H$, and $J$.

A mock demonstration of the re-encryption check, using stand-in K-PKE functions, illustrates the structure without pulling the full package.

import hashlib


def H(data):
    return hashlib.sha3_256(data).digest()


def G(data):
    digest = hashlib.sha3_512(data).digest()
    return digest[:32], digest[32:]


def J(data):
    return hashlib.shake_256(data).digest(32)


# Mock K-PKE: encryption prepends m to a deterministic tag derived
# from (ek, r); decryption reads m from the first 32 bytes. This is
# not the real Module-Regev construction — it exists only to exercise
# the FO wrapper's re-encryption check at the byte level. What
# matters for the mock: it round-trips on honest inputs and diverges
# when any byte of the ciphertext is flipped.
def mock_kpke_encrypt(ek, m, r):
    tag = hashlib.sha3_256(ek + r).digest()
    return m + tag


def mock_kpke_decrypt(dk_pke, c):
    return c[:32]


ek = b"public key bytes".ljust(32, b"\x00")
m = b"message_of_exactly_32_bytes_okay"
z = b"implicit_rejection_seed_32_bytes"
dk_pke = b"stub dk_pke, unused by the mock" + b"\x00"

# Encapsulate.
K, r = G(m + H(ek))
c = mock_kpke_encrypt(ek, m, r)

# Decapsulate: recover m', recompute (K', r'), re-encrypt, compare.
m_prime = mock_kpke_decrypt(dk_pke, c)
K_prime, r_prime = G(m_prime + H(ek))
c_prime = mock_kpke_encrypt(ek, m_prime, r_prime)
if c == c_prime:
    K_out = K_prime
else:
    K_out = J(z + c)

# Honest path: K matches K_prime.
print("honest decapsulation matches encapsulation K =", K_out == K)

# Tampered path: flip a byte of c and observe the rejection branch.
c_tampered = bytes([c[0] ^ 0xFF]) + c[1:]
m_prime_bad = mock_kpke_decrypt(dk_pke, c_tampered)
K_prime_bad, r_prime_bad = G(m_prime_bad + H(ek))
c_reenc = mock_kpke_encrypt(ek, m_prime_bad, r_prime_bad)
if c_tampered == c_reenc:
    K_bad = K_prime_bad
else:
    K_bad = J(z + c_tampered)
print("tampered decapsulation returns J(z || c) =",
      K_bad == J(z + c_tampered))
print("tampered K != honest K =", K_bad != K)
# ==> honest decapsulation matches encapsulation K = True
# ==> tampered decapsulation returns J(z || c) = True
# ==> tampered K != honest K = True

The mock exercises the control flow only. The real K-PKE.Encrypt is the Module-Regev construction built in the preceding sub-sections. What matters is the wrapper shape: the decapsulator always runs K-PKE.Decrypt, always recomputes $(K', r')$, always re-encrypts, and always compares. There is no early return on a decryption-failure signal. An adversary timing the decapsulator sees the same work regardless of whether the ciphertext was tampered or honest, up to the data-dependent branches inside the mock encryptor. FIPS 203 §6.3 specifies that decrypt, recompute, re-encrypt, compare sequence as ML-KEM.Decaps_internal, Algorithm 18 (National Institute of Standards and Technology, 2024). The production form is in the ch11-mlkem package under solutions/, lifted to the full K-PKE over Module-LWE.

The Python if c == c_prime: branch in the mock is pedagogical. A real ML-KEM decapsulator must perform the ciphertext comparison and the shared-secret selection in constant time. FIPS 203 §6.3 calls the implicit-rejection flag a secret piece of intermediate data that must be destroyed before decapsulation returns. It must therefore not leak through timing, branch, or memory-access behavior either.

Input checks before Encaps and Decaps. FIPS 203 §7.2 and §7.3 require an implementation to validate inputs before running the security-sensitive path, and name five checks between them (National Institute of Standards and Technology, 2024).

FIPS 203 check	Where	What it tests
Type check	Encaps	$\text{ek}$ is exactly $384 k + 32$ bytes
Modulus check	Encaps	$\text{ek}[0{:}384k]$ survives a $\text{ByteDecode}_{12}$ then $\text{ByteEncode}_{12}$ round trip unchanged
Ciphertext type check	Decaps	$c$ is exactly $32 (d_u k + d_v)$ bytes
Decapsulation key type check	Decaps	$\text{dk}$ is exactly $768 k + 96$ bytes
Hash check	Decaps	the hash stored in $\text{dk}$ equals a fresh $H$ of the $\text{ek}$ embedded beside it

The round-trip equality is the actual modulus check because $\text{ByteDecode}_{12}$ always reduces each 12-bit chunk modulo $q$, so a malformed chunk encoding a value outside $[0, q)$ does not survive re-encoding. Failed checks return an error before the secret-dependent code path runs. FIPS 203 draws one operational distinction: the encapsulation-key and decapsulation-key checks need not be repeated on every operation if assurance of key validity has been obtained elsewhere, but the ciphertext check must be performed on every execution of ML-KEM.Decaps.

The ch11-mlkem package under solutions/ implements the §6 internal algorithms, which are the interfaces the ACVP vectors address, so it asserts the three length checks at the top of ml_kem_encaps_internal and ml_kem_decaps_internal and implements neither the modulus check nor the hash check. That split follows the standard: FIPS 203 attaches input checking to ML-KEM.Encaps and ML-KEM.Decaps in §7, which wrap the internal algorithms rather than living inside them. A production KEM has to add the other two.

Cryptanalysis and known attacks

Chapter 13 handles the full lattice cryptanalysis. FIPS 203 §8 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). Table 2 itself gives the parameter tuples and required RBG strength. The category mapping appears in the surrounding §8 text.

Those categories come from NIST’s PQC evaluation framework, which rates a scheme by the resources an attack needs relative to reference attacks on generic primitives rather than by a single bit-security number. For the parameter sets used by ML-KEM, categories 1, 3, and 5 correspond to reference security levels based on the cost of key recovery against AES-128, AES-192, and AES-256 respectively; categories 2 and 4 use hash-collision reference problems. The CRYSTALS-Kyber submission package priced the $(n, q, k, \eta_1, d_u, d_v)$ tuples with the core-SVP methodology, over the attack families the Albrecht-Player-Scott survey catalogues (Albrecht et al., 2015; Avanzi et al., 2021, sec. 5.1), and Chapter 13 re-runs that estimate against the ML-KEM parameters and reads its cost estimates against the published category claims, under a stated attack and cost model, rather than deriving the table from them.

Against K-PKE alone (with no FO wrapper), an adversary with a decryption oracle recovers information about the secret vector $\mathbf{s}$ by probing decoder decisions near the noise-budget boundary. The structural shape of the attack: pick a ciphertext whose decryption value $\tilde v - \mathbf{s}^\top \tilde{\mathbf u}$ hugs a decoder boundary. Observe whether the decoded bit is what the attacker expected, and deduce information about one coordinate of $\mathbf{s}$ per query. The exact query complexity depends on the attack model and ciphertext construction. Chapter 13 walks one such construction in full against a small-secret variant of the Chapter 10 flat Regev PKE and notes what changes for K-PKE’s centered-binomial secret. The point here is that K-PKE is IND-CPA, not IND-CCA2, and needs wrapping.

The FO-style wrapper is designed to remove the useful decryption-oracle signal by re-encrypting and implicitly rejecting malformed ciphertexts. A tampered ciphertext $c \neq c'$ returns the pseudorandom rejection value $J(z \mathbin\Vert c)$, which depends on $z$ (secret but fixed per key) and $c$ (public) but has no algebraic dependence on the K-PKE secret $\mathbf{s}$. An adversary who flips bits and observes $K$ learns a random function of $c$ and nothing about $\mathbf{s}$ in the random oracle model.

The Hofheinz-Hövelmanns-Kiltz IND-CCA2 theorem (Hofheinz et al., 2017) makes this rigorous: it requires K-PKE to be OW-CPA and $\delta$-correct, and concludes IND-CCA2 in the random oracle model with an explicit reduction loss. The rigidity the second half of the transform relies on (decrypting a ciphertext and re-encrypting the result gives back the same ciphertext or rejects) is not assumed of K-PKE. The theorem proves it of the derandomized scheme in the middle of the transform, which encrypts $m$ under coins $G(m)$ and re-encrypts on decryption. The security statement is reduction-based and depends on the underlying Module-LWE assumption, the ROM (or QROM, for the quantum-attacker refinement) idealization of $G$, $H$, and $J$, and the small decapsulation-failure probability $\delta$ from FIPS 203 §3.2 Table 1. Constant-time implementation discipline at the decapsulator is also required. ML-KEM is therefore “believed to satisfy IND-CCA2” under these assumptions rather than unconditionally (National Institute of Standards and Technology, 2024).

Tradeoffs inside Part II

ML-KEM’s ring and modulus are fixed across all three parameter sets. The primary security lever is the module rank $k$, with smaller parameter-set adjustments to $\eta_1$ and, for ML-KEM-1024, the ciphertext compression widths. The alternatives fall along two axes: stay with lattices but change the ring structure, or leave lattices entirely.

• ML-KEM versus flat Regev (Chapter 10): flat Regev is conceptually simpler and has no NTT, but its public key scales as $O(n^2)$ bytes. A Chapter-10 Regev instance matching ML-KEM-768’s security would need an enormous $n$ and would have public keys in the megabyte range. Chapter 13’s tradeoffs draw the same comparison, without fixing a parameter set for it. ML-KEM’s ring structure cuts this to roughly $1.1$ kilobytes by amortizing $n = 256$ coefficients across each matrix entry.
• ML-KEM versus a Ring-LWE KEM (Chapter 9’s Ring-LWE setting, whose encryption descendant Chapter 10 builds): a Ring-LWE KEM at $k = 1$ would be even smaller than ML-KEM-768, but Module-LWE’s rank parameter $k$ provides a cleaner security lever. Scaling security in Ring-LWE means enlarging $n$, which changes the ring, the NTT, and every other primitive. Scaling Module-LWE means raising $k$, which keeps the ring fixed and just adds more matrix rows and more PRF calls. That is what the parameter table above shows: the three sets share the ring, the NTT, and the hash and XOF layer, and differ in $k$ plus two compensating adjustments. ML-KEM-512’s $\eta_1 = 3$ buys back noise that the smaller rank gives up; ML-KEM-1024’s wider $(d_u, d_v) = (11, 5)$ holds $\delta$ below $2^{-174}$ against the larger noise sums (National Institute of Standards and Technology, 2024).
• ML-KEM versus non-lattice KEMs (Part IV): code-based KEMs rely on different hardness assumptions and trade different costs against bandwidth. HQC (Chapter 21) is the only other post-quantum KEM NIST has selected at Category 3, in the Round 4 KEM selection of March 2025 (National Institute of Standards and Technology, 2025), with the final standard expected in 2027 per NIST’s announcement of that selection (National Institute of Standards and Technology, 2025b). It rests on the syndrome-decoding problem rather than Module-LWE (Gaborit et al., 2025). ML-KEM-768 at $1{,}184$-byte $\text{ek}$ and $1{,}088$-byte ciphertext (Table 3 in National Institute of Standards and Technology, 2024) is currently the only FIPS-standardized post-quantum KEM at Category 3. HQC-3, the current Category-3 profile in the August 2025 HQC specification, lists a $4{,}514$-byte encapsulation key and an $8{,}978$-byte ciphertext, both several times larger than ML-KEM-768.

SLH-DSA (Chapter 17), ML-DSA (Chapter 12), and SQIsign (Chapter 23) are signature schemes, not KEM alternatives. The comparison there is by primitive role rather than by ciphertext size, and each of those chapters discusses its own bandwidth tradeoffs. FO-style transforms are common across the lattice KEMs in the standardization pool, but the exact hash schedule, rejection behavior, and byte layout differ by scheme. ML-KEM’s particular FO-style hash schedule and implicit-rejection behavior are design choices, not consequences forced by Module-LWE alone (Hofheinz et al., 2017). Saber, FrodoKEM, NTRU, and ML-KEM therefore produce different ciphertext bytes even when their wrapper logic follows the same broad re-encrypt-and-check pattern. Chapter 13 attacks exactly the Module-LWE instance ML-KEM uses.

Chapter 12 is the immediate next step. ML-DSA keeps this chapter’s module-lattice setting and changes the goal from key encapsulation to signing, and that changes almost everything downstream. It rests on Module-SIS for unforgeability as well as Module-LWE for key recovery, and it picks a modulus admitting the full $256$-point NTT rather than this chapter’s partial one. Rejection sampling, not a Fujisaki-Okamoto wrapper, is what makes its output safe to publish.

Exercises

1. Compression noise at $d = 10$. Run a numpy sweep over $x \in \mathbb{Z}_q$ and verify $|\text{Decompress}_{10}(\text{Compress}_{10}(x)) - x| \leq 2$. Compute the closed-form upper bound $\lceil q / 2^{d+1} \rceil$ at $d = 11$ and $d = 4$, then sweep all $x \in \mathbb{Z}_q$ at each width to compare the bound against the actual maximum symmetric error. The bound is $105$ at $d = 4$ but the sweep maximum is $104$; at $d = 10$ both equal $2$. Explain why the closed form is an upper bound rather than always the exact maximum.

2. CBD versus uniform noise (stress test). Replace sample_poly_cbd(eta, seed, nonce) in the ch11-mlkem package under solutions/ with a uniform sampler over $\{-\eta, \ldots, \eta\}$. The replacement takes the same three arguments and returns the same shape: a degree-255 polynomial whose coefficients are drawn from the given support. The FIPS-203 decapsulation-failure rates ($\delta < 2^{-164.8}$ for ML-KEM-768) are too small to observe in any feasible Monte Carlo. Artificially lower the noise budget first: drop $d_u$ from $10$ to $8$ and raise $\eta_1$ from $2$ to $3$, leaving $d_v = 4$, then run the K-PKE round-trip $10^4$ times under each sampler and compare the failure counts. Lower the budget much further than that and the comparison stops working, because both samplers fail on essentially every trial. Explain why the uniform distribution’s heavier tail produces failures that the centered binomial’s tighter tail suppresses at the same support width.

3. Tampered ciphertext decapsulation. Run ML-KEM-768 key generation at the NIST tcId $= 26$ seed, encapsulate under an arbitrary $m$ to produce honest $(K, c)$, flip one byte of $c$ to produce $c^*$, and decapsulate $c^*$. Confirm that the returned shared secret equals $J(z \mathbin\Vert c^*)$ exactly, not the honest $K$. Repeat with a different byte flip and observe a different rejection value. Explain which property of the hash $J$ makes this enough to block a decryption oracle.

4. The matrix transpose trick. FIPS 203 Algorithm 14 specifies $\hat{\mathbf{A}}[i][j] \leftarrow \text{SampleNTT}(\rho \mathbin\Vert j \mathbin\Vert i)$ in K-PKE.Encrypt with the same byte order as K-PKE.KeyGen, and then uses $\hat{\mathbf{A}}^\top$ algebraically on line 19. Read sample_matrix_ntt in the ch11-mlkem package under solutions/ and verify the two paths agree. Calling it with transpose=True (which swaps the two suffix bytes to $\rho \mathbin\Vert i \mathbin\Vert j$) and then computing $\sum_j \hat{\mathbf{A}}[i][j] \cdot \hat{\mathbf{y}}[j]$ should give the same product as calling it with transpose=False and then computing $\sum_j \hat{\mathbf{A}}^\top[i][j] \cdot \hat{\mathbf{y}}[j]$. Write a small pytest that asserts the two approaches give identical $\hat{\mathbf{u}}$ tensors. The implementation equivalence is the point. FIPS itself stays in the original orientation and applies the transpose algebraically.

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

References

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

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

Fujisaki, E., & Okamoto, T. (1999). Secure integration of asymmetric and symmetric encryption schemes. Advances in Cryptology – CRYPTO 1999, 1666, 537–554. https://doi.org/10.1007/3-540-48405-1_34

Gaborit, P., Aguilar-Melchor, C., Aragon, N., Bettaieb, S., Bidoux, L., Blazy, O., Deneuville, J.-C., Persichetti, E., Zémor, G., Bos, J., Dion, A., Lacan, J., Robert, J.-M., Véron, P., Barreto, P. S. L. M., Ghosh, S., Gueron, S., Güneysu, T., Misoczki, R., … Vasseur, V. (2025). HQC: Hamming Quasi-Cyclic. https://pqc-hqc.org/doc/hqc_specifications_2025_08_22.pdf

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

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

National Institute of Standards and Technology. (2024). 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. (2025a). Status Report on the Fourth Round of the NIST Post-Quantum Cryptography Standardization Process (Internal Report NIST IR 8545). National Institute of Standards and Technology. https://doi.org/10.6028/NIST.IR.8545

National Institute of Standards and Technology. (2025b). NIST Selects HQC as Fifth Algorithm for Post-Quantum Encryption. NIST news release. https://www.nist.gov/news-events/news/2025/03/nist-selects-hqc-fifth-algorithm-post-quantum-encryption