1.5 Lattice Reduction

Transforming a bad basis into a good one — the algorithmic bridge between theory and cryptanalysis.

We’ve established that the same lattice can be described by many different bases, and that some bases are much more useful than others. A “good” basis has short, nearly orthogonal vectors. A “bad” basis has long, highly skewed vectors. Lattice reduction is the process of transforming a given basis into a better one — ideally, into one whose vectors are as short and orthogonal as possible.

Why does this matter? Two reasons. First, most lattice problems become easy once you have a short basis. Second, the difficulty of lattice reduction — specifically, how good a reduced basis you can achieve in polynomial time — sets the exact hardness of lattice-based cryptographic schemes. Security parameters are chosen so that no efficient reduction algorithm can produce a basis short enough to break the scheme.

Intuition

Imagine asking someone for walking directions to a store that is just 1 block North and 1 block East. A “good” set of directions says exactly that: “Go 1 block North, then 1 block East.”

A “bad” set of directions might say: “Go 100 blocks North, then 99 blocks South, then 100 blocks East, then 99 blocks West.” If you follow these instructions perfectly, you’ll still end up at the exact same store, but the instructions are awful, confusing, and huge.

In some lattice trapdoor schemes, a public description hides a useful secret basis. Lattice reduction tries to find shorter, less skewed vectors from a basis. It also helps attackers study schemes such as ML-KEM, whose public keys are noisy equations rather than bad bases.

What Makes a Basis “Reduced”?

The quality of a basis is measured by its Gram–Schmidt vectors (introduced in §1.2). A perfectly orthogonal basis has Gram–Schmidt vectors equal to the basis vectors themselves — no projection, no shortening. As the basis becomes more skewed, the Gram–Schmidt vectors shrink. The ratio between consecutive Gram–Schmidt norms tells us how fast the basis “deteriorates” from one vector to the next.

A reduced basis, informally, is one where this deterioration is controlled — each Gram–Schmidt vector is not too much shorter than the previous one.

Size Reduction: The First Step

Before any serious reduction, we perform size reduction: subtract integer multiples of earlier basis vectors from later ones to make the Gram–Schmidt coefficients small. This is analogous to the elimination steps in Gaussian elimination, but done over integers.

Definition 19 — Size-Reduced Basis

A basis B=(b1,…,bn)B = (b_1, \dots, b_n) is size-reduced if all Gram–Schmidt coefficients satisfy:

∣μij∣≤12for all i>j|\mu_{ij}| \leq \frac{1}{2} \quad \text{for all } i > j

where μij=⟨bi,b~j⟩/∥b~j∥2\mu_{ij} = \langle b_i, \tilde{b}_j \rangle / \|\tilde{b}_j\|^2 are the Gram–Schmidt coefficients. Achieving size reduction is easy: for each pair i>ji > j, subtract ⌊μij⌉⋅bj\lfloor \mu_{ij} \rceil \cdot b_j from bib_i. This keeps all lattice points intact (it’s a unimodular operation) and bounds the off-diagonal Gram–Schmidt coefficients.

Size reduction alone isn’t enough — we can have a size-reduced basis that is still heavily skewed. The next step is to ensure consecutive Gram–Schmidt vectors don’t shrink too fast.

The LLL Algorithm

The LLL algorithm (Lenstra, Lenstra, Lovász, 1982) was the first polynomial-time algorithm to produce a provably short lattice basis. It transformed the field — before LLL, no efficient basis reduction with guarantees existed.

LLL repeatedly does two things: size-reduce the current basis, then check whether swapping adjacent basis vectors would improve the Gram–Schmidt profile. The swap criterion — called the Lovász condition — ensures that after a swap, the geometric mean of consecutive Gram–Schmidt norms improves.

LLL in 2D, one step at a time

Press Next step (or Play) and read what each move does. On step 0 you can drag the tips of b₁ and b₂.

b₁b₂
step
0 / 6
‖b₁‖
3.62
‖b₂‖
5.00
μ = ⟨b₂,b₁⟩/‖b₁‖²
-1.37
orthogonality defect
12.58

Step 0: the starting basis. Press Next step, or drag the tips of b₁ and b₂ to pick your own.

What to notice: Only two moves are ever used: size-reduce (subtract a whole multiple of b₁ from b₂) and swap (put the shorter vector first). Neither move changes the lattice: the dots never move. In 2D, LLL with δ = 1 is exactly Lagrange–Gauss reduction and ends with a shortest vector in b₁. In higher dimensions LLL applies the same two moves to neighbouring pairs bk−1, bk, and uses the Lovász condition to decide when to swap.

Definition 20 — LLL-Reduced Basis

A basis is LLL-reduced with parameter δ∈(1/4,1]\delta \in (1/4, 1] (typically δ=3/4\delta = 3/4) if it is size-reduced and satisfies the Lovász condition for all consecutive pairs:

δ∥b~i∥2≤∥b~i+1∥2+μi+1,i2∥b~i∥2\delta \|\tilde{b}_i\|^2 \leq \|\tilde{b}_{i+1}\|^2 + \mu_{i+1,i}^2 \|\tilde{b}_i\|^2

Intuitively: the (i+1)(i+1)-th Gram–Schmidt vector cannot be much shorter than the ii-th one (adjusted for skew). If the condition is violated, swapping bib_i and bi+1b_{i+1} strictly improves the profile.

Theorem 4 — LLL Guarantee (Lenstra–Lenstra–Lovász 1982)

For δ=3/4\delta = 3/4, the LLL algorithm terminates in polynomial time and the output basis B′=(b1′,…,bn′)B' = (b_1', \dots, b_n') satisfies:

∥b1′∥≤2(n−1)/2⋅λ1(Λ)\|b_1'\| \leq 2^{(n-1)/2} \cdot \lambda_1(\Lambda)

∥b1′∥≤2(n−1)/4⋅det⁡(Λ)1/n\|b_1'\| \leq 2^{(n-1)/4} \cdot \det(\Lambda)^{1/n}

The first vector is at most exponentially longer than the true shortest vector, with a small base (about 21/2≈1.412^{1/2} \approx 1.41 per dimension relative to λ1\lambda_1, and 21/4≈1.192^{1/4} \approx 1.19 relative to det⁡(Λ)1/n\det(\Lambda)^{1/n}). This is a worst-case bound, not a law of nature: in practice LLL does much better, reaching about ∥b1∥≈1.0219n⋅det⁡(Λ)1/n\|b_1\| \approx 1.0219^n \cdot \det(\Lambda)^{1/n}.

Why LLL Terminates: The Potential Argument

The LLL algorithm terminates because each swap strictly decreases a carefully chosen potential function. Define the LLL potential as:

The Potential Function

Φ(B)=∏i=1n∥b~i∥2(n−i+1)\Phi(B) = \prod_{i=1}^n \|\tilde{b}_i\|^{2(n-i+1)}

Each swap decreases Φ\Phi by a factor of at least δ−μi+1,i2≥δ−1/4>0\delta - \mu_{i+1,i}^2 \geq \delta - 1/4 > 0. Since Φ\Phi is a positive integer bounded above by a function of the input, the algorithm must terminate after a polynomial number of swaps. Each swap and size-reduction step is itself polynomial-time, giving overall polynomial complexity.

Block Korkine–Zolotarev (BKZ) Reduction

LLL’s weakness is that it only looks at consecutive pairs of basis vectors. To get shorter output, you need to look at larger blocks simultaneously. The BKZ algorithm generalizes LLL by solving an SVP instance inside every consecutive block of size β\beta.

The tradeoff is stark: larger β\beta gives shorter output but requires exponential time (since solving SVP in a β\beta-dimensional block is exponential in β\beta). BKZ with β=2\beta = 2 is equivalent to LLL; BKZ with β=n\beta = n solves SVP exactly.

Definition 21 — BKZ-β Reduction

The BKZ-β\beta algorithm processes the basis in a sliding window of size β\beta. In each window, it:

1. Projects the current basis vectors onto the orthogonal complement of all previous Gram–Schmidt vectors.
2. Solves SVP in this projected β\beta-dimensional sublattice.
3. Inserts the short vector found back into the full basis.
4. Re-size-reduces.

This is repeated over all windows until no more progress is possible. The output satisfies:

∥b1∥≈δ0n⋅det⁡(Λ)1/n\|b_1\| \approx \delta_0^n \cdot \det(\Lambda)^{1/n}

where δ0≈(β2πe (πβ)1/β)1/(2(β−1))\delta_0 \approx \left( \frac{\beta}{2\pi e} \, (\pi\beta)^{1/\beta} \right)^{1/(2(\beta-1))} is the root Hermite factor achievable by BKZ-β\beta.

BKZ in Cryptanalysis

Security estimates for all lattice-based cryptosystems are computed by asking: what is the smallest block size β\beta for which BKZ-β\beta would recover the short vector underlying the scheme? The cost of BKZ with that β\beta is then the security level in bits.

BKZ cost model

Running BKZ-β\beta on an nn-dimensional lattice costs approximately:

T≈n⋅TSVP(β)T \approx n \cdot T_{\mathrm{SVP}}(\beta)

where TSVP(β)T_{\mathrm{SVP}}(\beta) is the cost of solving SVP in dimension β\beta. Using sieving as the SVP oracle: TSVP(β)≈20.292βT_{\mathrm{SVP}}(\beta) \approx 2^{0.292\beta} classically, 20.265β2^{0.265\beta} quantumly.

Realistic BKZ behavior

The theoretical BKZ model assumes perfect SVP oracles and many tours through the basis. In practice, BKZ behavior is modeled by the BKZ simulator (Chen–Nguyen 2011): it predicts the Gram–Schmidt profile after BKZ more accurately than worst-case analysis. Modern cryptanalysis tools (like the Lattice Estimator) use the simulator for security estimates.

Progressive BKZ

In practice, cryptanalysts run BKZ with increasing block sizes: β=20,30,40,…\beta = 20, 30, 40, \dots — called progressive BKZ. Each increase yields marginally better output but costs exponentially more. The security level is the block size where the total cost exceeds the target (e.g., 21282^{128}).

The Geometric Series Assumption (GSA)

When analyzing BKZ output, practitioners often use the Geometric Series Assumption (GSA): after BKZ reduction, the Gram–Schmidt norms decrease in a geometric sequence. Formally:

Definition 22 — Geometric Series Assumption

After BKZ-β\beta reduction, the Gram–Schmidt log-norms log⁡∥b~i∥\log \|\tilde{b}_i\| lie approximately on a line with negative slope:

log⁡∥b~i∥≈12log⁡(det⁡(Λ)2/n)+(n+12−i)⋅log⁡(δ02)\log \|\tilde{b}_i\| \approx \frac{1}{2}\log(\det(\Lambda)^{2/n}) + (\frac{n+1}{2} - i) \cdot \log(\delta_0^2)

This geometric decay of Gram–Schmidt norms makes the output predictable and allows closed-form computation of the first vector’s length, which is what matters for cryptanalysis. The GSA is empirically accurate for moderate BKZ block sizes.

The Root Hermite Factor δ₀ and How It Measures Output Quality

After a reduction algorithm terminates, we want a single number that describes how good its output is. The root Hermite factor δ0\delta_0 is that number. It measures the length of the first output basis vector relative to the lattice’s “expected” spacing, normalized by dimension so that it is comparable across different lattice sizes.

Root Hermite Factor — Definition and Formula

Given a lattice Λ\Lambda in dimension nn with determinant det⁡(Λ)\det(\Lambda), and a reduction algorithm that outputs a first basis vector of length ∥b1∥\|b_1\|, the root Hermite factor is:

δ0=(∥b1∥det⁡(Λ)1/n)1/n\delta_0 = \left( \frac{\|b_1\|}{\det(\Lambda)^{1/n}} \right)^{1/n}
Equivalently, ∥b1∥=δ0n⋅det⁡(Λ)1/n\|b_1\| = \delta_0^{n} \cdot \det(\Lambda)^{1/n}. This form makes the geometric interpretation clear: δ0n\delta_0^{n} is the factor by which the output exceeds the lattice spacing. (Some papers use the exponent 1/(n−1)1/(n-1) instead; for large nn the difference is negligible. This site uses 1/n1/n throughout.)

For BKZ-β\beta reduction, the achievable root Hermite factor is:

δ0(β)≈(β2πe (πβ)1/β)1/(2(β−1))\delta_0(\beta) \approx \left( \frac{\beta}{2\pi e} \, (\pi\beta)^{1/\beta} \right)^{1/(2(\beta-1))}
As β→∞\beta \to \infty, δ0→1\delta_0 \to 1 (approaching the true shortest vector). The formula is only accurate for β≳50\beta \gtrsim 50; for small block sizes one uses experimental values: δ0≈1.022\delta_0 \approx 1.022 for LLL (β=2\beta = 2) and δ0≈1.0128\delta_0 \approx 1.0128 for BKZ-20. The formula shows a clear tradeoff: smaller δ0\delta_0 requires larger β\beta, which means exponentially more computation.

For example, the round-3 Kyber analysis puts the block size needed to break ML-KEM-768 at about β≈623\beta \approx 623, i.e. δ0≈1.0029\delta_0 \approx 1.0029, with a Core-SVP cost of roughly 20.292⋅623≈21822^{0.292 \cdot 623} \approx 2^{182} classical operations.

HKZ, LLL, and BKZ: A Comparison

There is a spectrum of reduction algorithms, ranging from the computationally free but weak, to the optimal but exponential. The three most important points on this spectrum are HKZ, LLL, and BKZ.

HKZ Reduction (Hermite–Korkine–Zolotarev)

HKZ reduction is the gold standard — the best possible fully reduced basis. A basis is HKZ-reduced if: (1) it is size-reduced, and (2) the first vector b1b_1 is a shortest nonzero vector (∥b1∥=λ1\|b_1\| = \lambda_1), and (3) the projection of remaining vectors onto the orthogonal complement of b1b_1 is itself HKZ-reduced (applied recursively).

HKZ reduction achieves δ0→1\delta_0 \to 1 but requires solving SVP exactly in each recursive step — taking time 2O(n)2^{O(n)}. It is computationally equivalent to solving SVP. Used as a theoretical baseline, not in practice for large nn.

LLL Reduction

LLL is the practical workhorse — polynomial time with provable guarantees. It enforces a weak Lovász condition on consecutive pairs of Gram–Schmidt vectors. Its output satisfies ∥b1∥≤2(n−1)/2λ1\|b_1\| \leq 2^{(n-1)/2} \lambda_1.

Root Hermite factor: δ0≈1.022\delta_0 \approx 1.022 (dimension 100). Runtime: poly(n,log⁡B)\mathrm{poly}(n, \log B).

LLL is the default preprocessing step before any heavier reduction, and is used directly when speed matters more than output quality (e.g., in Coppersmith attacks on RSA).

BKZ Reduction

BKZ interpolates between LLL (β=2\beta=2) and HKZ (β=n\beta=n). It solves SVP inside every window of size β\beta and achieves: δ0(β)≈(β2πe (πβ)1/β)1/(2(β−1))\delta_0(\beta) \approx \left( \frac{\beta}{2\pi e} \, (\pi\beta)^{1/\beta} \right)^{1/(2(\beta-1))}.

Runtime: poly(n)⋅2O(β)\mathrm{poly}(n) \cdot 2^{O(\beta)} per tour. The tradeoff is stark — doubling β\beta roughly doubles the quality of reduction but squares the cost.

Modern variants (BKZ 2.0, progressive BKZ, pump-and-jump BKZ) incorporate better SVP oracles, preprocessing, and tour strategies to achieve better practical performance than the theoretical model predicts.

In summary: HKZ gives optimal output at exponential cost; LLL gives weak output at polynomial cost; BKZ covers all points in between. All post-quantum lattice security estimates are expressed in terms of the BKZ block size needed to break the scheme.

Summary: Reduction Algorithms and Their Guarantees

LLL (β = 2)

Time: poly(n,log⁡B)\mathrm{poly}(n, \log B) where BB is a bound on input size.

Output: ∥b1∥≤2(n−1)/2λ1\|b_1\| \leq 2^{(n-1)/2} \lambda_1.

Root Hermite factor: δ0≈1.022\delta_0 \approx 1.022 (dim 100). Fast and simple — the workhorse for preprocessing.

BKZ-20

Time: seconds to minutes in practice.

Root Hermite factor: δ0≈1.0128\delta_0 \approx 1.0128.

Output significantly better than LLL. Used in early stages of attacks. Not enough to break well-designed PQC schemes.

BKZ-100

Time: ∼229\sim 2^{29} per tour.

Root Hermite factor: δ0≈1.009\delta_0 \approx 1.009.

Achieves good quality but feasible in practice. Used in actual cryptanalysis of weak instances.

BKZ-623 (Kyber-768 security)

Time: ∼20.292⋅623≈2182\sim 2^{0.292 \cdot 623} \approx 2^{182} classical (Core-SVP).

Root Hermite factor: δ0≈1.0029\delta_0 \approx 1.0029.

This is the block size needed to break ML-KEM-768. Far beyond any feasible computation — ensuring ~182-bit security.

Check Your Understanding

  1. Q1. What does lattice reduction change, and what does it leave alone?

  2. Q2. An attacker switches from BKZ with block size 60 to block size 120. What should they expect?

  3. Q3. Why is LLL alone not a threat to ML-KEM, even though it runs in polynomial time?

  4. Q4. How is a lattice scheme’s security level typically estimated?