Weiqiang Wen and Jinwei Zheng of Télécom Paris, part of the Institut Polytechnique de Paris, have proved that Module Learning With Errors, known as Module-LWE or MLWE, is as hard for a quantum computer as a new structured version of the extrapolated dihedral coset problem (EDCP). The authors first posted the paper, which was accepted to the CRYPTO 2026 conference, to the IACR Cryptology ePrint Archive on January 30 and last revised it on July 16.
In Module-LWE, a solver must recover a secret from noisy linear equations in which the unknowns are polynomials. NIST’s ML-KEM (CRYSTALS-Kyber) standard is based on it, and its ML-DSA (CRYSTALS-Dilithium) standard is based on it together with a related problem, Module-SIS. The authors presented no algorithm that solves either problem and no attack on ML-KEM, ML-DSA, or any other scheme.
Module-LWE is a lattice problem, one of a family of questions about grids of points that repeat regularly across hundreds of dimensions. In the dihedral coset problem (DCP), a quantum computer must find a hidden amount from many quantum states, each a superposition of two numbers that differ by that amount. In the extrapolated version, each state spreads across several multiples of that amount.
What the authors proved
In their abstract, Wen and Zheng called Module-LWE “the fundamental hardness assumption underlying the key encapsulation and signature schemes ML-KEM and ML-DSA.” They wrote that they proved the equivalence for Module-LWE over “power-of-two cyclotomic rings with constant module rank, a setting of particular relevance in cryptographic applications.”
In such a ring, arithmetic is done on polynomials taken modulo X^d + 1, where d is a power of two. The module rank is the number of these polynomials in the secret. NIST chose this setting for ML-KEM, specifying polynomials modulo X^256 + 1, a modulus of 3329, module ranks of 2, 3, and 4, and noise drawn from a centered binomial distribution in FIPS 203.
In the authors’ new variant, IP-M-EDCP, the extrapolation depends on the ring’s degree, d, as well as on the noise rate. Each state is a superposition over a set of possibilities that grows exponentially with that degree, they wrote.
Wen and Zheng also gave a reduction from IP-M-EDCP to the plain EDCP. Under such a reduction, any efficient algorithm for EDCP can be converted into one for IP-M-EDCP. “Therefore, to analyze the quantum hardness of MLWE, it may be advantageous to study IP-M-EDCP, which might be easier than EDCP,” they wrote.
Earlier results on the same problems
Wen co-wrote the 2018 paper in which the extrapolated problem was introduced. In it, Zvika Brakerski, Elena Kirshanova, Damien Stehlé, and Wen showed that under quantum polynomial-time reductions, plain Learning With Errors (LWE), the unstructured form of the problem, is equivalent to EDCP. They wrote that a quantum solution for LWE “might not require the full power of solving DCP.”
At CRYPTO 2025, Shi Bai, Hansraj Jangir, Elena Kirshanova, Tran Ngo, and William Youmans presented a quasi-polynomial-time quantum algorithm for EDCP over power-of-two moduli. A quasi-polynomial running time grows faster than any polynomial in the problem size but far more slowly than an exponential one. The authors wrote that their algorithm uses a quasi-polynomial number of samples, the inputs a solver receives.
Bai and his co-authors wrote that their algorithm “does not affect the security of LWE with standard parameters.” They added that, under the reduction from standard LWE to EDCP, the number of samples is limited to a polynomial. ML-KEM’s modulus, 3329, is a prime number, not a power of two.
On August 3, Daniel R. Simon of Amazon Web Services submitted an unreviewed draft to the Cryptology ePrint Archive, claiming a polynomial-time quantum algorithm for the DCP itself.
Limits of the result
In the abstract, Wen and Zheng did not apply the result to ML-KEM’s standardized parameters, such as its modulus, its binomial noise, and its fixed number of samples. To turn the result into an attack on ML-KEM, researchers would need a quantum algorithm for IP-M-EDCP or EDCP that beats known methods. That algorithm would also have to work at ML-KEM’s parameters, with the number of samples available through the reductions.
CRYPTO 2026, where accepted papers are presented, runs August 17–20 in Santa Barbara, California.
Update, November 12, 2026: On August 15, Aparna Gupte, Seyoon Ragavan, and Mark Zhandry posted a paper arguing that Simon’s algorithm does not solve the DCP. On September 28, three researchers in Rennes, France, extended the 2025 quasi-polynomial EDCP algorithm from power-of-two moduli to powers of any fixed prime. They wrote that their result does not, by itself, give a quasi-polynomial algorithm for standard LWE.
