Lattice reduction (LLL and Lagrange-Gauss)

How it works

A lattice is the set of integer combinations of linearly independent basis vectors. The same lattice has many bases, and reduction looks for one with short, nearly orthogonal vectors. In dimension 2 the Lagrange-Gauss algorithm solves this exactly: keep the shorter vector first and subtract from the other the rounded multiple $\lfloor v_1 \cdot v_2 / |v_1|^2 \rceil$, until nothing changes. The result contains a shortest non-zero vector of the lattice.

LLL (Lenstra, Lenstra and Lovász, 1982) generalizes this to any dimension in polynomial time. It works with the Gram-Schmidt vectors $b_i^*$ and coefficients $\mu_{i,j}$: size reduction makes every $|\mu_{i,j}| \le 1/2$, and the Lovász condition $|b_k^*|^2 \ge (\delta - \mu_{k,k-1}^2) |b_{k-1}^*|^2$ decides whether to move on or to swap two vectors. The output satisfies $|b_1| \le \alpha^{(n-1)/2} \lambda_1$ with $\alpha = 1/(\delta - 1/4)$, so for $\delta = 3/4$ the first vector is at most $2^{(n-1)/2}$ times longer than a shortest vector. This tool keeps all values as exact fractions.

LLL is a basic tool of cryptanalysis: it breaks knapsack cryptosystems, small RSA exponents (Coppersmith’s method) and biased signature nonces. In high dimension, however, finding short vectors is believed to be hard even for quantum computers, which is the foundation of lattice-based schemes such as Kyber and Dilithium.