#latticecrypto — Public Fediverse posts on home.social

Marin Ivezic @[email protected] · 2026-08-06 · 14:49 UTC

Daniel Simon, creator of the algorithm that catalyzed Shor's, claims a polynomial-time quantum algorithm for the Dihedral Coset Problem (ePrint 2026/1591). If correct, the asymptotic security assumptions behind ML-KEM and ML-DSA would need reassessment.

Related interesting part: Wen and Zheng at Télécom Paris (ePrint 2026/155, accepted to CRYPTO 2026 and therefore peer-reviewed) prove that Module-LWE is quantum-polynomially equivalent to a structured dihedral variant, over the power-of-two cyclotomic rings with constant module rank that ML-KEM actually uses in production. They also reduce that structured variant to plain EDCP. The reduction chain between Simon's claim and the algorithms in your TLS stack has fewer unproven joints than it did a week ago, and half of that chain is now peer-reviewed.

Simon's paper is preliminary, several proofs are sketches, and the final SVP/LWE corollary rests on personal communications rather than published derivations. No concrete attack on any NIST parameter set is presented or costed. I am not a theoretical cryptographer and I am not declaring this proven. I am waiting for people like Micciancio, Peikert, Regev, Ducas to review it.

But this is the third event this summer hitting PQC from a different angle.

Bernstein demonstrated ML-DSA signing-key recovery in under one second by exploiting implementation flaws. The algorithm itself is fine; what organizations actually deploy is not. The attack surface is the gap between a correct specification and a correct implementation, and that gap exists in every deployment.

Anthropic's AI model autonomously recovered signing keys from HAWK-256 challenge instances. HAWK is a NIST Round 3 signature candidate, not a deployed standard, so nothing in production was touched. But the result showed that AI systems are now producing original cryptanalysis, not just assisting human researchers. Every deprecated or candidate algorithm still running in your estate became easier to attack the moment that capability crossed the line.

And now Simon's claim against the mathematical foundations themselves, with a peer-reviewed bridge connecting it to ML-KEM's specific hardness assumption.

Three different attack classes: implementation bugs found by a human, a PQC candidate broken autonomously by AI, and a theoretical quantum algorithm targeting foundational lattice assumptions.

If the lesson were just "lattice math is fragile," one event would suffice.

The lesson is that your cryptographic attack surface is wider than any single threat model covers, and the only architecture that absorbs all three is one built to replace algorithms without rebuilding infrastructure. I.e. crypto-agility.

SLH-DSA, LMS/XMSS, HQC, and everything hash-based or code-based is untouched by all of this.

Full analysis of the Simon paper, including where the proof is most vulnerable and what it means for migration planning:

https://postquantum.com/security-pqc/simon-quantum-algorithm-lattice-pqc/

#infosec #cybersecurity #PQC #postquantum #cryptography #quantum #MLKEM #latticecrypto #cryptoagility

#infosec #cybersecurity #pqc #postquantum #cryptography #quantum