What Are Quantum Cryptanalysis Algorithms? Shor's Algorithm and Where Lattice Cryptography Stands Today

The Current State: What's Broken, and What Isn't

As of this writing (2026), a fault-tolerant quantum computer capable of actually breaking practical-scale cryptography (such as RSA-2048 or the equivalent of ECC-256) does not yet exist. NISQ (Noisy Intermediate-Scale Quantum) devices are advancing rapidly, but running Shor's algorithm against practical key lengths is estimated to require error correction on the order of millions to tens of millions of logical-qubit-equivalent gates, and there's still a large gap to close. However, whether an algorithm is theoretically capable of breaking a scheme and whether hardware exists today to actually run it are two separate questions. This article addresses the former — what happens if a quantum computer is large enough.

Shor's Algorithm and Quantum Phase Estimation

Shor's algorithm (1994, Peter Shor) is a quantum algorithm that solves both integer factorization and the discrete logarithm problem in polynomial time — something impossible for a classical computer. Its core component is Quantum Phase Estimation (QPE).

Here's the rough outline. Let N be the number we want to factor. For a randomly chosen a, the problem reduces to finding the period (order) r of the function f(x) = a^x mod N. Using quantum phase estimation to find this period r is the heart of Shor's algorithm. By reading out the phase of the eigenvalues of the unitary transformation that computes f, using the quantum Fourier transform, information about r can be obtained all at once (via superposition) in a single quantum computation. Where a classical computer takes exponential time to find r, quantum phase estimation finds it in polynomial time.

This structure of "finding a period" is shared not just by integer factorization (RSA), but also by the discrete logarithm problem over a finite field (DH), and the discrete logarithm problem over an elliptic curve (ECC/ECDSA/ECDHE). All of these reduce to the same underlying framework of "finding a periodic structure inside a group," which means a single variant of Shor's algorithm can, in theory, break RSA, DH, and ECC all in polynomial time. This is the fundamental reason why the push toward "migrating to post-quantum cryptography" exists.

Why Lattice Cryptography Is (So Far) Safe

Meanwhile, the lattice cryptography schemes that NIST selected as post-quantum standards — ML-KEM (Kyber) and ML-DSA (Dilithium) — base their security on the hardness of problems such as the Shortest Vector Problem (SVP) and Learning With Errors (LWE). These problems have no "periodic structure" of the kind Shor's algorithm exploits. The reason RSA, DH, and ECC can be broken is that the hardness underlying them is fundamentally rooted in hidden periodicity within a group — the structure of abelian groups — and quantum phase estimation is exactly the kind of algorithm that excels at finding that periodic structure. For lattice problems, no method is currently known for exploiting that kind of algebraic structure.

However, "not known" is not proof of "does not exist." In August 2026, Daniel R. Simon, a researcher in the AWS (Amazon Web Services) Cryptography Group, posted a paper to the IACR ePrint Archive claiming a polynomial-time quantum algorithm for the Dihedral Coset Problem (DCP), drawing considerable attention. Roughly two decades of prior research have established reductions linking the DCP to lattice problems (approximate Shortest Vector Problem, Learning With Errors), so if the claim had held up, it would have had consequences for part of the hardness underlying lattice cryptography.

However, by August 15, 2026 — just days after the initial post — critical errors were identified in the paper, and the claimed algorithm turned out not to work (at least not in polynomial time). No standardized lattice scheme (ML-KEM/ML-DSA) was actually broken, and no costed attack against any parameter set was ever demonstrated. This is simply the most recent example of a pattern that recurs in this field: a groundbreaking claim, followed by a retraction once peer review and independent verification catch an error.

Summary

• Shor's algorithm can, in theory, break RSA, DH, and ECC all by using quantum phase estimation to find the period (order) in polynomial time
• This vulnerability stems from the fact that these problems rely on the periodic structure of abelian groups
• Lattice cryptography (SVP/LWE) has no such periodic structure and is not a target for quantum phase estimation
• AWS researcher Daniel R. Simon's August 2026 claim of a polynomial-time DCP algorithm was retracted the same month after errors were found
• That said, research is ongoing, and it's important to keep checking peer-reviewed primary sources
• A fault-tolerant quantum computer capable of breaking practical-scale RSA/ECC does not yet exist as of this writing