Basis Reduction in Practice: LLL, BKZ and the Delta Parameter

Every security claim about a lattice scheme is a claim about the cost of the best known algorithm for a geometric problem. That cost is not a complexity-theoretic bound; it is an estimate produced by running basis-reduction algorithms against the proposed parameters, extrapolating their cost curves, and taking the minimum over a family of attacks. The results are published in the parameter tables of FIPS 203 and in the candidate documentation, and reading them requires understanding what a reduced basis is and why the block size parameter is the single number that sets the security level.

What reduction produces

A lattice of rank $n$ has many bases, all related by unimodular transformations. A basis is reduced when its vectors are as short as possible and as orthogonal as possible, in a sense made precise by the algorithm. The two named quality measures are the root-Hermite factor

$$\delta = \left(\frac{|b_1|}{\det(\Lambda)^{1/n}}\right),$$

which compares the shortest produced vector against the determinant of the lattice, and the Hermite factor $\delta^n$. A perfect basis would have $\delta = 1$ for an orthogonal basis of equal-length vectors, which is impossible for a non-orthogonal lattice; a random basis has $\delta$ around $(\Gamma(n/2+1))^{1/n}/\sqrt{\pi}$, which grows with $n$. Reduction algorithms attempt to minimise $\delta$, and the achievable $\delta$ as a function of the algorithm’s effort is the cost curve that determines security.

The point of a good basis is that the first vector is short. For the shortest vector problem, the attack is to reduce the basis and hope the shortest basis vector is the shortest lattice vector. For the closest vector problem, a reduced basis allows Babai’s nearest-plane algorithm to find a good approximation. For the decoding attack on Learning With Errors, the reduction is on a lattice built from the public matrix and the syndrome, and the error vector appears as a short vector in it.

LLL as preprocessing, and why it is not enough

The Lenstra–Lenstra–Lovász algorithm swaps and subtracts basis vectors while maintaining a Lovász condition on adjacent pairs, parameterised by a constant $\delta \in (1/4, 1]$ that the original paper sets to $3/4$. The Lovász condition is

$$\delta |b_k^|^2 \le |b_{k+1}^|^2 + \mu_{k+1,k}^2 |b_k^*|^2,$$

where $b^*$ is the Gram–Schmidt orthogonalisation and $\mu$ the Gram–Schmidt coefficients. The algorithm terminates in polynomial time and produces a basis with $|b_1| \le 2^{(n-1)/2} \det(\Lambda)^{1/n}$, which is an exponential factor away from the Minkowski bound. For lattice cryptography at $n = 512$ or higher, that factor is enormous; LLL alone does not solve the problem.

What LLL does buy is a well-conditioned starting point. Its vectors are short enough that the enumeration and sieving steps of the stronger algorithms do not overflow fixed-width arithmetic and do not waste effort on obviously bad directions. Every practical reduction pipeline starts with LLL, which is why the algorithm is described as the foundation rather than the answer. The complexity is $O(n^4 \log B)$ bit operations for entries bounded by $B$, on the order of $10^6$ operations for a 256-dimensional basis with small entries, which is negligible against what follows.

The $\delta$ parameter in LLL is a knob, but a weak one. Setting it closer to 1 produces a slightly better basis at a higher cost, and the relationship is a constant factor rather than a change in the exponent. The exponent is fixed at 4 in the bit-complexity expression, and no setting of $\delta$ improves it. Recourse to higher precision is another matter: floating-point LLL can fail on ill-conditioned bases, and the standard fix is to use higher-precision arithmetic or exact rational arithmetic in the Gram–Schmidt step. Implementations that use double precision and silently accept a loss of accuracy produce a basis that is not reduced, so the attack fails for reasons that have nothing to do with the lattice.

BKZ and the block size as the security parameter

Schnorr’s blockwise reduction generalises LLL by treating the basis in blocks of size $\beta$ and finding the shortest vector in each block’s projected lattice exactly, then inserting it and continuing. The block size $\beta$, often called $K$ in the literature, interpolates between LLL at $\beta = 2$ and exact reduction at $\beta = n$. The quality of the output is characterised by the root-Hermite factor over the full dimension, approximately

$$\delta(\beta) \approx \left(\frac{\beta}{2\pi e} (\pi \beta)^{1/\beta}\right)^{1/(2(\beta-1))}.$$

This curve is the bridge from the algorithmic effort to the security estimate. At $\beta = 60$, $\delta$ is roughly 1.0085, at $\beta = 100$ around 1.0050, and at $\beta = 300$ near 1.0015. A smaller $\delta$ means the reduction produces a shorter vector for the same lattice, which means the attack succeeds at a smaller dimension, which means the scheme’s parameters must be larger to reach the same security.

The core steps inside BKZ are two, and their costs set the overall runtime. Enumeration finds the shortest vector in a basis of dimension $\beta$ by a depth-first search over the coefficients of the target vector, with pruning to cut the tree. The cost is roughly $2^{O(\beta \log \beta)}$ for the straightforward version, and the memory is small. Sieving finds many short vectors by sorting a large list of candidates and looking for pairs that are close, and its cost is $2^{O(\beta)}$ with a constant in the exponent of about 0.29 for the best known algorithms, at the price of $2^{O(\beta)}$ memory. For large $\beta$ the memory term dominates the practical cost, and the standard security analysis uses the minimum of the two attacks at each block size.

The number of BKZ tours is the second parameter. A single tour with full block size does not reduce the basis to the asymptotic quality; implementations run several tours, and the basis quality improves monotonically. The relevant figure for a security estimate is the rank and the block size at which the expected number of tours is a small constant, not the cost of one tour. The extrapolation from measured runtimes to larger dimensions is where the estimate becomes uncertain, and the community’s practice is to take the most pessimistic of several extrapolation models. That is why the parameter tables carry a margin rather than a single number.

What the pipeline assumes about the adversary’s data

The attack pipeline described in the previous subsection takes a matrix and a syndrome as input, which assumes the adversary has as many samples as the lattice dimension requires. In practice the attack is run with $m$ samples, and $m + n + 1$ is the lattice dimension, so the cost grows with the number of ciphertexts the attacker collects under the same key. For a KEM where each key is used once, $m = 1$, and the primal attack loses its advantage. That is the reason the security analysis for a KEM works on a different attack model from the one for a public-key encryption scheme, even though the underlying problem is the same. The standard’s parameter choices are made for the one-shot setting, and a protocol that reuses a KEM key pair across many encryptions is weaker than the standard assumes; that matters for long-lived host keys.

The attack pipeline on an LWE instance

Given a public matrix $A$ and a syndrome $b$, the primal attack embeds the problem in a lattice of dimension $m + n + 1$ with the basis

[ q I_m    0     0 ]
[ A        I_n   0 ]
[ b        0     t ]

with a scaling factor $t$ on the last coordinate to balance the error term against the modulus. The short vector $(-e, s, t)$ appears in this lattice precisely when $e$ is a valid error and $s$ is the secret, and its norm is $\sqrt{|e|^2 + |s|^2 + t^2}$. Basis reduction attempts to find it, and the success condition is a numerical inequality relating the error norm, the modulus, and the achievable $\delta$: the attack succeeds when the reduction quality is good enough that the target vector is shorter than the $n$-th root of the determinant.

The dual attack takes a different route: find a short vector $w$ in the dual lattice such that $w^T A$ is short, and use the inner product $w^T b$ to distinguish the distribution from uniform. The distinguishing advantage is proportional to the distance of that inner product from uniform, and the algorithm’s cost is again the reduction of the dual basis. Modern estimates run both attacks at every parameter set and take the smaller cost.

The number that emerges is expressed in “gate” units or in “core-Sieve” operations, which normalise against the cost of one sieve in a benchmark implementation. FIPS 203 reports its parameter sets against such an estimate at the three security categories, and the table is not a proof: it is a snapshot of the best known attacks at the time of publication, with the explicit understanding that a better algorithm or a better extrapolation would change the numbers. The historical precedent is instructive. Parameters proposed in the early 2010s for ring-LWE schemes were revised upward when improved sieving and improved enumeration changed the cost curve, and the round-three Kyber parameters include that revision.

Two practical caveats follow. First, the security analysis assumes that the lattice has no exploitable structure, which is why the module form is used rather than a plain ring: the module variant interpolates between the ring and the full matrix and gives a knob that the analysis can move without redesigning the scheme. The trade is discussed in MOD-LWE’s structure trade-off. Second, the estimates assume the adversary has enough samples; in a KEM the adversary gets one ciphertext per key, and the attack dimension is limited by that, which usually makes the primal attack weaker than a plain decision attack. Both of these are reasons the parameter tables are more conservative than the raw cost curve would suggest.