Lattices

Lattice-based cryptography is the leading approach to post-quantum cryptography. This page gives a short introduction to the area and points to a small selection of resources that I recommend to students and colleagues who want to learn it.

What is a lattice?

A lattice is a regular grid of points in n-dimensional space. Given linearly independent basis vectors b₁, …, b_n, the lattice consists of all their integer linear combinations z₁b₁ + … + z_nb_n. The same lattice has infinitely many bases: a “good” basis of short, nearly orthogonal vectors makes many problems easy, while a “bad” basis of long, skewed vectors hides the structure of the lattice. Finding a short non-zero vector (the Shortest Vector Problem, SVP) or the lattice point closest to a given target (the Closest Vector Problem, CVP) is believed to be hard in high dimensions, for classical and quantum computers alike. The best known algorithms, lattice reduction such as BKZ combined with sieving or enumeration, take time exponential in the dimension.

Why lattices for cryptography?

Lattice problems such as SVP have been studied for decades, and no quantum algorithm is known to solve them significantly faster than classical algorithms. This is in stark contrast to RSA and elliptic-curve cryptography, which are broken by Shor’s algorithm on a large quantum computer. On top of this, lattice-based cryptography offers a rare combination of properties: security reductions from worst-case lattice problems, efficient schemes with small keys and fast operations, and a remarkable versatility that goes far beyond encryption and signatures. Lattices underlie all practical fully homomorphic encryption schemes, and support advanced primitives such as zero-knowledge proofs, threshold and blind signatures, and verifiable encryption and mix-nets, which is where much of my own research is focused.

In August 2024, NIST published its first post-quantum standards: ML-KEM (FIPS 203, based on Kyber) for key encapsulation and ML-DSA (FIPS 204, based on Dilithium) for digital signatures, both built on module lattices, with the NTRU-based signature scheme Falcon to follow as FN-DSA (FIPS 206). The CRYSTALS website is the home of the Kyber and Dilithium projects, and the NIST Post-Quantum Cryptography project tracks the remaining standardization work. To see how lattice-based signatures compare to the other post-quantum candidates in NIST’s additional signature process, and to classical schemes, the PQC Signature Zoo gives an up-to-date overview of key sizes, signature sizes, and performance.

SIS and LWE

Almost all of modern lattice cryptography rests on two average-case problems, both defined over the integers modulo a number q. What makes them special is that they come with worst-case to average-case reductions: breaking a random instance is provably at least as hard as solving certain lattice problems in the worst case.

The Short Integer Solution (SIS) problem asks, given a uniformly random matrix A ∈ ℤ_q^n×m with more columns than rows, to find a non-zero integer vector x with small norm such that Ax = 0 mod q. Without the norm bound this is easy linear algebra, but requiring x to be short turns it into the problem of finding a short vector in the lattice of all integer solutions. If SIS is hard, then the function x ↦ Ax mod q restricted to short inputs is collision-resistant, since any collision x ≠ x′ gives a short solution x − x′. This directly gives hash functions and commitment schemes, and, combined with trapdoors or the Fiat–Shamir with aborts technique, digital signatures. Ajtai (1996) showed that solving SIS on average is as hard as approximating short vector problems in every lattice of a related dimension.

The Learning with Errors (LWE) problem asks to recover a secret vector s, given a random matrix A and b = As + e mod q, where e is a small random error vector. In the decision version, the task is only to distinguish (A, b) from uniformly random. Without the error, s could be found by Gaussian elimination; the small noise is what makes the problem hard. LWE directly gives public-key encryption: in Regev’s scheme, the public key is (A, b), a bit is encrypted by adding a random subset of the samples and hiding the bit in the most significant part of the result, and the secret key s removes everything except a small amount of noise. Regev (2005) proved LWE as hard as worst-case lattice problems under a quantum reduction, later complemented by classical reductions for suitable parameters. LWE is the basis for most modern lattice-based encryption, including fully homomorphic encryption.

The two problems are closely related: a short vector x with x^TA = 0 mod q, that is, a SIS solution for the transposed matrix, gives x^Tb = x^Te, which is small and hence distinguishes LWE samples from random. The best known attacks on both problems therefore come from lattice reduction.

For efficiency, practical schemes use structured variants in which A consists of blocks of polynomials in a ring such as ℤ_q[X]/(Xⁿ + 1). Ring-SIS and Ring-LWE use a single row of ring elements, and Module-SIS and Module-LWE use small matrices of ring elements, which allows a trade-off between efficiency and structure. These variants reduce key sizes from quadratic to linear in the dimension and allow fast multiplication with the number-theoretic transform, while retaining worst-case hardness guarantees for structured (ideal and module) lattices.

Lattice-based cryptography built on these problems is already widely deployed. Hybrid key exchange combining X25519 with ML-KEM is enabled by default in recent versions of all major browsers and many TLS libraries, and by late 2025 more than half of human-initiated traffic to Cloudflare was protected by post-quantum key agreement. Messaging apps have followed, with Kyber used in Signal’s PQXDH protocol and Apple’s iMessage PQ3.

NTRU

NTRU, introduced by Hoffstein, Pipher, and Silverman in 1998, was one of the first practical lattice-based public-key cryptosystems, developed independently of the worst-case hardness results behind SIS and LWE. It works in a polynomial ring, where the public key is a quotient h = g/f mod q of two secret polynomials f and g with small coefficients. Recovering such a short pair from h amounts to finding a short vector in a highly structured “NTRU lattice”. This structure gives very compact keys and ciphertexts, and NTRU lattices admit efficient trapdoors: the signature scheme Falcon, which uses hash-and-sign with fast Fourier sampling over NTRU lattices, is being standardized by NIST as FN-DSA (FIPS 206). NTRU-based key exchange is already deployed in practice, for example through Streamlined NTRU Prime, which is part of the default hybrid key exchange in OpenSSH. NTRU can also be used for fully homomorphic encryption, but early NTRU-based schemes relied on “overstretched” parameters with a very large modulus, which turned out to be vulnerable to dedicated lattice attacks. FINAL was the first NTRU-based FHE scheme with secure parameters.

A brief history

The table below gives a rough and admittedly biased history of the foundations of modern lattice-based cryptography, shaped by my own research interests; many other important works have also pushed the frontier of the field.

Where to start

If you want to understand how ML-KEM and ML-DSA work, start with Vadim Lyubashevsky’s Basic Lattice Cryptography: The concepts behind Kyber (ML-KEM) and Dilithium (ML-DSA). It is a self-contained tutorial by one of the designers of both schemes, explaining the underlying mathematical concepts and design decisions, as well as the main ideas behind other lattice-based KEMs such as Frodo and NTRU.

For a broader and more theoretical view, Chris Peikert’s survey A Decade of Lattice Cryptography covers the foundations of SIS and LWE, worst-case hardness, ring-based variants, trapdoors, and advanced constructions such as fully homomorphic encryption. Oded Regev’s short survey The Learning with Errors Problem is a good companion for understanding LWE itself.

Courses and lecture notes

Chris Peikert’s graduate course Lattices in Cryptography (University of Michigan) has the most up-to-date and comprehensive lecture notes on lattice cryptography. The notes are maintained on GitHub, were used most recently in 2026, and cover everything from the shortest vector problem and the LLL algorithm to SIS, LWE, and digital signatures.

As a complement with more emphasis on algorithms, complexity, and cryptanalysis, Daniele Micciancio’s course Lattice Algorithms and Applications (UC San Diego) has excellent lecture notes on the geometry of lattices, the LLL algorithm, duality, harmonic analysis, and the hardness of lattice problems.

Talks

Vinod Vaikuntanathan’s colloquium talk Lattices and Cryptography: A Match Made in Heaven is an accessible one-hour overview of why lattices have become central to cryptography. For an in-depth series of lectures by leading researchers in the field, the Lattices: Algorithms, Complexity, and Cryptography Boot Camp at the Simons Institute (2020) is still the best starting point, and the workshops of the full Simons program cover more advanced topics.

Homomorphic encryption

All practical fully homomorphic encryption (FHE) schemes, such as BGV, BFV, CKKS, and TFHE, are based on (Ring-)LWE. The Survey on Fully Homomorphic Encryption, Theory, and Applications by Marcolla et al. (Proceedings of the IEEE, 2022) gives a good overview of the schemes and their applications. The community site FHE.org maintains an up-to-date collection of tutorials, courses, conference talks, and libraries, and OpenFHE is a widely used open-source library implementing all the major schemes. For choosing parameters and implementing FHE securely, see the Security Guidelines for Implementing Homomorphic Encryption by Bossuat et al. (IACR Communications in Cryptology, 2025).

Zero-knowledge proofs

Lattice-based zero-knowledge proofs have become efficient enough for real applications such as anonymous credentials and blind signatures. The LNP framework and BDLOP commitments form the basis for proving linear relations and norm bounds, and LaBRADOR gives compact succinct proofs from Module-SIS (see the table above). The best way to get started in practice is the LaZer library, which lets you specify lattice relations and norm bounds in Python and automatically generates the corresponding proof system, with demos for blind signatures, anonymous credentials, and proofs of Kyber keys.

Advanced signatures

Threshold signatures distribute the signing key among several parties so that no single party can sign alone. Threshold Raccoon by del Pino et al. (Eurocrypt 2024) was the first efficient lattice-based threshold signature from standard assumptions. More recent schemes include our Olingo, which adds distributed key generation and identifiable abort (ACM CCS 2026). NIST is currently standardizing threshold schemes through its Multi-Party Threshold Cryptography project, and the submissions to the first call include several lattice-based threshold signatures.

Cryptanalysis and tools

To estimate the concrete security of lattice-based schemes, the Lattice Estimator is the standard tool, and fplll and G6K provide state-of-the-art implementations of lattice reduction and sieving for experiments. As the number of new lattice assumptions grows, Martin Albrecht’s overview of SIS with hints is a useful reference: it catalogues SIS-like assumptions that give out additional hints, and records whether each is known to be standard, equivalent to another assumption, or broken. The community-maintained Lattice Assumption Zoo aims to catalogue all average-case lattice assumptions more broadly, with their relationships, hardness rationale, known cryptanalysis, and the constructions that rely on them.

Libraries

Open-source libraries for post-quantum and lattice-based cryptography:

• LaZer: lattice-based zero-knowledge and succinct proofs
• Lattigo: homomorphic encryption and multiparty homomorphic encryption in Go
• liboqs: post-quantum key encapsulation and signatures from the Open Quantum Safe project
• OpenFHE: fully homomorphic encryption (BGV, BFV, CKKS, FHEW, and TFHE)
• TFHE-rs: fully homomorphic encryption over booleans and integers in Rust