Learning with errors

This article may be too technical for most readers to understand. Please help improve it to make it understandable to non-experts, without removing the technical details. (October 2018) (Learn how and when to remove this message)

In cryptography, learning with errors (LWE) is a mathematical problem that is widely used to create secure encryption algorithms.^[1] It is based on the idea of representing secret information as a set of equations with errors. In other words, LWE is a way to hide the value of a secret by introducing noise to it.^[2] In more technical terms, it refers to the computational problem of inferring a linear ${\displaystyle n}$-ary function ${\displaystyle f}$ over a finite ring from given samples ${\displaystyle y_{i}=f(\mathbf {x} _{i})}$ some of which may be erroneous. The LWE problem is conjectured to be hard to solve,^[1] and thus to be useful in cryptography.

More precisely, the LWE problem is defined as follows. Let ${\displaystyle \mathbb {Z} _{q}}$ denote the ring of integers modulo ${\displaystyle q}$ and let ${\displaystyle \mathbb {Z} _{q}^{n}}$ denote the set of ${\displaystyle n}$-vectors over ${\displaystyle \mathbb {Z} _{q}}$. There exists a certain unknown linear function ${\displaystyle f:\mathbb {Z} _{q}^{n}\rightarrow \mathbb {Z} _{q}}$, and the input to the LWE problem is a sample of pairs ${\displaystyle (\mathbf {x} ,y)}$, where ${\displaystyle \mathbf {x} \in \mathbb {Z} _{q}^{n}}$ and ${\displaystyle y\in \mathbb {Z} _{q}}$, so that with high probability ${\displaystyle y=f(\mathbf {x} )}$. Furthermore, the deviation from the equality is according to some known noise model. The problem calls for finding the function ${\displaystyle f}$, or some close approximation thereof, with high probability.

The LWE problem was introduced by Oded Regev in 2005^[3] (who won the 2018 Gödel Prize for this work); it is a generalization of the parity learning problem. Regev showed that the LWE problem is as hard to solve as several worst-case lattice problems. Subsequently, the LWE problem has been used as a hardness assumption to create public-key cryptosystems,^[3][4] such as the ring learning with errors key exchange by Peikert.^[5]