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

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 as a candidate technique that might someday be adapted to IP-M-EDCP, listing it as an open problem alongside adapting Kuperberg’s algorithms. Simon’s unverified claim goes further, asserting polynomial time for the DCP itself.

Line 3: Module-LWE’s quantum reduction picture. Before Wen-Zheng, the direct dihedral equivalence had been established for plain LWE (through BKSW 2018), while the quantum hardness of Module-LWE was studied through module-lattice reductions and its relationships with other structured lattice problems. A direct Module-LWE analogue of EDCP was missing. Module-LWE, with its ring structure and module rank, needed its own treatment.

That treatment is what the CRYPTO 2026 paper provides.

What the Paper Proves

The result is built from three technical components. I will state each and then translate what it means for people who are not lattice researchers.

Theorem 1 (equivalence). For the cyclotomic polynomial f(x) = x^d + 1 with d a power of 2, there is a quantum polynomial-time equivalence between Module-LWE and the Gaussian IP-M-EDCP problem, with module rank n = O(1), modulus q = poly(d), and specific sample and noise parameters.

In plain terms: solving Module-LWE is computationally the same as solving IP-M-EDCP, and vice versa. If you can break one efficiently, you can break the other. If one is hard, so is the other.

The ring f(x) = x^d + 1 with d a power of 2 is not an arbitrary mathematical choice. It is the ring ML-KEM uses. ML-KEM-512 uses d = 256 with module rank 2. ML-KEM-768 uses d = 256 with module rank 3. ML-KEM-1024 uses d = 256 with module rank 4. All three are power-of-two cyclotomic rings with constant module rank. The ring family and constant-rank restriction overlap directly with ML-KEM’s parameter regime. The remaining theorem conditions (asymptotic modulus, Gaussian distributions, sample requirements) do not map automatically to ML-KEM’s standardized parameter sets, and that gap matters.

Theorem 2 (reduction to EDCP). There exists a quantum polynomial-time reduction from IP-M-EDCP to plain EDCP with the same modulus.

In plain terms: IP-M-EDCP is no harder than EDCP. Anything that solves EDCP also solves IP-M-EDCP. The authors go further, noting that a dimension-modulus switching technique lets them reduce the exponentially large modulus f(q) down to a polynomially large modulus q, so the final EDCP instance has dimension O(nd log q) and modulus q.

They also observe the converse is not established. IP-M-EDCP might be strictly easier than EDCP, meaning a quantum algorithm could solve IP-M-EDCP without solving EDCP in general. The authors write this as an explicit open problem and frame it as motivation for cryptanalysts: “it seems interesting to ask whether there exists an algorithm that solves IP-M-EDCP asymptotically faster than EDCP.”

That sentence is an invitation. The authors go further in Section 2.5, naming two specific approaches: adapting Kuperberg’s algorithms to exploit the extra structure of IP-M-EDCP, and investigating whether Bai et al.’s EDCP algorithm can be adapted to solve IP-M-EDCP with lower time or sample complexity. They are telling the community: here is a problem that is provably equivalent to a specified Module-LWE family, provably no harder than EDCP, and possibly easier. Study it.

The sample amplification step. The equivalence requires bridging a sample gap. The reduction from IP-M-EDCP to Module-LWE produces only O(log κ) samples, while the reverse direction needs poly(κ) samples. The authors close this gap using the Regularity Lemma of Lyubashevsky, Peikert and Regev, which applies to cyclotomic rings. This is why the full equivalence requires cyclotomic polynomials specifically. For other ring families, the authors prove one direction (MLWE to IP-M-EDCP given enough samples) but cannot close the loop.

What the Paper Does Not Prove

Five limitations matter for anyone trying to draw operational conclusions.

The equivalence covers search Module-LWE, not decision Module-LWE. Most cryptographic security proofs, including ML-KEM’s, work with the decision variant (distinguishing Module-LWE samples from random). The authors acknowledge this in their open problems section: their use of Rényi divergence “is particularly suitable for the search variants but does not naturally extend to decision variants.” Search-to-decision reductions are known in some MLWE settings, but Wen and Zheng do not establish or compose one here. Their theorem therefore does not directly cover the decisional formulation used in ML-KEM’s security analysis.

The constant module rank restriction is a mathematical necessity of the proof technique, not a convenience. The Rényi divergence analysis that makes the reduction from IP-M-EDCP to Module-LWE work requires module rank n = O(1). ML-KEM’s module ranks (2, 3, 4) satisfy this. But any lattice scheme using large module rank would fall outside the theorem’s scope.

No concrete attack is presented, attempted or costed. The paper is a reduction result, not a cryptanalysis result. It tells you that solving Module-LWE is equivalent to solving IP-M-EDCP; it does not solve either one.

ML-KEM’s actual parameters are not analyzed. The modulus, noise distribution (centered binomial rather than discrete Gaussian), sample count and security reduction from the KEM construction to the underlying Module-LWE problem all introduce parameter transformations that the paper does not trace. The paper does not perform this composition, and I am not aware of a complete concrete analysis that does.

Nothing about hash-based, code-based or symmetric cryptography is affected. SLH-DSA (FIPS 205), LMS, XMSS, HQC, AES, SHA-2 and SHA-3 are all outside the scope of this result.

The Uncomfortable Observation About Unstructured Lattices

One implication of the Wen-Zheng paper deserves separate attention because it inverts a piece of widely repeated advice.

ANSSI, France’s national cybersecurity agency, names FrodoKEM as an acceptable conservative alternative KEM, precisely because FrodoKEM avoids ring and module structure. The reasoning is that algebraic structure might be exploitable, so an unstructured-lattice scheme provides a hedge. Germany’s BSI keeps FrodoKEM on its acknowledged list for similar reasons. The advice has been: if you are worried about lattice structure being a weakness, use an unstructured lattice.

The Wen-Zheng paper introduces IP-M-EDCP as a structured problem equivalent to Module-LWE, and reduces it to plain EDCP. The 2018 BKSW paper established that plain LWE is equivalent to plain EDCP. FrodoKEM rests on plain LWE.

So the reduction chain for FrodoKEM is shorter, not longer, than the one for ML-KEM. FrodoKEM’s hardness assumption connects to EDCP without the intermediate IP-M-EDCP step. Any advance against EDCP engages FrodoKEM’s mathematical foundation through a chain that is no longer than ML-KEM’s.

This does not mean FrodoKEM is less secure than ML-KEM. The concrete parameters, key sizes, noise distributions and security margins differ, and reduction-chain length is not a security ordering. Bai et al.’s CRYPTO 2025 result provides a useful counterpoint: despite FrodoKEM using a power-of-two modulus, which superficially fits Bai’s modulus condition, their sample requirement prevents the result from reaching standard LWE. FrodoKEM remains a genuine hedge against attacks that exploit ring or module structure, which is what ANSSI and BSI recommended it for.

What it does not hedge against is a breakthrough in the broader LWE/EDCP problem family itself. Avoiding ring structure does not remove plain LWE from the dihedral research picture. For migration planners, the takeaway is that cross-family diversity, deploying a code-based or hash-based alternative alongside a lattice scheme, provides a broader hedge than structured-versus-unstructured lattice diversity. I made this argument in my Simon analysis and the Wen-Zheng paper gives it a precise mathematical form.

The Convergence

Three groups, working independently, are probing the same fault line from different angles.

Wen and Zheng mapped a specified search-Module-LWE family into the dihedral world and invited attacks on the structured variant. Bai, Jangir, Kirshanova, Ngo and Youmans produced a genuine algorithmic advance against a restricted EDCP regime at CRYPTO 2025, though their own sample and modulus constraints prevent it from reaching standard LWE or ML-KEM today. Simon claims to have crossed the polynomial-time threshold for DCP itself, but the claim is unverified and composing it through the EDCP transformations at relevant parameters is further work nobody has published.

One of these is accepted at CRYPTO 2026, one published at CRYPTO 2025, and the third is an unverified preliminary draft from a researcher whose previous algorithm reshaped the field. They are not the same result. None of them constitutes an attack on deployed systems, and specific mechanical gaps (sample counts, modulus shape, DCP-to-EDCP parameter losses) still separate them from one another and from deployed parameters. But they are pointed at the same problem family, and that family is the assumption central to NIST’s primary KEM and signature standards.

This is the picture I want CISOs and migration planners to hold in their heads when they make architectural decisions. Not “is lattice cryptography broken” (it is not) or “should I stop deploying ML-KEM” (you should not). The question is: does the trajectory of published, peer-reviewed quantum cryptanalysis research support the assumption that lattice hardness against quantum computers is a settled question?

The answer, as of CRYPTO 2026, is no.

What This Means for Your Migration

I would not change a single ML-KEM deployment decision based on this paper. The cryptanalytic consequence of Shor’s algorithm is established, HNDL exposure already exists, and migration deadlines are concrete. The theoretical challenge to lattice assumptions is undated and unquantified. Pausing migration to wait for resolution is bad arithmetic.

What I would change is the architectural assumptions behind the migration.

Treat lattice-only dependence as a concentration risk. If every KEM in your estate is ML-KEM and every signature is ML-DSA, you are running a single-family portfolio against a research environment that is actively producing new problem formulations and quantum-algorithmic results for that family. Put it in the risk register with an owner and a review date.

Get SLH-DSA into signature planning alongside ML-DSA rather than as a footnote. Its hash-based foundation is untouched by anything in the dihedral research line, and NIST standardized it for exactly this reason.

Track HQC. The code-based KEM that NIST selected in March 2025 as the non-lattice backup to ML-KEM rests on entirely different mathematics. Its standard is expected in 2027. This paper does not justify changing that timeline, but it strengthens the architectural case for preparing to support HQC when the standard arrives.

Build for algorithm replacement. The protocols, identities, key-management infrastructure and certificate chains around your algorithms should accept a swap without a multi-year rebuild. That is crypto-agility as an architecture discipline, not as a talking point. The organizations that have it will absorb the next paper, and the one after that, without breaking stride. The rest will discover, each time, that they built on an assumption rather than an architecture.

Those regulatory and business deadlines are still running. The research calendar does not consult them.