CRYPTO 2026 Paper Links ML-KEM's Math to EDCP

Cookie policy

Quantum Security & PQC

A Peer-Reviewed CRYPTO 2026 Paper Just Gave ML-KEM’s Foundation a New Quantum Target

Marin Ivezic

Follow on X

Send an email

August 6, 2026 10 minutes read

Table of Contents

August 6, 2026 — Today I published an analysis of Daniel Simon’s preliminary claim of a polynomial-time quantum algorithm for the Dihedral Coset Problem. That paper is unverified, its proofs are sketches, and it may not survive peer review. This article is about a different paper that already has, and that I think matters just as much.

Weiqiang Wen and Jinwei Zheng of Télécom Paris have published "Module Learning With Errors and Structured Extrapolated Dihedral Cosets", the full revision of a paper accepted to CRYPTO 2026, one of the field’s top venues. Their result is precise and narrow: they prove a quantum polynomial-time equivalence between Module-LWE and a new structured variant of the Extrapolated Dihedral Coset Problem, and they show that this structured variant reduces to plain EDCP. The equivalence holds for power-of-two cyclotomic rings with constant module rank, which is the setting ML-KEM (FIPS 203) uses in production.

The bottom line: this paper maps the mathematical assumption behind ML-KEM into a problem class that three separate research groups are actively studying with quantum algorithms. It does not break anything. It does not even claim to weaken anything. What it does is draw a line on a map that was not there before, connecting a deployed standard to a target that the authors themselves say might be easier than the problem it reduces to.

Why This Paper Matters Independently of Simon

When I analyzed Simon’s DCP claim, I identified a gap: Simon’s paper addresses plain LWE and general lattice SVP, while ML-KEM and ML-DSA rest on Module-LWE, which carries additional algebraic structure. Simon’s stated LWE consequences concern plain LWE. They do not by themselves establish a result for Module-LWE, whose samples carry additional ring structure. The connection between "DCP is broken" and "ML-KEM is threatened" required hand-waving across that gap.

Wen and Zheng fill part of it with published, peer-reviewed mathematics. They show that Module-LWE is quantum-polynomially equivalent to a structured problem they call IP-M-EDCP (Integer Polynomial Module Extrapolated Dihedral Coset Problem), and that IP-M-EDCP reduces to plain EDCP. The chain they build is:

Module-LWE ↔ IP-M-EDCP → EDCP

That chain matters whether or not anyone solves the DCP. If Simon’s DCP algorithm survives scrutiny, and if its techniques extend to the Gaussian-weighted EDCP instances that Wen-Zheng produce (which is itself unproven), it may be possible to compose the results for matching parameter regimes. No such end-to-end composition has been demonstrated. If Simon’s proof fails, the chain still exists, waiting for the next algorithm that pushes further into EDCP territory.

The Research Map

The paper sits at the intersection of three research lines that have been converging for two decades. Understanding where each line stands is the point of this article, because the strategic question for CISOs and migration planners is not whether one paper or another is correct. It is whether the overall trajectory of research on lattice quantum hardness supports the assumption that these problems will remain hard for quantum computers indefinitely.

Line 1: LWE and the Dihedral Coset Problem. Oded Regev connected the DCP to lattice problems in 2004. Brakerski, Kirshanova, Stehlé and Wen formalized the connection in 2018, proving that LWE is quantum-polynomially equivalent to the Extrapolated Dihedral Coset Problem for suitable parameters. That 2018 result established EDCP as the quantum lens through which to study LWE hardness. Wen is a co-author of both the 2018 paper and the new one, so this is the same research program continuing, not a coincidence.

Line 2: Attacking EDCP directly. Greg Kuperberg gave a subexponential-time quantum algorithm for the Dihedral Hidden Subgroup Problem in 2005, running in roughly 2^O(√n) time. For twenty years, nobody improved on that bound in a way that changed the security picture. In 2024, Yilei Chen posted a polynomial-time claim for lattice problems via an EDCP variant; Vidick and Wu independently found the flaw and Chen withdrew the paper within days. Then at CRYPTO 2025, Bai, Jangir, Kirshanova, Ngo and Youmans presented a quasi-polynomial-time quantum algorithm for EDCP over power-of-two moduli, a genuine algorithmic advance. Two barriers prevent it from composing with the Wen-Zheng chain for ML-KEM: the algorithm requires quasi-polynomially many EDCP samples, while the relevant reductions provide only polynomially many, and it applies only to power-of-two moduli, while ML-KEM uses q = 3329. Bai et al. explicitly state that their current result does not affect the security of LWE with standard parameters. Wen and Zheng cite it...