Lattice-based cryptography

Lattice-based cryptography constructs security mechanisms from computational problems associated with Euclidean lattices and related noisy linear equations. A lattice is easy to describe by a basis, while finding particular short vectors or recovering hidden information from noisy equations can be difficult in suitably chosen dimensions and parameter ranges. Different constructions rely on different problems and reductions.

For the schematic learning with errors relation $b=As+e(\mathrm{mod}q)$, $A$ and $b$ are public, while the secret vector $s$ is masked by a small error vector $e$. With no error, ordinary modular linear algebra may recover $s$ efficiently when the system has suitable rank. The noise changes the problem. Real security depends on error distribution, dimension, modulus, available samples and attack model, rather than merely making the displayed equation look complicated. ML-KEM and ML-DSA illustrate encapsulation and signature applications; they use structured module arithmetic to obtain practical sizes and computation costs.

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]