◇ OpenCyber Academy
Engineering · Chapter 24 · English

Chapter 24 — Quantum and post-quantum security: methods I

Open, free learning for anyone who wants to protect people and technology. No account is required to read this text or its worked answers.

Chapter 24 — Quantum and post-quantum security: methods I

Lesson map

Lesson 24 published. Map, example, EX047.

flowchart TD
  N0["Learning outcomes"]
  N1["24.1 Learning with errors"]
  N2["24.2 Encrypting one bit"]
  N3["24.3 Practical activity — Lab W toy, insecure"]
  N4["24.4 From toy to ML-KEM"]
  N5["Synthesis"]
  N0 --> N1 --> N2 --> N3 --> N4 --> N5
  N5 --> EX["Worked example"]
  EX --> Q["Exercise EX047"]

Logical drawing

flowchart LR
  N0["Learning outcomes"]
  N1["24.1 Learning with errors"]
  N2["24.2 Encrypting one bit"]
  N3["24.3 Practical activity — Lab W toy, insecure"]
  N4["24.4 From toy to ML-KEM"]
  N5["Synthesis"]
  N0 --> N1 --> N2 --> N3 --> N4 --> N5 --> Q["EX047"]

[Learning outcomes]
    |
    v
[24.1 Learning with errors]
    |
    v
[24.2 Encrypting one bit]
    |
    v
[24.3 Practical activity — Lab W toy, insecure]
    |
    v
[24.4 From toy to ML-KEM]
    |
    v
[Synthesis]
    |
    v
[Worked example] --> [Exercise EX047]

Learning outcomes

You will (1) explain learning with errors (LWE) and why noise makes linear algebra hard; (2) follow a toy LWE encryption; (3) relate it to ML-KEM's structure; and (4) understand the role of the Fujisaki–Okamoto transform. It builds on Chapter 2 and grounds design choices in Chapters 25–28.

24.1 Learning with errors

Given a random matrix A and b = A·s + e mod q, where s is secret and e is a vector of small random errors, find s. Without e this is Gaussian elimination. With e, no efficient classical or quantum algorithm is known for suitable parameters; Regev (2009) related LWE to worst-case lattice problems. Best attacks use lattice reduction, whose cost grows exponentially in dimension.

The role of the noise can be seen in the dimension: in Lab W, sixteen unknowns with small errors are easy to solve by brute force on the errors, while ML-KEM-768 works with dimension 768, where the best lattice reduction attacks need far more work than any computer can perform.

24.2 Encrypting one bit

To encrypt a bit, sum a random subset of rows of (A, b): u = ΣrᵢAᵢ, v = Σrᵢbᵢ + bit·⌊q/2⌋. The key holder computes v − ⟨u, s⟩ = bit·⌊q/2⌋ + small noise and rounds. Decryption works while the accumulated noise stays below q/4.

In Lab W the errors are at most 2 in absolute value and the subset has at most 64 rows, so the accumulated noise is at most 128. That is far below q/4, which is about 832, so every bit decrypts correctly. Larger errors or more rows would push the noise toward q/4 and cause failures, which is the trade-off ML-KEM's parameters balance against security.

24.3 Practical activity — Lab W (toy, insecure)

# Lab W (ch 24): 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)

These parameters are far too small for security and leak through many routes; the lab exists only to make the algebra concrete.

The result of 2000 out of 2000 follows from the bound: noise at most 128 can never cross the 832 threshold. Change small() to draw from −20 to 20 and rerun; the worst-case noise rises to 1,280, above the threshold, yet all 2000 bits still decrypt, because a sum of about 32 random errors rarely approaches its worst case; failures appear only with much larger errors, as Exercise EX047 shows. Then change it to always return 0 and solve for s from sixteen rows of A and b by Gaussian elimination, which shows that the errors carry the security.

24.4 From toy to ML-KEM

ML-KEM replaces integers with polynomials in Z₃₃₂₉[x]/(x²⁵⁶+1) and uses module structure (k = 2, 3 or 4 polynomial vectors) for compact keys, compresses ciphertexts, samples noise from a centred binomial distribution and derives randomness with SHAKE. The underlying public-key encryption is only secure against passive attackers; ML-KEM applies a Fujisaki–Okamoto-style transform — re-encrypting during decapsulation and returning a pseudo-random "implicit rejection" key on mismatch — to resist chosen-ciphertext attacks (FIPS 203).

Each change has a purpose: polynomials and modules shrink keys, compression saves bytes, and the transform resists active attacks.

24.5 Worked example

A BPA engineer asks why ML-KEM decapsulation re-encrypts. Answer: to detect manipulated ciphertexts. Without that check, an attacker could submit crafted ciphertexts and learn about the secret key from whether decryption succeeds. Implementations must perform the comparison in constant time, or the timing of the check leaks the same information.

The implicit rejection key also matters: returning an error on mismatch would itself tell the attacker the ciphertext was invalid. By returning a pseudo-random key derived from a secret value, ML-KEM makes the invalid case look like a normal success to the attacker, and the protocol fails later in a way that reveals nothing about the key.

24.6 Common errors and limits

Lab W shows the first point directly: remove the errors and the secret falls to Gaussian elimination. The passive-secure scheme without the transform is open to the chosen-ciphertext attacks the worked example described. The toy uses dimension sixteen and no compression, so it offers no security at all, and its only use is teaching.

Exercises

Synthesis

LWE hides secrets under noise; a toy shows decryption as rounding; ML-KEM adds ring/module structure, compression and the FO transform for chosen-ciphertext security.

Continue studying — chapter 24 of 50

← Chapter 23 (draft) · Course chapter index · Chapter 25 (draft) →