Chapter 10 — Quantum and post-quantum security: orientation
Lesson map
Lesson 10 published. Map, example, EX019.
flowchart TD
N0["Learning outcomes"]
N1["10.1 Standards"]
N2["10.2 The idea underneath ML-KEM"]
N3["10.3 Interface and parameters"]
N4["10.4 Implementer rules"]
N5["10.7 Signatures in one paragraph"]
N6["Synthesis"]
N0 --> N1 --> N2 --> N3 --> N4 --> N5 --> N6
N6 --> EX["Worked example"]
EX --> Q["Exercise EX019"]
Logical drawing
flowchart LR
N0["Learning outcomes"]
N1["10.1 Standards"]
N2["10.2 The idea underneath ML-KEM"]
N3["10.3 Interface and parameters"]
N4["10.4 Implementer rules"]
N5["10.7 Signatures in one paragraph"]
N6["Synthesis"]
N0 --> N1 --> N2 --> N3 --> N4 --> N5 --> N6 --> Q["EX019"]
[Learning outcomes]
|
v
[10.1 Standards]
|
v
[10.2 The idea underneath ML-KEM]
|
v
[10.3 Interface and parameters]
|
v
[10.4 Implementer rules]
|
v
[10.7 Signatures in one paragraph]
|
v
[Synthesis]
|
v
[Worked example] --> [Exercise EX019]
Learning outcomes
You will (1) summarise NIST's post-quantum standards and their status; (2) explain LWE with a toy lab; (3) describe ML-KEM's interface and parameter sets; and (4) state what implementers must and must not do with PQC.
10.1 Standards
NIST published FIPS 203 (ML-KEM), FIPS 204 (ML-DSA) and FIPS 205 (SLH-DSA) in August 2024; SP 800-208 covers LMS and XMSS; SP 800-227 gives KEM recommendations. NIST's draft IR 8547 proposes deprecating quantum-vulnerable algorithms after 2030 and disallowing them after 2035. FN-DSA and an HQC-based KEM were in development.
For KLS implementers, the practical reading is: ML-KEM for key establishment now, ML-DSA for signatures as tooling allows, hash-based signatures for firmware, and dates from the draft IR 8547 as planning assumptions until finalised.
10.2 The idea underneath ML-KEM
Learning With Errors (Regev, 2009) hides a secret in noisy linear equations.
# Lab W (ch 10): a TOY Regev-style LWE encryption of one bit. Deliberately insecure parameters.
import random
rng = random.Random(5)
n, q, m = 16, 3329, 64
def small(): return rng.choice([-2, -1, 0, 1, 2])
s = [rng.randrange(q) for _ in range(n)]
A = [[rng.randrange(q) for _ in range(n)] for _ in range(m)]
b = [(sum(A[i][j] * s[j] for j in range(n)) + small()) % q for i in range(m)] # b = A s + e
def enc(bit):
r = [rng.randrange(2) for _ in range(m)] # random subset
u = [sum(r[i] * A[i][j] for i in range(m)) % q for j in range(n)]
v = (sum(r[i] * b[i] for i in range(m)) + bit * (q // 2)) % q
return u, v
def dec(u, v):
d = (v - sum(u[j] * s[j] for j in range(n))) % q # = bit*q/2 + small noise
return 1 if q // 4 < d < 3 * q // 4 else 0
ok = sum(dec(*enc(bit)) == bit for bit in [rng.randrange(2) for _ in range(2000)])
print(f"toy LWE: {ok}/2000 bits decrypted correctly (noise stays below q/4)")
Expected output:
toy LWE: 2000/2000 bits decrypted correctly (noise stays below q/4)
The toy uses 16 dimensions and is trivially breakable; ML-KEM uses structured module lattices with 256-coefficient polynomials and a transform that protects against chosen-ciphertext attacks.
The lab's design makes the decryption rule visible. The ciphertext value v carries the bit as either 0 or q/2, about 1,664, plus the accumulated noise from adding up to 64 small errors chosen in {−2,…,2}. Decryption subtracts u·s and asks whether the remainder is nearer 0 or q/2. Because the noise is far below q/4, every one of the 2,000 bits decrypts correctly. Larger error ranges or more summed rows would push noise over that threshold and decryption would start to fail, the same trade-off ML-KEM's parameters are chosen to manage.
10.3 Interface and parameters
ML-KEM is a KEM: KeyGen → (encapsulation key, decapsulation key); Encaps(ek) → (ciphertext, 32-byte shared secret); Decaps(dk, ct) → shared secret. ML-KEM-512/768/1024 target NIST categories 1/3/5, with encapsulation keys of 800/1,184/1,568 bytes and ciphertexts of 768/1,088/1,568 bytes. X25519MLKEM768 in TLS uses ML-KEM-768.
For implementers the interface matters more than the mathematics. The client generates a key pair and sends the encapsulation key; the server encapsulates and returns the ciphertext; both obtain the same 32-byte secret. There is no message encryption step, so ML-KEM is always paired with a symmetric cipher.
10.4 Implementer rules
Use vetted libraries and platform providers; never write your own. Keep libraries updated (KyberSlash showed timing leaks in some implementations; Bernstein et al., 2024). Prefer hybrids during transition. Check lengths and handle errors without leaking detail. Record algorithm and library versions in the inventory.
At KLS these rules become review questions on every pull request touching cryptography: which library and version, is it on the approved list, is the parameter set explicit, and what happens on malformed input. A pull request that answers "we wrote it ourselves" is closed without further review.
10.5 Worked example
A KLS developer proposes a home-grown ML-KEM in Python "for the scanners". Response: rejected — the standard library lacks ML-KEM, toy code is unsafe, and the vendor's image or a vetted library is the only acceptable route; meanwhile the scanners' data flows are minimised.
The minimisation step is concrete: the scanners upload manifests in one daily batch instead of per scan, which reduces the volume of harvestable sessions while the vendor's image is pending. The rejection and the interim control are both recorded in the scanner's inventory row with the vendor ticket number.
10.6 Common errors and limits
- Treating the toy lab as usable.
- Using ML-KEM as if it encrypted arbitrary messages.
- Ignoring library update advisories.
Each error has a recognisable symptom. Someone pasting Lab W's 16-dimensional code into a service, believing it is "lattice crypto", has shipped something breakable in seconds. Someone calling ML-KEM to "encrypt the manifest" has misread the interface: it only produces a shared secret for a symmetric cipher. And a team ignoring advisories such as KyberSlash keeps a timing leak that a library update would have removed. The orientation here is deliberately shallow; the standards themselves are the authority.
10.7 Signatures in one paragraph
ML-DSA (FIPS 204) is the general-purpose lattice signature, with ML-DSA-44/65/87 signatures of 2,420/3,309/4,627 bytes. SLH-DSA (FIPS 205) relies only on hash functions; its public keys are tiny but its signatures run from 7,856 to 49,856 bytes. LMS and XMSS (SP 800-208) are compact hash-based signatures that require the signer to track state and never reuse an index. Implementers will meet ML-DSA in certificates and code signing first, and hash-based schemes in firmware signing.
For KLS that means ML-DSA for the internal CA and release signing, and LMS for scanner firmware only if the vendor's HSM manages state.
Exercises
- EX019 — Sizes. Give the ML-KEM-768 encapsulation key and ciphertext sizes and the shared secret length. Rubric: 3 = 1,184, 1,088 and 32 bytes.
- EX020 — Rules. List four implementer rules for PQC. Rubric: 3 = vetted libraries, updates, hybrids, length/error handling.
Synthesis
NIST's standards define the replacements; ML-KEM is a KEM on module lattices with three parameter sets. Implementers configure vetted implementations, never build their own.
Continue studying — chapter 10 of 30
← Chapter 09 (draft) · Course chapter index · Chapter 11 (draft) →