Amazon researcher's quantum algorithm claim could challenge PQC's mathematical foundations

[Wasp]

An Amazon Web Services cryptographer has put out a preliminary paper claiming a polynomial time quantum algorithm for something called the Dihedral Coset Problem, and if the result actually holds up under scrutiny it would meaningfully strengthen the theoretical case that quantum computers could one day efficiently solve the lattice problems that most post quantum cryptography is actually built on

The paper comes from Daniel R Simon of AWS Cryptography Group, and its worth noting hes the same Simon behind the classic Simons algorithm from the 1990s that helped inspire Shors factoring algorithm, the Dihedral Coset Problem has occupied quantum algorithm researchers for more than two decades because earlier work by mathematician Oded Regev showed a reduction connecting it to the Shortest Vector Problem and Learning With Errors, the two mathematical foundations that underpin most of NISTs standardized post quantum encryption schemes

The catch has always been that Regevs original reduction depended on an idealized subset sum oracle that nobody actually knew how to build efficiently, and the best real algorithm anyone had for the related Dihedral Subgroup Problem, from Greg Kuperberg, only ran in subexponential time rather than polynomial time, Simons paper claims to finally supply that missing polynomial time procedure without needing the idealized oracle, specifically by dividing quantum samples into groups and carefully erasing information from them without destroying the quantum phase that encodes the hidden answer, the paper also claims the method can tolerate a reasonably high rate of faulty quantum samples, which matters because the reductions from lattice problems to this problem naturally introduce exactly that kind of noise

Its genuinely important to be clear about what this is and isnt though, this is a complexity theoretic advance rather than a practical attack, the paper doesnt analyze any specific standardized cryptographic scheme, doesnt demonstrate an actual key recovery attack against a deployed system, and doesnt estimate how many logical qubits or error corrected operations an attack would actually require at cryptographically relevant sizes, a polynomial time algorithm can still be completely impractical if the polynomial degree is high or the constant factors are enormous, and the paper is already reportedly in discussion with prominent lattice cryptography researchers including Daniele Micciancio, Vinod Vaikuntanathan and Thomas Vidick who will need to comb through the probability arguments line by line before anyone treats this as settled

Given the questions people are asking about companies like SEALSQ, which trades as LAES and builds PQC hardware like its Quantum Shield chips, and EnSilica, which designs PQC enabled semiconductor IP, its worth being precise here, this paper does not break any deployed cryptography and does not invalidate NISTs chosen algorithms like Kyber or Dilithium today, if anything a genuine theoretical narrowing of the security margin for lattice cryptography would probably increase urgency and demand for exactly this kind of PQC hardware transition work rather than undermine the business case for it, the actual risk to these companies would only come if a much later, fully worked out version of this result produced real practical attack parameters against the specific standardized schemes their chips implement, and that is a very different and much further off milestone than what this preprint claims

Amazon Researcher Claims Quantum Algorithm Could Challenge PQC Foundationsthequantuminsider.com

[Aidan]

The distinction between a complexity theoretic advance and an actual practical attack is the whole story here, this paper doesnt even attempt to estimate the qubit count or gate count needed, which is usually where these headline claims quietly fall apart once people do the resource estimation

[QuantumToken65]

Worth remembering Daniel Simon has serious pedigree, his own algorithm from the 90s directly inspired Shors factoring algorithm, so this isnt some random preprint from an unknown source, that alone means the lattice cryptography community will take the review seriously rather than dismissing it immediately

[NightHarbour30]

If this actually gets validated it would probably be good news for PQC chip vendors longer term rather than bad news, a real narrowing of the security margin on lattice schemes is exactly the kind of headline that accelerates enterprise and government urgency to actually migrate hardware, not the opposite

[DeepCourier]

The subset sum oracle gap Regev left open back in the day has been sitting there for over two decades, if Simon genuinely closed that gap without needing an idealized shortcut thats a real piece of unfinished business in quantum algorithms getting resolved regardless of the cryptographic implications

[PowerhouseHobbs_Fan]

This is a good real world example of why PQC transition plans usually build in crypto agility from the start rather than betting everything on one specific algorithm family, if lattice based schemes ever did take a real hit the industry would need to pivot to hash based or code based alternatives relatively quickly

[RuntimeCandle]

Would want to see the actual resource estimate translated into logical qubits before taking this anywhere near seriously as a near term threat, plenty of polynomial time quantum algorithms exist on paper that would still need millions of high fidelity qubits to run at cryptographically relevant sizes, which is nowhere close to todays hardware

[CollapseState75]

Tolerating faulty quantum samples at a rate as high as one over the log of the problem size is a surprisingly generous error tolerance claim, that specific detail is going to get heavily scrutinized since noise tolerance claims in these hidden subgroup style algorithms have tripped up prior papers before

[Router48]

This feels like one of those papers where the footnotes may be more important than the headline. If the claimed algorithm really gives a polynomial-time solution to the relevant Dihedral Coset Problem, that could have serious consequences for assumptions used in parts of post-quantum cryptography. But the phrase polynomial time covers a gigantic range of possible realities.

A useful analogy is finding a clever shortcut for a route that used to take exponential time. If the shortcut takes ten million years on the machines we can build, it is mathematically transformative but not exactly tomorrow morning's security incident. Cryptography needs both the complexity result and an implementation-level analysis before we can say which schemes are actually threatened.

There is also an important difference between weakening a mathematical foundation and invalidating every system built around it. A particular construction might rely on several assumptions, have parameter choices that remain safe, or be replaceable with another primitive. The sensible response is therefore not panic but pressure-testing: check the proof, determine the concrete complexity, map the result onto real schemes, and see whether independent teams reach the same conclusion. If all of that survives, then we can start reaching for the emergency coffee.

[Weary Wolfhound]

The square root of n polylogarithmic approximation factor for the Shortest Vector Problem is genuinely not the same as solving SVP exactly, cryptographers set their security parameters with a lot of margin specifically to survive approximation algorithms like this without an actual attack

[Jedi Stuart]

LAES and EnSilica stock probably sees some short term volatility off headlines like this regardless of the actual technical nuance, market reactions to scary sounding quantum cryptography news rarely wait around for the peer review process to actually finish

[TealBear]

This is going to shock some quantum companies working on Lattice based security PQC. Though I think its set to be upgradable so long term should be ok I think.

[CipherMonk37]

Having Micciancio, Vaikuntanathan and Vidick already reviewing this is a good sign the process is happening the right way, those are about as credible a set of names as you could hope for scrutinizing a lattice cryptography result before anyone treats it as confirmed

[WeightWarden]

The exciting part here is the distinction between a result that changes our understanding of a problem and one that immediately breaks deployed cryptography. A polynomial-time algorithm would be a huge theoretical development, but there is a long road between that and something an attacker can actually run at useful parameters

For the practical side, the missing estimates matter enormously. How does the running time scale with the security parameter? What are the constants? What kind of quantum memory and error correction would be required? An asymptotically better algorithm can still be useless for decades if the resource requirements explode in the range that cryptographic systems actually use

The good news is that this is exactly the sort of result the community should scrutinize rather than dismiss. Independent researchers trying to reproduce the argument, identify hidden assumptions, and connect it to concrete cryptographic constructions will tell us much more than the headline does. A preliminary claim getting a lot of attention is not the same thing as a practical attack, and it is perfectly reasonable to be excited and cautious at the same time.