Paper 2012/230

On Ideal Lattices and Learning with Errors Over Rings

Vadim Lyubashevsky, Chris Peikert, and Oded Regev

Abstract

The ``learning with errors'' (LWE) problem is to distinguish random linear equations, which have been perturbed by a small amount of noise, from truly uniform ones. The problem has been shown to be as hard as worst-case lattice problems, and in recent years it has served as the foundation for a plethora of cryptographic applications. Unfortunately, these applications are rather inefficient due to an inherent quadratic overhead in the use of LWE. A main open question was whether LWE and its applications could be made truly efficient by exploiting extra algebraic structure, as was done for lattice-based hash functions (and related primitives). We resolve this question in the affirmative by introducing an algebraic variant of LWE called \emph{ring-LWE}, and proving that it too enjoys very strong hardness guarantees. Specifically, we show that the ring-LWE distribution is pseudorandom, assuming that worst-case problems on ideal lattices are hard for polynomial-time quantum algorithms. Applications include the first truly practical lattice-based public-key cryptosystem with an efficient security reduction; moreover, many of the other applications of LWE can be made much more efficient through the use of ring-LWE.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Full version of paper appearing in Eurocrypt 2010
Keywords
latticesLWEringsalgebraic number theory
Contact author(s)
cpeikert @ cc gatech edu
History
2013-06-26: last of 2 revisions
2012-04-30: received
See all versions
Short URL
https://ia.cr/2012/230
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/230,
      author = {Vadim Lyubashevsky and Chris Peikert and Oded Regev},
      title = {On Ideal Lattices and Learning with Errors Over Rings},
      howpublished = {Cryptology ePrint Archive, Paper 2012/230},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/230}},
      url = {https://eprint.iacr.org/2012/230}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.