International Association
for Cryptologic Research

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 \\emph{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.