Paper 2026/155

Module Learning With Errors and Structured Extrapolated Dihedral Cosets

Abstract

The Module Learning With Errors (MLWE) problem is the fundamental hardness assumption underlying the key encapsulation and signature schemes ML-KEM and ML-DSA, which have been selected by NIST for post-quantum cryptography standardization. Understanding its quantum hardness is crucial for assessing the security of these standardized schemes. Inspired by the equivalence between LWE and Extrapolated Dihedral Cosets Problem (EDCP) in [Brakerski, Kirshanova, Stehlé and Wen, PKC 2018], we show that the MLWE problem is as hard as a variant of the EDCP, which we refer to as the structured EDCP (stEDCP). This extension from EDCP to stEDCP relies crucially on the algebraic structure of the ring underlying MLWE: the extrapolation depends not only on the noise rate, but also on the ring’s degree. In fact, an stEDCP state forms a superposition over an exponential (in ring degree) number of possibilities. Our equivalence result holds for MLWE defined over power-of-two cyclotomic rings with constant module rank, a setting of particular relevance in cryptographic applications. Moreover, we present a reduction from stEDCP to EDCP. Therefore, to analyze the quantum hardness of MLWE, it may be advantageous to study stEDCP, which might be easier than EDCP.