Lattice Sieving and Enumeration
Lattice sieving and enumeration are the two engine-room subroutines that lattice attacks ultimately run on. When a primal or dual attack hands its lattice to BKZ, BKZ chops the problem into small blocks and, for each block, has to solve a shortest-vector problem exactly. There are two known families of algorithms for that inner job. Enumeration walks a search tree using almost no memory but a punishing amount of time. Sieving keeps an enormous pool of vectors in memory and combines them to find shorter ones, which is asymptotically the faster approach and the one behind the modern speed records, at the cost of storage that grows exponentially with the dimension. That memory cost is the reason the picture is more subtle than “sieving wins,” and it is a live question in how conservatively the standards should be priced.
Source: Anja Becker, Léo Ducas, Nicolas Gama & Thijs Laarhoven, “New directions in nearest neighbor searching with applications to lattice sieving,” SODA 2016, ePrint 2015/1128.
The short version:
- They are the two ways to solve the shortest-vector problem exactly. BKZ calls one of them on every block, so the cost of a lattice attack is really the cost of this inner solver at the required block size.
- Enumeration uses tiny memory but superexponential time. It searches a tree of candidate vectors, needs only polynomial memory, and its running time grows faster than any single exponential, so it is the low-storage, high-time option.
- Sieving uses exponential time and exponential memory. It holds a huge list of lattice vectors and repeatedly combines pairs into shorter ones. The best known heuristic sieve solves the shortest-vector problem in time about
2^(0.292n), which is asymptotically faster than enumeration. - The memory is the catch. Sieving’s storage grows exponentially too, roughly
2^(0.208n), and at cryptographic dimensions that quickly reaches astronomical sizes, which is why memory cost matters for real-world security estimates. - Both feed Core-SVP. The security number a standard quotes depends on which SVP-solver you assume and whether you charge for its memory.
Picture BKZ as a manager that keeps asking the same small question over and over: given this block of the lattice, what is the shortest vector in it? Two workers can answer. Enumeration is a meticulous searcher who tries candidate directions one at a time down a branching tree, carrying almost nothing in hand but taking an enormous number of steps as the block grows. Sieving is a hoarder who fills a vast warehouse with lattice vectors and keeps subtracting them from each other to breed shorter ones, reaching the answer in fewer effective steps but needing a warehouse whose size explodes as the dimension climbs. Both return the shortest vector. Which one is cheaper depends on the dimension and, crucially, on whether you count the cost of the warehouse.
What is lattice enumeration?
Lattice enumeration is an exhaustive tree search for the shortest vector that runs in polynomial memory. It systematically walks through candidate lattice vectors whose length falls under a bound, organizing the search as a tree where each level fixes one more coordinate, and it prunes branches that cannot lead to a short enough vector. Because it only ever holds the current path through the tree rather than a large collection of vectors, its memory footprint stays small, growing merely polynomially with the dimension. That frugality with storage is enumeration’s defining virtue and the reason it stayed the practical method of choice for a long time.
Source: Wikipedia, “Lattice problem,” section on algorithms for the shortest vector problem, “these algorithms take superexponential time but only polynomial space,” Wikipedia.
The price enumeration pays for its light memory is time. Its running time grows superexponentially with the dimension, which means it climbs faster than any fixed exponential base, so doubling the block size does far worse than squaring the work. Techniques like discrete pruning and extreme pruning cut the constant factors substantially and kept enumeration competitive well into the modern era, but they do not change the superexponential shape of the curve. For the block sizes that matter in attacking cryptographic parameters, that shape is what eventually makes enumeration lose to the other family.
What is lattice sieving?
Lattice sieving finds the shortest vector by maintaining a massive list of lattice vectors and repeatedly combining them into shorter ones. You start with a large collection of vectors in the lattice, then look for pairs whose difference is shorter than either original, add those differences back into the pool, and repeat. Over many rounds the pool fills with shorter and shorter vectors until the true shortest vector emerges. The number of vectors you have to keep for the process to work is itself exponential in the dimension, which is where the memory cost comes from, but the payoff is that sieving reaches the answer in asymptotically fewer operations than enumeration.
Source: Anja Becker, Léo Ducas, Nicolas Gama & Thijs Laarhoven, “New directions in nearest neighbor searching with applications to lattice sieving,” SODA 2016, ePrint 2015/1128.
The fastest known heuristic sieve is the BDGL algorithm, named for Becker, Ducas, Gama, and Laarhoven, which uses a nearest-neighbor-search trick to find combinable pairs quickly. It solves the shortest-vector problem in heuristic time roughly 2^(0.292n) in dimension n, improving on the previous 2^(0.298n) sieves. Both its time and its memory are single-exponential, which puts sieving in a strictly better asymptotic time class than enumeration’s superexponential curve. This is the algorithm that most current security estimates assume when they price the strongest available attack, because if a defender is going to plan against the best cryptanalysis, sieving is it.
Source: Anja Becker, Léo Ducas, Nicolas Gama & Thijs Laarhoven, “New directions in nearest neighbor searching with applications to lattice sieving,” SODA 2016, ePrint 2015/1128.
Why does sieving memory cost matter for real security?
Sieving’s memory cost matters because an attack you cannot physically store is not an attack you can run, so charging for that memory changes the security number. The best sieve needs on the order of 2^(0.208n) vectors held in memory at once, and at the dimensions relevant to cryptographic parameters that count runs past the number of atoms available to build storage out of. An adversary who genuinely has to keep that pool in real hardware faces a wall that the pure time count hides, and moving all those vectors around memory adds its own cost that a naive “operations only” estimate ignores.
Source: Anja Becker, Léo Ducas, Nicolas Gama & Thijs Laarhoven, “New directions in nearest neighbor searching with applications to lattice sieving,” SODA 2016, ePrint 2015/1128.
This is where the two families create a genuine estimation dilemma. Enumeration is asymptotically slower but almost free on memory, so it can be run to completion on modest hardware. Sieving is asymptotically faster but demands a memory pool that may be unbuildable at the block sizes where it would win. A conservative security estimate refuses to give the attacker free memory and prices the sieve realistically, which raises the security number; an aggressive estimate assumes the attacker can store anything and counts only operations, which lowers it. NIST’s approach and the Core-SVP convention deliberately lean conservative on this question, and the exact right way to charge for sieve memory is one of the open debates that keeps the standardized parameters carrying margin.
How do sieving and enumeration compare in practice?
In practice the two families crossed over about a decade ago, and sieving now wins at the dimensions attacks care about, provided you grant it the memory. For years enumeration was faster in the block sizes people could actually run, so it was the method behind most records. The arrival of fast heuristic sieves changed that: modern sieving implementations overtake state-of-the-art enumeration once the dimension climbs past the low seventies, so for the large block sizes involved in attacking cryptographic parameters, sieving is the faster engine.
Source: Martin R. Albrecht, Léo Ducas, Gottfried Herold, Elena Kirshanova, Eamonn W. Postlethwaite & Marc Stevens, “The General Sieve Kernel and New Records in Lattice Reduction,” Eurocrypt 2019, “we observe a performance crossover between G6K and FPLLL’s state of the art implementation of enumeration at dimension 70,” ePrint 2019/089.
| Property | Enumeration | Sieving |
|---|---|---|
| Time | Superexponential, 2^(ω(n)) | Single-exponential, about 2^(0.292n) |
| Memory | Polynomial in dimension | Exponential, about 2^(0.208n) |
| Asymptotically faster? | No | Yes |
| Practical crossover | Wins at small block sizes | Wins past dimension ~70 |
| Best-known example | Extreme / discrete pruning | BDGL nearest-neighbor sieve |
The practical upshot for anyone reading a security estimate is that the headline number quietly depends on two modeling choices: which SVP-solver you assume, and whether you charge the sieve for its memory. Assume a memory-unlimited attacker running the best sieve and you get the lowest, most conservative-to-quote security number. Charge realistically for that memory and the number rises. Both flavors of estimate appear in the literature, which is why two analyses of the same scheme can report slightly different security levels without either being wrong.
Common misconceptions
- “Lattice attacks just run one big algorithm.” They run BKZ, which itself calls a shortest-vector solver on each block, and that inner solver is either enumeration or sieving. The cost of the whole attack is really the cost of this inner subroutine at the required block size.
- “Sieving is simply the better algorithm.” Sieving is asymptotically faster, but it needs exponential memory that may be unbuildable at the dimensions where it would win. Enumeration is slower yet runs in tiny memory, so which one is cheaper depends on the block size and on whether memory is charged.
- “Time is the only thing that determines an attack’s cost.” For sieving, memory is a first-class cost. A pool of
2^(0.208n)vectors can exceed any storage that could physically be built, so ignoring memory understates the real difficulty of the attack. - “The security estimate is a single fixed number.” It depends on which SVP-solver you assume and how you price the sieve’s memory. Conservative and aggressive models give different numbers, which is why two honest analyses of the same parameters can differ.
- “Enumeration is obsolete.” Enumeration still wins at small block sizes and remains the low-memory option, so it stays part of the picture and part of any careful comparison, even though sieving drives the modern records.
Questions people ask
What is the difference between lattice sieving and enumeration?
They are the two families of algorithms that solve the shortest-vector problem inside BKZ. Enumeration searches a tree using polynomial memory but superexponential time. Sieving keeps an exponentially large pool of vectors and combines them, which is asymptotically faster, running in heuristic time about 2^(0.292n), at the cost of exponential memory.
Why does sieving need so much memory?
Sieving works by repeatedly combining pairs of lattice vectors into shorter ones, and it has to keep enough vectors on hand for those combinations to keep producing shorter results. The size of that pool grows exponentially with the dimension, on the order of 2^(0.208n), which is what makes memory a defining cost of the method.
Is sieving always faster than enumeration? Asymptotically yes, and in practice modern sieves overtake enumeration once the dimension passes the low seventies, which covers the block sizes that matter for attacking cryptographic parameters. Enumeration still wins at small block sizes and uses far less memory, so it is not gone from the comparison.
Why does the memory cost affect security estimates? Because an attack that needs more storage than can be physically built is not really runnable at that cost. A conservative estimate charges the sieve for its memory and reports a higher security number, while an aggressive estimate assumes unlimited memory and counts only operations. NIST and the Core-SVP convention lean conservative on this.
What is the BDGL sieve?
It is the fastest known heuristic sieve, named for Becker, Ducas, Gama, and Laarhoven, which uses a nearest-neighbor-search technique to find combinable vector pairs quickly. It solves the shortest-vector problem in heuristic time about 2^(0.292n), and it is the algorithm most current security estimates assume when pricing the strongest available lattice attack.
Do I need to understand these to migrate to the standards? No. The migration work is inventory, sizing, and testing, and the lattice arithmetic lives inside the libraries you integrate. Understanding sieving and enumeration explains why the lattice security numbers carry margin and why two analyses of the same scheme can report slightly different security levels.
Everything here is the map, given freely. When your team needs the lattice standards sized, sequenced, and hedged across your own estate, that’s what an alignment briefing is for.
Last verified 2026-07-12 · Maintained by Addie LaMarr, LaMarr Labs.