CISPA
Browse

Hardness of LWE on General Entropic Distribution

Download (459.43 kB)
conference contribution
posted on 2023-11-29, 18:12 authored by Zvika Brakerski, Nico DöttlingNico Döttling
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.

History

Preferred Citation

Zvika Brakerski and Nico Döttling. Hardness of LWE on General Entropic Distribution. In: International Conference on the Theory and Application of Cryptographic Techniques (EUROCRYPT). 2020.

Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

International Conference on the Theory and Application of Cryptographic Techniques (EUROCRYPT)

Legacy Posted Date

2020-03-31

Open Access Type

  • Unknown

BibTeX

@inproceedings{cispa_all_3058, title = "Hardness of LWE on General Entropic Distribution", author = "Brakerski, Zvika and Döttling, Nico", booktitle="{International Conference on the Theory and Application of Cryptographic Techniques (EUROCRYPT)}", year="2020", }

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC