Description
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.
Practical infos
Next sessions
-
TBA
Speaker : Eran Lambooij - Inria
-
Cryptography
-
-
Key Attack on the ACDGV Matrix Encryption Scheme
Speaker : Anmoal Porwal - Technical University of Munich
I will present our key-recovery attack on the ACDGV public-key encryption scheme proposed at ASIACRYPT 2024 by Aragon, Couvreur, Dyseryn, Gaborit, and Vinçotte. The secret key is a Gabidulin code hidden by appending random rows and columns and by left- and right-multiplication with invertible matrices. Our attack exploits the resulting algebraic structure to recover an equivalent secret key. It[…]-
Cryptography
-
Asymmetric primitive
-