On Ideal lattices and learning with errors over rings

Vadim Lyubashevsky, Chris Peikert, Oded Regev

Research output: Contribution to journalArticlepeer-review

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 polynomialtime 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.

Original languageEnglish (US)
Article number43
JournalJournal of the ACM
Volume60
Issue number6
DOIs
StatePublished - Nov 2013

Keywords

  • Additional key words and phrases: Lattice
  • Average-case hardness
  • Cryptography
  • Public key encryption
  • Quantum computation

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

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

Cite this