= 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$ and
$$
b=\langle a,s\rangle+e\pmod q,
$$
where $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\equiv9\pmod{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.<On Lattices, Learning with Errors, Random Linear Codes, and Cryptography by Oded Regev>[§1, learning problem and main theorem]{ref}
Back to article page
