Entropic Hardness of Module-LWE from Module-NTRU

Katharina Boudgoust; Corentin Jeudy; Adeline Roux-Langlois; Weiqiang Wen

Paper 2022/245

Entropic Hardness of Module-LWE from Module-NTRU

Katharina Boudgoust, Aarhus University

Corentin Jeudy

, Orange Labs, Applied Crypto Group, Univ Rennes, CNRS, IRISA

Adeline Roux-Langlois, Normandie Univ, UNICAEN, ENSICAEN, CNRS, GREYC

Weiqiang Wen, LTCI, Telecom Paris, Institut Polytechnique de Paris

Abstract

The Module Learning With Errors problem (M-LWE) has gained popularity in recent years for its security-efficiency balance, and its hardness has been established for a number of variants. In this paper, we focus on proving the hardness of (search) M-LWE for general secret distributions, provided they carry sufficient min-entropy. This is called entropic hardness of M-LWE. First, we adapt the line of proof of Brakerski and Döttling on R-LWE (TCC’20) to prove that the existence of certain distributions implies the entropic hardness of M-LWE. Then, we provide one such distribution whose required properties rely on the hardness of the decisional Module-NTRU problem.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Published elsewhere. Indocrypt 2022
DOI: 10.1007/978-3-031-22912-1_4
Keywords: Lattice-based Cryptography Module Learning With Errors Entropic Hardness Module-NTRU
Contact author(s): katharina boudgoust @ cs au dk
corentin jeudy @ irisa fr
adeline roux-langlois @ cnrs fr
weiqiang wen @ telecom-paris fr
History: 2023-02-20: last of 3 revisions; 2022-03-02: received; See all versions
Short URL: https://ia.cr/2022/245
License: CC BY

BibTeX

@misc{cryptoeprint:2022/245,
      author = {Katharina Boudgoust and Corentin Jeudy and Adeline Roux-Langlois and Weiqiang Wen},
      title = {Entropic Hardness of Module-{LWE} from Module-{NTRU}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/245},
      year = {2022},
      doi = {10.1007/978-3-031-22912-1_4},
      url = {https://eprint.iacr.org/2022/245}
}