 Learning with errors

Learning with errors asks for a secret vector $s$ from noisy modular linear observations. An observation has a known random vector $a$ andwhere $e$ is sampled from a specified small-error probability distribution. The search version recovers $s$; the decision version distinguishes these samples from uniformly random pairs. Parameters and the error distribution are essential parts of the problem.

For a tiny illustration, let $q=17$, $s=(3,5)$ and $a=(2,4)$. The exact inner product is $26\equiv 9(\mathrm{mod}17)$, while error $e=-1$ gives $b=8$. Without errors, enough independent equations admit ordinary modular linear solving; adding errors obstructs that direct approach. This tiny instance is not a secure parameter choice. Oded Regev's work connects appropriately parameterized instances to worst-case lattice problems and constructs a public-key cryptography from the assumption.^[ref]