Is Some Lattice-Based Post-Quantum Cryptography Broken? (update: No!)
A click-bait layman overview of the possible implications of Daniel R. Simon most recent submission
Disclaimer: I am not a cryptographer, nor an Euclidean Lattice expert. My understanding of the problems at hand remains limited and I can only share what I understand. We will have to wait for qualified people to actually help sort the strength and ramifications of this piece of news. My intent with this post is to gather pieces of information and references I looked at when searching this topic so others interested in this can have useful pointers .
Update August 15th 2026: it seems the paper presented in this post had some critical errors which makes the algorithm non-functional (at least not in polynomial quantum time). See for example https://github.com/sragavan99/lean-ePrint-2026-1591-refutation
On August 3rd 2026, Daniel R. Simon from AWS submitted “A Polynomial-Time Quantum Algorithm for the Dihedral Coset Problem” to the Cryptology ePrint Archive. The manuscript, dated July 31st, was approved on August 6, 2026 (as far as I know, without peer-review, and as stated by the author the manuscript is a preliminary draft).
This manuscript introduces a polynomial-time quantum algorithm to solve the Dihedral Coset Problem (DCP). This is one of the current holy graal of cryptography, solving the hidden subgroup problem (HSP) in quantum polynomial time (BQP) would break some of the Post-Quantum Cryptography (PQC) algorithms based on approximate version of some the “hard” lattices problems (Shortest Vector Problem and Learning With Error problems).
Who is behind this submission?
Daniel R. Simon is a recognized and accomplished member of the cryptography community: he invented Simon’s problem and Simon’s algorithm and has been involved in quantum computing and cryptography for many decades. Those are reasons to consider his work serious. Thorough peer reviews are still required, mistakes and short cuts can remain and some people are calling in question some assumptions in the paper, but overall the paper is not coming from a newbie [as yours truly] in the domain, it is coming from someone with a proven track record and demonstrated seriouness.
The Dihedral Coset Problem (DCP) and its variants (like the Dihedral Subset Problem or DSP) have been studied for some time. [Regev2005] introduced a reduction from the unique Shortest Vector Problem to the DSP. They represent a known link in a possible chain to attack some lattrice problems.
Possible blast radius of the discovery
If Simon’s new link works as publicized, this would mean that some of the Post-Quantum Cryptography (PQC) algorithms would not actually be immune to quantum computers. Based on Marin Ivezic’s report, algorithms such as ML-KEM/Kyber, ML-DSA/Dilithium (although more indirectly) would be affected. Algorithms based on other non-lattice primitives (such as SLH-DSA, based on hash chains or HQC-based schemes, Hamming Quasi-Cyclic) would not be impacted; FN-DSA/FALCON (based on a different set of lattice problem) would not be directly affected either.
The discovery would impact other fields based on the hardness of approximate lattices problems such as the Fully Homomorphic Encryption (FHE) schemes based on LWE.
Further readings
Marin Ivezic published on postquantum.com (his personal blog) an interesting deep dive on Simon’s paper linking it with a peer-reviewed CRYPTO 2006 paper linking ML-KEM and a specific class of quantum problems. The post presents the context, the paper and its author, the possible implications, the unknown. I used a lot of it as material for this post.
Reddit’s r/crypto has a thread discussing the issue.
The Quantum Cryptanalysis discord server seems to be another place where the conversation happen: lots of activity on the paper.
What now?
The cryptography community is in turmoil and there seem to be multiple discussions and effort going on to proofread Simon’s work. We can certainly expect feedback in the coming weeks. It is highly likely that the subject will be discussed at the Crypto 2026 conference.
Whatever the final outcome, this event is, in my opinion, a good justification that PQC should continue to diversify and rely on as many problems not known to be easy for classical and quantum computers. I did not invent anything there, Daniel J. Bernstein shared a similar opinion much earlier (with much much more credential). We should also salute the effort of the cryptography community to continue attacking those theoretical problems with real pragmatic impacts and to keep investing in developing new schemes and testing them.
Reference(s):
The actual pre-print being discussed:
Cryptology ePrint Archive of “A Polynomial-Time Quantum Algorithm for the Dihedral Coset Problem”: https://eprint.iacr.org/2026/1591
A refutation of the paper:
“The ePrint:2026/1591 Quantum Algorithm Does Not Solve DCP“ https://github.com/sragavan99/lean-ePrint-2026-1591-refutation (to appear on ePrint)
Interesting literature:
[Regev2005] Oded Regev’s 2005: Quantum Computation and Lattice Problems
News covering the issue:
Marin Ivezic’s blog https://postquantum.com/security-pqc/simon-quantum-algorithm-lattice-pqc/
Marin Ivezic’s blog on a relevant recent paper: https://postquantum.com/security-pqc/mlwe-edcp-crypto-2026-ml-kem/
Forum(s) discussing the issue:
Update August 9th, 2026, 9:36PM (Pacific): Daniel Apon (Director of Cryptography at Anduril) is questioning some of the Lemmas (in particular Lemma 3), see https://lnkd.in/p/gB2NgMnd