4.3 Lattice Sieving

Sieving algorithms solve the Shortest Vector Problem (SVP) by maintaining a large list of lattice vectors and repeatedly combining pairs (or tuples) to produce shorter ones. Starting from an exponentially large random sample of lattice vectors, sieving distills them down to a list containing a shortest vector.

Sieving currently achieves the best known asymptotic complexity for SVP — single-exponential in dimension — and is the algorithm of choice inside BKZ for solving the local SVP oracle. The cost of sieving directly determines the security level of deployed lattice schemes.

The AKS Sieve (2001)

Ajtai, Kumar, and Sivakumar proved in 2001 that SVP can be solved in single-exponential time and space — the first such algorithm. The AKS sieve runs in:

time and space for some constant $c$. While not practical (the constant is large and the algorithm is complex), it established that SVP can be solved in single-exponential time $2^{O(n)}$, beating the $2^{O(n \log n)}$ of enumeration.

The Gauss Sieve (2010)

Nguyen and Vidick’s 2008 sieve was the first practical heuristic sieve; Micciancio and Voulgaris’s Gauss sieve (2010) made sieving much faster in practice. It maintains a list $L$ of vectors and repeatedly reduces pairs:

For vectors $v, w \in L$, if $\|v - w\| < \|v\|$ or $\|v + w\| < \|v\|$, replace $v$ with the shorter combination. Continue until no further reductions are possible. The result is a Gauss-reduced list whose shortest element approximates $\lambda_1(\Lambda)$.

The Gauss sieve is conjectured to run in heuristic time $2^{0.415n + o(n)}$ with a list of about $2^{0.2075n + o(n)}$ vectors.

The 2-Sieve and ListSieve

Alongside the Gauss sieve, Micciancio and Voulgaris (2010) introduced ListSieve, a variant with provable guarantees but much larger exponents (roughly $2^{3.2n}$ time). The heuristic 2-sieve idea, from Nguyen–Vidick: sample about $N = 2^{0.2075n}$ lattice vectors of length around $R$, then find all pairs within distance $R$ of each other:

Replace both $v$ and $w$ with $v - w$ if it is shorter. Repeat. Heuristically, the list converges to a shortest vector in $2^{0.415n}$ time and $2^{0.2075n}$ space.

The BDGL Sieve (2016)

Becker, Ducas, Gama, and Laarhoven’s 2016 sieve reduced the exponent to approximately $0.292n$ using angular locality-sensitive hashing (LSH). This is currently the best known classical algorithm:

The idea: instead of checking all $\mathcal{O}(N^2)$ pairs in the list, use LSH to quickly find pairs of vectors with small angle (equivalently, vectors where their sum or difference is short). Two vectors $v, w$ produce a short combination when:

i.e., the angle between them is less than $60°$. LSH partitions the unit sphere into caps; vectors in the same cap are likely to have a small angle and thus form a productive pair.

Quantum Sieving

The BDGL sieve can be quantized using Grover’s algorithm to speed up the pair-finding step. The quantum variant achieves:

This is why post-quantum parameters must account for this quantum speedup as well as classical sieving — the block size an attack needs has to be large enough that even $2^{0.2653\beta}$ stays out of reach.

Sieving in Practice

Sieving becomes practical in dimensions above roughly 70–80 (compared to enumeration, which dominates below that). Inside BKZ-$\beta$ with large $\beta$, the local SVP oracle is solved by a sieve in the projected $\beta$-dimensional sublattice. For $\beta \geq 80$, sieving is faster than pruned enumeration.

The g6k library (see next section) provides a production-quality implementation of these sieves and is the tool of choice for lattice challenges and security analysis.

The Nguyen–Vidick Sieve: Precise Complexity

The Nguyen–Vidick (NV) sieve (2008) was the first practically efficient sieve with a clean heuristic analysis. Given a list of $N$ lattice vectors sampled uniformly from a ball of radius $R$, the sieve finds all pairs $(v, w)$ such that $\|v - w\| \leq R$ and replaces them. The list converges when no more reductions are possible.

The heuristic analysis proceeds by counting the expected number of pairs. In dimension $n$, two vectors $v, w$ of length about $R$ satisfy $\|v-w\| \leq R$ exactly when their angle is at most 60°, which for random directions happens with probability:

To ensure each output vector has expected one productive partner — so the list self-reduces — we need $N \cdot P \approx 1$, giving list size:

Checking all $N^2 / 2$ pairs naively then dominates the running time:

Later sieves keep the same list size and attack the quadratic pair search, which is exactly what BDGL’s locality-sensitive hashing does.

Tuple Sieving: k-Sieve for k > 2

Tuple sieves generalize pairwise sieving to combinations of $k$ vectors. The $k$-sieve (Bai–Laarhoven–Stehlé, 2016; Herold–Kirshanova, 2017) finds tuples $(v_1, \dots, v_k)$ such that $\sum_{i=1}^k \epsilon_i v_i$ is shorter than all $v_i$, for signs $\epsilon_i \in \{\pm 1\}$.

The key improvement: a $k$-tuple reduces vectors that no 2-subset can reduce. The 3-sieve (implemented in g6k) achieves heuristic complexity:

The 3-sieve is slower than BDGL (which achieves $2^{0.292n}$). Its advantage is memory: a list of $2^{0.1887n}$ vectors instead of $2^{0.2075n}$. When memory rather than time is the bottleneck, trading extra time for a smaller list is worthwhile, which is why g6k ships a triple sieve.

Larger $k$ lowers the memory exponent further but raises the time, and the combinatorial cost of managing $k$-tuples grows rapidly, making $k = 3$ the practical sweet spot.

Time–Memory Trade-offs in Sieving

Sieving algorithms exhibit a fundamental time–memory trade-off: using less memory forces more computation, and vice versa. This trade-off is critical for security analysis because an adversary with a large memory budget can sieve faster.

At the extremes: with a full list of about $2^{0.208n}$ vectors, BDGL achieves $T = 2^{0.292n}$. Going below that list size means switching to tuple sieves or other low-memory variants, and the time exponent rises as the memory exponent falls; at the far end, polynomial-memory enumeration pays super-exponential time.

For attacks on NIST schemes (sieving block sizes of roughly 400 and above), BDGL’s list would hold $2^{80}$ or more vectors — far beyond any classical hardware. Memory-reducing variants are therefore more practically relevant for hardware-constrained adversaries, and cost estimates that ignore memory (such as Core-SVP) err on the conservative side.