Lattice Sieving — AKS, Gauss Sieve, BDGL

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.

Beginner's Intuition 💡

Imagine trying to find the single shortest piece of spaghetti in an incredibly massive, tangled bowl. Instead of measuring every single piece one by one (which would take forever), Lattice Sieving takes a different approach.

It grabs handfuls of spaghetti, compares them to each other, snaps off the longer parts, and throws away the rest. It keeps combining and comparing the remaining pieces, "sieving" through the pile until only the absolute shortest piece is left. While this takes a massive amount of memory (you need a huge "bowl" to hold all the pieces you're comparing), it is currently the fastest known way to solve the Shortest Vector Problem, acting as the ultimate benchmark for lattice security.

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:

O (2^{c n})

time and space for some constant $c$ . While not practical (the constant is large and the algorithm is complex), it established that SVP is not intrinsically harder than $2^{n}$ .

The Gauss Sieve (2008)

Nguyen and Vidick's Gauss sieve made sieving practical. 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 $λ_{1} (Λ)$ .

The Gauss sieve runs in heuristic time and space $2^{0.415 n + o (n)}$ .

The 2-Sieve and ListSieve

Micciancio and Voulgaris (2010) introduced the 2-sieve with provable guarantees and the ListSieve. The key insight: sample $N = 2^{0.5 n}$ vectors uniformly from a ball of radius $R$ , then find all pairs within distance $R$ of each other:

v, w \in L, ∥ v - w ∥ \leq R ⟹ v - w is a candidate

Replace both $v$ and $w$ with $v - w$ if it is shorter. Repeat. The list converges to a shortest vector in $2^{0.415 n}$ time and space (provable bound).

The BDGL Sieve (2016)

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

T_{BDGL} = 2^{0.292 n + o (n)}, M_{BDGL} = 2^{0.208 n + o (n)}

The idea: instead of checking all $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:

⟨ v, w ⟩ > \frac{1}{2} ∥ v ∥∥ w ∥

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:

T_{quantum} = 2^{0.2653 n + o (n)}

This is why NIST post-quantum standards target $2^{128}$ classical security but also must account for this quantum speedup — requiring lattice dimensions large enough that even $2^{0.2653 n}$ exceeds $2^{128}$ .

Sieving in Practice

Sieving becomes practical in dimensions above roughly 70–80 (compared to enumeration, which dominates below that). Inside BKZ- $β$ with large $β$ , the local SVP oracle is solved by a sieve in the projected $β$ -dimensional sublattice. For $β \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 uniform random vectors $v, w$ from a ball of radius $R$ satisfy $∥ v - w ∥ \leq R$ with probability:

P [∥ v - w ∥ \leq R] = \frac{Vol ( B _{n} ( R ) \cap ( v + B _{n} ( R )))}{Vol ( B _{n} ( R ))} \approx 2^{- 0.4057 n}

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:

N = 2^{0.4057 n + o (n)}

Processing all $N^{2} /2$ pairs naively takes $2^{0.8114 n}$ time, but since each vector participates in roughly one productive pair, the total work is dominated by list maintenance:

T_{NV} = 2^{0.4057 n + o (n)}, q u a d M_{NV} = 2^{0.2075 n + o (n)}

where the memory bound uses the fact that the reduced list size after one pass is $2^{0.2075 n}$ vectors. This tighter analysis was given by Pujol–Stehlé (2009).

Tuple Sieving: k-Sieve for k > 2

Tuple sieves generalize pairwise sieving to combinations of $k$ vectors. The $k$ -sieve (Herold–Kirshanova, 2017; Ducas, 2018) finds tuples $(v_{1}, \dots, v_{k})$ such that $\sum_{i = 1}^{k} ϵ_{i} v_{i}$ is shorter than all $v_{i}$ , for signs $ϵ_{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:

T_{3 -sieve} = 2^{0.3689 n + o (n)}, q u a d M_{3 -sieve} = 2^{0.2075 n + o (n)}

At first glance the 3-sieve seems slower than BDGL (which achieves $2^{0.292 n}$ ). However, the 3-sieve uses the same memory as the 2-sieve. The correct comparison is at fixed memory: at memory $M = 2^{0.208 n}$ , the best 2-sieve time is $2^{0.292 n}$ (BDGL), while the 3-sieve at the same memory achieves a better time-memory trade-off curve for intermediate memory budgets.

Asymptotically, the optimal $k$ -sieve for $k \to \infty$ would achieve time $2^{0.2075 n}$ — matching the memory lower bound — but 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.

For the BDGL sieve with a memory budget of $M = 2^{α n}$ vectors (where $0 < α \leq 0.208$ ), the time complexity scales as:

T (α) = 2^{(0.292 - α + ϵ) n + o (n)}

At the extremes: with full memory $α = 0.208$ one achieves $T = 2^{0.292 n}$ (BDGL optimum). With memory $α \to 0$ (streaming sieve, essentially no database), time degrades toward $2^{c n}$ with large constant $c$ .

The low-memory sieve of Bai–Miller–Nguyen (2023) achieves:

T = 2^{0.2972 n}, q u a d M = 2^{0.1486 n}

halving the memory exponent at the cost of a modest time increase. For large-scale attacks on NIST schemes (which require dimensions ~500–1000), the memory required by BDGL would be $2^{100}$ + entries — far beyond any classical hardware. The low-memory variants are therefore more practically relevant for hardware-constrained adversaries.

NIST security categories account for both time and memory requirements by requiring attacks to cost at least $2^{128}$ in both metrics simultaneously — ensuring that no time–memory trade-off brings a scheme within reach of a realistic adversary.