On lattices, learning with errors, random linear codes, and cryptography

Research output: Contribution to journalArticlepeer-review


Our main result is a reduction from worst-case lattice problems such as GapSVP and SIVP to a certain learning problem. This learning problem is a natural extension of the learning from parity with error problem to higher moduli. It can also be viewed as the problem of decoding from a random linear code. This, we believe, gives a strong indication that these problems are hard. Our reduction, however, is quantum. Hence, an efficient solution to the learning problem implies a quantum algorithm for GapSVP and SIVP. A main open question is whether this reduction can be made classical (i.e., nonquantum). We also present a (classical) public-key cryptosystem whose security is based on the hardness of the learning problem. By the main result, its security is also based on the worst-case quantum hardness of GapSVP and SIVP. The new cryptosystem is much more efficient than previous lattice-based cryptosystems: the public key is of size (n2) and encrypting a message increases its size by a factor of (n) (in previous cryptosystems these values are (n4) and (n 2), respectively). In fact, under the assumption that all parties share a random bit string of length (n2), the size of the public key can be reduced to (n).

Original languageEnglish (US)
Article number1568324
JournalJournal of the ACM
Issue number6
StatePublished - Sep 1 2009


  • Average-case hardness
  • Cryptography
  • Lattice
  • Public key encryption
  • Quantum computation

ASJC Scopus subject areas

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


Dive into the research topics of 'On lattices, learning with errors, random linear codes, and cryptography'. Together they form a unique fingerprint.

Cite this