Chapter 23 — Quantum and post-quantum security: methods I
Lesson map
Lesson 23 published. Map, example, EX045.
flowchart TD
N0["Learning outcomes"]
N1["23.1 Learning With Errors"]
N2["23.2 Practical activity — Lab W"]
N3["23.3 From LWE to ML-KEM"]
N4["Synthesis"]
N0 --> N1 --> N2 --> N3 --> N4
N4 --> EX["Worked example"]
EX --> Q["Exercise EX045"]
Logical drawing
flowchart LR
N0["Learning outcomes"]
N1["23.1 Learning With Errors"]
N2["23.2 Practical activity — Lab W"]
N3["23.3 From LWE to ML-KEM"]
N4["Synthesis"]
N0 --> N1 --> N2 --> N3 --> N4 --> Q["EX045"]
[Learning outcomes]
|
v
[23.1 Learning With Errors]
|
v
[23.2 Practical activity — Lab W]
|
v
[23.3 From LWE to ML-KEM]
|
v
[Synthesis]
|
v
[Worked example] --> [Exercise EX045]
Learning outcomes
You will (1) state the Learning With Errors (LWE) problem; (2) run a toy LWE encryption and explain why decryption works; (3) describe how ML-KEM turns this idea into a KEM; and (4) explain parameter sets and security categories.
23.1 Learning With Errors
Given a random matrix A modulo q and a vector b = As + e, where s is secret and e is a vector of small random errors, recover s. Without e, Gaussian elimination solves the system quickly. With e, the best known classical and quantum algorithms take time exponential in the dimension, because the problem becomes one of finding short vectors in high-dimensional lattices. Regev (2009) introduced LWE and showed its hardness relates to worst-case lattice problems. ML-KEM uses a structured variant, Module-LWE, over the polynomial rings of Chapter 6.
23.2 Practical activity — Lab W
# Lab W (ch 23): 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)
To encrypt a bit, add a random subset of the rows; the accumulated noise stays small, while the bit is placed at q/2. The decryptor removes the s-dependent part and checks whether the remainder is nearer 0 or q/2. The parameters here are toys — a 16-dimensional secret is easy to recover — and serve only to show the mechanism.
Running the lab several times with different random choices shows that decryption still succeeds, because the noise stays below the threshold.
23.3 From LWE to ML-KEM
ML-KEM (FIPS 203) uses Module-LWE with 256-coefficient polynomials, compresses ciphertexts, and wraps the encryption in a transform (a variant of Fujisaki–Okamoto) so that decapsulation re-encrypts and checks the ciphertext, which protects against chosen-ciphertext attacks. The interface is a KEM: KeyGen produces an encapsulation key and decapsulation key; Encaps produces a ciphertext and a 32-byte shared secret; Decaps recovers the secret. Parameter sets ML-KEM-512, -768 and -1024 target NIST categories 1, 3 and 5. Encapsulation keys are 800, 1,184 and 1,568 bytes; ciphertexts 768, 1,088 and 1,568 bytes.
23.4 Worked example
HCU chooses ML-KEM-768 for hybrid key exchange because category 3 offers a margin above AES-128-equivalent security, it is the parameter set used by the widely deployed X25519MLKEM768 TLS group, and its 1,184-byte key fits typical handshakes. ML-KEM-1024 is reserved for any partner whose rules demand category 5.
The choice is recorded with its reasons so it can be revisited if guidance changes. Larger keys and ciphertexts were measured in the lab before the choice was confirmed, and the branch links handled them without changes to the network.
23.5 Common errors and limits
- Thinking the toy lab's parameters are secure.
- Forgetting that ML-KEM is a KEM, not a general encryption function.
- Choosing parameters by size alone without considering policy requirements.
The toy parameters are chosen so that a reader can follow the arithmetic, which means an attacker could too. A KEM produces a shared secret that a symmetric cipher then uses; it does not encrypt arbitrary messages directly. Parameter choice depends on security category, policy and protocol support, as well as size. A smaller set may suit most uses, but a partner's rules can require a larger one regardless of performance.
Exercises
- EX045 — Why noise matters. Explain in three sentences why LWE without error is easy and with error is believed hard. Rubric: 3 = linear algebra versus lattice short-vector argument.
- EX046 — Parameter choice. HCU's partner requires category 5 for key establishment. Which ML-KEM set, and how many bytes are the encapsulation key and ciphertext? Rubric: 3 = ML-KEM-1024, 1,568 and 1,568 bytes.
Synthesis
LWE hides a secret under small noise; ML-KEM builds an efficient, chosen-ciphertext-secure KEM on its module variant, with three parameter sets mapped to NIST categories.
Continue studying — chapter 23 of 40
← Chapter 22 (draft) · Course chapter index · Chapter 24 (draft) →