A KEM establishes secret material — nothing more. The surrounding protocol decides whose key was used, what the secret means, and whether the peer actually possesses it. Understanding that boundary is exactly as important as understanding the lattice arithmetic underneath. This chapter traces ML-KEM's exact interface, the internal K-PKE encryption engine, the Fujisaki-Okamoto-style transform that turns it into a chosen-ciphertext-secure KEM, implicit rejection's precise meaning, and a reproducible native OpenSSL lab whose exact results are reported below — not invented.
1. What you will learn
Parts 2 and 6 supplied the prerequisites: authenticated encryption, KDFs, noisy linear systems, polynomial rings, and Module-LWE. This chapter connects those pieces to ML-KEM's public interface and internal construction. You'll be able to trace key generation, encapsulation, decapsulation, and failure handling; distinguish raw algorithm sizes from encoded file sizes; and reproduce both successful and unsuccessful exchanges yourself.
The reference is FIPS 203, finalized August 13, 2024. Its publication page currently links potential errata — as checked for this chapter, those clarify the NTT constants array and a decryption comment referring to the wrong polynomial. These are potential corrections to documentation, not a replacement algorithm and not a license to silently invent a variant.
2. The interface: create a key, encapsulate, recover
A KEM has three operations. KeyGen produces an encapsulation key \(ek\) and a secret decapsulation key \(dk\). Encaps takes \(ek\) and fresh randomness, returning a ciphertext \(c\) and a shared secret \(K\). Decaps takes \(dk\) and \(c\), returning a shared secret. Correctly generated inputs produce matching secrets except with the construction's extremely small failure probability.
The names prevent a common misunderstanding: encapsulation does not accept an arbitrary application message to encrypt — it creates fresh secret material. To protect a file, a protocol derives encryption keys from that material and applies a separate authenticated-encryption scheme (Part 2 §6). The KEM ciphertext transports what's needed for recovery; it is never the file ciphertext itself.
Fig. 1 — The "authenticated" arrow is a protocol requirement, not something ML-KEM's math provides. An attacker who substitutes their own ek establishes their own secret with the sender — certificates or a separately provisioned trust relationship must supply that binding (Part 2 §11).
Key confirmation is another layer entirely. A recovered byte string alone does not establish that the peer derived the same value — a protocol normally demonstrates possession through a transcript authenticator or authenticated data. NIST's final SP 800-227 describes KEM usage considerations in depth; implementing the primitive correctly is only one component of using it securely.
3. Three parameter sets, exact byte counts
These are the raw encodings specified by FIPS 203 — not the size of an ASN.1 container or a PEM file. All three parameter sets return 32-byte shared secrets.
| Parameter set | NIST category | Encapsulation key | Decapsulation key | Ciphertext |
|---|---|---|---|---|
| ML-KEM-512 | 1 | 800 bytes | 1,632 bytes | 768 bytes |
| ML-KEM-768 | 3 | 1,184 bytes | 2,400 bytes | 1,088 bytes |
| ML-KEM-1024 | 5 | 1,568 bytes | 3,168 bytes | 1,568 bytes |
The numeric suffix is a parameter-set identifier — it is not the length of the shared secret, nor a claim of 512, 768, or 1,024 "security bits." NIST's categories compare attack costs against reference primitives under a specific framework; they are not exact universal quantum work factors. A system selects a parameter set according to its protocol profile, policy, performance budget, and implementation support — not by picking the biggest number available.
The degree \(n\) is 256 and modulus \(q\) is 3,329 for every one of the three sets (Part 6 §8). The module rank \(k\) grows from 2 to 3 to 4. Increasing \(k\) changes the number of polynomial components and the resulting attack landscape. Compression parameters and noise choices also differ between sets — changing only the rank in homemade code does not reproduce another standardized set.
For example: the encapsulation key contains \(k\) encoded polynomials plus a 32-byte matrix seed. At 12 bits per coefficient, one 256-coefficient polynomial occupies 384 bytes. Thus ML-KEM-768 uses \(3 \times 384 + 32 = 1{,}184\) bytes — this calculation explains a table entry without confusing mathematical storage with an implementation's expanded in-memory representation.
4. Inside the key: a compact public matrix and noisy secret
The internal K-PKE key-generation procedure expands a seed into a public matrix \(A\) and samples short secret and error vectors \(s\) and \(e\). Conceptually it forms \(t = As+e\) in the polynomial module (exactly Part 6 §5–6's cancellation mechanism, now over polynomials). Public material includes \(t\) and the seed needed to regenerate \(A\); secret material retains \(s\). The actual algorithm specifies transform representation, domain-separated hash expansion, byte encoding, and exact sampling routines that this sketch omits.
A public seed is not a weak secret — its role is reproducibly generating public coefficients without ever shipping the whole matrix. Conversely, secret noise must follow the exact specified distribution and randomness requirements; replacing that sampler with convenient small integers changes the scheme and invalidates its security argument entirely.
The NTT accelerates polynomial products (Part 6 §11). ML-KEM's modulus lacks the primitive 512th root needed for a simple, fully-split negacyclic scalar transform of this length — its transform instead ends in degree-two components. A scalar pointwise-multiplication toy from a different modulus (like Part 6's) is useful for intuition, but copying that toy directly would produce incorrect ML-KEM arithmetic.
5. K-PKE: the internal encryption engine
K-PKE encrypts a 32-byte internal message using specified coins. In a schematic coefficient-domain description, it samples an ephemeral short vector \(r\) and errors \(e_1\), \(e_2\), then forms \(u\) from \(A^T r + e_1\) and \(v\) from \(t^T r + e_2\) plus the encoded message. Compression reduces the transmitted coefficient widths and adds a bounded rounding error on top.
The receiver computes a value corresponding to \(v - s^T u\). Substituting \(t=As+e\) cancels the main product and leaves the message embedding plus accumulated noise — decompression and message decoding recover the bits when that noise stays within the allowed margin. This explanation intentionally omits implementation details like transform-domain storage; the standard's algorithms remain authoritative for those.
6. From encryption to a chosen-ciphertext-secure KEM
The construction follows the broad Fujisaki–Okamoto transformation idea: derive encryption randomness from a candidate message, then verify recovery by reconstructing its ciphertext. This binds a recovered message to the exact encapsulation procedure. The specific transformation matters a great deal here; this conceptual description is not a generic recipe for wrapping an arbitrary encryption scheme.
The following pseudocode summarizes FIPS 203's internal flow. \(H\), \(G\), and \(J\) denote distinct hash/XOF roles defined in the standard. Concatenation is written \(||\). Public wrappers perform required input checks and obtain approved randomness before calling these internal functions.
KeyGen_internal(d, z):
ekPKE, dkPKE = K-PKE.KeyGen(d)
ek = ekPKE
dk = dkPKE || ek || H(ek) || z
return ek, dk
Encaps_internal(ek, m):
K, r = G(m || H(ek))
c = K-PKE.Encrypt(ek, m, r)
return K, c
Decaps_internal(dk, c):
parse dk into dkPKE, ek, h, z
m_recovered = K-PKE.Decrypt(dkPKE, c)
K_candidate, r = G(m_recovered || h)
K_fallback = J(z || c)
c_reconstructed = K-PKE.Encrypt(ek, m_recovered, r)
return constant_time_select(c == c_reconstructed,
K_candidate, K_fallback)Key generation uses independently generated 32-byte inputs \(d\) and \(z\); encapsulation generates a fresh 32-byte \(m\). These are cryptographic random inputs, never passwords, timestamps, or application identifiers. Decapsulation itself does not request fresh randomness — its fallback secret derives entirely from a secret value retained in the decapsulation key plus the received ciphertext.
Notice that the decapsulation key includes the encapsulation key and its hash, not just the lattice secret — that explains much of its larger serialized size (§3) and enables re-encryption without asking the application to supply another public key. Applications should treat the complete decapsulation-key encoding as secret material, including any seed representation their library supports.
7. Implicit rejection and the meaning of "success"
For a correctly sized but invalid ciphertext, decapsulation returns a pseudorandom fallback secret rather than exposing an explicit validity flag. An attacker must not learn whether the internal re-encryption comparison succeeded — secret-dependent timing, error messages, or follow-on behavior can undermine this protection even when the code returns a 32-byte buffer every single time.
This does not mean all malformed inputs are quietly accepted. External validation still checks ciphertext lengths, encapsulation-key encoding and modulus requirements, and decapsulation-key structure and hash consistency exactly as specified — a truncated ciphertext still produces an ordinary input error. The protected distinction is specifically the internal validity decision for an otherwise admissible ciphertext.
Operational code must check API return values, output lengths, and protocol authentication separately. It must also avoid recording the candidate secret, fallback secret, recovered internal message, or comparison flag in debug logs — failure telemetry can count public input errors and handshake failures without retaining information that turns diagnostics into a decryption oracle.
8. A reproducible native OpenSSL experiment
This lab was executed on macOS ARM64 using an isolated OpenSSL 3.5.8 build, using the native implementation documented in OpenSSL's ML-KEM manual and pkeyutl reference. Set OPENSSL to the exact executable you intend to test, and inspect its version before assuming a system command supports these algorithms at all.
The following script creates disposable keys, confirms agreement, flips one ciphertext bit, and separately truncates a ciphertext. It prints no secret bytes. Temporary-directory permissions reduce accidental exposure, while deletion afterward is ordinary cleanup, not a guarantee of forensic erasure on every filesystem.
#!/usr/bin/env bash
set -euo pipefail
OPENSSL=${OPENSSL:-openssl}
LAB=$(mktemp -d)
trap 'rm -rf "$LAB"' EXIT
umask 077
cd "$LAB"
"$OPENSSL" version
"$OPENSSL" genpkey -algorithm ML-KEM-768 -out private.pem
"$OPENSSL" pkey -in private.pem -pubout -out public.pem
"$OPENSSL" pkeyutl -encap -pubin -inkey public.pem -out ciphertext.bin -secret sender.bin
"$OPENSSL" pkeyutl -decap -inkey private.pem -in ciphertext.bin -secret recipient.bin
cmp sender.bin recipient.bin
python3 - <<'PY'
from pathlib import Path
c = bytearray(Path('ciphertext.bin').read_bytes())
assert len(c) == 1088
assert len(Path('sender.bin').read_bytes()) == 32
c[0] ^= 1
Path('corrupted.bin').write_bytes(c)
Path('truncated.bin').write_bytes(c[:-1])
PY
"$OPENSSL" pkeyutl -decap -inkey private.pem -in corrupted.bin -secret rejected.bin
if cmp -s sender.bin rejected.bin; then
echo 'Unexpected matching secret after corruption' >&2; exit 1
fi
if "$OPENSSL" pkeyutl -decap -inkey private.pem -in truncated.bin -secret unused.bin 2>error.log; then
echo 'Unexpected acceptance of truncated ciphertext' >&2; exit 1
fi
printf '%s\n' 'PASS: agreement, 1088-byte ciphertext, 32-byte secret, implicit rejection, length rejection'Repeat the experiment using the other parameter names and their expected ciphertext lengths from §3. Keep raw standard sizes separate from PEM byte counts — a PEM object includes encoding and headers; an implementation may store a seed or expanded private material in its own supported container. File size alone cannot validate a standardized raw-key representation.
9. CPU, memory, and integration costs
Polynomial multiplication, sampling, hashing, and encoding all consume time. Optimized vector instructions can accelerate arithmetic, but performance depends on architecture, compiler, provider, and whether keys or expanded matrices are cached. A command-line measurement also includes process startup and file parsing, which may dominate a genuinely short cryptographic operation — Part 14 covers fair benchmark methodology in full.
Memory planning must include more than the serialized private key. Expanded matrices, intermediate polynomial vectors, transform buffers, thread-local state, and temporary hash contexts all affect stack and heap usage. A high-concurrency service multiplies some of these costs by the number of simultaneous operations; an embedded device may care more about peak stack usage than average CPU time.
Decapsulation requires particular care because attackers influence its input while it processes long-lived secret material. Constant-time comparisons and selections, fixed arithmetic paths where required, compiler review, and architecture-specific testing are all part of the implementation obligation here. The KyberSlash research illustrates how seemingly routine integer operations can create exploitable timing leakage in implementations of this exact algorithm family — Part 13 covers this class of bug in depth.
Protocol integration adds another cost dimension: an encapsulation key and ciphertext must fit the handshake framing and transport behavior. TLS hybrid groups (Part 11) specify exactly how classical and ML-KEM contributions are encoded and combined together. Concatenating secrets in an application and choosing a KDF informally is not equivalent to following that protocol construction.
10. Key lifetime and forward secrecy
A static recipient decapsulation key is convenient for asynchronous delivery, but its later compromise can expose earlier ciphertexts an adversary recorded (harvest-now-decrypt-later, Part 1 §5). ML-KEM alone does not make those historical exchanges forward secret — ephemeral key establishment, deletion of ephemeral secrets, or a ratcheting protocol can change that exposure, provided the complete protocol actually establishes the claimed property.
Consider an archival upload service. If every upload encapsulates to one permanent server key, protecting that key today is essential but does not eliminate future compromise risk. If the service instead rotates keys daily but retains every old private key indefinitely for recovery purposes, the effective compromise window still covers all those retained keys — rotation schedules and actual deletion policies must agree with each other, or rotation is theater.
A threat model should therefore name the lifetime of decapsulation keys, shared secrets, derived traffic keys, backups, and diagnostic artifacts separately. Testing a fresh exchange after rotation does not demonstrate that historical material was actually retired. This distinction becomes especially important comparing a one-shot KEM exchange against the recurring key updates of a messaging protocol like Signal's.
11. Review questions and engineering decisions
Before approving an integration, answer four concrete questions: Where does the authenticated encapsulation key come from? Which protocol-defined KDF consumes the shared secret? What demonstrates the peer derived the same keys? What happens when input parsing, decapsulation, or the later authentication step fails? Each answer should point to an implemented mechanism and a test, not a plan.
Also be able to explain why an invalid ciphertext may return a secret without an error, and why this doesn't make it valid (§7); why replacing randomness with a fixed seed for reproducibility is acceptable only inside an explicitly controlled test (§6); and why the "768" suffix does not describe a 768-bit output (§3). These distinctions prevent more real integration mistakes than memorizing the size table alone.
For a small project, extend §8's lab into a test harness that records only algorithm name, binary version, input lengths, and pass/fail outcomes. Add wrong-key decapsulation, multiple independent exchanges, and malformed-key tests through supported library interfaces. Don't expose the internal validity decision to make testing easier — test public behavior and final key confirmation instead, exactly as a real attacker would be limited to.
Does ML-KEM authenticate the peer's public key?
No (§2). Certificates, an authenticated handshake, or a separately provisioned trust relationship must supply that binding — ML-KEM's math establishes a shared secret between whoever holds each key pair, with no opinion on who that should be.
If decapsulation "succeeds" on a corrupted ciphertext, was the exchange compromised?
No (§7). Implicit rejection returns a pseudorandom fallback secret specifically so an attacker can't distinguish valid from invalid ciphertexts by timing or behavior. The two endpoints simply end up with different secrets, and the protocol's own authentication step should then fail downstream.
Does a bigger ML-KEM parameter set (1024 vs 512) always mean more security bits?
The numeric suffix is a parameter-set identifier tied to a NIST security category, not a literal bit count (§3). Larger parameter sets do target higher NIST categories, but the number itself isn't the quantum work factor.
Takeaways
- A KEM establishes secret material only — it doesn't authenticate anyone. The protocol wrapping ML-KEM has to supply key authentication and key confirmation separately.
- ML-KEM = K-PKE (§5) + a Fujisaki-Okamoto-style transform (§6) + implicit rejection (§7). K-PKE alone is not a secure standalone API — the wrapping is what achieves chosen-ciphertext security.
- Implicit rejection means "decapsulation returned output" ≠ "the exchange succeeded." A pseudorandom fallback secret on invalid input is the specified, correct behavior, not a bug.
- The reproducible lab (§8) passed all five checks on real hardware — agreement, correct sizes, corruption detection via mismatched secrets, and explicit truncation rejection — functional evidence, not a conformance certificate.
- KyberSlash-class timing bugs live in "seemingly routine" integer operations in decapsulation specifically, because that's where attacker-influenced input meets long-lived secret material.
- Key rotation without an actual deletion policy doesn't reduce the compromise window — the threat model has to name key/secret/backup lifetimes separately and verify old material is actually gone.
References & further reading
- FIPS 203 (ML-KEM) · publication page (errata) — the primary standard for this entire chapter.
- NIST SP 800-227 — §2, KEM usage considerations beyond the primitive.
- OpenSSL ML-KEM manual · pkeyutl reference — §8, the lab commands.
- KyberSlash research — §9, real timing-leak case study.