# Learning with errors

## Mathematical problem in cryptography / From Wikipedia, the free encyclopedia

#### Dear Wikiwand AI, let's keep it short by simply answering these key questions:

Can you list the top facts and stats about Learning with errors?

Summarize this article for a 10 year old

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 $n$-ary function $f$ over a finite ring from given samples $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.

This article may be too technical for most readers to understand. (October 2018) |

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