Amazon Cryptographer Claims Polynomial-Time Quantum Algorithm for Lattice Problems

Daniel R. Simon, of Amazon Web Services' Cryptography Group, has posted a preliminary paper claiming a polynomial-time quantum algorithm for the Dihedral Coset Problem (DCP) — a result that, if it holds, sits uncomfortably close to the mathematics underpinning the lattice-based post-quantum schemes NIST has proposed for standardisation, according to The Quantum Insider.

The paper does not break any of those schemes. It does not attack a standardised system, does not estimate the quantum hardware such an attack would need, and has not been peer-reviewed. What it offers is a theoretical claim, and the honest way to read it is as a claim: interesting enough to demand scrutiny, thin enough that no CISO should be rewriting a migration plan this quarter. What follows is my reading of where that claim can and cannot reach.

What Simon Actually Claims

The abstract states a polynomial-time quantum algorithm for DCP, built on Regev's known reduction of the related Dihedral Subgroup Problem (DSP) to the modular subset-sum problem — but using a new technique to erase sample bits without invoking a subset-sum oracle, according to the IACR listing.

That "without the oracle" clause is the whole story. Regev's reduction has been on the books for years; the missing piece was always a polynomial-time procedure that didn't lean on an oracle nobody knew how to build efficiently. Simon's paper claims to supply exactly that missing procedure.

To calibrate the ambition: the best previously known quantum algorithm for the DSP, due to Greg Kuperberg, ran in subexponential time — faster than brute force, still nowhere near polynomial, per the paper's own framing. Moving from subexponential to polynomial is not an incremental tightening. It is a categorical jump, and categorical jumps in complexity theory are precisely the results that get the most brutal peer review, because they are the ones most often wrong.

What It Would Mean for Lattices — And What It Wouldn't

The concrete cryptographic hook is an approximation factor. The paper claims a polynomial-time method for obtaining roughly a $\sqrt{n}$ polylog($n$) approximation to the shortest vector in an $n$-dimensional lattice, and says the algorithm tolerates a faulty sample rate as high as $1/O(\log n)$ — enough, it argues, to solve SVP or LWE instances at that same $\sqrt{n}$ polylog($n$) approximation factor, according to the IACR abstract.

Here is where the excitement has to meet the constraint. Learning With Errors — the LWE problem named in that abstract — is the hard problem that lattice-based post-quantum schemes are built on. But the security of a lattice scheme does not rest on solving LWE at a $\sqrt{n}$-ish approximation factor. It rests on the hardness of the specific parameter regimes cryptographers chose, with margins deliberately built in against approximation-based attacks. A polynomial algorithm for a $\sqrt{n}$ polylog($n$) approximation is a serious theoretical object; whether it reaches into the regime where deployed keys actually live is a separate question the paper does not answer.

And that gap is not a nuance. By the account of The Quantum Insider, the manuscript does not analyse any specific cryptographic standard, does not provide a key-recovery attack against any deployed system, and does not show how its approximation factors map onto the parameters real schemes use. Nor does it count the cost: no estimate of logical qubits, gate depth, or error-corrected operations needed to run the thing at cryptographically relevant scale.

That last omission is the one I'd stare at longest. A polynomial-time algorithm is polynomial in the exponent, not in your data centre. The overhead constants and the fault-tolerance tax are where quantum "breaks" quietly become "in principle, on a machine that does not exist." An algorithm can be asymptotically devastating and operationally irrelevant for decades. Until someone runs the resource-estimation calculation, the distance between this result and a working attack is unmeasured — not small, not large, unmeasured.

How the Argument Is Built — And Where It's Fragile

Mechanically, the approach divides a large collection of quantum samples into groups, processing some so they contribute no unwanted phases, while information from other groups is measured off and separated to leave the relevant quantum state nearly balanced. The phase encoding of one bit of the hidden value is then transferred onto a replacement qubit, and polynomially many repetitions are meant to push the probability of recovering that bit toward certainty, as described in the coverage of the paper.

The load-bearing assumption is statistical: that the relevant quantum states become close to uniformly distributed across their possible values, and that the subset sums behave as the argument needs them to. The paper's own presentation flags these probability arguments as the part likely to draw the closest examination — and rightly so. In this class of algorithm, the collapse usually happens exactly there: a distribution assumed uniform that isn't, a correlation between samples that quietly voids the success-probability bound. The algorithm can be flawless in structure and fail on a single unwarranted "approximately uniform."

What Builders Should Do — Now Versus Later

Nothing, this week, at the level of your production stack. NIST's standards remain the sanctioned path, and a preliminary, unreviewed paper with no demonstrated attack is not grounds to trigger a migration you'd otherwise have run on a multi-year horizon. Treating this as a five-alarm event would be a category error — the same error, inverted, as ignoring it.

What it is: a credible signal that the theoretical floor under lattice cryptography deserves fresh attention. The disciplined response is to watch the right things.

• Watch the proof, not the headline. The result stands or falls on those uniform-distribution and subset-sum claims. Independent verification — either a clean confirmation or a specific counterexample — is the event that matters, and it will come from the cryptography community reading the eprint, not from press.
• Watch for a resource estimate. If a follow-up puts real numbers on logical qubits and gate counts at cryptographic parameters, that converts an asymptotic claim into a threat model you can actually reason about.
• Watch for a parameter mapping. The moment anyone shows the approximation factor reaching the parameter scale of a deployed lattice scheme is the moment the roadmap conversation genuinely changes.

If you have not already built crypto-agility into your architecture — the ability to swap primitives without re-architecting — that is the durable lesson here, and it was the right move before this paper existed. The specific virtue of agility is that it lets you treat results like this one as information rather than emergencies.

The claim that would change my mind runs in either direction, and both are worth naming. If a competent group reproduces the argument and confirms polynomial-time DCP, the field owes a hard recalibration of how much margin the standardised lattice schemes really carry. If someone locates the flawed distributional assumption — the likelier outcome, on base rates for results this large — this becomes a footnote in the long history of quantum algorithms that were beautiful and wrong. Either way, the verdict belongs to the proof, and the proof is now in the open where it can be checked. That is exactly where it should be.