Chapter 5: KEMs vs key agreement vs public-key encryption

KEMs, key agreement, and public-key encryption are three primitives for three different problems. A key-encapsulation mechanism (KEM) produces a fresh random symmetric key on the sender’s side and lets the receiver recover it from a ciphertext. A key-agreement protocol lets two parties derive a shared secret from public exchanges where both sides contribute randomness. A public-key encryption (PKE) scheme encrypts a specific message the sender already has. The three primitives solve different problems and compose differently. Treating any two as interchangeable leads to wrong parameter choices and wrong interface boundaries.

The Fujisaki-Okamoto transform ties PKEs and KEMs together: it is a family of compilers that turns a weaker public-key encryption component into an IND-CCA2-secure KEM in the random-oracle model (ROM). ML-KEM follows this route. FIPS 203 first defines an internal Module-LWE-based PKE called K-PKE, then wraps it with a re-encryption check using implicit rejection (not explicit rejection). For inputs of the right form the decapsulation API returns a 256-bit value rather than a $\bot$ symbol, and length/type/hash input-check failures are surfaced separately as API-level validation errors rather than as the FO rejection branch (National Institute of Standards and Technology, 2024).

A shared key without a pre-shared secret

The canonical motivating scenario is two parties who have never met and want a fresh symmetric key, say a 256-bit key for the rest of the session. Alice and Bob can see each other’s public values over an authenticated channel but share no prior secret. The 1976 paper of Diffie and Hellman gave the first published solution to this problem (Diffie & Hellman, 1976). Fix a prime $p$ and a generator $g$ of the multiplicative group $(\mathbb{Z}/p\mathbb{Z})^\times$. Alice picks a random exponent $a$ and sends $A = g^a \bmod p$. Bob picks a random exponent $b$ and sends $B = g^b \bmod p$. Each side then computes the shared value from the other side’s public value:

$$K_A = B^a \bmod p, \qquad K_B = A^b \bmod p.$$

Substituting $A = g^a$ and $B = g^b$ gives $K_A = g^{ab} = K_B$, so both sides derive the same element of the group. The whole exchange runs on a toy prime in a few lines of Python:

# Toy Diffie-Hellman in (Z/pZ)^* with p = 23 and g = 5.
# g is a primitive root mod 23, so ord(g) = phi(23) = 22.
p = 23
g = 5

# Alice picks a secret exponent and publishes A.
a = 6
A = pow(g, a, p)

# Bob picks a secret exponent and publishes B.
b = 15
B = pow(g, b, p)

# Each party computes the shared value from the other's public value.
alice_shared = pow(B, a, p)
bob_shared = pow(A, b, p)
print(A, B)
print(alice_shared == bob_shared, alice_shared)
# ==> 8 19
# ==> True 2

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

The shared value $2$ is not yet a usable AES key, because the group element lives in a small range and is not uniform in any byte string. Real deployments feed the group element through a key-derivation function (for example HKDF-Extract-then-Expand with SHA-256) to produce the actual symmetric key. Computing the raw group element rests on the computational Diffie-Hellman assumption: given $g$, $A = g^a$, and $B = g^b$ in a suitable group, it is hard to compute $g^{ab}$. Treating the derived symmetric key as pseudorandom is a separate requirement, and it rests on hash Diffie-Hellman. CDH suffices for HDH in the random-oracle model, and decisional Diffie-Hellman (DDH) combined with a suitable key-derivation function is the other route. Boneh and Shoup treat all three assumptions in their graduate cryptography textbook (Boneh & Shoup, 2023).

Now flip the question. Suppose Alice already has a 256-bit key $K$ that she chose herself, and she wants to send it to Bob. Diffie-Hellman cannot do this. Alice has no way to force the shared output to equal a specific $K$ she chose. Public-key encryption can. Alice encrypts $K$ under Bob’s public key and sends the ciphertext. But if Alice only wants Bob to end up with any fresh random key that Alice also knows, public-key encryption is overkill. Alice does not need to choose $K$; she only needs some random $K$ that Bob can recover. That is the KEM problem, and it is the primitive the rest of the chapter develops.

IND-CCA2 and the KEM correctness condition

The PKE and KEM parts of the chapter use IND-CCA2-style indistinguishability games. Key agreement has a different security story: passive secrecy of the group element under CDH, pseudorandomness of the derived key under HDH or under DDH with a suitable KDF, plus authentication to resist active attacks. The IND-CCA2 game for a public-key encryption scheme runs like this. The challenger generates a keypair $(\text{pk}, \text{sk})$ and gives $\text{pk}$ to the adversary. The adversary may submit any ciphertext $c$ to a decryption oracle and receive $\text{Dec}(\text{sk}, c)$. At one moment the adversary picks two equal-length plaintexts $m_0$ and $m_1$. The challenger picks a bit $b \in \{0, 1\}$ uniformly and returns the challenge ciphertext $c^* = \text{Enc}(\text{pk}, m_b)$. The adversary may keep querying the decryption oracle on any ciphertext except $c^*$. Eventually the adversary outputs a guess $b'$, and its advantage is

$$\mathrm{Adv}^{\text{IND-CCA2}}(\mathcal{A}) = \bigl| \Pr[b' = b] - 1/2 \bigr|.$$

A public-key encryption scheme is IND-CCA2-secure if every polynomial-time adversary’s advantage is negligible in the security parameter (Boneh & Shoup, 2023).

The corresponding game for a KEM is almost identical. The challenger gives $\text{pk}$ to the adversary, and the adversary has access to a decapsulation oracle both before and after the challenge. At one moment the challenger runs $(c^*, K_0) \gets \text{Encap}(\text{pk})$, so $K_0$ is the real encapsulated key. The challenger then samples a fresh uniform $K_1$ of the same length, flips a bit $b \in \{0, 1\}$, and returns the pair $(c^*, K_b)$. The adversary may continue to query $\text{Decap}$ on any ciphertext except $c^*$, and eventually outputs a guess $b'$. The advantage is defined the same way. The abstract KEM/DEM game and its proof-theoretic lemmas live in the Boneh-Shoup textbook (Boneh & Shoup, 2023).

KEM correctness is the dual condition: the legitimate decapsulation must almost always return the same key that encapsulation produced. A KEM is $\varepsilon$-correct if

$$\Pr_{\substack{(\text{pk},\, \text{sk}) \,\gets\, \text{Gen} \\ (c,\, K) \,\gets\, \text{Encap}(\text{pk})}}\bigl[\, \text{Decap}(\text{sk}, c) \neq K \,\bigr] \;\leq\; \varepsilon,$$

where $\varepsilon$ is a negligible function of the security parameter. Note which randomness the probability runs over: the key generation as well as the encapsulation. That is weaker than a per-key guarantee, and deliberately so: the published average does not imply a bound for every generated keypair, so quantifying over every honestly generated keypair would claim more than the figures below support. For lattice-based KEMs like ML-KEM the error $\varepsilon$ is not exactly zero, because the underlying LWE decryption can fail on rare noise samples. FIPS 203 reports decapsulation-failure estimates of approximately $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). Chapter 11 develops the centered-binomial noise budget these rates come out of, and takes the exact figures from the same FIPS 203 analysis rather than re-deriving them.

For the toy RSA-based KEM built below, correctness is exact for every $K \in [1, n-1]$. Textbook RSA decryption recovers the original residue mod $pq$ for all inputs (not only those coprime to $n$), by reducing modulo $p$ and $q$ separately and applying the Chinese remainder theorem. So coprimality is not a correctness condition here at all. A uniform $K \in [1, n-1]$ shares a factor with $n$ with probability at most $1/p + 1/q$, under $2^{-30}$ for the 32-bit primes used below. Nothing in this chapter depends on that number. The mauling attack in the cryptanalysis section needs its own blinding factor to be invertible, which is a different quantity, and the attacker picks it rather than sampling it. Exercise 3 works the count anyway, because knowing which quantity a bound applies to is part of reading one.

Key agreement as an interactive primitive

A two-party key-agreement protocol is a pair of interactive algorithms $(A, B)$. Alice runs $A$ and Bob runs $B$. Each party sends one or more public messages, and at the end both parties output a shared secret $K$ of some fixed bit length $\ell_K$. For Diffie-Hellman the two messages are $A = g^a$ and $B = g^b$, and both parties output $K = \mathrm{KDF}(g^{ab})$ where $\mathrm{KDF}$ is a key-derivation function. Security is stated against an adversary that reads both public messages but cannot actively interfere. Without an authenticated channel the scheme is vulnerable to man-in-the-middle, which the cryptanalysis section below walks.

The shared-secret length is not the security level

The symbol $\lambda$ denotes the target classical security level in bits, and Appendix B summarizes its scope across later parts. The shared-secret length $\ell_K$ is matched to $\lambda$ at design time but is a separate quantity. ML-KEM outputs a 256-bit shared secret at every parameter set, including ML-KEM-512, which targets a lower NIST security category, so $\ell_K$ alone does not determine $\lambda$.

The post-quantum version of this story does not replace the math of Diffie-Hellman directly. Shor’s algorithm breaks the discrete logarithm in $(\mathbb{Z}/p\mathbb{Z})^\times$ and on elliptic curves (Shor, 1994), so every group that worked for pre-quantum Diffie-Hellman fails. Deployed post-quantum cryptography replaces classical Diffie-Hellman with a KEM rather than another interactive key-agreement protocol, though early lattice proposals (NewHope, Frodo) did start from the interactive framing. The underlying PKE component in ML-KEM is K-PKE, a Module-LWE-based public-key encryption scheme (Chapter 9 develops Module-LWE; Chapter 11 plugs K-PKE into the FO-style transform specified in FIPS 203). ML-KEM’s Module-LWE instantiation fixes the polynomial degree at $n = 256$ and scales its parameter sets by changing the module rank $k \in \{2, 3, 4\}$, which is structurally distinct from a pure Ring-LWE construction.

Public-key encryption and OAEP

A public-key encryption scheme is a triple $(\text{Gen}, \text{Enc}, \text{Dec})$. Gen() samples a keypair. Enc(pk, m) produces a ciphertext $c$. Dec(sk, c) returns the plaintext $m$ or a rejection symbol. Textbook RSA from Chapter 4 is the deterministic function $m \mapsto m^e \bmod n$. It fails the IND-CCA2 game immediately, because the adversary can check whether a given ciphertext is the encryption of a chosen plaintext by re-running the encryption map and comparing. It also fails IND-CPA (indistinguishability under chosen-plaintext attack) against an adversary that picks two plaintexts to distinguish, for the same reason.

Optimal asymmetric encryption padding (OAEP) fixes the deterministic-encryption problem by randomizing the input before the RSA function sees it (Bellare & Rogaway, 1994). Let $k$ be the RSA modulus length in bytes and let $h$ be the output length of the hash function. OAEP takes a message $m$ of length at most $k - 2 h - 2$ bytes and a fresh random seed $r$ of length $h$ bytes. It builds a data block $\text{DB} = \text{lHash} \,\|\, \text{PS} \,\|\, \mathtt{0x01} \,\|\, m$ of length $k - h - 1$ bytes. Here $\text{lHash}$ is the hash of an optional label (empty by default) and $\text{PS}$ is a run of zero bytes, and the $\mathtt{0x01}$ byte separates $\text{PS}$ from $m$ at the parsing step. A single mask-generating function $\mathrm{MGF}$ (itself built from the hash function) is applied twice, first to mask the data block and then to mask the seed:

$$\text{maskedDB} = \text{DB} \oplus \mathrm{MGF}(r,\, k - h - 1), \qquad \text{maskedSeed} = r \oplus \mathrm{MGF}(\text{maskedDB},\, h).$$

The encoded message is $\mathtt{0x00} \,\|\, \text{maskedSeed} \,\|\, \text{maskedDB}$, a total of $k$ bytes, and is fed to raw RSA. The leading $\mathtt{0x00}$ byte ensures that the encoded message, interpreted as an integer, lies in the valid RSA message-representative range below $n$. Decryption reverses the two masks and parses the data block back into $\text{lHash}$, $\text{PS}$, the $\mathtt{0x01}$ separator, and $m$. The exact byte layout is standardized in PKCS #1 v2.2 (Moriarty et al., 2016).

The proof history of OAEP is more delicate than the original 1994 paper suggested. Bellare and Rogaway introduced OAEP and proved a plaintext-awareness-style result in the random-oracle model (Bellare & Rogaway, 1994). Shoup later showed that this argument does not establish IND-CCA2 security for an arbitrary trapdoor one-way permutation (Shoup, 2001). He proposed a modified construction (OAEP+) for which generic IND-CCA2 can be proven. For the specific RSA instantiation, Fujisaki, Okamoto, Pointcheval, and Stern proved that RSA-OAEP is IND-CCA2-secure in the random-oracle model under the RSA assumption, although the reduction is non-tight (Fujisaki et al., 2001). RFC 8017 cites this proof as the security justification for RSAES-OAEP (Moriarty et al., 2016). The rest of the chapter takes RSA-OAEP as given.

The KEM API and a toy RSA-KEM

A KEM is a triple $(\text{Gen}, \text{Encap}, \text{Decap})$. Gen() samples a keypair $(\text{pk}, \text{sk})$. Encap(pk) uses fresh randomness to produce a ciphertext $c$ and a shared key $K \in \{0, 1\}^{\ell_K}$, and returns the pair $(c, K)$. The ciphertext $c$ travels over the wire, and both parties use $K$ as the shared symmetric key. Decap(sk, c) returns $K$, or in implicit-rejection schemes returns a pseudorandom-looking fallback rather than a distinguished symbol on a malformed ciphertext. The conceptual split between a KEM and a PKE is exactly this: in a KEM, neither Alice nor Bob chooses $K$; the encapsulation routine derives it from fresh randomness. In a PKE, the sender chooses the plaintext. Boneh and Shoup give the abstract KEM/DEM decomposition and its security game (Boneh & Shoup, 2023).

Figure 5.1. The KEM/DEM flow. The KEM handles key establishment: encap(pk) on Alice's side produces (ct, K), and Bob's decap(sk, ct) recovers the same K. NIST SP 800-227 notes that a KEM can be viewed as key transport or as key agreement depending on its construction, and places ML-KEM on the key-agreement reading, so "establishment" is the safer word for the general picture (National Institute of Standards and Technology, 2025). The DEM handles message confidentiality with K. In a direct KEM/DEM construction the DEM is an authenticated encryption with associated data (AEAD) construction such as AES-GCM or ChaCha20-Poly1305, so a tampered symmetric ciphertext fails its integrity check. In a protocol such as TLS 1.3 there is no standalone DEM: K feeds a key schedule that derives the AEAD traffic keys, and the AEAD rather than the schedule is what rejects tampering.

Textbook RSA can be wrapped as a toy KEM. Encapsulation samples a random $K$ in $[1, n - 1]$ and sets the ciphertext to $c = K^e \bmod n$. Decapsulation is $K = c^d \bmod n$, which is the same computation as textbook RSA decryption. The snippet below builds the toy KEM on the 64-bit modulus from Chapter 4 and verifies a single round-trip:

# Toy RSA-KEM built on the 64-bit textbook RSA from Chapter 4.
# Encap samples a random K in [1, n - 1] and encrypts it as K^e mod n.
# Decap runs raw RSA decryption to recover the same K.
# Demo only: random.Random is deterministic and NOT cryptographically secure.
# Real encapsulation uses secrets.SystemRandom and feeds the output through
# a KDF to produce a fixed-length symmetric key.
import random

p = 3184935163
q = 3199286161
n = p * q
e = 65537
d = pow(e, -1, (p - 1) * (q - 1))
public_key = (n, e)
private_key = (n, d)

def encap(pk, rng):
    mod, exp = pk
    K = rng.randint(1, mod - 1)
    c = pow(K, exp, mod)
    return (c, K)

def decap(sk, c):
    mod, dec_exp = sk
    return pow(c, dec_exp, mod)

rng = random.Random(7)  # fixed seed for reproducibility
c, K_alice = encap(public_key, rng)
K_bob = decap(private_key, c)
print(K_alice == K_bob)
print(0 < K_bob < n)
# ==> True
# ==> True

This toy KEM is correct but not IND-CCA2-secure, because textbook RSA is malleable. An adversary who sees the ciphertext $c$ can compute $c' = c \cdot r^e \bmod n$ for a blinding factor $r$ of its choice. Taking $r = 2$ and submitting $c'$ to the decapsulation oracle in the CCA game returns $(r \cdot K) \bmod n$, which leaks a non-trivial function of the challenge key $K$. The choice of $r$ is not free: the oracle refuses the challenge ciphertext, so $c'$ has to differ from $c$, and the cryptanalysis section below shows that an invertible $r$ does not guarantee it. The cryptanalysis section below walks this attack at a working level.

Textbook RSA is not itself IND-CPA-secure: the deterministic map Chapter 4 builds repeats a ciphertext whenever the message repeats. This toy KEM is therefore a weaker starting point than the FO transform requires, and it serves to make the malleability concrete with one line of arithmetic. The fix at the level of a real KEM is not to hand-patch the toy construction but to apply a generic compiler that turns an IND-CPA-secure public-key encryption scheme into an IND-CCA2-secure KEM. That compiler is the Fujisaki-Okamoto transform.

The Fujisaki-Okamoto transform: from PKE component to CCA-secure KEM

The Fujisaki-Okamoto (FO) transform is a family of compilers whose input is an IND-CPA-secure public-key encryption scheme and whose output is an IND-CCA2-secure KEM in the random-oracle model. The original Fujisaki-Okamoto paper (Fujisaki & Okamoto, 1999) gave the first construction. The 2017 modular analysis by Hofheinz, Hövelmanns, and Kiltz (Hofheinz et al., 2017) isolates a family of variants. They differ in two axes:

• Derandomization with a hash $G$ of the message $m$, so $\mathrm{Enc}$ becomes deterministic given $m$ and the re-encryption check is well-defined.
• Rejection style on a failed re-encryption check. The explicit-rejection variant $\mathrm{FO}^{\perp}$ returns a distinguished symbol $\perp$. The implicit-rejection variant $\mathrm{FO}^{\not\perp}$ returns a pseudorandom-looking key derived from a private seed and the offending ciphertext, so the decapsulation API never reveals whether the ciphertext was malformed.

ML-KEM per FIPS 203 uses an FO-style implicit-rejection construction on top of K-PKE. The teaching-level theorem below states the abstract pattern. The exact byte-level mapping in FIPS 203 is more specific. Successful decapsulation in FIPS 203 derives the shared secret as $(K, r) = G(m \,\|\, H(\mathrm{ek}))$, where $\mathrm{ek}$ is the encapsulation key. FIPS 203 §4.1 instantiates these three functions with different primitives: $H$ is SHA3-256, $G$ is SHA3-512 (its two 32-byte output halves being $K$ and $r$), and $J$ is SHAKE256 truncated to 32 bytes. The derivation omits the ciphertext, a deliberate optimization relative to the $H(m, c)$ teaching variant stated below. Hofheinz, Hövelmanns and Kiltz analyse variants that drop it too. On a failed re-encryption check, ML-KEM returns the implicit-rejection fallback $J(z \,\|\, c)$, where $z$ is a 32-byte private seed in the decapsulation key. The fallback retains the dependence on $c$.

For inputs of the right form the public decapsulation API does not surface the re-encryption-check result as $\perp$; the caller sees only a 256-bit output. The defensive motivation is to remove an explicit failure flag from the API surface. A calling protocol such as TLS 1.3 cannot then branch on KEM failure, so a Bleichenbacher-style adaptive attack on the KEM has no $\perp$ signal to exploit. Implementations still have to compute the check and the conditional assignment without leaking the secret reject flag through timing, cache, or other side channels. FIPS 203 explicitly notes that the implicit-reject flag is secret intermediate data.

Chapter 11 maps this abstract pattern to the exact FIPS 203 construction, including the input-checking and key-encoding details. The theorem below states only the implicit-rejection variant, since that is the form ML-KEM relies on. The chapter states the theorem without proving it.

Theorem ($\mathrm{FO}^{\not\perp}$, informal). Let $\Pi = (\mathrm{Gen}, \mathrm{Enc}, \mathrm{Dec})$ be a public-key encryption scheme with message space $\mathcal{M}$. Assume $\Pi$ is IND-CPA-secure and $\delta$-correct, where $\delta$ bounds the expectation over key generation of the worst-case message decryption-failure probability, so a scheme cannot be called $\delta$-correct on the strength of an average over $m$. Let $G$ and $H$ be two hash functions modeled as random oracles. Define a KEM $\mathrm{FO}^{\not\perp}(\Pi)$ as follows. Key generation runs $\Pi.\mathrm{Gen}$ and samples a uniform private seed $z \gets \mathcal{M}$, drawn from the same message space the construction encapsulates over. Encapsulation samples a random $m \in \mathcal{M}$, computes $c = \mathrm{Enc}(\mathrm{pk}, m;\, G(m))$ (the encryption coins are derived from $G(m)$), and returns $(c, K)$ with $K = H(m, c)$. Decapsulation decrypts $c$ to $m'$ and returns the implicit-rejection fallback $\bar{K} = H(z, c)$ if $\mathrm{Dec}$ output $\perp$ or if the re-encryption $\mathrm{Enc}(\mathrm{pk}, m';\, G(m'))$ differs from $c$; otherwise it returns $K = H(m', c)$. Both failure conditions route to the fallback, and omitting the $\perp$ case leaves the transform unsound. Then $\mathrm{FO}^{\not\perp}(\Pi)$ is IND-CCA2-secure in the random-oracle model, with

$$\mathrm{Adv}^{\text{IND-CCA2}} \;\leq\; q_{\mathrm{RO}}\, \delta \;+\; \frac{3\, q_{\mathrm{RO}}}{|\mathcal{M}|} \;+\; 3\, \mathrm{Adv}^{\text{IND-CPA}},$$

where $q_{\mathrm{RO}} = q_G + q_H$ counts the adversary’s random-oracle queries (Hofheinz et al., 2017).

The seed’s domain is part of the theorem rather than a detail. The guessing term is written over $|\mathcal{M}|$ because both of the adversary’s short-circuits, guessing the challenge message and guessing the fallback seed, then live in one space. Sampling $z$ from an independent $\lambda$-bit space instead contributes at most $q_H / 2^{\lambda}$ from seed guessing, so the displayed bound no longer follows unchanged for an arbitrary $\mathcal{M}$. The query count belongs in that term: the adversary gets one attempt per hash query, which is why HHK bounds the same event by $q_H / |\mathcal{M}|$ rather than by $1 / |\mathcal{M}|$. For ML-KEM the distinction collapses, since its messages and its seed are both 32-byte strings.

Three things about that bound are worth reading off. The advantage term carries a constant factor of 3 and no factor of $q_{\mathrm{RO}}$, so this IND-CPA-based route is tight. The looser reduction people mean when they call FO non-tight is the one starting from a one-way rather than an indistinguishability assumption, and the reductions in the quantum random-oracle model (QROM) are non-tight as well. The $q_{\mathrm{RO}} / |\mathcal{M}|$ term is why the theorem needs a large message space: an adversary that can guess $m$ wins outright, so $|\mathcal{M}|$ must be big enough to make that term negligible. And the $q_{\mathrm{RO}}\, \delta$ term is why $\delta$-correctness has to hold in the worst case over messages rather than on average: a chosen-ciphertext adversary picks which messages to push through the failure branch.

Three observations on the construction:

• The re-encryption check at decapsulation turns the underlying PKE into a publicly verifiable scheme. That is what lets the security reduction simulate a decryption oracle to the adversary using only the IND-CPA game on $\Pi$.
• Deriving the encryption coins from $G(m)$ makes $\mathrm{Enc}$ deterministic given $m$, so the re-encryption check is well-defined.
• In the teaching theorem the symmetric key is $H(m, c)$ on success and $H(z, c)$ on failure, so the output depends on $c$ in both branches. FIPS 203’s ML-KEM optimizes the success path by deriving $K$ from $G(m \,\|\, H(\mathrm{ek}))$ without the ciphertext, while keeping $c$ in the fallback $J(z \,\|\, c)$. The binding to $c$ on the failure branch is what prevents a chosen-ciphertext adversary from forcing two mauled ciphertexts to share a fallback key.

The companion explicit-rejection variant $\mathrm{FO}^{\perp}$ replaces the implicit fallback by a literal $\perp$ output. It admits a similar reduction in the ROM under an extra $\gamma$-spread condition on $\Pi$, but its public failure behavior is precisely what implementers want to avoid in protocols carrying secret-dependent branches. Chapter 11 instantiates the implicit-rejection theorem above with a lattice-based $\Pi$, namely the Module-LWE-based K-PKE specified in FIPS 203, to obtain ML-KEM, including the FIPS 203 byte-level deviations from the abstract theorem flagged above.

What breaks without the transforms

Textbook RSA is malleable: $\mathrm{Enc}(m_1) \cdot \mathrm{Enc}(m_2) = (m_1 m_2)^e \bmod n = \mathrm{Enc}(m_1 m_2)$. An IND-CCA2 adversary exploits this in a single query. It submits two distinct non-zero challenge plaintexts, preferably both coprime to $n$, and receives $c^* = m_b^e \bmod n$. It then takes $r = 2$, computes $c' = c^* \cdot r^e \bmod n$, and queries the decryption oracle on $c'$. The oracle then returns $(m_b \cdot r) \bmod n$, and the adversary recovers $m_b$ by multiplying with $r^{-1} \bmod n$.

Two conditions have to hold for that query to be legal, and the choices above secure both. First, $r$ must be invertible mod $n$, so the recovery step can divide it out. Second, $c'$ must differ from $c^*$, because the CCA oracle refuses the challenge ciphertext itself. Invertibility alone does not give the second condition, which is the subtlety the exercises return to, and no $r$ helps at all if the adversary chose $m_b = 0$: then $c^* = 0$, which multiplication cannot move.

OAEP closes this gap by randomizing the input before RSA. The decryption of a mauled ciphertext is a random-looking block that almost never parses as a valid OAEP encoding. The IND-CCA2 proof for RSA-OAEP combines the original Bellare-Rogaway construction with the later Fujisaki-Okamoto-Pointcheval-Stern argument and Shoup’s reanalysis (Bellare & Rogaway, 1994; Fujisaki et al., 2001; Shoup, 2001).

Textbook Diffie-Hellman falls to a man-in-the-middle without authentication. Against a purely passive eavesdropper it holds up: seeing $A = g^a$ and $B = g^b$, that adversary cannot compute $g^{ab}$ under the computational Diffie-Hellman assumption. Concluding that the derived key $\mathrm{KDF}(g^{ab})$ also looks random to it is a stronger statement needing a stronger assumption. That assumption is hash Diffie-Hellman, which CDH implies when the key-derivation function is modeled as a random oracle. DDH plus a suitable extractor is the other standard route (Boneh & Shoup, 2023).

An active adversary defeats the exchange without touching either assumption. Eve intercepts both messages, forwarding $A_E = g^{a_E}$ to Bob in place of Alice’s $A$, and $B_E = g^{b_E}$ to Alice in place of Bob’s $B$. Alice, who received $B_E$, computes $B_E^{\,a} = g^{a b_E}$, which Eve recomputes as $A^{b_E}$. Bob, who received $A_E$, computes $A_E^{\,b} = g^{a_E b}$, which Eve recomputes as $B^{a_E}$. Each honest party pairs its own secret exponent with Eve’s matching public value, never with the other party’s, so Eve ends up holding two unrelated shared secrets while Alice and Bob each believe they share one with the other.

The defence is to authenticate the protocol, either via a signature on the exchange (as in TLS 1.3) or via a pre-shared long-term public key. Chapter 28 walks the TLS 1.3 handshake and where post-quantum key establishment lands in it; Chapter 29 covers the certificate chain that carries the authenticating signature.

A KEM built by naively wrapping a merely IND-CPA-secure PKE should not be assumed IND-CCA2-secure. The toy RSA-KEM above is intentionally a weaker example: textbook RSA is not even IND-CPA-secure, but it makes the malleability concrete. The adversary blinds the challenge ciphertext by $r = 2$, which is both invertible and guaranteed to move the ciphertext, submits the result to the decapsulation oracle, and reads back a function of the challenge key. In an FO-style KEM, decapsulation re-encrypts its decrypted message and checks for byte-equality with the input ciphertext. Over a randomized scheme, a ciphertext mauled by an algebraic relation on the challenge almost never survives that check, and the rejection branch runs. ML-KEM uses implicit rejection, returning the fallback $J(z \,\|\, c)$ rather than $\perp$.

Note what the transform does not claim. An adversary is always free to encapsulate honestly and hand back a well-formed ciphertext, which passes the check by construction. Security does not rest on every non-challenge ciphertext being rejected. It rests on any accepted ciphertext yielding a key derived from its own plaintext, so a decapsulation query says nothing about the challenge key beyond what the underlying IND-CPA scheme already allowed.

The re-encryption argument needs the underlying scheme to be randomized, which is why it does not rescue the toy above. Textbook RSA has no encryption coins to derive from $G(m)$, so the mauled $c \cdot r^e$ is a legitimate encryption of $rK$ and would survive a byte-equality check. What defeats the attack in an FO-style KEM is that the shared secret is a hash of the recovered message rather than the message itself: the adversary obtains a hash of $rK$, which says nothing about the hash of $K$. Chapter 11 builds the randomized case, where re-encryption does reject.

Tradeoffs across post-quantum deployments

The three primitives are not interchangeable at deployment time.

Primitive	What the receiver ends up with	Classical example	Post-quantum status
Key agreement	A shared secret both parties contributed randomness to	Diffie-Hellman	The Ring-LWE variants in Chapter 9 are not widely deployed as standalone interactive protocols
Public-key encryption	The specific message the sender chose	RSA-OAEP	Post-quantum standards expose KEM APIs rather than direct PKE APIs
KEM	A random symmetric key neither party chose	The toy RSA-KEM above	ML-KEM (Chapter 11) is the finalized standard; HQC (Chapter 21) is selected but not yet published

Two rows of that last column need qualifying. Schemes such as ML-KEM and HQC do contain internal PKE-like components: K-PKE for ML-KEM, and the quasi-cyclic code-based PKE inside HQC. Those components are wrapped into KEMs before they are exposed to protocols, so a deployment never programs against the PKE API. ML-KEM’s standard is FIPS 203, published and final (National Institute of Standards and Technology, 2024). HQC was selected in March 2025 as a backup KEM for future standardization, so it should not be described as a finalized FIPS standard at the time of writing (National Institute of Standards and Technology, 2025a).

IETF working groups are defining ML-KEM key establishment for TLS 1.3, SSH, and IKEv2/IPsec, and the three documents differ in both status and shape. The TLS one finished first: RFC 10024, Standards Track, specifies hybrid NamedGroups. The SSH one followed on 31 August 2026: RFC 10042, Informational, specifies hybrid key-exchange methods instead (Kampanakis et al., 2026; Kwiatkowski et al., 2026). The IKEv2 standards-track draft is the permissive one: it assigns the ML-KEM identifiers and allows ML-KEM alone as well as alongside another exchange, carried by the generic multiple-key-exchange framework of RFC 9370 (Post-Quantum Key Exchange with ML-KEM in the Internet Key Exchange Protocol Version 2 (IKEv2), 2026; Tjhai et al., 2023). Deployment ran ahead of publication rather than following it: Go 1.24 enabled X25519MLKEM768 by default in crypto/tls while the TLS document was still a draft (Valsorda & Shoemaker, 2025). Chapters 27 and 28 walk the TLS 1.3 codepoints and rollout state in detail; neither covers SSH or IKEv2, whose documents are cited here and not developed further in this edition.

The post-quantum standardization effort concentrated on KEMs, not on PKE or interactive key agreement. The reason is that every practical protocol that used to need a key-agreement or PKE primitive (TLS, SSH, IPsec, hybrid public-key encryption stacks) can be rewired to use a KEM with a symmetric cipher on top. KEMs also fit hybrid encryption and one-pass key transport cleanly once the recipient’s encapsulation key is available. In interactive protocols such as TLS, SSH, or IKEv2 they are composed into the existing handshake rather than eliminating interaction altogether. “KEMs are cheaper” is therefore a context-dependent claim, not a universal one: ML-KEM ciphertexts are larger than X25519 key shares, for example. ML-KEM is the first post-quantum KEM standardized by NIST. Its security depends on the Module-LWE assumption Chapter 9 develops and on the Fujisaki-Okamoto transform above (Hofheinz et al., 2017; National Institute of Standards and Technology, 2024).

Where Chapter 5 ends and Chapter 6 picks up

This chapter separated the three confidentiality primitives and put a security definition behind each one. Public-key encryption delivers the message the sender chose; key agreement delivers a secret both sides contributed randomness to; a KEM delivers a random key neither side chose. IND-CCA2 is the bar for the first and the third, and the chapter showed two ways of missing it. Textbook RSA falls to one multiplication by $r^e$, and a KEM built by naively wrapping a merely IND-CPA-secure PKE should not be assumed to clear the bar either. The Fujisaki-Okamoto transform is what closes that gap, and Chapter 11 instantiates it on the Module-LWE-based K-PKE to obtain ML-KEM.

Textbook Diffie-Hellman fails for a different reason, and that reason is the seam into Chapter 6. What breaks it is not the ciphertext-mauling attack that broke the toy KEM; it is the absence of authentication. The man-in-the-middle above breaks no computational assumption, it substitutes Eve’s own public values for Alice’s and Bob’s. Authentication is the signature’s job, and signatures carry their own security definition and their own textbook failures. Chapter 6 states that definition as the EUF-CMA game and forges a textbook RSA signature using the same multiplicative structure this chapter used to maul a ciphertext. It also pays off Chapter 4’s Exercise 4, recovering an ECDSA private key from two signatures that reused a nonce.

Exercises

1. Run the toy DH on a larger prime. Replace $p = 23$ with $p = 2{,}063$, which is prime, and keep $g = 5$. Pick your own secret exponents $a$ and $b$, run the same pow-based exchange, and confirm that alice_shared == bob_shared. Separately compute pow(5, 1031, 2063) and report whether the result is $1$. How large does $p$ need to be before discrete logarithm becomes hard on a classical computer?

2. Round-trip and maul the toy RSA-KEM. Take the toy RSA-KEM snippet above, run encap and decap, and confirm the round-trip. Then try a mauling attack. Take $r = 2$, compute $c' = (c \cdot \mathrm{pow}(r, e, n)) \bmod n$, and run decap(private_key, c_prime). Check that the result is $(r \cdot K) \bmod n$, then recover $K$ as $(\mathrm{decap\_output} \cdot \mathrm{pow}(r, -1, n)) \bmod n$.

   Now show why “any invertible $r \neq 1$” is not good enough. In the CCA game the oracle refuses the challenge ciphertext, so the attack needs $c' \neq c$, and invertibility does not deliver that. Take $K = p$ and pick $r$ by the Chinese remainder theorem with $r \equiv 2 \pmod p$ and $r \equiv 1 \pmod q$. Verify that this $r$ is invertible and is not $1 \bmod n$, then verify that $c' = c$ exactly, so the query is forbidden. Then show that $r = 2$ escapes this for every $K$, and under every valid two-prime RSA key rather than only this one. The property your argument needs is what $e$ being invertible modulo $(p-1)(q-1)$ forces about $\gcd(e, p-1)$ and $\gcd(e, q-1)$.

   Finally, two short answers. Say what extra restriction the same attack needs in the PKE game, where the adversary picks the challenge plaintexts instead of encapsulation sampling $K$. Then explain in two sentences why the attack fails against an $\mathrm{FO}^{\not\perp}$-transformed KEM (the implicit-rejection variant ML-KEM uses).

3. Prove the toy KEM’s correctness, and bound the non-coprime fraction. First, show that decap(private_key, c) == K for every K produced by encap. The clean argument is by the Chinese remainder theorem. Fermat’s little theorem gives $K^{ed} \equiv K \pmod{p}$ and $K^{ed} \equiv K \pmod{q}$, trivially so when $p \mid K$ or $q \mid K$, and CRT lifts the pair to $K^{ed} \equiv K \pmod{pq}$. Euler’s theorem from Chapter 4 covers only the coprime case; CRT closes the remaining residues.

   Second, bound the non-coprime fraction. Use inclusion-exclusion on the sets of $p$-multiples and $q$-multiples in $[1, n-1]$. Show that a uniform $K$ shares a factor with $n = pq$ with probability $(p + q - 2) / (pq - 1) < 1/p + 1/q$, which for the 32-bit primes in the snippet is below $2^{-30}$. Then say what this fraction does not govern. It is not a correctness bound, since the first part showed decap is exact on the whole range. Nor is it the mauling attack’s failure rate: that attack needs its blinding factor $r$ to be invertible, not $K$, and it chooses $r$ deliberately. Which $r$ would you pick, for an RSA modulus, to make the choice trivially safe?

4. State the $\mathrm{FO}^{\not\perp}$ theorem in your own words. Without copying from this chapter, state the inputs, the output, the role of the private seed $z$, the behavior of decapsulation when the re-encryption check fails, the security game, and the assumption on the random oracles. The exercise is not to prove the theorem; it is to produce a statement precise enough that someone else could look up the proof in (Hofheinz et al., 2017).

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

References

Bellare, M., & Rogaway, P. (1994). Optimal asymmetric encryption. Advances in Cryptology – EUROCRYPT 1994, 950, 92–111. https://doi.org/10.1007/BFb0053428

Boneh, D., & Shoup, V. (2023). A Graduate Course in Applied Cryptography (v0.6). Free online textbook. https://toc.cryptobook.us/

Diffie, W., & Hellman, M. E. (1976). New directions in cryptography. IEEE Transactions on Information Theory, 22(6), 644–654. https://doi.org/10.1109/TIT.1976.1055638

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

Fujisaki, E., Okamoto, T., Pointcheval, D., & Stern, J. (2001). RSA-OAEP is secure under the RSA assumption. Advances in Cryptology – CRYPTO 2001, 2139, 260–274. https://doi.org/10.1007/3-540-44647-8_16

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

Kampanakis, P., Stebila, D., & Hansen, T. (2026). Post-Quantum/Traditional Hybrid Key Exchange with the Module-Lattice-Based Key-Encapsulation Mechanism for Use in SSH. RFC 10042, Informational. https://www.rfc-editor.org/rfc/rfc10042.html

Kwiatkowski, K., Kampanakis, P., Westerbaan, B., & Stebila, D. (2026). Post-Quantum Traditional (PQ/T) Hybrid Key Agreement Mechanisms for TLS 1.3. RFC 10024. https://doi.org/10.17487/RFC10024

Moriarty, K., Kaliski, B., Jonsson, J., & Rusch, A. (2016). PKCS #1: RSA Cryptography Specifications Version 2.2. RFC 8017. https://doi.org/10.17487/RFC8017

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). 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

National Institute of Standards and Technology. (2025b). Recommendations for Key-Encapsulation Mechanisms. NIST Special Publication 800-227. https://doi.org/10.6028/NIST.SP.800-227

Post-quantum Key Exchange with ML-KEM in the Internet Key Exchange Protocol Version 2 (IKEv2). (2026). IETF Internet-Draft, draft-ietf-ipsecme-ikev2-mlkem. https://datatracker.ietf.org/doc/draft-ietf-ipsecme-ikev2-mlkem/

Shor, P. W. (1994). Algorithms for quantum computation: discrete logarithms and factoring. Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS), 124–134. https://doi.org/10.1109/SFCS.1994.365700

Shoup, V. (2001). OAEP reconsidered. Advances in Cryptology – CRYPTO 2001, 2139, 239–259. https://doi.org/10.1007/3-540-44647-8_15

Tjhai, C., Tomlinson, M., Bartlett, G., Fluhrer, S., Van Geest, D., Garcia-Morchon, O., & Smyslov, V. (2023). Multiple Key Exchanges in the Internet Key Exchange Protocol Version 2 (IKEv2). IETF RFC 9370. https://doi.org/10.17487/RFC9370

Valsorda, F., & Shoemaker, R. (2025). crypto/tls: enable X25519MLKEM768 by default. golang.org/issue/69985. https://go.dev/issue/69985