Quantum Resistance: Why Shor's Algorithm Doesn't Apply

The honest claim is: no known efficient quantum attack exists — not "mathematically proven impossible forever." These are different statements, and conflating them would overstate the science.

What Shor's Algorithm Exploits

Shor showed that both integer factoring and the discrete logarithm problem succumb to efficient quantum algorithms, using the same underlying technique: period-finding. The deeper reason both fall together: factoring, discrete log, and related problems are all instances of a single algebraic structure called the Hidden Subgroup Problem (HSP) for finite abelian groups.

A quantum computer that solves HSP for abelian groups has the fundamental machinery to threaten RSA, Diffie-Hellman, and ECC in one stroke. Wikipedia's summary states the same structural fact: "Shor's algorithms for factoring and discrete logarithms are instances of the hidden subgroup problem for finite abelian groups."

Why LWE Doesn't Offer That Foothold

RSA and ECC rely on clean, periodic, abelian group structure — exactly what a quantum Fourier transform is built to exploit. LWE is a geometric search problem over a noisy lattice, with no known periodic structure of that kind for period-finding to use.

The difference is not a matter of degree — it is a difference in the kind of mathematical problem:

The Active Research Frontier

This boundary is an active research frontier, not a closed wall. The HSP framework extends in principle to harder, non-abelian cases, and lattice problems connect to that frontier:

The existence of efficient quantum algorithms for HSPs for certain non-abelian groups would imply efficient quantum algorithms for the graph isomorphism problem and certain shortest vector problems in lattices.

More specifically, a polynomial-time quantum algorithm for the dihedral hidden subgroup problem would imply a polynomial-time quantum algorithm for certain hard lattice problems considered intractable classically. And LWE has been shown to be quantum polynomial-time equivalent to an extrapolated version of the dihedral coset problem.

The current state of that frontier: the best known quantum algorithms for the dihedral hidden subgroup problem are subexponential — faster than brute force, but nowhere near the clean polynomial-time efficiency Shor's algorithm achieves against factoring.

The Precise, Defensible Statement

Lattice problems like LWE are connected to a harder, non-abelian relative of the same Hidden Subgroup Problem that broke RSA — and no known quantum algorithm solves that harder version efficiently.

As one industry summary of the current standards puts it: "no known quantum or classical polynomial-time algorithm solves MLWE" — that is the hardness assumption the standard rests on.

The Built-In Review Cycle

NIST explicitly acknowledges that the matter is not permanently settled. The standard itself builds in a formal review cycle:

NIST will continue to follow developments in the analysis of the ML-KEM algorithm, and will formally reevaluate this standard every five years; awareness of any breakthrough in technology or any mathematical weakness will cause NIST to reevaluate the standard.

This five-year review cycle is the responsible approach: acknowledge the possibility of future advances, monitor the frontier, and stand ready to adapt. The current scientific consensus is that MLWE is secure against known quantum attacks — but NIST is not treating that as a permanent guarantee.

Key Takeaways

• Shor's algorithm exploits abelian group structure that LWE does not have
• LWE connects to the non-abelian HSP — a harder problem with no efficient quantum solution known
• The best known quantum attacks on lattice problems are subexponential — not the polynomial-time break Shor achieves against RSA
• NIST's five-year review cycle accounts for the possibility of future advances
• The defensible claim: no known efficient quantum attack exists — not a guarantee of permanent immunity