Description
We introduce a new variant MP-LWE of the Learning With Errors problem (LWE) making use of the Middle Product between polynomials modulo an integer q. We exhibit a reduction from the Polynomial-LWE problem (PLWE) parametrized by a polynomial f, to MP-LWE which is defined independently of any such f. The reduction only requires f to be monic with constant coefficient coprime with q. It incurs a noise growth proportional to the so-called expansion factor of f. We also describe a public-key encryption scheme with quasi-optimal asymptotic efficiency (the bit-sizes of the keys and the run-times of all involved algorithms are quasi-linear in the security parameter), which is secure against chosen plaintext attacks under the MP-LWE hardness assumption. The scheme is hence secure under the assumption that PLWE is hard for at least one polynomial f of degree n among a family of f’s which is exponential in n.
Next sessions
-
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
-
-
Module Learning With Errors and Structured Extrapolated Dihedral Cosets
Speaker : Jinwei Zheng - Télécom Paris
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[…]-
Cryptography
-