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]

Module learning with errors is a structured version of learning with errors in which matrix entries and secret components are elements of a specified polynomial ring. A typical relation isHere $A$ is a public $k\times k$ matrix of ring elements, while $s$ and $e$ have sampled small coefficients. Multiplication combines polynomial multiplication with reduction by the defining polynomial and coefficient modulus.

A ring element packs $n$ coefficients, giving structured linear operations without storing an arbitrary dense matrix of all scalar coefficients. This saves space and computation, while introducing an algebraic structure that the security assumption must cover. CRYSTALS-Kyber uses module-LWE, and ML-KEM standardizes a related encapsulation construction. This is a conditional hardness basis, not a proof that every choice of ring and parameters is secure.^[ref]