On ideal lattices and learning with errors over rings

Vadim Lyubashevsky, Chris Peikert, Oded Regev

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

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 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. Finally, the algebraic structure of ring-LWE might lead to new cryptographic applications previously not known to be based on LWE.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology - Eurocrypt 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
Pages1-23
Number of pages23
DOIs
StatePublished - 2010
Event29th in the Series of EuropeanConferences on the Theory and Application of Cryptographic Techniques, Eurocrypt 2010 - French Riviera, France
Duration: May 30 2010Jun 3 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6110 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other29th in the Series of EuropeanConferences on the Theory and Application of Cryptographic Techniques, Eurocrypt 2010
CountryFrance
CityFrench Riviera
Period5/30/106/3/10

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'On ideal lattices and learning with errors over rings'. Together they form a unique fingerprint.

Cite this