Learning with errors

In <a href="/facts/Cryptography/e94PEVau">cryptography</a>, learning with errors (LWE) is a mathematical problem that is widely used to create secure <a href="/facts/Encryption_algorithms/16q29Fdv">encryption algorithms</a>. 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. In more technical terms, it refers to the <a href="/facts/Computational_problem/jQ7bYUVh">computational problem</a> of inferring a linear 
 
 
 
 n
 
 
 {\displaystyle n}
 
-ary function 
 
 
 
 f
 
 
 {\displaystyle f}
 
 over a finite <a href="/facts/Ring_(mathematics)/JnCUXz63">ring</a> from given samples 
 
 
 
 
 y
 
 i
 
 
 =
 f
 (
 
 
 x
 
 
 i
 
 
 )
 
 
 {\displaystyle y_{i}=f(\mathbf {x} _{i})}
 
 some of which may be erroneous. The LWE problem is conjectured to be hard to solve, and thus to be useful in cryptography.
More precisely, the LWE problem is defined as follows. Let 
 
 
 
 
 
 Z
 
 
 q
 
 
 
 
 {\displaystyle \mathbb {Z} _{q}}
 
 denote the ring of integers <a href="/facts/Modular_arithmetic/0wtRa5dU">modulo</a> 
 
 
 
 q
 
 
 {\displaystyle q}
 
 and let

Z
 
 
 q
 
 
 n
 
 
 
 
 {\displaystyle \mathbb {Z} _{q}^{n}}
 
 denote the set of 
 
 
 
 n
 
 
 {\displaystyle n}
 
-<a href="/facts/Vector_(mathematics_and_physics)/U8mM7A5F">vectors</a> over 
 
 
 
 
 
 Z
 
 
 q
 
 
 
 
 {\displaystyle \mathbb {Z} _{q}}
 
. There exists a certain unknown linear function 
 
 
 
 f
 :
 
 
 Z
 
 
 q
 
 
 n
 
 
 →
 
 
 Z
 
 
 q
 
 
 
 
 {\displaystyle f:\mathbb {Z} _{q}^{n}\rightarrow \mathbb {Z} _{q}}
 
, and the input to the LWE problem is a sample of pairs 
 
 
 
 (
 
 x
 
 ,
 y
 )
 
 
 {\displaystyle (\mathbf {x} ,y)}
 
, where 
 
 
 
 
 x
 
 ∈
 
 
 Z
 
 
 q
 
 
 n
 
 
 
 
 {\displaystyle \mathbf {x} \in \mathbb {Z} _{q}^{n}}
 
 and 
 
 
 
 y
 ∈
 
 
 Z
 
 
 q
 
 
 
 
 {\displaystyle y\in \mathbb {Z} _{q}}
 
, so that with high probability 
 
 
 
 y
 =
 f
 (
 
 x
 
 )
 
 
 {\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 
 
 
 
 f
 
 
 {\displaystyle f}
 
, or some close approximation thereof, with high probability.
The LWE problem was introduced by <a href="/facts/Oded_Regev_(computer_scientist)/qb5CDFDC">Oded Regev</a> in 2005 (who won the 2018 <a href="/facts/G%25C3%25B6del_Prize/RdbqdDj6">Gödel Prize</a> for this work); it is a generalization of the <a href="/facts/Parity_learning/A2b22xIe">parity learning</a> problem. Regev showed that the LWE problem is as hard to solve as several worst-case <a href="/facts/Lattice_problems/YHXNNrrG">lattice problems</a>. Subsequently, the LWE problem has been used as a <a href="/facts/Computational_hardness_assumption/ewjpb1I7">hardness assumption</a> to create <a href="/facts/Public-key_cryptography/gowoFTxS">public-key cryptosystems</a>, such as the <a href="/facts/Ring_learning_with_errors_key_exchange/mRJkburf">ring learning with errors key exchange</a> by Peikert.

Learning with errors open-in-new

Learning with errors