Paper 2020/1238

Hardness of Entropic Module-LWE

Hao Lin, Mingqiang Wang, Jincheng Zhuang, and Yang Wang

Abstract

The Learning with Errors (LWE) problem is a versatile basis for building various purpose post-quantum schemes. Goldwasser et al. [ISC 2010] initialized the study of a variant of this problem called the Entropic LWE problem, where the LWE secret is generated from a distribution with a certain min-entropy. Brakerski and D{\"o}ttling recently further extended the study in this field, and first proved the hardness of the Entropic LWE problem with unbounded secret [Eurocrypt 2020], then gave a similar result for the Entropic Ring-LWE problem [TCC 2020]. In this work, we systematically study the hardness of the Entropic Module-LWE problem. Adapting the ``lossiness approach" to the module setting, we give lower entropy bounds for the secret distribution that guarantee the hardness of the Entropic Module-LWE problem in both search and decision cases, where results are divided into two settings: bounded and unbounded norm. We also present that our search entropy lower bound in the unbounded case is essentially tight. An application of our bounded result is to deduce the hardness for the Binary Module-LWE problem. One of our central techniques is a new generalized leftover hash lemma over rings, which might be of independent interest.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MAJOR revision.
Keywords
Post-quantum cryptographyEntropic Module-LWEBinary Module-LWEEntropic Ring-LWELeftover hash lemma
Contact author(s)
lhao17 @ mail sdu edu cn
History
2022-05-13: revised
2020-10-09: received
See all versions
Short URL
https://ia.cr/2020/1238
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1238,
      author = {Hao Lin and Mingqiang Wang and Jincheng Zhuang and Yang Wang},
      title = {Hardness of Entropic Module-LWE},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1238},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/1238}},
      url = {https://eprint.iacr.org/2020/1238}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.