Notebook 15 — Shor vs. the lattice

Notebook 15 — Shor vs. the lattice#

Closing chapter: why the algorithm we just implemented cannot break ML-KEM.

Shor’s secret: reducing to order finding#

Integer factoring and discrete logarithm both reduce to finding the multiplicative order of an element in a group. The quantum speedup comes from one specific trick: the QFT on \(\mathbb{Z}_N\) sees periodicity exponentially faster than any classical Fourier transform. This trick depends on the underlying problem having a periodic (or more generally, group-theoretic) structure that the QFT can latch onto.

The hidden subgroup problem (HSP)#

Both factoring and discrete log are special cases of the Abelian Hidden Subgroup Problem: given a function \(f: G \to S\) that is constant on cosets of a subgroup \(H\) of \(G\), find \(H\). When \(G\) is abelian — \((\mathbb{Z}_N, +)\), \((\mathbb{Z}_N^*, \times)\) — the QFT diagonalizes the group algebra and the algorithm is efficient. This is why RSA, Diffie-Hellman, ECDH all fall to Shor: they are Abelian HSP instances in disguise.

LWE is not an HSP instance#

The Learning With Errors problem asks: given many samples \((\mathbf{a}_i, \langle \mathbf{a}_i, \mathbf{s} \rangle + e_i \bmod q)\) with small errors \(e_i\), recover \(\mathbf{s}\). There is no hidden subgroup here — the relationship between the samples and the secret is linear with additive noise, not periodic. No QFT on any natural group reveals \(\mathbf{s}\). The reduction Shor exploits simply does not apply.

Known quantum algorithms against lattices#

What do we know? The best known quantum algorithms for LWE and related lattice problems fall into three buckets:

(a) BKZ with quantum speedups for sieving — Grover-style quadratic improvements on the innermost loop. Still exponential overall.
(b) Dihedral Hidden Subgroup Problem — LWE has a reduction to (non-abelian) dihedral HSP. The best known dihedral HSP algorithm is sub-exponential (Kuperberg) but still beats no polynomial-time quantum algorithm.
(c) Quantum sieve variants — Laarhoven and others have proposed quantum lattice sieving with modest speedups. Nothing breaks the exponential wall.

ML-KEM’s parameters are chosen with all of these in mind.

Why this matters for you#

If tomorrow someone discovered an efficient quantum algorithm for LWE, ML-KEM would fall. This is conjectured hardness, not proven hardness. That’s why we deploy hybrid (X25519 + ML-KEM): safe if either component survives. It’s also why NIST standardized SLH-DSA (hash-based signatures) in parallel — hash-based crypto rests on collision-resistance alone, with no algebraic structure for Shor or its descendants to attack.

The narrative arc, closed#

00a warned: Shor breaks RSA and ECC.
Notebooks 01–09 built: ML-KEM, conjectured to be quantum-safe.
Notebooks 12–14 showed: Shor really does break RSA — here is the code, running.
This chapter explains: and here is why the same trick does not break ML-KEM.

The crypto world is betting that lattice problems remain hard against quantum attackers. That bet is informed, but not proved. The hedge is hybrid deployment, the backup is hash-based signatures, and the long game is continued research.

Thanks for reading all 15 notebooks.