Learning with Errors (LWE)

From Cryptology City
Jump to navigation Jump to search


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:

  • - the prime modulus
  • - the dimension of the secret vector
  • - the noise distribution over
  • - the number of samples given to the adversary

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

We will write -LWE to make it clear which parameter regime is assumed to be hard.

Formal assumption

We say that the Learning with Errors (LWE) assumption holds if for any efficient algorithm and any polynomial , there is a negligible function such that,

where is uniform from , is uniform from , is drawn from , and is uniform from . Note that addition is computed modulo .

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 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

Relationship to other assumptions

Implied primitives

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).