math concept
1 topics use this
Math concept
Lattices
Core equation
$$\mathcal{L} = \{B\mathbf{z} : \mathbf{z} \in \mathbb{Z}^n\}$$
A lattice is a discrete additive subgroup of $\mathbb{R}^n$, generated by a basis matrix $B$. Finding the shortest vector in a lattice (SVP) is believed hard for quantum computers, making lattice-based cryptography the leading post-quantum paradigm.
Lattice hard problems
- Shortest Vector Problem (SVP): find the shortest non-zero vector in $\mathcal{L}$
- Closest Vector Problem (CVP): given target $\mathbf{t}$, find the closest lattice point
- Learning With Errors (LWE): given $(\mathbf{A}, \mathbf{As}+\mathbf{e})$ with small noise $\mathbf{e}$, recover $\mathbf{s}$
LWE reduces to worst-case lattice problems — making it a solid foundation even against quantum attacks.
Post-quantum standards
NIST standardised lattice-based schemes in 2024:
- CRYSTALS-Kyber (ML-KEM): key encapsulation based on Module-LWE
- CRYSTALS-Dilithium (ML-DSA): digital signatures based on Module-LWE/SIS
Fields that use this concept
Engineering & CS
Cryptography