[BLPRS13] Classical Hardness of Learning with Errors

Authors: Zvika Brakerski, Adeline Langlois, Chris Peikert, Oded Regev, Damien Stehlé | Venue: STOC 2013 | Source

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 cryptographic constructions, most notably fully homomorphic encryption schemes.

BibTeX

Copy

@Inproceedings{STOC:BLPRS13,
  author = {Zvika Brakerski and Adeline Langlois and Chris Peikert and Oded Regev and Damien Stehl{\'e}},
  title = {Classical hardness of learning with errors},
  pages = {575--584},
  editor = {Dan Boneh and Tim Roughgarden and Joan Feigenbaum},
  booktitle = {45th Annual {ACM} Symposium on Theory of Computing},
  address = {Palo Alto, CA, USA},
  month = {jun~1--4},
  publisher = {{ACM} Press},
  year = {2013},
  doi = {10.1145/2488608.2488680},
}