Cryptology ePrint Archive: Report 2020/1020
Towards Classical Hardness of Module-LWE: The Linear Rank Case
Katharina Boudgoust and Corentin Jeudy and 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.
Category / Keywords: foundations / Lattice-based cryptography, module learning with errors, classical hardness, binary secret
Original Publication (with minor differences): IACR-ASIACRYPT-2020
Date: received 24 Aug 2020, last revised 27 Aug 2020
Contact author: katharina boudgoust at irisa fr
Available format(s): PDF | BibTeX Citation
Version: 20200827:065744 (All versions of this report)
Short URL: ia.cr/2020/1020
[ Cryptology ePrint archive ]