LLL Reduction — the polynomial-time workhorse behind almost every lattice attack

LLL (Lenstra–Lenstra–Lovász, 1982) is a polynomial-time algorithm that turns any lattice basis into a "reduced" one — nearly orthogonal, short vectors — and it is the actual reduction step every lattice attack in this wiki calls once the lattice itself is built.

The signal that gives it away

This isn't the page that tells you *whether* your challenge is lattice-shaped — that triage lives in Lattice Fundamentals — encoding a bounded unknown as a short vector. This page is the concrete tool you reach for once you're there. The signal that plain LLL (not something heavier) is the right call:

- You've already encoded a bounded unknown as a short vector in an integer lattice — a small modular root (Coppersmith's Method — recovering a small unknown from a modular polynomial via lattice reduction), a partially-leaked nonce (Hidden Number Problem — recovering a secret from many small-bounded-error samples, DSA/ECDSA Biased-Nonce Lattice Attack — turning partial nonce leaks into a private-key recovery), a low-density subset sum (Knapsack Cryptosystem — subset-sum ciphertexts broken by low-density lattice reduction), a short NTRU key (NTRU Fundamentals — recovering the short (f,g) key pair via lattice reduction), or any other "small unknown satisfies a known linear relation." - The lattice dimension is modest — up to a few hundred. LLL is polynomial time, but the *quality* guarantee (how close the output is to the true shortest vector) degrades exponentially with dimension, so past a few hundred rows plain LLL increasingly returns a short-but-not-shortest vector even though it still terminates fast. - You don't need a provably exact shortest vector, only one short enough to decode the secret — LLL only *guarantees* the first output vector is within a factor 2^((n-1)/2) of the true shortest vector λ₁(L) (for the standard δ=3/4 parameterization), but field experience across this wiki's attacks is that it lands on or extremely close to the actual shortest vector far more often than the worst-case bound suggests, which is exactly why it works as a practical attack tool rather than just a theoretical result.

If the dimension is too large, or the true shortest vector's length is too close to the gap the 2^((n-1)/2) bound allows, that's the signal to escalate past plain LLL (see below), not to abandon the lattice approach.

How to exploit it

1. Assemble the integer matrix. Rows are your basis vectors, encoding the linear relation(s) that pin down the secret. Every entry must be an integer — if your construction naturally produces rationals (moduli, scaling factors), multiply through by a common denominator first. Sage's Matrix(ZZ, rows) will simply fail to do what you want (or silently coerce) if you hand it rationals where it expects integers. 2. Balance entry sizes with diagonal weights. This is the step people skip and then wonder why LLL "doesn't work." An unweighted lattice, where every coordinate is the same order of magnitude, has no geometric reason to make your planted secret-encoding vector the *shortest* vector in the lattice — LLL will happily return some other short vector that is correct-looking but useless. Scale the rows/columns (typically via a diagonal weight matrix K) so that the vector you actually want is provably shorter than the "noise" vectors under the Euclidean norm. This weighting step is exactly what Hidden Number Problem — recovering a secret from many small-bounded-error samples and Coppersmith's Method — recovering a small unknown from a modular polynomial via lattice reduction each do in their own lattice constructions — this page is the shared mechanism, not a separate trick per attack. 3. Reduce and read off candidate rows. ``python from sage.all import Matrix, ZZ B = Matrix(ZZ, rows) R = B.LLL() # reduced basis, rows roughly sorted short -> long cand = R[0] # often the planted short vector, but check every short row # scale-aware: divide back any weight columns to recover the unknowns ` Sage's .LLL() runs the standard LLL reduction on the rows of the matrix in polynomial time (documented alongside Sage's other integer-matrix lattice routines). 4. **Escalate to BKZ if plain LLL doesn't surface the vector.** For higher dimension or a tighter gap, use block reduction: M.BKZ(block_size=20) (or larger). BKZ trades *double*-exponentially increasing runtime in the block size for a basis with a stronger shortest-vector guarantee than LLL's — a much steeper cost than LLL's own runtime, so push the block size up cautiously — useful precisely in the regime where LLL's 2^((n-1)/2)` bound stops being reassuring. Start with a modest block size (20-30) before jumping to something expensive. 5. For closest-vector-shaped problems, add the embedding row. If what you actually have is a CVP instance (a target point, not a lattice-native short vector), append the standard embedding row before calling LLL/BKZ rather than trying to force it through plain SVP reduction. 6. Verify before trusting. Recompute the original equation (re-derive the modulus, re-sign a message, re-check the polynomial root) from whatever candidate LLL hands you. A wrong-but-short vector is a normal outcome, not a rare edge case — treat every candidate row as unverified until it round-trips.

What does NOT work

- Skipping the weighting step. The single most common way LLL "fails" in practice isn't the algorithm — it's an unweighted matrix where the planted vector was never going to be the shortest one geometrically. If LLL returns something plausible-looking but wrong, check the weighting before questioning the lattice construction itself. - Feeding it unscaled rational entries. Clear denominators into an integer matrix first; don't rely on the tooling to do the right thing with rationals. - Assuming `R[0]` is always the answer. The reduced basis is *roughly* sorted short-to-long, not guaranteed sorted, and the target vector can come out negated. Scan several of the shortest rows, and try the negation, before concluding the construction is broken. - Trusting a short vector without verification. "Looks short and has plausible-looking values" is not the same as correct — always check the candidate against the original relation before spending time downstream on it. - Pushing plain LLL into large dimensions and expecting the shortest vector. Past a few hundred dimensions (or whenever the true shortest vector isn't comfortably within the 2^((n-1)/2) slack), plain LLL increasingly returns a short-but-wrong vector even though it still runs fast. That's a signal to move to BKZ with a larger block size, not to add more rows and hope. - Treating a CVP-shaped problem as if it were plain SVP. If the unknown is "close to" a lattice point rather than naturally short as a lattice vector, running plain .LLL() without the embedding row wastes effort on the wrong problem shape.

Related

Lattice Fundamentals — encoding a bounded unknown as a short vector Coppersmith's Method — recovering a small unknown from a modular polynomial via lattice reduction Hidden Number Problem — recovering a secret from many small-bounded-error samples Knapsack Cryptosystem — subset-sum ciphertexts broken by low-density lattice reduction DSA/ECDSA Biased-Nonce Lattice Attack — turning partial nonce leaks into a private-key recovery Boneh-Durfee Attack — the lattice extension of Wiener that reaches d < N^0.292 NTRU Fundamentals — recovering the short (f,g) key pair via lattice reduction LWE Fundamentals — recognizing and breaking noisy linear equations mod q