Paper 2020/1020

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

Katharina Boudgoust, Corentin Jeudy, Adeline Roux-Langlois, and Weiqiang Wen

Abstract

We prove that the module learning with errors (M-LWE) problem with arbitrary polynomial-sized modulus p is classically at least as hard as standard worst-case lattice problems, as long as the module rank d is not smaller than the number field degree 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.

Note: Section 4.1 simplified due to update of reference paper Albrecht and Deo from Asiacrypt'2017.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A minor revision of an IACR publication in ASIACRYPT 2020
DOI
10.1007/978-3-030-64834-3_10
Keywords
Lattice-based cryptographymodule learning with errorsclassical hardnessbinary secret
Contact author(s)
katharina boudgoust @ irisa fr
History
2021-03-16: last of 2 revisions
2020-08-27: received
See all versions
Short URL
https://ia.cr/2020/1020
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1020,
      author = {Katharina Boudgoust and Corentin Jeudy and Adeline Roux-Langlois and Weiqiang Wen},
      title = {Towards Classical Hardness of Module-LWE: The Linear Rank Case},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1020},
      year = {2020},
      doi = {10.1007/978-3-030-64834-3_10},
      note = {\url{https://eprint.iacr.org/2020/1020}},
      url = {https://eprint.iacr.org/2020/1020}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.