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 -ary function
over a finite ring from given samples
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 denote the ring of integers modulo
and let
denote the set of
-vectors over
. There exists a certain unknown linear function
, and the input to the LWE problem is a sample of pairs
, where
and
, so that with high probability
. Furthermore, the deviation from the equality is according to some known noise model. The problem calls for finding the function
, 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]