Skip to content

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:

  1. Explain which cryptographic primitives quantum computers break and which survive.
  2. State the lattice problems SVP, CVP, LWE and Module-LWE and why they are believed quantum-hard.
  3. Describe CRYSTALS-Kyber (ML-KEM): key generation, encapsulation, decapsulation and parameters.
  4. Describe ML-DSA (Dilithium), SLH-DSA (SPHINCS+) and FN-DSA (Falcon) and compare them.
  5. 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

\[ \mathcal{L} = \left\{\sum_{i=1}^{n} z_i\vec b_i \ :\ z_i\in\mathbb{Z}\right\} \]

— 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

\[ \big(\vec a_i,\ b_i = \langle\vec a_i,\vec s\rangle + e_i \bmod q\big) \]

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.

  1. 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).
  2. Sample a small secret \(\mathbf{s}\in R_q^{k}\) and small error \(\mathbf{e}\in R_q^{k}\) from a centred binomial distribution.
  3. Compute \(\mathbf{t} = \mathbf{A}\mathbf{s} + \mathbf{e}\).
  4. 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).

  1. Sample small \(\mathbf{r}, \mathbf{e}_1, e_2\).
  2. \(\mathbf{u} = \mathbf{A}^{T}\mathbf{r} + \mathbf{e}_1\)
  3. \(v = \mathbf{t}^{T}\mathbf{r} + e_2 + \mathrm{Encode}(m)\), where \(m\) is a random 32-byte message
  4. Ciphertext: \((\mathbf{u}, v)\), compressed. Shared secret: \(K = \mathrm{KDF}(m, H(c))\).

Decapsulation.

  1. Compute \(v - \mathbf{s}^{T}\mathbf{u}\) and decode to recover \(m'\).
  2. 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.
  3. \(K = \mathrm{KDF}(m', H(c))\).

Why decryption works.

\[ v - \mathbf{s}^T\mathbf{u} = \big(\mathbf{A}\mathbf{s}+\mathbf{e}\big)^T\mathbf{r} + e_2 + \mathrm{Encode}(m) - \mathbf{s}^T\big(\mathbf{A}^T\mathbf{r}+\mathbf{e}_1\big) \]
\[ = \mathrm{Encode}(m) + \underbrace{\mathbf{e}^T\mathbf{r} + e_2 - \mathbf{s}^T\mathbf{e}_1}_{\text{small}} \]

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:

\[ K = \mathrm{KDF}\big(K_{\text{X25519}} \,\|\, K_{\text{ML-KEM}}\big) \]

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:

\[ 3329^{768} \approx 10^{2712} \]

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.

\[ v - \mathbf{s}^T\mathbf{u} = \big(\mathbf{t}^T\mathbf{r} + e_2 + \mathrm{Encode}(m)\big) - \mathbf{s}^T\big(\mathbf{A}^T\mathbf{r}+\mathbf{e}_1\big) \]

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}\):

\[ = \mathbf{s}^T\mathbf{A}^T\mathbf{r} + \mathbf{e}^T\mathbf{r} + e_2 + \mathrm{Encode}(m) - \mathbf{s}^T\mathbf{A}^T\mathbf{r} - \mathbf{s}^T\mathbf{e}_1 \]
\[ \boxed{\ = \mathrm{Encode}(m) + \underbrace{\big(\mathbf{e}^T\mathbf{r} + e_2 - \mathbf{s}^T\mathbf{e}_1\big)}_{\text{total noise } \delta}\ } \]

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

\[ |\delta| < \frac{q}{4} = \frac{3329}{4} = 832 . \]

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

\[ \sigma_\delta \approx \sqrt{2\cdot 256k}\ \cdot O(1) \approx 40 \ \text{for } k=3 . \]

Then

\[ \Pr[|\delta| \ge 832] \approx 2\,\Phi(-832/40) = 2\Phi(-20.8) \]

— astronomically small. The published figure for ML-KEM-768, accounting exactly for compression noise, is

\[ \Pr[\text{decryption failure}] < 2^{-164} . \]

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
\[ \text{Increase factor} = \frac{21428}{416} \approx \mathbf{51\times} \]

Practical consequences.

  1. 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.
  2. QUIC amplification limit. A server may send at most 3× the bytes received before address validation, which post-quantum certificate chains can exceed.
  3. 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

\[ \boxed{\ Y + M \ >\ Q\ } \]

— i.e. if data encrypted today is still sensitive when the quantum computer arrives, given that migration itself takes time.

(a) Medical records.

\[ Y + M = 50 + 5 = 55 \quad > \quad Q = 15 \]
\[ \text{Deficit} = 55 - 15 = \mathbf{40\ \text{years}} \]

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.

\[ Y + M = 0.01 + 1 = 1.01 \quad < \quad Q = 15 \]

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

  1. Verify an LWE sample: \(q=13\), \(\vec s = (3,1)\), \(\vec a = (2,4)\), \(e = -1\). Find \(b\). [Ans: \(b = 9\)]
  2. Compare ML-KEM-768 and RSA-3072 public-key sizes. [Ans: 1184 B vs 384 B — about 3× larger]
  3. Why can Shor's algorithm not be applied to lattice problems?
  4. Which NIST security level does ML-DSA-65 target? [Ans: level 3]
  5. Compute the handshake overhead using Falcon-512 instead of ML-DSA-65 in Problem 3.
  6. Apply Mosca's inequality with \(Y=10\), \(M=3\), \(Q=20\). [Ans: \(13 < 20\) — no immediate problem, but little margin]
  7. 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.