Lattice Reduction (LLL and BKZ)
Lattice reduction is the family of algorithms that turns an ugly, tangled description of a lattice into a cleaner one made of short, nearly perpendicular vectors, and it is the single most important tool an attacker uses against lattice-based cryptography. Every practical attack on Learning With Errors and its relatives eventually runs a lattice-reduction algorithm, so the entire security estimate of ML-KEM and ML-DSA comes down to how strong a reduction it takes to crack them. The two names to know are LLL, a fast algorithm that gives a rough answer, and BKZ, a tunable algorithm that gives a better answer the longer you let it run. Understanding the trade between those two is understanding how lattice crypto is actually broken.
The short version:
- A lattice is a grid of points, and a basis is the set of vectors you use to describe it. The same lattice has many bases, some clean (short, near-perpendicular vectors) and some messy (long, skewed ones), and reduction is the process of trading a messy basis for a clean one.
- LLL is the fast baseline. Lenstra, Lenstra, and Lovász published it in 1982, and it runs in polynomial time to produce a “reduced” basis of reasonably short vectors, but the shortness guarantee weakens exponentially as the dimension grows.
- BKZ is the tunable workhorse. It generalizes LLL with a block size parameter, and turning that dial up buys shorter vectors at a steeply rising cost in time, which is the exact quality-versus-time trade that sets a scheme’s security.
- This is the attack lattice security is measured against. The “core-SVP” estimate that assigns bit-security to ML-KEM and ML-DSA is a statement about the block size BKZ would need, so lattice reduction is the yardstick.
- It is a classical attack, and Shor’s algorithm has no role here. The open question for lattice crypto has always been whether reduction algorithms improve, not whether a quantum computer breaks them outright.
Picture trying to describe a tiled floor to someone over the phone. You could hand them two long, slanted rulers that reach diagonally across many tiles, and they would struggle to figure out where any single tile corner sits. Or you could hand them two short rulers that run straight along the tile edges, and suddenly every corner is easy to locate. The floor is identical either way; only the pair of rulers changed. Lattice reduction is the work of swapping the long, slanted rulers for the short, straight ones, because once you hold the short ones, finding the nearest point (which is what an attacker needs) becomes far easier.
What is lattice reduction?
Lattice reduction is the process of taking one basis for a lattice and computing a different basis for the same lattice whose vectors are shorter and closer to perpendicular. A lattice is an infinite, regularly spaced grid of points in many dimensions, and a basis is a small set of vectors whose whole-number combinations generate every point in that grid. Crucially, a single lattice has infinitely many valid bases, and they differ enormously in usefulness: a “good” basis of short, near-orthogonal vectors makes the lattice’s hard problems tractable, while a “bad” basis of long, skewed vectors hides them. Reduction is the algorithmic bridge from bad to good.
The reason this matters for cryptography is that the security of a lattice scheme rests on two hard problems that a good basis cracks open. The shortest-vector problem (SVP) asks for the shortest nonzero vector in the lattice, and the closest-vector problem (CVP) asks for the lattice point nearest to some target. A Learning With Errors secret is recoverable if you can solve a version of these, and a good basis is exactly what lets you. So an attacker’s job is to reduce the public basis far enough that one of these problems falls, and the defender’s job is to pick parameters where reducing that far is computationally hopeless.
Source: “Lattice reduction,” Wikipedia, en.wikipedia.org.
How does the LLL algorithm work?
The LLL algorithm, named for Arjen Lenstra, Hendrik Lenstra, and László Lovász, is the foundational lattice-reduction method, and its landmark property is that it runs in polynomial time. Published in 1982 in a paper titled “Factoring polynomials with rational coefficients,” it walks through the basis vectors and repeatedly does two things: it subtracts whole-number multiples of earlier vectors from later ones to make them shorter (a size-reduction step), and it swaps adjacent vectors whenever doing so shortens the basis according to a fixed condition. It keeps sweeping until no swap helps anymore, at which point the basis is “LLL-reduced.”
Source: A. K. Lenstra, H. W. Lenstra Jr., L. Lovász, “Factoring polynomials with rational coefficients,” Mathematische Annalen 261(4), 1982, pp. 515-534, doi.org.
The catch is the quality of the answer. LLL guarantees a first vector that is short, but only within an approximation factor that grows exponentially with the dimension of the lattice. In the low dimensions LLL was invented for, like factoring polynomials and solving fixed-dimension integer programs, that is plenty. In the hundreds of dimensions a modern lattice scheme lives in, an LLL-reduced basis is nowhere near good enough to recover a secret, so its vectors are still far too long. LLL alone does not threaten ML-KEM. It is the fast first pass and the building block that stronger algorithms call as a subroutine, which is where BKZ comes in.
How does BKZ improve on LLL, and what is the block size trade?
BKZ, short for block Korkine-Zolotarev reduction, is the stronger algorithm that closes the gap LLL leaves, and it works by solving small hard sub-problems exactly to guide the reduction of the whole basis. Where LLL only ever compares two adjacent vectors at a time, BKZ slides a window of some chosen width across the basis and finds the genuinely shortest vector inside each window before moving on. That window width is the block size, usually written beta, and it is the one dial that controls everything. When the block size is 2, BKZ reduces to LLL. As the block size grows, BKZ produces progressively shorter vectors and gets progressively closer to actually solving the shortest-vector problem.
Source: “Lattice reduction,” Wikipedia, en.wikipedia.org; C. P. Schnorr, M. Euchner, “Lattice basis reduction: Improved practical algorithms and solving subset sum problems,” Mathematical Programming 66, 1994, pp. 181-199, doi.org.
The trade is unforgiving, and it is the whole game. Finding the shortest vector inside each block means running an exact SVP solver in a lattice of dimension equal to the block size, and the best known solvers for that (lattice sieving) cost time that grows exponentially in the block size. So a larger block gives you a better attack, but the cost climbs steeply:
- Small block size: cheap to run, but the resulting vectors are too long to recover a well-chosen secret. This is the regime where a scheme is safe.
- Large block size: expensive to run, but the vectors get short enough to break the scheme. A scheme is “secure to X bits” precisely when the block size needed to break it costs about 2^X operations.
- The crossover is the security level. Cryptographers set parameters so the block size required to recover the secret sits above the target, so the attack exists in principle but is astronomically expensive in practice.
This is why lattice security is not a yes-or-no wall like factoring. It is a smooth dial, and the standardized parameters are chosen to put the break far up a cost curve that rises exponentially.
Why is lattice reduction the workhorse of lattice cryptanalysis?
Because nearly every serious attack on a lattice scheme, whatever clever framing it starts from, ends up as a lattice-reduction problem, so reduction is the common bottleneck the whole field studies. An attack on LWE typically rewrites the noisy-equations problem as a lattice problem (either finding a short vector in a cleverly built lattice, the “primal” attack, or in a related dual lattice, the “dual” attack) and then throws BKZ at it. Attacks on the Short Integer Solution problem that underpins lattice signatures do the same. The specific construction differs, but the engine is always lattice reduction, which is why improvements to BKZ ripple across the security of every lattice standard at once.
That shared dependence is a double-edged thing. On one hand, it concentrates the risk: a genuinely better reduction algorithm would weaken ML-KEM, ML-DSA, and every other lattice scheme together, which is part of why the standards carry deliberate margin and why code-based and hash-based backups exist. On the other hand, it concentrates the scrutiny: because so much rests on BKZ and the sieving algorithms inside it, this is among the most heavily studied corners of cryptanalysis, and progress has been steady and incremental rather than sudden. The community watches the cost of the best sieve continuously, and the standardized parameters are set against the best known cost, with a cushion on top.
How does lattice reduction set a scheme’s security estimate?
The connection between reduction and a published bit-security number runs through a deliberately conservative model called core-SVP, which lower-bounds an attack by the cost of the single hardest step inside BKZ. Instead of trying to model the full, messy cost of running BKZ to completion, core-SVP charges the attacker only for one call to the shortest-vector solver in the block dimension, using the cost of the best known lattice sieve. The best classical sieve (Becker, Ducas, Gama, and Laarhoven, 2016) runs in time about 2^(0.292 times the block size), and its quantum-accelerated version is estimated at about 2^(0.265 times the block size).
Source: E. Alkim, L. Ducas, T. Pöppelmann, P. Schwabe, “Post-quantum key exchange - a new hope,” USENIX Security 2016, IACR ePrint 2015/1092; A. Becker, L. Ducas, N. Gama, T. Laarhoven, “New directions in nearest neighbor searching with applications to lattice sieving,” SODA 2016, IACR ePrint 2015/1128.
Reading a security estimate, then, means reading a statement about block size. When a scheme claims a given security category, the designers have computed the smallest block size at which BKZ recovers the secret and confirmed that the core-SVP cost of that block size clears the target. Because the model charges only the cheapest possible attack (one sieve call, ignoring the many calls BKZ actually makes and the memory it needs), the real attack is more expensive than the estimate, which is exactly the safety cushion the conservatism buys. The concrete calculation is automated in the LWE security tooling the community maintains, so parameter choices can be re-checked as the sieving cost estimates are refined. See Core-SVP and Lattice Security Estimation for how that estimate becomes a NIST security category.
Common misconceptions
- “LLL breaks lattice cryptography.” LLL runs fast but its shortness guarantee decays exponentially with dimension, so in the hundreds of dimensions a real scheme uses, an LLL-reduced basis is nowhere near good enough to recover a secret. It is the fast first pass and a subroutine, and BKZ with a large block size is what would actually threaten a scheme.
- “Lattice reduction is a quantum attack.” It is a classical algorithm. Shor’s algorithm breaks factoring and the discrete logarithm and has no purchase on lattices. The only quantum angle is a modest speedup to the sieving inside BKZ, which the parameters already price in.
- “If BKZ can eventually reduce any basis, lattice crypto is broken.” BKZ can reach any quality if you make the block size large enough, but the cost grows exponentially in the block size, so a well-chosen scheme sits far up that cost curve. Security is the price of the reduction, not the impossibility of it.
- “A single breakthrough could suddenly break all lattice schemes.” Because every lattice attack routes through reduction, a major improvement would affect many schemes together, which is a real concentration risk. In practice, progress on sieving and BKZ has been incremental and heavily watched, and the standards carry margin against it.
- “The security number is exact.” The core-SVP estimate is deliberately conservative, charging the attacker for only the single cheapest step of BKZ. The genuine attack costs more, so the published number is a floor with a cushion, not a precise prediction.
Questions people ask
What is lattice reduction in simple terms? It is the job of swapping a bad description of a lattice (long, skewed vectors) for a good one (short, nearly perpendicular vectors) that describes the same grid of points. A good description makes the lattice’s hard problems easy, so reduction is the main tool for attacking lattice-based cryptography.
What is the difference between LLL and BKZ? LLL is fast (polynomial time) but only mildly reduces a basis, with a quality that degrades exponentially as the dimension grows. BKZ is tunable through a block size parameter: turning that dial up yields shorter vectors at a steeply rising cost, and it is the algorithm strong enough to threaten a real scheme. LLL is BKZ with block size 2.
Who invented the LLL algorithm and when? Arjen Lenstra, Hendrik Lenstra, and László Lovász, in a 1982 paper on factoring polynomials with rational coefficients. It was a breakthrough because it reduced lattices in polynomial time, and its original uses were in number theory and integer programming rather than in attacking cryptography.
Does lattice reduction break ML-KEM or ML-DSA today? No. The block size BKZ would need to recover a secret from the standardized parameters costs far more than any feasible computation, which is exactly how those parameters were chosen. Reduction is the attack the security is measured against, and the schemes are set to sit well above what it can reach.
Is a quantum computer needed to run lattice reduction? No, it is a classical attack. Quantum computers add only a modest speedup to the sieving step inside BKZ, which the NIST parameters already account for. The serious open question for lattice crypto is whether classical reduction improves, not whether a quantum machine cracks it.
Why does so much depend on one family of algorithms? Because attacks on LWE and SIS almost always reduce to a lattice-reduction problem, BKZ is the shared engine underneath. That concentrates both the risk (a better algorithm weakens many schemes at once) and the scrutiny (this is among the most studied areas of cryptanalysis), which is why the standards keep margin and non-lattice backups exist.
Everything here is the map, given freely. When your team needs the lattice standards sized and stress-tested against the way they are actually attacked, that’s what an alignment briefing is for.
Last verified 2026-07-12 · Maintained by Addie LaMarr, LaMarr Labs.