= 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\pmod q$, $A$ and $b$ are public, while the secret vector $s$ is masked by a small error vector $e$. With no error, ordinary <linear algebra>[modular linear algebra] may recover $s$ efficiently when the system has suitable <matrix rank>[rank]. The <noise> changes the problem. Real security depends on <probability distribution>[error distribution], dimension, <modular arithmetic>[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.
Back to article page
