International Association for Cryptologic Research

International Association
for Cryptologic Research


Towards Classical Hardness of Module-LWE: The Linear Rank Case

Katharina Boudgoust
Corentin Jeudy
Adeline Roux-Langlois
Weiqiang Wen
DOI: 10.1007/978-3-030-64834-3_10
Search ePrint
Search Google
Abstract: We prove that the module learning with errors (M-LWE) problem with arbitrary polynomial-sized modulus $p$ is \emph{classically} at least as hard as standard worst-case lattice problems, as long as the module rank $d$ is not smaller than the ring dimension $n$. Previous publications only showed the hardness under quantum reductions. We achieve this result in an analogous manner as in the case of the learning with errors (LWE) problem. First, we show the classical hardness of M-LWE with an exponential-sized modulus. In a second step, we prove the hardness of M-LWE using a binary secret. And finally, we provide a modulus reduction technique. The complete result applies to the class of power-of-two cyclotomic fields. However, several tools hold for more general classes of number fields and may be of independent interest.
Video from ASIACRYPT 2020
  title={Towards Classical Hardness of Module-LWE: The Linear Rank Case},
  booktitle={Advances in Cryptology - ASIACRYPT 2020},
  author={Katharina Boudgoust and Corentin Jeudy and Adeline Roux-Langlois and Weiqiang Wen},