On Ideal Lattices and Learning with Errors over Rings

• DOI: 10.1145/2535925
• Publication Date: 2013-12-04T14:04:47Z
• Authors: Vadim Lyubashevsky; Chris Peikert; Oded Regev
• Keywords: Learning with errors; Lattice problem; Lattice-based Cryptography; Post-quantum cryptography; Lattice (music); Oblivious transfer

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. has shown be as hard worst-case lattice problems, and in recent years it served the foundation for plethora cryptographic applications. Unfortunately, these applications are rather inefficient due an inherent quadratic overhead use LWE. A main open question was whether LWE its could made efficient exploiting extra algebraic structure, done lattice-based hash functions (and related primitives). We resolve this affirmative introducing variant called ring-LWE , proving that too enjoys very strong hardness guarantees. Specifically, we show distribution pseudorandom, assuming problems on ideal lattices polynomial-time quantum algorithms. Applications include first practical public-key cryptosystem security reduction; moreover, many other can much more through ring-LWE.