Lattice-based cryptography builds security on hard problems involving mathematical lattices, much as RSA relies on the difficulty of factorization. A lattice is a vector space restricted to integer combinations of basis vectors. section 14.3 section 14.3.1
Cryptographic constructions commonly connect to these problems:
- Shortest vector problem (SVP) asks for the shortest nonzero vector in a lattice. section 14.3.1
- Closest vector problem (CVP) asks for the lattice point nearest to a coordinate outside the lattice. section 14.3.1
- Learning with errors (LWE) hides a secret vector among modular vector computations disturbed by small random errors; reductions connect it to lattice problems such as CVP. section 14.3.2
A small lattice and LWE setup
Using basis vectors (0,1) and (1,0), integer combinations produce points such as (0,99) and (3,6), forming a repeating grid. In an LWE example, the secret vector is s = (3,6), while random vectors include a₀ = (5,2) and a₁ = (2,0); each computation adds a small random error. section 14.3.1 section 14.3.2
Figure 14.7 On the left, a basis of two vectors is drawn on a graph. A lattice can be formed by taking all of the possible integer linear combinations of these two vectors (middle figure). The resulting lattice can be interpreted as a pattern of points repeating forever in space (right figure).
Visualizes how a basis becomes an infinite lattice through integer combinations. section 14.3.1
Important post-quantum examples include Kyber for asymmetric encryption and key exchange, and Dilithium for digital signatures. Lattice-based schemes are promising partly because they provide shorter keys and signatures. section 14.3 section 14.5
