Learning With Errors

This file gives a general definition of the LWE problem. It is parameterized by the following:

• n: the dimension of the secret
• m: the number of samples
• p: the modulus (not necessarily prime)
• errSamp : ProbComp (Fin p): a probabilistic sampling algorithm for the error

(errSamp can potentially be replaced with χ : PMF (Fin p) instead, to be used with evalDistWhen with non-uniform distributions)

We define the (decision) LWE problem as a security experiment on an oracle that takes as input:

• A matrix A : Fin m → Fin n → Fin p
• A vector u : Fin m → Fin p, either sampled uniformly at random, or sampled from the LWE distribution s * A + e, where s : Fin n → Fin p is the secret and e : Fin m → Fin p has every entry sampled from errSamp.

The adversary wins if it can correctly guess which case the distribution is.

The search LWE problem instead asks that the adversary given A and u = s * A + e outputs the secret s.