Helpful context:

In 1994, Peter Shor published an algorithm that, on a large enough quantum computer, factors any $n$-bit integer in polynomial time. Since RSA’s security rests on the hardness of integer factorization, and Diffie-Hellman rests on the discrete logarithm problem (which Shor also solves), a quantum computer of sufficient scale would break essentially all public-key cryptography deployed today. The question is not whether such computers will exist, but when - current estimates range from 10 to 30 years.

The response from the cryptographic community has been a decade-long effort to find problems that quantum computers cannot solve efficiently. The winner, at least so far, comes from geometry. A lattice is a regular grid of points in high-dimensional space, and the problem of finding the shortest nonzero vector in such a grid - even approximately - appears to be hard for classical and quantum computers alike. The hardness is not merely empirical: Oded Regev proved in 2005 that breaking certain lattice-based cryptosystems is at least as hard as solving worst-case lattice problems, giving a security reduction from a geometric problem that has resisted attack for decades.

In 2022, NIST completed its post-quantum cryptography standardization process. The primary standards for key encapsulation and digital signatures are both lattice-based: CRYSTALS-Kyber and CRYSTALS-Dilithium. These are not theoretical constructs - they are already deployed in TLS 1.3, Google Chrome, and AWS. The transition to post-quantum cryptography is underway.

What is a Lattice?

Let $\mathbf{b}_1, \ldots, \mathbf{b}_n \in \mathbb{R}^m$ be linearly independent vectors. The lattice generated by this basis is the set of all integer linear combinations:

$$\mathcal{L}(B) = \left\{ \sum_{i=1}^n z_i \mathbf{b}_i : z_i \in \mathbb{Z} \right\}.$$

The matrix $B = [\mathbf{b}_1 \mid \cdots \mid \mathbf{b}_n]$ with columns $\mathbf{b}_i$ is the basis matrix. When $m = n$, the lattice is full-rank.

A simple example: $\mathbb{Z}^n$ (all vectors with integer coordinates) is a lattice with basis $B = I_n$. The hexagonal lattice in $\mathbb{R}^2$ (used in sphere packing) has basis vectors $\mathbf{b}_1 = (1, 0)$ and $\mathbf{b}_2 = (1/2, \sqrt{3}/2)$.

The same lattice has many bases. If $U$ is any $n \times n$ integer matrix with $|\det U| = 1$ (a unimodular matrix), then $B' = BU$ generates the same lattice as $B$. A “good” basis has short, nearly orthogonal vectors; a “bad” basis has long, nearly parallel vectors. Moving between bases is easy; distinguishing good from bad is hard. This gap is the source of cryptographic security.

Hard Problems on Lattices

The Shortest Vector Problem (SVP). Given a basis $B$ for a lattice $\mathcal{L}$, find the shortest nonzero vector in $\mathcal{L}$.

The length of the shortest vector is the first minimum $\lambda_1(\mathcal{L})$. Minkowski’s theorem gives a lower bound: $\lambda_1 \leq \sqrt{n} \cdot |\det(\mathcal{L})|^{1/n}$. Finding a vector achieving this bound is SVP.

For $n$-dimensional lattices, the best known classical algorithms run in $2^{O(n)}$ time and space. The best known quantum algorithms also run in $2^{O(n)}$ - quantum speedup gives at most a constant in the exponent, not a polynomial improvement. This is why lattice problems are believed to be post-quantum hard.

The Closest Vector Problem (CVP). Given a basis $B$ and a target point $\mathbf{t} \notin \mathcal{L}$, find the lattice vector $\mathbf{v} \in \mathcal{L}$ minimizing $|\mathbf{v} - \mathbf{t}|$.

CVP is at least as hard as SVP (there is a polynomial-time reduction from SVP to CVP). Both are NP-hard in the worst case. Cryptographic constructions use approximate versions - finding vectors within a polynomial factor of optimal - which are still believed hard.

Learning With Errors (LWE)

The most important lattice-based hardness assumption is Learning With Errors (LWE), introduced by Regev in 2005.

The LWE problem. Fix parameters: dimension $n$, modulus $q$, error distribution $\chi$ over $\mathbb{Z}_q$ (typically a discrete Gaussian with small standard deviation $\sigma \ll q$). Sample a secret $\mathbf{s} \in \mathbb{Z}_q^n$ uniformly. For many independent trials:

  • Sample $\mathbf{a} \sim \mathbb{Z}_q^n$ uniformly.
  • Sample small error $e \sim \chi$.
  • Output $(\mathbf{a}, b) = (\mathbf{a}, \langle \mathbf{a}, \mathbf{s} \rangle + e \bmod q)$.

The search LWE problem asks: given many $(\mathbf{a}, b)$ pairs, recover $\mathbf{s}$.

The decision LWE problem asks: distinguish LWE samples $(\mathbf{a}, b)$ from uniformly random $(\mathbf{a}, b) \in \mathbb{Z}_q^n \times \mathbb{Z}_q$.

Without the error $e$, recovering $\mathbf{s}$ from $b = \langle \mathbf{a}, \mathbf{s} \rangle \bmod q$ is just solving a linear system modulo $q$ - easy. The small error makes this hard: the equations are “noisy,” and recovering the exact values requires solving an approximate linear system over $\mathbb{Z}_q$, which is equivalent to CVP.

Regev’s reduction. For appropriate parameters, solving LWE (even the decision variant) is at least as hard as approximating SVP on random lattices in the worst case. This is a worst-case to average-case reduction: an algorithm that breaks LWE on a random instance would also solve the hardest SVP instances. No other standard cryptographic assumption (factoring, discrete log) has this property.

LWE-Based Encryption: Regev’s Scheme

Setup. Choose parameters $n, q, m$, and an error distribution $\chi$.

Key generation.

  • Sample secret $\mathbf{s} \in \mathbb{Z}_q^n$ uniformly.
  • Sample $m$ LWE samples: $(\mathbf{A}, \mathbf{b}) = (\mathbf{A}, \mathbf{A}\mathbf{s} + \mathbf{e} \bmod q)$ where $\mathbf{A} \in \mathbb{Z}_q^{m \times n}$ and $\mathbf{e} \in \mathbb{Z}_q^m$ has small entries.
  • Public key: $(\mathbf{A}, \mathbf{b})$. Secret key: $\mathbf{s}$.

Encryption of a single bit $m \in \{0, 1\}$:

  • Sample a random subset indicator $\mathbf{r} \in \{0,1\}^m$.
  • Compute $\mathbf{u} = \mathbf{A}^T \mathbf{r} \bmod q \in \mathbb{Z}_q^n$.
  • Compute $v = \mathbf{b}^T \mathbf{r} + m \cdot \lfloor q/2 \rceil \bmod q \in \mathbb{Z}_q$.
  • Ciphertext: $(\mathbf{u}, v)$.

Decryption:

  • Compute $v - \langle \mathbf{u}, \mathbf{s} \rangle = \mathbf{b}^T\mathbf{r} - \langle \mathbf{A}^T\mathbf{r}, \mathbf{s} \rangle + m \lfloor q/2 \rceil = \mathbf{e}^T \mathbf{r} + m \lfloor q/2 \rceil \bmod q$.
  • The term $\mathbf{e}^T\mathbf{r}$ is small (sum of $r$-selected small errors). Round to the nearest multiple of $\lfloor q/2 \rceil$ to recover $m$.

Security: the public key $(\mathbf{A}, \mathbf{b})$ looks uniformly random by the LWE assumption. An adversary who can decrypt must be able to distinguish LWE from uniform - which is hard by assumption.

Ring-LWE and Practical Efficiency

Regev’s original LWE has a significant drawback: the public key is $m \times n$ numbers over $\mathbb{Z}_q$, which for $n = 256$ and $q \approx 2^{12}$ already requires tens of kilobytes. Ring-LWE (Lyubashevsky, Peikert, Regev, 2010) solves this.

Ring-LWE works in the polynomial ring $R_q = \mathbb{Z}_q[x]/(x^n + 1)$ for $n$ a power of 2. Elements of $R_q$ are polynomials of degree less than $n$ with coefficients in $\mathbb{Z}_q$. Multiplication in $R_q$ is polynomial multiplication modulo $x^n + 1$ and modulo $q$.

The LWE equation $\mathbf{b} = \mathbf{A}\mathbf{s} + \mathbf{e}$ becomes, over $R_q$:

$$b = a \cdot s + e \in R_q,$$

where $a, s, e \in R_q$ and $e$ has small coefficients. A single ring element $a \in R_q$ replaces the matrix $\mathbf{A} \in \mathbb{Z}_q^{m \times n}$, reducing the public key from $O(n^2)$ to $O(n)$ ring elements. The number-theoretic transform (NTT) enables polynomial multiplication in $O(n \log n)$ operations.

Security: Ring-LWE reduces to worst-case lattice problems on ideal lattices (lattices with ring structure). The security reduction is slightly more specialized than plain LWE, but the best known attacks are still exponential in $n$.

CRYSTALS-Kyber: NIST’s KEM Standard

CRYSTALS-Kyber (now standardized as ML-KEM, FIPS 203) is a key encapsulation mechanism based on module-LWE: a generalization using small matrices of ring elements rather than a single ring element.

Module-LWE with module rank $k$: work in $R_q^k$ (vectors of $k$ ring elements). The matrix $\mathbf{A} \in R_q^{k \times k}$ replaces a single ring element, balancing security and performance.

Kyber parameters (Kyber-768, the recommended level):

  • Ring: $\mathbb{Z}_q /(x^{256} + 1)$ with $q = 3329$.
  • Module rank: $k = 3$.
  • Error distribution: centered binomial with small support.
  • Public key: $\approx 1184$ bytes.
  • Ciphertext: $\approx 1088$ bytes.
  • Shared secret: 32 bytes.

For comparison, RSA-2048 has a 256-byte public key but is broken by Shor’s algorithm on a quantum computer. Kyber’s larger key sizes are the cost of post-quantum security.

Decapsulation failure probability is negligible ($< 2^{-139}$) - the error terms in decryption stay small with overwhelming probability. NTT-based polynomial multiplication makes encapsulation and decapsulation fast: roughly 50 microseconds on a modern CPU for Kyber-768.

CRYSTALS-Dilithium: NIST’s Signature Standard

CRYSTALS-Dilithium (now ML-DSA, FIPS 204) is a signature scheme based on module-LWE and module-SIS (Short Integer Solution). Its design is based on the Fiat-Shamir with aborts framework of Lyubashevsky.

Signature sizes (Dilithium3, recommended level):

  • Public key: $1952$ bytes.
  • Signature: $3293$ bytes.
  • Security: 128-bit post-quantum security.

For comparison, ECDSA-256 produces 64-byte signatures with a 64-byte public key. Dilithium’s overhead is the price of resistance to quantum attack.

SPHINCS+ (FIPS 205) is a hash-based signature alternative standardized alongside Dilithium. Its security relies only on hash function security, not lattice problems, providing diversity of assumptions.

The Hybrid Transition

During the transition period, deploying lattice cryptography alone introduces risk: if a subtle weakness is found in Ring-LWE (it is newer and less studied than RSA), the system is broken. The solution is hybrid key exchange: combine classical ECDH with post-quantum Kyber.

In TLS 1.3, this looks like:

  1. Client and server run ECDH over X25519 (classical).
  2. Client and server run Kyber-768 key encapsulation (post-quantum).
  3. Both shared secrets are fed into the key derivation function.

Security: an attacker must break both ECDH and Kyber to learn the session key. The session is secure against classical attackers (via ECDH) and secure against quantum attackers (via Kyber). Google Chrome, Cloudflare, and AWS have deployed hybrid post-quantum TLS.

Summary

Concept Description
Lattice $\mathcal{L}(B)$ Integer linear combinations of basis vectors $\mathbf{b}_1, \ldots, \mathbf{b}_n$
SVP Find shortest nonzero vector; best algorithms $2^{O(n)}$ classical and quantum
CVP Find closest lattice vector to a target; at least as hard as SVP
LWE Distinguish $(\mathbf{a}, \langle \mathbf{a},\mathbf{s}\rangle + e)$ from uniform; reduces to worst-case SVP
Ring-LWE LWE over $\mathbb{Z}_q[x]/(x^n+1)$; $O(n)$ key size, $O(n\log n)$ operations
Module-LWE Hybrid of plain and ring LWE; balances security and efficiency
CRYSTALS-Kyber NIST KEM standard; ~1 KB keys; fast via NTT
CRYSTALS-Dilithium NIST signature standard; ~2 KB signatures
Hybrid TLS ECDH + Kyber; secure against classical and quantum attackers simultaneously

The move to post-quantum cryptography is one of the largest infrastructure transitions in the history of the internet. Lattice-based schemes are the leading vehicle for that transition.

Read next: