An Introduction to Lattice-Based Cryptography

The Main Idea

Lattice-based cryptography is a leading approach to building secure systems that can resist attacks from both classical and future quantum computers. This resistance stems from the fact that the underlying mathematical problems are believed to be hard even for quantum computers, as they lack the specific structure that algorithms like Shor's exploit to break current cryptography.

The core of lattice cryptography relies on problems that are simple to state but computationally difficult to solve. The most fundamental of these is the Shortest Vector Problem (SVP). Imagine a lattice: an infinitely repeating, grid-like pattern of points in a high-dimensional space. SVP asks: what is the shortest non-zero vector from the origin to any other point in the lattice? This problem is believed to be computationally hard, and its security can be formally reduced to worst-case lattice problems. The best-known algorithms run in exponential time, approximately \(2^{\mathcal{O}(n)}\), where \(n\) is the dimension of the lattice.

This difficulty provides the foundation for a cryptographic "trapdoor." We can create a lattice in such a way that we have secret information, a "good" basis, that makes solving hard problems on that lattice easy for us. Anyone without this secret only has a "bad" basis, for which the same problems remain computationally infeasible.

Formally Defining Lattices

Formally, a lattice \(L\) is the set of all integer linear combinations of a set of linearly independent vectors \(\{b_1, b_2, \ldots, b_n\}\), which form a basis for the lattice. \[ L = \left\{ \sum_{i=1}^n a_i b_i \mid a_i \in \mathbb{Z} \right\} \]

The distinction between a "good" and a "bad" basis is crucial. A good basis consists of vectors that are short and nearly orthogonal. A bad basis consists of vectors that are long and nearly parallel. We can quantify this "goodness" with the Hadamard ratio, which compares the volume of the parallelepiped spanned by the basis vectors to the product of their lengths. For a basis matrix \(B\) with column vectors \(b_i\): \[ \text{Hadamard Ratio}(B) = \left( \frac{|\det(B)|}{\prod_{i=1}^n \|b_i\|} \right)^{1/n} \]

A ratio close to 1 indicates a good, nearly orthogonal basis, while a ratio close to 0 indicates a bad one.

The cryptographic trapdoor is created using a unimodular matrix: a square matrix \(U\) with integer entries and \(\det(U) = \pm 1\). Multiplying a basis \(B_g\) by \(U\) produces a new basis \(B_b = U B_g\) that generates the exact same lattice. The trick is to start with a good basis \(B_g\) (the private key) and construct a special unimodular matrix \(U\) (e.g., via random walks on \(\mathrm{SL}_n(\mathbb{Z})\)) that produces a very bad basis \(B_b\) (the public key) with a high orthogonality defect.

This concept is demonstrated by the Goldreich-Goldwasser-Halevi (GGH) cryptosystem (GGH97).

GGH Key Generation and Encryption

Alice generates a "good" private basis \(R\) and a carefully chosen unimodular matrix \(U\). Her public key is the "bad" basis \(B = UR\). To encrypt a message vector \(m\), Bob computes the ciphertext \(c = mB + e\), where \(e\) is a small, random error vector. The ciphertext \(c\) is a point in space very close to the true lattice point \(mB\).

GGH Decryption

When Alice receives \(c\), she uses her good basis \(R\) to solve the Closest Vector Problem (CVP), the problem of finding the closest lattice point to a given target vector. Using an efficient method like Babai's rounding algorithm, her good basis allows her to easily find the integer coefficients \(v\) for the lattice point \(vR\) that is nearest to \(c\). Because the error \(e\) was small, this point is \(mB\). Thus, the coefficients she recovers are \(v = mU\). She then recovers the message by computing: \[ v U^{-1} = (mU)U^{-1} = m \]

An eavesdropper, Eve, who only has the bad basis \(B\), faces the difficult task of solving CVP for \(c\), which is intractable.

Security Limitations of GGH

While GGH is an excellent pedagogical tool, it is considered insecure for practical use. Its security relies on the difficulty of turning the public basis \(B\) back into a good one. However, lattice reduction algorithms, most famously the LLL algorithm (LLL82), can do just that. The LLL algorithm can find a reduced basis that approximates the shortest vector within a factor exponential in the dimension. In practice, this is often sufficient to compromise GGH security under certain parameters, rendering it obsolete. This vulnerability motivated the shift towards systems based on the Learning with Errors problem.

Learning with Errors (LWE)

The Learning With Errors (LWE) problem (Regev05) is the foundation for most modern, secure lattice cryptosystems. To align with standard LWE literature, we now switch from treating vectors as rows (like \(mB\)) to treating them as columns (like \(As\)).

The LWE problem is about distinguishing two scenarios. Suppose we are given a set of pairs \((a_i, b_i)\), where the \(a_i\) are random vectors.

1. Random Scenario: Each \(b_i\) is a truly random number.
2. LWE Scenario: There exists a secret vector \(s\). Each \(b_i\) is calculated as \(b_i = \langle a_i, s \rangle + e_i \pmod{q}\), where \(e_i\) is a small error.

The errors \(e_i\) are sampled from a narrow discrete Gaussian distribution, \(\mathcal{D}_{\mathbb{Z}, \sigma}\), over the integers with a small standard deviation \(\sigma\). This ensures that \(|e_i| \ll q\), a condition critical for both security proofs and correctness. The LWE problem is to determine which scenario the samples came from.

LWE-Based Cryptography

We can build cryptographic schemes from the LWE problem. Let public parameters include a prime modulus \(q\), dimensions \(m\) and \(n\), and an error distribution. Typically, \(m > n\) to ensure sufficient security. The modulus \(q\) is often chosen to be a prime that allows for efficient modular arithmetic, particularly for the Number Theoretic Transform (NTT) used in more advanced schemes. Let \(A \in \mathbb{Z}_q^{m \times n}\) be a public matrix.

Key Exchange

Alice and Bob can establish a shared key as follows:

1. Alice generates a secret vector \(s_A \in \mathbb{Z}_q^n\) and an error vector \(e_A \in \mathbb{Z}_q^m\). She computes her public key \(p_A = As_A + e_A\) and sends it to Bob.
2. Bob generates a secret vector \(s_B \in \mathbb{Z}_q^m\) and an error vector \(e_B \in \mathbb{Z}_q^n\). He computes his public value \(p_B = A^T s_B + e_B\) and sends it to Alice.
3. Alice computes her key \(K_A = p_B^T s_A = (A^T s_B + e_B)^T s_A = s_B^T A s_A + e_B^T s_A\).
4. Bob computes his key \(K_B = s_B^T p_A = s_B^T(A s_A + e_A) = s_B^T A s_A + s_B^T e_A\).

Both parties now share the same principal term \(s_B^T A s_A\). Since all secret and error vectors have small components, the error terms are small, so \(K_A \approx K_B\). To obtain an identical key, they use a public error reconciliation mechanism. For example, they can agree on a shared bit by rounding their value to the nearest multiple of \(q/4\); if their initial values are close enough, they will both round to the same result.

Public Key Encryption

A recipient's private key is a secret vector \(s\). The public key is the pair \((A, p = As + e)\). To encrypt a single bit (the message):

1. The sender chooses a random, small binary vector \(r \in \{0, 1\}^m\).
2. The sender computes two values: \(u = A^T r\) and \(v' = p^T r + \text{message} \cdot \lfloor q/2 \rfloor\).
3. The ciphertext is the pair \((u, v')\).

To decrypt, the recipient computes \(v' - s^T u\). This simplifies to: \[ (p^T r + \text{message} \cdot \lfloor q/2 \rfloor) - s^T(A^T r) = ((As+e)^T r + \dots) - s^T A^T r = e^T r + \text{message} \cdot \lfloor q/2 \rfloor \]

Since \(e\) and \(r\) consist of small entries, the error term \(e^T r\) is small (specifically, we require \(|e^T r| < q/4\)). The recipient checks if the result is closer to 0 (message was 0) or to \(\lfloor q/2 \rfloor\) (message was 1).

Ring-LWE and The Future

While LWE is secure, its large key sizes (due to the matrix \(A\)) can be impractical. The need for greater efficiency led to the development of Ring-LWE (RLWE). This variant replaces vectors and matrices with polynomials, operating in a polynomial ring. The LWE equation becomes: \[ b(x) \equiv a(x) s(x) + e(x) \pmod{q} \quad \text{in the ring } \mathbb{Z}_q[x]/\langle \Phi_n(x) \rangle \]

Here, \(a(x), s(x), e(x)\) are polynomials, and all operations are performed modulo a prime \(q\) and a cyclotomic polynomial \(\Phi_n(x)\) (e.g., \(x^n+1\)).

This algebraic structure provides two major benefits:

1. Smaller Key Sizes: A single polynomial \(a(x)\) compactly represents the structure of an entire \(m \times n\) LWE matrix, drastically reducing key and ciphertext sizes.
2. Faster Computations: Polynomial multiplication, using algorithms like the Number Theoretic Transform (NTT), is much faster (\(O(n \log n)\)) than matrix-vector multiplication.

These immense efficiency gains have made structured lattices the basis for real-world post-quantum cryptography. The U.S. National Institute of Standards and Technology (NIST) selected algorithms based on Module-LWE, a variant of Ring-LWE that offers better security and flexibility, as its primary standards. These include CRYSTALS-Kyber for key encapsulation and CRYSTALS-Dilithium for digital signatures, securing our digital infrastructure for the quantum era.