Learning with Errors (LWE)

The Learning with Errors (LWE) assumption is a common assumption, first introduced in [Reg05]. It has been used since to construct a wide variety of powerful primitives.

Parameters

The LWE assumption has 4 key parameters:

• $q$ - the prime modulus
• $n$ - the dimension of the secret vector
• $\eta$ - the noise distribution over $\mathbb {Z} _{q}$
• $m$ - the number of samples given to the adversary

For a better sense of these parameters, note that when $\eta$ is uniform over $\mathbb {Z} _{q}$, the assumption will be trivially true. In contrast, when $\eta$ is constant, then one can solve the LWE problem via Gaussian elimination. The other key parameters are $n$ and $q$, which control the number of possible secret vectors, since there are $q^{n}$ possible secret vectors. If this is too small, then an adversary could brute-force over all of them. The $m$ parameter is often ignored, as we assume adversaries run in polynomial time and that LWE is hard for any $m$ is polynomial in the security parameter.

We will write $(q,n,\eta )$-LWE to make it clear which parameter regime is assumed to be hard.

Formal assumption

We say that the $(q,n,\eta )$ Learning with Errors (LWE) assumption holds if for any efficient algorithm $D$ and any polynomial $m(n)$, there is a negligible function $\nu$ such that,

$|\Pr[D(A,A\cdot s+e)=1]-\Pr[D(A,z)=1]|\leq \nu (n),$

where $A$ is uniform from $\mathbb {Z} _{q}^{m(n)\times n}$, $s$ is uniform from $\mathbb {Z} _{q}^{n}$, $e$ is drawn from $\eta ^{m(n)}$, and $z$ is uniform from $\mathbb {Z} _{q}^{m(n)}$. Note that addition is computed modulo $q$.

In more plain terms, we are assuming that it is hard to distinguish between a uniformly random vector and a vector which is a linear combination of the columns of $A$ after some noise has been applied. This is why the parameters (especially the noise) is critical to the security of the LWE assumption.

Known attacks

• The best known approach to solving LWE is to attack the Shortest-Vector Problem (SVP) directly.

Relationship to other assumptions

• The LWE problem has a quantum reduction to the Shortest-Vector Problem (SVP)
• There is a worst-case to average-case reduction for the LWE assumption

Implied primitives

• Public Key Encryption (PKE) can be built only assuming the hardness of LWE

Other notes

There are a few variations of the LWE assumption, specifically Learning Parity with Noise (LPN) and the Ring Learning with Errors (Ring-LWE).