up:: The Threat MOC
Quantum Attacks Beyond Shor and Grover
Shor’s and Grover’s are the two quantum algorithms everyone knows, and between them they set the headline threat: Shor’s ends public-key cryptography, Grover’s dents symmetric keys. They aren’t the only quantum algorithms that touch cryptography, though. A handful of others matter, less because they break anything standardized and more because they shape the security margins the standards are built with. Kuperberg’s subexponential algorithm is why isogeny schemes like CSIDH need careful sizing. Quantum sieving gives a modest speedup against lattices. Simon’s-algorithm attacks break certain symmetric modes in an idealized model. None of them breaks the standardized lattice or hash schemes, and knowing why is part of knowing why those standards were chosen.
The short version:
- Kuperberg’s algorithm solves the dihedral hidden subgroup problem in subexponential time, which is the reason isogeny group-action schemes like CSIDH have to be sized carefully. It’s weaker than Shor’s, so it pressures parameters rather than breaking the idea.
- Quantum sieving applies Grover-style search to lattice algorithms, shaving the exponent on the shortest-vector problem. The speedup is small and, at cryptographic dimensions, currently impractical, so it’s a margin adjustment for the lattice standards.
- Simon’s-algorithm attacks break several symmetric modes (CBC-MAC, GCM, others) in polynomial time, but only under a strong model where the attacker queries the cipher in quantum superposition, which real protocols don’t grant.
- The load-bearing takeaway: none of these breaks the standardized lattice or hash-based schemes. ML-KEM, ML-DSA, and SLH-DSA stand against every one of them.
- What they do is set the size of the safety margin. The standardized parameters already absorb the best known versions of all three.
Think of Shor’s algorithm as a master key that opens one specific brand of lock outright, and Grover’s as a lock-pick that halves the effort on a different brand. The algorithms here are neither. They’re specialty tools, each shaped for one narrow family: a shortcut through the particular symmetry of isogeny group actions, a slightly faster search inside lattice solvers, a period-finder that only works when you’re allowed to interrogate a cipher in ways no real system permits. Each one narrows a margin somewhere. None of them opens the locks the world is migrating to.
What is Kuperberg’s algorithm, and why does it matter for isogenies?
Kuperberg’s algorithm is a quantum algorithm that solves the dihedral hidden subgroup problem in subexponential time, and it matters because certain isogeny-based schemes rest on a problem that reduces to it. Greg Kuperberg published it in 2003, achieving time and query complexity of roughly 2^(O(√log N)), which is subexponential, faster than the classical square-root cost but far short of the polynomial-time collapse Shor’s delivers.
Source: G. Kuperberg, “A subexponential-time quantum algorithm for the dihedral hidden subgroup problem,” 2003, arXiv:quant-ph/0302112.
The connection to cryptography runs through commutative isogeny schemes. CSIDH, a post-quantum group-action key exchange proposed in 2018, bases its security on recovering a secret group action, and that recovery can be cast as a hidden-shift problem that Kuperberg’s machinery attacks. So CSIDH does not enjoy fully exponential quantum security; it enjoys subexponential security, and its parameters have to be chosen large enough that the subexponential attack still costs more than the target level.
Source: W. Castryck, T. Lange, C. Martindale, L. Panny, J. Renes, “CSIDH: An Efficient Post-Quantum Commutative Group Action,” ASIACRYPT 2018, SpringerLink, the scheme whose security must be set against the Kuperberg-style attack.
This is why isogeny cryptography carries a reputation for needing care. It’s a separate matter from the classical break of SIDH/SIKE in 2022, which killed that particular construction; the Kuperberg pressure is a quantum consideration that applies to the surviving commutative-group-action designs and forces conservative parameter choices rather than ending the approach.
Do quantum computers speed up attacks on lattices?
Quantum computers do speed up the best classical lattice attacks, but only modestly, and not by enough to threaten the standardized schemes. The hardest computational core of lattice cryptanalysis is the shortest-vector problem, and the leading classical algorithms for it are “sieving” methods that search enormous lists of lattice vectors for close pairs. That search is exactly the kind of unstructured lookup Grover’s algorithm accelerates, so applying Grover-style search inside a sieve lowers the running-time exponent.
The improvement is real and small. Classical sieving runs in time about 2^(0.292d) for a lattice of dimension d, and the quantum-accelerated versions bring the exponent down to roughly 2^(0.257d) to 2^(0.265d), a reduction of around 10 percent in the exponent. That’s nothing like Shor’s exponential collapse; it’s a Grover-flavored trim on an already-exponential cost.
More importantly, recent analysis finds the quantum speedup essentially vanishes at cryptographically relevant sizes once real hardware costs are counted. A 2024 study estimated that quantum sieving at dimension 400, near NIST’s minimum security level, would demand on the order of 10^13 physical qubits and timescales matching classical computation, concluding there’s little to no practical quantum advantage in the dimensions that matter.
Source: J. Doriguello, G. Giapitzakis, A. Luongo, A. Morolia, “On the practicality of quantum sieving algorithms for the shortest vector problem,” PQCrypto 2026, arXiv:2410.13759, which finds the quantum sieving advantage impractical at cryptographic dimensions.
So the lattice standards fold this into their margins and move on. ML-KEM and ML-DSA are parameterized against the best known attacks including their quantum versions, and quantum sieving leaves them comfortably clear.
How does Simon’s algorithm attack symmetric cryptography?
Simon’s algorithm attacks symmetric cryptography by finding hidden periods in a function, and when a symmetric construction secretly contains such a period, Simon’s recovers it in polynomial time. A 2016 result showed this breaks a surprising list of symmetric modes: CBC-MAC, PMAC, GMAC, GCM, and OCB, along with several authenticated-encryption designs, all fall in polynomial time to a Simon’s-based attack, versus the classical square-root query cost.
Source: M. Kaplan, G. Leurent, A. Leverrier, M. Naya-Plasencia, “Breaking Symmetric Cryptosystems using Quantum Period Finding,” CRYPTO 2016, arXiv:1602.05973.
The catch is the attack model, and it’s a large catch. These attacks require the adversary to query the cipher in quantum superposition, meaning the attacker feeds a superposition of many inputs into the actual keyed primitive and gets a superposition of outputs back. Real protocols never expose a keyed cipher that way; a classical attacker interacting with a normal server can’t build the superposition the attack depends on. So the results are foundational for how the field reasons about quantum-secure symmetric design, and they don’t translate into a break of correctly deployed AES-based systems.
A related line of work, the offline Simon’s algorithm, relaxes some of the superposition requirement and combines Simon’s with Grover’s, which sharpens certain attacks. It still doesn’t grant a practical break of the standardized primitives; it refines the theoretical boundary of where quantum period-finding bites.
Which post-quantum standards do any of these break?
None of them break the finalized post-quantum standards, which is the whole point of surveying them. Each of these algorithms is powerful against one narrow target, and the standardized schemes were selected on families those tools don’t crack.
| Quantum algorithm | Real target | Effect | Breaks a NIST standard? |
|---|---|---|---|
| Kuperberg’s | dihedral hidden subgroup / isogeny group actions | subexponential, forces larger CSIDH parameters | No |
| Quantum sieving | shortest-vector problem in lattices | ~10% exponent cut, impractical at crypto sizes | No; margins absorb it |
| Simon’s (superposition) | symmetric modes with a hidden period | polynomial-time break in an unrealizable query model | No; real protocols block it |
The standardized answers to the quantum threat rest on math these tools don’t reach. ML-KEM and ML-DSA rest on structured lattices, sized against quantum sieving. SLH-DSA rests on hash functions, whose only quantum exposure is Grover’s generic search, already handled by output length. So the practical migration story is unchanged: deploy the finalized standards, and treat these algorithms as the reason the parameters look the way they do, not as new fires to fight.
Source: NIST IR 8105, Report on Post-Quantum Cryptography, 2016, nvlpubs.nist.gov, which frames the quantum threat as Shor’s against public-key and Grover’s against symmetric, with the standardized families chosen to resist both.
Why do these algorithms matter if they break nothing standardized?
They matter because security is a margin, and these algorithms set where the margin has to be. A cryptographic parameter isn’t chosen against “does any attack break it,” but against “how expensive is the best attack, quantum ones included, and is our margin above it.” Every algorithm here moves that best-attack estimate for some family, so each one is a term in the equation designers solve when they pick key and parameter sizes.
Kuperberg’s is the clearest case: it’s the difference between an isogeny scheme claiming full exponential quantum security and claiming only subexponential security, which changes the parameter sizes by a lot. Quantum sieving is why lattice parameters carry a little extra headroom. The Simon’s-model results are why the field insists on symmetric constructions that stay secure even in the paranoid superposition-query world, so that a future surprise in the attack model finds the primitives already hardened.
The through-line is that a mature migration reasons about the whole known quantum toolkit, beyond the two famous algorithms. The finalized standards were built by people who accounted for all of it, which is a large part of why they can be deployed with confidence today.
Common misconceptions
“Quantum computers break lattice cryptography.” They don’t, on any current evidence. The best quantum attack on lattices is a roughly 10-percent-exponent speedup from quantum sieving, impractical at cryptographic sizes, and ML-KEM’s parameters already account for it. There’s no Shor-style break of lattices known.
“Kuperberg’s algorithm breaks isogeny cryptography.” It doesn’t break it; it constrains it. Kuperberg’s gives a subexponential attack on the commutative group-action problem, so schemes like CSIDH must use larger parameters to stay secure. The classical 2022 break of SIDH/SIKE was a separate event that killed that specific construction.
“Simon’s algorithm breaks AES.” It doesn’t break correctly deployed AES. Simon’s-based attacks need superposition access to the keyed cipher, which real protocols never provide, so the results shape quantum-secure symmetric design rather than threatening deployed AES.
“If these algorithms exist, the post-quantum standards aren’t safe.” The opposite: the standards were selected knowing these algorithms exist. ML-KEM, ML-DSA, and SLH-DSA rest on families none of these tools break, with parameters sized against the best known versions.
Questions people ask
Are Shor’s and Grover’s the only quantum algorithms that matter for cryptography? They’re the two that set the headline threat, but Kuperberg’s algorithm, quantum sieving, and Simon’s-algorithm attacks all shape post-quantum security margins, even though none breaks a finalized standard.
Does any quantum algorithm break ML-KEM? No. The relevant quantum attack on lattices is quantum sieving, which trims the exponent by around 10 percent and is impractical at cryptographic dimensions (arXiv:2410.13759). ML-KEM’s parameters already absorb it.
Why does CSIDH need special care? Because its security reduces to a problem Kuperberg’s algorithm solves in subexponential time, so it earns only subexponential quantum security and must use larger parameters than a fully-exponential scheme would (arXiv:quant-ph/0302112).
Do Simon’s-algorithm attacks mean AES is quantum-broken? No. They break certain modes only when the attacker can query the cipher in quantum superposition, which real protocols don’t allow (arXiv:1602.05973). Deployed AES faces only Grover’s generic search.
So do any of these change what I should deploy? No. Deploy the finalized standards. These algorithms are the reason the standardized parameters look the way they do, and the standards were chosen to stand against all of them.
The quantum toolkit against cryptography is larger than Shor’s and Grover’s, and a serious migration plan is built by people who accounted for the whole of it. Everything here is the map, given freely. When your team needs a threat picture built for your own systems and timeline, that’s the work I do. Request an alignment briefing.
Last verified 2026-07-12 · Maintained by Addie LaMarr, LaMarr Labs.