Paper 2015/046

On the concrete hardness of Learning with Errors

Martin R. Albrecht, Rachel Player, and Sam Scott

Abstract

The Learning with Errors (LWE) problem has become a central building block of modern cryptographic constructions. This work collects and presents hardness results for concrete instances of LWE. In particular, we discuss algorithms proposed in the literature and give the expected resources required to run them. We consider both generic instances of LWE as well as small secret variants. Since for several methods of solving LWE we require a lattice reduction step, we also review lattice reduction algorithms and use a refined model for estimating their running times. We also give concrete estimates for various families of LWE instances, provide a Sage module for computing these estimates and highlight gaps in the knowledge about algorithms for solving the Learning with Errors problem.

Note: Update to caution the reader against using this work as a reference for the state of the art in assessing the cost of solving LWE or making sense of the LWE estimator.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Minor revision. Journal of Mathematical Cryptology
Keywords
Learning with ErrorsLattice-based CryptographyLattice Reduction
Contact author(s)
rachel player 2013 @ live rhul ac uk
History
2019-08-05: last of 4 revisions
2015-01-20: received
See all versions
Short URL
https://ia.cr/2015/046
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/046,
      author = {Martin R.  Albrecht and Rachel Player and Sam Scott},
      title = {On the concrete hardness of Learning with Errors},
      howpublished = {Cryptology ePrint Archive, Paper 2015/046},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/046}},
      url = {https://eprint.iacr.org/2015/046}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.