What the Dihedral Coset Claim Means for Lattice Standards

A paper dated July 31 and posted to the Cryptology ePrint Archive this week claims a polynomial-time quantum algorithm for the Dihedral Coset Problem. The author is Daniel R. Simon of the AWS Cryptography Group, known for the 1994 oracle separation that inspired Shor’s algorithm. Combined with reductions published by Regev in 2004 and improved by Brakerski, Kirshanova, Stehlé and Wen in 2018, the claimed algorithm would solve approximate SVP within a √n polylog(n) factor and LWE at comparable noise rates, in quantum polynomial time. Those parameters reach the assumptions behind the deployed lattice standards. The paper attacks no concrete parameter set.

What the paper claims

Regev showed in 2004 that a dihedral solver breaks lattice problems, and he gave a polynomial-time quantum algorithm for the dihedral problem, but it required a subset sum oracle nobody has. Kuperberg’s algorithm needs no oracle but requires error-free samples and runs in time 2^O(√n). The lattice reductions emit faulty samples, so the combination has never beaten classical lattice reduction. The draft replaces the oracle step with a Hadamard-and-measure procedure over groups of samples and claims tolerance of a faulty sample rate up to 1/O(log n), enough to accept the samples the reductions emit at useful approximation factors. Twenty years of work on the dihedral route stalled on exactly this step.

What it does not establish

The title says preliminary draft. The load-bearing lemmas are proof sketches. Two citations are personal communications, and those two support the headline corollary. The construction is asymptotic, drawing kn^c+1 quantum samples with c at least 12, so even a correct proof prices no attack on any concrete parameter set. Classical security is untouched. Nothing in the paper affects data protected against classical adversaries today.

The precedent is Yilei Chen’s April 2024 claim of a polynomial-time quantum algorithm for LWE. Hongxun Wu and Thomas Vidick independently found a bug the author could not repair, eight days after posting, and the claim was withdrawn. Vidick appears in the acknowledgements of the new draft, so the reviewers most likely to find a fatal flaw have seen it. Three developments would settle the status: a technical verdict on the proof from the lattice community, a revision replacing the sketches with full arguments, or a named counterexample to the amplitude claims in Lemmas 3 and 4. None has occurred. No conclusion about ML-KEM security follows from the paper today.

First reactions

The first responses arrived within a day and split along familiar lines. Daniel Bernstein wrote that his recommendations hold whether or not the proof survives: “use the largest parameters you can afford; keep the ECC seatbelt; keep investing in alternatives.” Chris Peikert replied that an attack which collapses leaves the status quo unchanged, one more serious attempt by a quantum expert that failed. The disagreement is about how much confidence lattice assumptions deserve. Neither position changes the operational work, and Bernstein’s three recommendations resolve to attributes a scanner reads from an estate: parameter sizes in use, hybrid presence per connection, and the distribution of algorithm families across assets.

Scope if it holds

The affected family is lattice cryptography: ML-KEM (FIPS 203), ML-DSA (FIPS 204), plain-LWE schemes such as FrodoKEM, and lattice-based homomorphic encryption. The chain from a dihedral solver to those standards runs through published reductions. Brakerski, Kirshanova, Stehlé and Wen proved LWE equivalent to extrapolated dihedral cosets in 2018. Wen and Zheng relate Module-LWE, the assumption under ML-KEM and ML-DSA, to a structured variant they call stEDCP in ePrint 2026/155. Their abstract states one direction of that relation. The direction an attacker needs, from a dihedral solver to a Module-LWE solver, sits in the full paper and deserves confirmation before treating ML-KEM as covered. FN-DSA rests on NTRU lattices and sits outside the LWE chain, although a general algorithm for polynomial-factor approximate SVP would raise its own questions for NTRU keys. Outside the family sit SLH-DSA (FIPS 205, hash-based), the code-based KEMs Classic McEliece and HQC, and symmetric cryptography at adequate key lengths.

Two consequences follow for anyone whose threat model includes recorded traffic. Confidentiality that rests only on lattice key exchange joins RSA and ECDH in the harvest-now-decrypt-later class, readable once a sufficiently capable machine exists. Hybrid key exchange such as X25519 with ML-KEM defends against a classical break of ML-KEM, and it does not defend against this scenario, where a cryptographically relevant quantum computer defeats both components, Shor on the curve and the dihedral route on the lattice. The hedge against a family failure is diversity across mathematical assumptions. The engineering cost of the main code-based alternative is measurable now, and [PQ]math includes a Classic McEliece preset for that comparison.

What it means for migration planning

The operational test arrived before any verdict on correctness. Within hours of a paper like this, a security team should be able to answer one query: which assets depend on a lattice assumption as their only post-quantum mechanism. That is a filter over a cryptographic bill of materials by algorithm family. A CycloneDX 1.6 CBOM records the family per asset, and [PQ]probe emits that inventory from code, configuration, and network evidence, so the query takes minutes. A team that cannot run it has no measurement of its exposure to this class of event.

The harder question is the cost of changing the answer: how long a swap takes and what it breaks. Algorithm selections have already shifted this year, as the HAWK withdrawal showed on the signature side, and they will shift again. Migration duration and swap cost are the numbers to track through each of these events, and both need to fall far below where they sit today, because changes of this type will recur for the rest of the transition. The verdict on the proof changes none of that.

Sources: