Paper 2020/119

Hardness of LWE on General Entropic Distributions

Zvika Brakerski and Nico Döttling

Abstract

The hardness of the Learning with Errors (LWE) problem is by now a cornerstone of the cryptographic landscape. In many of its applications the so called ``LWE secret'' is not sampled uniformly, but comes from a distribution with some min-entropy. This variant, known as ``Entropic LWE'', has been studied in a number of works, starting with Goldwasser et al. (ICS 2010). However, so far it was only known how to prove the hardness of Entropic LWE for secret distributions supported inside a ball of small radius. In this work we resolve the hardness of Entropic LWE with arbitrary long secrets, in the following sense. We show an entropy bound that guarantees the security of arbitrary Entropic LWE. This bound is higher than what is required in the ball-bounded setting, but we show that this is essentially tight. Tightness is shown unconditionally for highly-composite moduli, and using black-box impossibility for arbitrary moduli. Technically, we show that the entropic hardness of LWE relies on a simple to describe lossiness property of the distribution of secrets itself. This is simply the probability of recovering a random sample from this distribution $s$, given $s+e$, where $e$ is Gaussian noise (i.e. the quality of the distribution of secrets as an error correcting code for Gaussian noise). We hope that this characterization will make it easier to derive entropic LWE results more easily in the future. We also use our techniques to show new results for the ball-bounded setting, essentially showing that under a strong enough assumption even polylogarithmic entropy suffices.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in EUROCRYPT 2020
Keywords
Learning with ErrorsEntropic LWE
Contact author(s)
zvika brakerski @ weizmann ac il
History
2020-06-23: revised
2020-02-06: received
See all versions
Short URL
https://ia.cr/2020/119
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/119,
      author = {Zvika Brakerski and Nico Döttling},
      title = {Hardness of LWE on General Entropic Distributions},
      howpublished = {Cryptology ePrint Archive, Paper 2020/119},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/119}},
      url = {https://eprint.iacr.org/2020/119}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.