Learning with Errors (LWE): Difference between revisions

From Cryptology City
Jump to navigation Jump to search
No edit summary
Line 27: Line 27:


== Relationship to other assumptions ==
== Relationship to other assumptions ==
* The [[LWE]] problem has a quantum reduction to the [[Shortest-Vector Problem]]
* 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
* There is a worst-case to average-case reduction for the [[LWE]] assumption



Revision as of 15:33, 4 July 2024


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 revealed

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