LLL Lattice Reduction: How the Knapsack Cryptosystem Fell

This article has three layers:

1. The intuition: lattices, good and bad bases, the knapsack problem
2. Real-world use: the rise and fall of knapsack cryptography, recovering private keys from side-channel leaks, choosing post-quantum parameters
3. The mathematics: Gaussian reduction in two dimensions, the idea of LLL, the knapsack cryptosystem and its lattice attack, with worked examples

Layer 1: The Intuition

1.1 Lattices, good bases and bad bases

Take two vectors $b_1, b_2$ in the plane. All their integer combinations $a_1 b_1 + a_2 b_2$ form a regularly arranged set of points called a lattice.

The same array of points can be generated by different bases. Take the integer lattice $\mathbb{Z}^2$ (all points with integer coordinates):

• Good basis: $(1, 0)$ and $(0, 1)$, short and mutually perpendicular;
• Bad basis: $(5, 8)$ and $(8, 13)$, long and nearly parallel. You can verify that their integer combinations also generate exactly all the integer points (determinant $= 5 \cdot 13 - 8 \cdot 8 = 1$).

Someone holding the bad basis has a hard time seeing that "the shortest vector in this lattice has length just 1". This is the basic idea of lattice cryptography: the public key gives a bad basis, and the private key is a good one (see "Post-Quantum Cryptography").

1.2 The knapsack problem

You are given a pile of items of different weights, $\{82, 123, 287, 83, 248, 373, 10, 471\}$. Which ones add up to exactly $881$?

This is the subset sum problem. In general it is NP-complete, and with many items you are left with something close to brute force. In 1978 Merkle and Hellman built one of the earliest public-key cryptosystems on it: which items you pick are the plaintext bits, and the total weight is the ciphertext.

1.3 Why it fell

To let the legitimate recipient decrypt, Merkle–Hellman hid a "trapdoor" structure in the item weights. In 1982 Shamir used this structure to break it; soon after, people found a more general method: write the knapsack problem as a lattice, where the secret bit string corresponds to an unusually short vector in the lattice, and run LLL to get it straight out.

Layer 2: Real-World Use

The rise and fall of knapsack cryptography

What LLL is used for today

• Recovering ECDSA private keys from partial leaks: even if the nonce $k$ of ECDSA leaks only a few bits per signature (through a timing side channel, say), collecting a few hundred signatures lets you build a lattice and solve for the private key with LLL or BKZ. This is called the "hidden number problem" (HNP). Attacks such as TPM-Fail (2019) and Minerva (2019) all work this way. (See the extreme case of repeated $k$ in "Elliptic Curves".)
• Coppersmith's method: finds small roots of modular polynomial equations, attacking certain uses of small-exponent RSA, or factoring $n$ when half the bits of $p$ are known.
• Choosing post-quantum parameters: the security parameters of Kyber and Dilithium are estimated from "how long the best lattice reduction algorithm (BKZ) takes". Here LLL is the "enemy", used to measure how high the defenses stand.
• Beyond cryptography: integer relation detection (discovering identities among mathematical constants), integer programming and resolving GPS carrier-phase ambiguity.

Layer 3: The Mathematics

3.1 The definition of a lattice

Given linearly independent vectors $b_1, \dots, b_n \in \mathbb{R}^m$, the lattice is

$$L = \Big\{\sum_i a_i b_i : a_i \in \mathbb{Z}\Big\}.$$

Two bases $B$, $B'$ generate the same lattice if and only if $B' = UB$, where $U$ is a unimodular matrix (an integer matrix with determinant $\pm 1$), that is, $U \in GL_n(\mathbb{Z})$. So "changing basis" means multiplying by an element of the group $GL_n(\mathbb{Z})$.

The determinant of a lattice (the volume of the fundamental parallelepiped), $|\det B|$, doesn't change with the basis; it is an invariant of the lattice.

3.2 Two dimensions: Gaussian reduction, the vector version of the Euclidean algorithm

In two dimensions there is an exact algorithm (Lagrange–Gauss): repeatedly use the short vector to "whittle down" the long one, until no more can be removed. This is exactly the same idea as "subtract the smaller from the larger" when computing a greatest common divisor.

3.3 The idea of LLL

In high dimensions there is no algorithm both exact and efficient (the shortest vector problem, SVP, is NP-hard), so LLL settles for an approximation:

1. Size reduction: for each $b_i$, subtract integer multiples of the earlier vectors, making its components along the Gram–Schmidt directions as small as possible (a generalization of two-dimensional Gaussian reduction);
2. The Lovász condition: if two adjacent vectors are in a "bad" order (the Gram–Schmidt length of the later one is much shorter than the earlier one's), swap them and return to step 1.

It can be proved that this ends in polynomial time, and the first output vector satisfies

$$\|b_1\| \le 2^{(n-1)/2} \cdot \lambda_1(L),$$

where $\lambda_1$ is the length of the true shortest vector. In the worst case this approximation factor is exponential, but real performance is far better than theory, often finding the shortest vector outright in a few dozen dimensions. The stronger BKZ algorithm builds on LLL by solving blocks exactly, trading time for quality.

3.4 Merkle–Hellman and its lattice attack

Private key: a superincreasing sequence $w = (2, 3, 7, 14, 30, 57, 120, 251)$ (each term exceeds the sum of all earlier ones), a modulus $q = 491 > \sum w_i$ and a multiplier $r = 41$ with $\gcd(r, q) = 1$.

Public key: $b_i = r w_i \bmod q$, that is, $b = (82, 123, 287, 83, 248, 373, 10, 471)$. It looks like a general knapsack, with the superincreasing structure "hidden" by the modular multiplication.

The lattice attack: build the lattice whose basis is the following rows (the last column holds the weights):

$$\begin{pmatrix} 1 & 0 & \cdots & 0 & b_1 \\ 0 & 1 & \cdots & 0 & b_2 \\ \vdots & & \ddots & & \vdots \\ 0 & 0 & \cdots & 1 & b_n \\ 0 & 0 & \cdots & 0 & -C \end{pmatrix}$$

Taking the plaintext bits $x_i$ as coefficients, adding the first $n$ rows and then the last row gives

$$(x_1, \dots, x_n,\ \textstyle\sum x_i b_i - C) = (x_1, \dots, x_n,\ 0).$$

This is an extremely short vector whose components are only 0 and 1, with length at most $\sqrt{n}$, while other vectors in the lattice are usually much longer. When the knapsack's "density" is low, LLL finds it directly, and the bit string is the plaintext.

Summary