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 structured variant of the EDCP, which we refer to as the Integer Polynomial Module EDCP(IP-M-EDCP). This extension from EDCP to IP-M-EDCP 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 IP-M-EDCP 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 IP-M-EDCP to EDCP. Therefore, to analyze the quantum hardness of MLWE, it may be advantageous to study IP-M-EDCP, which might be easier than EDCP.