A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
A lattice is the set of all integer linear combinations of a set of basis vectors in Rn. Lattice problems — finding short vectors (SVP), finding close vectors (CVP) — are believed hard even for quantum computers. Lattice-based cryptography builds encryption, signatures, FHE, and more on the hardness of these problems. The key advantage over number-theoretic schemes is worst-case to average-case reductions (Ajtai 1996): breaking a random lattice instance is as hard as solving the worst case of standard lattice problems. This provides stronger theoretical foundations and quantum resistance, making lattices the basis for NIST's post-quantum standards (ML-KEM, ML-DSA).
A lattice is a regular, repeating grid of points in n-dimensional space, generated by integer linear combinations of a set of basis vectors. In 2D, think of a parallelogram tiling of the plane — every vertex is a lattice point. In high dimensions, lattices exhibit a remarkable property: fundamental geometric problems become computationally hard. The Shortest Vector Problem (SVP) asks for the shortest nonzero vector in the lattice. The Closest Vector Problem (CVP) asks for the lattice point nearest to a given target point. Both are believed to be exponentially hard in the lattice dimension, even for quantum computers — making lattices the primary foundation for post-quantum cryptography.
The theoretical strength of lattice-based cryptography comes from worst-case to average-case reductions, first established by Ajtai in 1996. He showed that if there exists any efficient algorithm that can solve a random instance of certain lattice problems, then there exists an efficient algorithm that can solve the worst case of SVP. This is dramatically stronger than the assumptions underlying RSA or Diffie-Hellman, which assume that random instances are hard without any connection to worst-case complexity. For lattice cryptography, "random instances are easy" implies "ALL instances are easy" — a much harder claim to believe, providing stronger evidence for the assumption's truth.
Two core problems underpin most constructions. SIS (Short Integer Solution) asks for a short vector in the kernel of a random matrix — finding such a vector is at least as hard as worst-case SVP. SIS gives collision-resistant hash functions and forms the basis of lattice signatures. LWE (Learning with Errors) asks to distinguish noisy inner products from random values — it is at least as hard as worst-case lattice problems and forms the basis of lattice encryption, key exchange, and FHE. Ring variants (Ring-SIS, Ring-LWE) use polynomial rings instead of general vectors, achieving comparable security with smaller keys and faster operations.
NIST selected lattice-based schemes as the primary post-quantum standards: ML-KEM (Kyber) for key encapsulation and ML-DSA (Dilithium) for digital signatures, both based on Module-LWE. Lattices won the competition not by being the only quantum-resistant option but by offering the best balance of security confidence (decades of cryptanalysis, worst-case reductions), performance (key sizes around 1-2 KB, fast operations), and versatility (the same mathematical framework supports encryption, signatures, FHE, zero-knowledge proofs, and advanced primitives like identity-based encryption). The transition from RSA/ECC to lattice-based cryptography is underway and represents the most significant change in deployed cryptographic infrastructure since the adoption of public-key cryptography in the 1990s.