Classical hardness of learning with errors

Zvika Brakerski, Adeline Langlois, Chris Peikert, Oded Regev, Damien Stehlé

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We show that the Learning with Errors (LWE) problem is classically at least as hard as standard worst-case lattice problems, even with polynomial modulus. Previously this was only known under quantum reductions. Our techniques capture the tradeoff between the dimension and the modulus of LWE instances, leading to a much better understanding of the landscape of the problem. The proof is inspired by techniques from several recent crypto- graphic constructions, most notably fully homomorphic encryption schemes.

Original languageEnglish (US)
Title of host publicationSTOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing
Pages575-584
Number of pages10
DOIs
StatePublished - 2013
Event45th Annual ACM Symposium on Theory of Computing, STOC 2013 - Palo Alto, CA, United States
Duration: Jun 1 2013Jun 4 2013

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other45th Annual ACM Symposium on Theory of Computing, STOC 2013
CountryUnited States
CityPalo Alto, CA
Period6/1/136/4/13

Keywords

  • Lattices
  • Learning with errors

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Classical hardness of learning with errors'. Together they form a unique fingerprint.

  • Cite this

    Brakerski, Z., Langlois, A., Peikert, C., Regev, O., & Stehlé, D. (2013). Classical hardness of learning with errors. In STOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing (pp. 575-584). (Proceedings of the Annual ACM Symposium on Theory of Computing). https://doi.org/10.1145/2488608.2488680