On Ideal Lattices and Learning with Errors over Rings

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…

• AP
  Alfred P. Sloan Foundation
• US
  United States - Israel Binational Science Foundation
• WF
  Wolfson Foundation
• IS
  Israel Science Foundation
• ER
  European Research Council
• SF
  Sixth Framework Programme
• DO
  Division of Computing and Communication Foundations

  Award: CCF-1054495
• DO
  Division of Computer and Network Systems

  Award: CNS-0716786