Lesson 25: Post-Quantum Cryptography: Kyber and Quantum-Resistant Signatures¶
25.1 Learning Outcomes¶
By the end of this hour a student will be able to:
- Explain which cryptographic primitives quantum computers break and which survive.
- State the lattice problems SVP, CVP, LWE and Module-LWE and why they are believed quantum-hard.
- Describe CRYSTALS-Kyber (ML-KEM): key generation, encapsulation, decapsulation and parameters.
- Describe ML-DSA (Dilithium), SLH-DSA (SPHINCS+) and FN-DSA (Falcon) and compare them.
- Plan a migration strategy, including hybrid modes and crypto-agility.
25.2 What Breaks and What Survives¶
| Primitive | Hard problem | Quantum attack | Status |
|---|---|---|---|
| RSA | integer factoring | Shor — polynomial | broken |
| Diffie–Hellman | discrete log mod \(p\) | Shor — polynomial | broken |
| ECDSA / ECDH | elliptic-curve discrete log | Shor — polynomial (fewer qubits than RSA!) | broken |
| DSA | discrete log | Shor | broken |
| AES-128 | key search | Grover — \(2^{64}\) | weakened |
| AES-256 | key search | Grover — \(2^{128}\) | safe |
| SHA-256/384 | preimage | Grover — \(2^{128}/2^{192}\) | safe |
| Lattice problems | SVP/CVP/LWE | none known | believed safe |
| Hash-based signatures | hash security only | Grover only | safe (most conservative) |
| Code-based (McEliece) | syndrome decoding | none known | believed safe |
The asymmetry. Symmetric cryptography survives by doubling parameters. All deployed public-key cryptography must be replaced.
Elliptic curves fall first. Breaking a 256-bit ECC key needs about 2330 logical qubits, versus ~4100 for RSA-2048 — because the group order is much smaller. Ironically, the "stronger" modern choice is the easier quantum target.
25.3 The NIST Standards (August 2024)¶
After an eight-year competition (2016–2024), NIST published:
| FIPS | Name | Original | Purpose | Basis |
|---|---|---|---|---|
| 203 | ML-KEM | CRYSTALS-Kyber | key encapsulation | Module-LWE (lattices) |
| 204 | ML-DSA | CRYSTALS-Dilithium | signatures (primary) | Module-LWE/SIS |
| 205 | SLH-DSA | SPHINCS+ | signatures (backup) | hash functions only |
| (2025) | FN-DSA | Falcon | signatures (compact) | NTRU lattices |
Also standardised for stateful use: XMSS and LMS (RFC 8391/8554) for firmware signing.
HQC (code-based) was selected in March 2025 as a backup KEM with a different mathematical foundation from lattices — insurance against a lattice breakthrough.
25.4 Lattice Cryptography¶
Lattices¶
Definition. Given linearly independent \(\vec b_1,\dots,\vec b_n\in\mathbb{R}^{n}\), the lattice they generate is
— a regular grid of points, infinite in extent but discrete.
Hard problems.
| Problem | Statement | Best known |
|---|---|---|
| SVP (shortest vector) | find the shortest non-zero \(\vec v\in\mathcal L\) | \(2^{\Theta(n)}\) classically and quantumly |
| CVP (closest vector) | given \(\vec t\notin\mathcal L\), find the nearest lattice point | \(2^{\Theta(n)}\) |
| SIS (short integer solution) | find short \(\vec z\) with \(A\vec z\equiv 0 \bmod q\) | \(2^{\Theta(n)}\) |
Why lattices resist quantum attack. Shor's algorithm solves the abelian Hidden Subgroup Problem. Lattice problems reduce to the dihedral HSP, which is non-abelian. The best known quantum algorithm (Kuperberg's sieve) runs in \(2^{O(\sqrt n)}\) — sub-exponential but still exponential, and it does not translate into a practical attack on the parameters in use.
Lattices also enjoy worst-case to average-case reductions (Ajtai 1996; Regev 2005): breaking a random instance is as hard as solving the worst case, an unusually strong security guarantee that RSA does not have.
Learning With Errors (LWE)¶
Definition (Search-LWE). Fix a secret \(\vec s\in\mathbb{Z}_q^{n}\). Given many samples
with \(\vec a_i\) uniform and \(e_i\) small "noise" drawn from a narrow distribution, recover \(\vec s\).
Without the noise this is just a linear system, solved instantly by Gaussian elimination. The small errors make it hard — Gaussian elimination amplifies them catastrophically.
Definition (Decision-LWE). Distinguish LWE samples from uniform random pairs. Regev proved this is as hard as Search-LWE, and (quantumly) as hard as worst-case lattice problems.
Module-LWE¶
Plain LWE needs large matrices — public keys of megabytes. Ring-LWE replaces \(\mathbb{Z}_q\) with the polynomial ring \(R_q = \mathbb{Z}_q[X]/(X^{n}+1)\), so a whole \(n\times n\) structured matrix is described by \(n\) coefficients and multiplication uses an NTT in \(O(n\log n)\).
Module-LWE interpolates: work with \(k\times k\) matrices over the ring, giving a security/size dial. Kyber uses \(n = 256\) with \(k \in \{2,3,4\}\). Module structure hedges against attacks that might exploit the full algebraic structure of Ring-LWE.
25.5 ML-KEM (CRYSTALS-Kyber)¶
Parameters¶
Ring \(R_q = \mathbb{Z}_{3329}[X]/(X^{256}+1)\); \(q = 3329\), \(n = 256\).
| Variant | \(k\) | NIST level | Public key | Ciphertext | Secret key |
|---|---|---|---|---|---|
| ML-KEM-512 | 2 | 1 (≈AES-128) | 800 B | 768 B | 1632 B |
| ML-KEM-768 | 3 | 3 (≈AES-192) | 1184 B | 1088 B | 2400 B |
| ML-KEM-1024 | 4 | 5 (≈AES-256) | 1568 B | 1568 B | 3168 B |
ML-KEM-768 is the recommended default (used by Chrome, Signal, Cloudflare).
The scheme (structure)¶
Key generation.
- Sample a uniform matrix \(\mathbf{A}\in R_q^{k\times k}\) (expanded from a 32-byte seed \(\rho\) — the key stores the seed, not the matrix).
- Sample a small secret \(\mathbf{s}\in R_q^{k}\) and small error \(\mathbf{e}\in R_q^{k}\) from a centred binomial distribution.
- Compute \(\mathbf{t} = \mathbf{A}\mathbf{s} + \mathbf{e}\).
- Public key: \((\rho, \mathbf{t})\). Secret key: \(\mathbf{s}\).
Recovering \(\mathbf{s}\) from \((\mathbf{A},\mathbf{t})\) is exactly Module-LWE.
Encapsulation (sender produces a shared secret + ciphertext).
- Sample small \(\mathbf{r}, \mathbf{e}_1, e_2\).
- \(\mathbf{u} = \mathbf{A}^{T}\mathbf{r} + \mathbf{e}_1\)
- \(v = \mathbf{t}^{T}\mathbf{r} + e_2 + \mathrm{Encode}(m)\), where \(m\) is a random 32-byte message
- Ciphertext: \((\mathbf{u}, v)\), compressed. Shared secret: \(K = \mathrm{KDF}(m, H(c))\).
Decapsulation.
- Compute \(v - \mathbf{s}^{T}\mathbf{u}\) and decode to recover \(m'\).
- Re-encrypt \(m'\) and check the ciphertext matches (the Fujisaki–Okamoto transform), giving CCA security; on mismatch, return a pseudorandom key rather than failing — this prevents chosen- ciphertext attacks.
- \(K = \mathrm{KDF}(m', H(c))\).
Why decryption works.
The big terms \(\mathbf{s}^T\mathbf{A}^T\mathbf{r}\) cancel exactly. The residual is a sum of products of small values, which stays below \(q/4\); \(\mathrm{Encode}\) maps each message bit to \(0\) or \(\lceil q/2\rceil\), so rounding recovers \(m\) correctly with failure probability \(< 2^{-138}\).
Performance¶
ML-KEM is faster than RSA-2048 and comparable to X25519 — key generation and encapsulation take tens of microseconds. The cost is size: a 1184-byte public key versus 32 bytes for X25519, which matters for constrained IoT devices and can push TLS handshakes past one MTU.
25.6 Post-Quantum Signatures¶
ML-DSA (Dilithium) — the default¶
Based on Module-LWE and Module-SIS, using the Fiat–Shamir with aborts paradigm: generate a commitment from a masked secret, derive a challenge by hashing, respond, and reject-and-retry if the response would leak information about the secret. Rejection sampling makes the signature distribution independent of the key.
| Variant | NIST level | Public key | Signature |
|---|---|---|---|
| ML-DSA-44 | 2 | 1312 B | 2420 B |
| ML-DSA-65 | 3 | 1952 B | 3309 B |
| ML-DSA-87 | 5 | 2592 B | 4627 B |
SLH-DSA (SPHINCS+) — the conservative choice¶
Security rests on hash functions alone — no number theory, no lattices. Built from:
- WOTS+ one-time signatures (a Winternitz hash chain),
- Merkle trees authenticating many one-time keys,
- a hypertree of Merkle trees, plus FORS (a few-time signature) at the leaves,
- a randomised index so the same leaf is rarely reused, making it stateless.
| Property | Value |
|---|---|
| Public key | 32–64 B (tiny) |
| Signature | 7 856 – 49 856 B (huge) |
| Signing speed | slow (milliseconds) |
| Assumption | only that SHA-2/SHAKE is secure |
Use it for firmware signing and root certificates — anything long-lived where you cannot risk a lattice break and where signature size does not matter.
FN-DSA (Falcon) — compact¶
NTRU lattices with Gaussian sampling over the ring.
| Variant | Public key | Signature |
|---|---|---|
| Falcon-512 | 897 B | 666 B |
| Falcon-1024 | 1793 B | 1280 B |
Smallest post-quantum signatures, ideal for certificate chains. The drawback is implementation difficulty: it needs constant-time floating-point Gaussian sampling, notoriously easy to get wrong and vulnerable to side-channel attacks.
Comparison¶
| Scheme | PK | Sig | Sign speed | Verify speed | Assumption |
|---|---|---|---|---|---|
| RSA-2048 | 256 B | 256 B | slow | fast | factoring (broken) |
| Ed25519 | 32 B | 64 B | fast | fast | ECDLP (broken) |
| ML-DSA-65 | 1952 B | 3309 B | fast | fast | Module-LWE/SIS |
| Falcon-512 | 897 B | 666 B | medium | fast | NTRU |
| SLH-DSA-128s | 32 B | 7856 B | very slow | medium | hashes only |
25.7 Migration Strategy¶
1. Inventory. Find every use of RSA/ECC — TLS, VPNs, code signing, PKI, SSH, database encryption, embedded firmware. This is usually the hardest and longest step.
2. Prioritise by data lifetime. "Harvest now, decrypt later" means confidentiality of long-lived data is the urgent case. Medical records, state secrets and genomic data need PQC today. Ephemeral session data is less urgent.
3. Deploy hybrid modes first. Combine classical and post-quantum:
Secure if either component holds. Already deployed as X25519MLKEM768 in Chrome, Firefox,
Cloudflare, AWS and Signal's PQXDH.
4. Build crypto-agility. Design systems so algorithms can be swapped without redesign — the lesson of the slow SHA-1 and TLS 1.0 migrations.
5. Watch the timeline. NIST's guidance: deprecate RSA/ECC by 2030, disallow by 2035.
25.8 Solved Problems¶
Problem 1 — A toy LWE instance¶
Let \(q = 17\), \(n = 3\), secret \(\vec s = (2, 5, 3)\). Given the samples below, verify each and explain why recovering \(\vec s\) is hard at scale.
| \(i\) | \(\vec a_i\) | \(b_i\) | \(e_i\) |
|---|---|---|---|
| 1 | \((1,3,2)\) | \(\mathbf{7}\) | \(+1\) |
| 2 | \((4,1,6)\) | \(\mathbf{15}\) | \(+1\) |
| 3 | \((2,2,1)\) | \(\mathbf{0}\) | \(0\) |
Solution.
Sample 1. \(\langle\vec a_1,\vec s\rangle = 1(2) + 3(5) + 2(3) = 2+15+6 = 23 \equiv 6 \pmod{17}\). With \(e_1 = +1\): \(b_1 = 7\) ✓
Sample 2. \(4(2)+1(5)+6(3) = 8+5+18 = 31 \equiv 14 \pmod{17}\). With \(e_2 = +1\): \(b_2 = 15\) ✓
Sample 3. \(2(2)+2(5)+1(3) = 4+10+3 = 17 \equiv 0 \pmod{17}\). With \(e_3=0\): \(b_3 = 0\) ✓
Why it is hard. Without noise, three equations in three unknowns over \(\mathbb{Z}_{17}\) are solved by Gaussian elimination in a few operations. With noise, the system is inconsistent: no exact solution exists, and Gaussian elimination's row operations combine and amplify the errors, so the "solution" is garbage.
Brute force over all \(\vec s\) costs \(q^{n} = 17^{3} = 4913\) here — trivial. But Kyber uses \(q = 3329\) and \(n\cdot k = 256\times3 = 768\) dimensions:
Lattice reduction (BKZ) does far better than brute force, but still requires \(2^{\Theta(n)}\) time, and the parameters are set so this exceeds \(2^{128}\) even for the best known classical and quantum lattice sieves.
Problem 2 — Kyber decryption correctness¶
Show that Kyber decryption recovers the message, and estimate the error budget.
Solution.
The computation.
Substitute \(\mathbf{t} = \mathbf{A}\mathbf{s}+\mathbf{e}\), so \(\mathbf{t}^T\mathbf{r} = \mathbf{s}^T\mathbf{A}^T\mathbf{r} + \mathbf{e}^T\mathbf{r}\):
Error budget. \(\mathrm{Encode}\) maps bit 0 to \(0\) and bit 1 to \(\lceil q/2\rceil = 1665\). Decoding rounds to whichever is nearer, so it succeeds iff
Magnitude of \(\delta\). Each of \(\mathbf{s},\mathbf{e},\mathbf{r},\mathbf{e}_1\) has coefficients from a centred binomial \(\mathrm{CBD}(\eta)\) with \(\eta = 2\), so entries lie in \([-2,2]\) with standard deviation \(\sigma = \sqrt{\eta/2} = 1\). The dominant terms are inner products of \(256k\) such values, so by the central limit theorem \(\delta\) is approximately Gaussian with
Then
— astronomically small. The published figure for ML-KEM-768, accounting exactly for compression noise, is
Why the failure rate must be tiny. Decryption failures leak information about the secret key (the failing ciphertexts correlate with \(\mathbf{s}\)). An adversary who can collect failures mounts a key-recovery attack. So the bound must be far below any practical query budget.
Problem 3 — Bandwidth cost of migration¶
A TLS 1.3 handshake currently uses X25519 (32 B key share each way) and Ed25519 certificates (32 B key + 64 B signature). Compute the handshake size increase when moving to X25519+ML-KEM-768 hybrid with ML-DSA-65 certificates. Assume a chain of 3 certificates.
Solution.
Current (classical).
| Item | Size |
|---|---|
| Client key share (X25519) | 32 B |
| Server key share (X25519) | 32 B |
| 3 × cert public key (Ed25519) | 96 B |
| 3 × cert signature (Ed25519) | 192 B |
| Handshake signature | 64 B |
| Total crypto material | 416 B |
Post-quantum hybrid.
| Item | Size |
|---|---|
| Client key share (X25519 + ML-KEM-768 PK) | \(32 + 1184 = 1216\) B |
| Server key share (X25519 + ML-KEM ciphertext) | \(32 + 1088 = 1120\) B |
| 3 × cert public key (ML-DSA-65) | \(3\times1952 = 5856\) B |
| 3 × cert signature (ML-DSA-65) | \(3\times3309 = 9927\) B |
| Handshake signature | 3309 B |
| Total | 21 428 B |
Practical consequences.
- TCP slow start. The initial congestion window is typically 10 packets ≈ 14 KB. A 21 KB handshake needs an extra round trip — measurably slower page loads.
- QUIC amplification limit. A server may send at most 3× the bytes received before address validation, which post-quantum certificate chains can exceed.
- Mitigations in progress: using Falcon for certificates (666 B signatures) cuts the total to about 6 KB; certificate compression (RFC 8879); abridged certificate chains that omit intermediates the client already has; KEMTLS, which replaces handshake signatures with KEM operations entirely.
This is why key-exchange migration (ML-KEM) is proceeding faster than certificate migration (ML-DSA): the key-exchange overhead is tolerable today, the certificate overhead is not.
Problem 4 — Choosing algorithms for three scenarios¶
Recommend a post-quantum algorithm for each, with justification.
(a) Firmware signing for a 20-year industrial controller. (b) TLS key exchange for a high-traffic CDN. (c) Signatures in a blockchain where every signature is stored forever. (d) A constrained IoT sensor with 32 KB RAM.
Solution.
(a) Firmware, 20-year lifetime → SLH-DSA (SPHINCS+) or LMS/XMSS. Reasoning: the device must remain verifiable for 20 years, during which a lattice cryptanalysis breakthrough is a real risk. SLH-DSA's security rests on hash functions only — the most conservative assumption available, and the one property Grover merely halves. Firmware is signed rarely (slow signing is fine) and the 8–50 KB signature is negligible next to a firmware image. If state can be managed reliably, stateful LMS gives smaller signatures.
(b) CDN TLS key exchange → X25519MLKEM768 hybrid. Reasoning: exactly what Cloudflare and Google deployed. ML-KEM-768 gives NIST level 3; the hybrid retains X25519 so a flaw in either scheme is not fatal. Performance is excellent (faster than RSA-2048); the 1.2 KB overhead per handshake is acceptable. Do not use pure ML-KEM yet — hybrid is current best practice.
(c) Blockchain, signatures stored forever → Falcon (FN-DSA-512). Reasoning: on-chain storage is the scarcest resource and is paid for by every node forever. Falcon's 666-byte signature is by far the smallest post-quantum option — 5× smaller than ML-DSA-44 and 12× smaller than SLH-DSA. The implementation risk (constant-time Gaussian sampling) is manageable because blockchain clients use a small number of audited libraries. Verification is fast, which matters when every node verifies every signature.
(d) Constrained IoT, 32 KB RAM → ML-KEM-512 + ML-DSA-44, or pre-shared symmetric keys. Reasoning: ML-KEM-512 needs about 3 KB of working memory and is implementable on Cortex-M4. SLH-DSA is ruled out by signature size and signing time; Falcon is ruled out by the floating-point requirement. Best of all, if the deployment allows it: avoid public-key cryptography entirely and use pre-shared AES-256 keys, which are quantum-safe with no bandwidth cost.
Problem 5 — Quantifying the harvest-now-decrypt-later risk¶
Data must remain confidential for \(Y\) years. Migration to PQC takes \(M\) years. A cryptographically relevant quantum computer arrives in \(Q\) years. State Mosca's inequality and apply it to (a) medical records (\(Y = 50\), \(M = 5\), \(Q = 15\)) and (b) a news website's session cookies (\(Y = 0.01\), \(M = 1\), \(Q = 15\)).
Solution.
Mosca's theorem. You have a problem if
— i.e. if data encrypted today is still sensitive when the quantum computer arrives, given that migration itself takes time.
(a) Medical records.
Severe problem. Records encrypted today with RSA/ECC and captured by an adversary will be readable roughly 15 years from now, while still being sensitive for another 35 years. Action: migrate immediately, and re-encrypt archived data with PQC or with symmetric-only schemes.
(b) Session cookies.
No problem for confidentiality. By the time a quantum computer exists, every cookie encrypted today is long expired.
But note the different risk for authentication. Signatures and certificates must be quantum-safe at the moment of use, not retroactively — an adversary cannot forge a past signature after the fact, but from year 15 onward they can forge new ones. So the deadline for signature migration is \(Q\) itself, not \(Q - Y\). Both deadlines matter; they are simply different.
General decision rule.
| Data type | \(Y\) | Urgency |
|---|---|---|
| State secrets, genomic data | 50–100 | critical — migrate now |
| Medical, legal, financial records | 10–50 | high |
| Corporate IP | 5–20 | high |
| Personal email | 5–10 | medium |
| Session tokens, ephemeral traffic | < 1 | low (but signatures still need migrating by \(Q\)) |
25.9 Practice Problems¶
- Verify an LWE sample: \(q=13\), \(\vec s = (3,1)\), \(\vec a = (2,4)\), \(e = -1\). Find \(b\). [Ans: \(b = 9\)]
- Compare ML-KEM-768 and RSA-3072 public-key sizes. [Ans: 1184 B vs 384 B — about 3× larger]
- Why can Shor's algorithm not be applied to lattice problems?
- Which NIST security level does ML-DSA-65 target? [Ans: level 3]
- Compute the handshake overhead using Falcon-512 instead of ML-DSA-65 in Problem 3.
- Apply Mosca's inequality with \(Y=10\), \(M=3\), \(Q=20\). [Ans: \(13 < 20\) — no immediate problem, but little margin]
- Why does Kyber use Module-LWE rather than plain Ring-LWE?
25.10 Summary¶
- Shor breaks all deployed public-key cryptography (RSA, DH, ECDSA); Grover only halves symmetric and hash security, fixed by doubling parameters.
- NIST standards (Aug 2024): ML-KEM (FIPS 203), ML-DSA (204), SLH-DSA (205); FN-DSA and HQC follow.
- Lattice problems (SVP, CVP, LWE, Module-LWE) resist quantum attack because they reduce to the non-abelian dihedral HSP, and they enjoy worst-case-to-average-case reductions.
- ML-KEM (Kyber): \(\mathbf{t} = \mathbf{A}\mathbf{s}+\mathbf{e}\) hides \(\mathbf{s}\); decryption works because the large terms cancel and the residual noise stays below \(q/4\); failure probability \(<2^{-164}\), which matters because failures leak key information.
- Signatures: ML-DSA (default), FN-DSA/Falcon (smallest), SLH-DSA/SPHINCS+ (most conservative, hash-only).
- Migration: inventory → prioritise by data lifetime → hybrid modes (X25519MLKEM768) → crypto-agility. NIST: deprecate RSA/ECC by 2030, disallow by 2035.
- Mosca's inequality \(Y + M > Q\) tells you whether to act now.
Unit II is now complete. You can construct oracles, derive Deutsch–Jozsa, Bernstein–Vazirani and Simon, build the QFT and phase estimation, assemble Shor's algorithm end to end, analyse Grover geometrically, and explain both the quantum threat to cryptography and the standardised response.
Next lesson: L26 — Introduction to quantum machine learning and data encoding (Unit III begins).
Practise now: unit2-algorithms-lab.html → PQC Explorer: build a toy LWE instance, watch
encryption and decryption succeed while the noise stays inside the decoding radius, and use the
Mosca calculator on your own data-lifetime assumptions.