4.4 g6k

g6k (General Sieve Kernel) is a software library and algorithmic framework for lattice sieving, introduced by Albrecht, Ducas, Herold, Kirshanova, Postlethwaite, and Stevens in 2019. It provides a unified interface over multiple sieve variants, integrates them tightly with BKZ, and has been used to set world records on lattice challenges including the TU Darmstadt SVP Challenge.

g6k is not just an implementation — it introduces the concept of a pump, a principled way to combine sieving with BKZ that achieves better quality than either alone.

The Sieve Kernel

At its core, g6k maintains a database (the sieve list) of lattice vectors represented in terms of the current basis. The database can be filtered, extended, compressed, and projected. Three operations on this database are the primitives of the framework:

extend_left / extend_right: extend the coordinate range of vectors in the database, bringing in a new basis vector. This grows the effective dimension of the sieve.

shrink_left: project out the leftmost coordinate. This reduces dimension and recenters the sieve.

sieve: run one iteration of a sieve (Gauss sieve or 3-sieve) on the current database, reducing all pairwise reducible pairs.

The Pump

The pump is g6k’s central abstraction. Given a BKZ index $\kappa$, a block size $b$ and a number $f$ of “dimensions for free” (Ducas, 2018), a pump works on the block starting at $\kappa$:

1. Pump up: starts from a small sieve context at the right end of the block and repeatedly extends it one dimension to the left, sieving after each extension. This is progressive sieving in increasing dimension, up to dimension $b - f$ in the projected sublattice.

2. Lifts the short projected vectors through the $f$ remaining dimensions (Babai-style), so the sieve never has to run in the full dimension $b$.

3. Pump down: shrinks the context from the left again, at each step inserting the best lifted vector back into the BKZ basis (optionally sieving again as it goes).

The pump gets close to the quality of an SVP call in dimension $b$ for the cost of sieving in dimension $b - f$, and the parameters allow fine-grained trade-offs between time and output quality.

Progressive Sieving

Rather than solving SVP from scratch for each BKZ call, g6k uses a progressive strategy: the sieve database is maintained across BKZ tours and updated incrementally. When the basis changes, only a small fraction of the database becomes invalid. This amortizes the cost of sieve initialization across many BKZ iterations, achieving a dramatic practical speedup.

The 3-Sieve

g6k implements the 3-sieve (triple sieve), which combines triples of vectors rather than pairs. For three vectors $u, v, w$, if:

then replace the longest of the three with the short combination. The 3-sieve achieves a better length reduction per step than the 2-sieve and is especially effective in high dimensions.

Dual Sieving and MATZOV

g6k can also work on the dual lattice $\Lambda^*$, and a sieve database is a natural source of the many short dual vectors a dual attack on LWE needs. Separately, the MATZOV report (2022) presented an improved dual attack with its own cost model — not built on g6k — that lowered the estimates for Kyber somewhat.

It prompted debate about the attack’s heuristics (Ducas–Pulles, 2023, questioned them), but ML-KEM’s parameter sets were not changed as a result.

Records and Impact

Using g6k, the authors solved Darmstadt SVP challenges up to dimension 155 on CPUs (2019). The GPU version by Ducas, Stevens and van Woerden (2021) pushed this to dimension 180, a record that was far out of reach for enumeration.

For developers implementing lattice cryptography, g6k defines the state of the art for what an adversary can do. Security margins in NIST standards implicitly assume an adversary running g6k or a future improvement on it.

Installation and Interface

g6k is a Python library with a C++ kernel. The C++ layer (the sieve itself) is written for performance; the Python layer exposes a high-level API for composing algorithms. Installation requires a C++14 compiler, FPLLL, and a few Python dependencies:

# dependencies: fplll, fpylll, cython
git clone https://github.com/fplll/g6k
cd g6k
pip install -r requirements.txt
python setup.py build_ext --inplace

The primary objects are the Siever (the sieve kernel) and the SieverParams configuration. A Siever is initialized from an FPLLL IntegerMatrix and wraps it with the g6k coordinate system.

The Key API: Siever and Pump

The two core abstractions in g6k are the siever object and the pump function. The siever holds the basis and the sieve database. The pump is the high-level BKZ-replacement that drives reduction.

The siever exposes the basis through a context manager that tracks which coordinate range $[\ell, r)$ is currently active. Sieving always operates on the projected sublattice $\pi_\ell(b_\ell, \dots, b_{r-1})$. The extend_left and shrink_left operations move $\ell$; extend_right moves $r$.

Pseudocode for running a pump at index $\kappa$ with dimensions-for-free parameter $f$ and block size $b$:

from g6k import Siever
from g6k.algorithms import pump
from g6k.utils.stats import dummy_tracer

# load a basis (e.g. from a lattice challenge)
from fpylll import IntegerMatrix, LLL
A = IntegerMatrix.random(120, "qary", k=60, bits=30)
LLL.reduction(A)

# create siever
g6k = Siever(A)

# run a pump at index kappa=0, block b=40, f=10 dimensions for free
# this is roughly equivalent to one BKZ-40 SVP call
kappa, b, f = 0, 40, 10
pump(g6k, dummy_tracer, kappa, b, f)

# retrieve the shortest vector found so far
db = list(g6k.itervalues())
shortest = min(db, key=lambda v: sum(x**2 for x in v))

The pump function internally calls g6k.extend_left() repeatedly (the pump-up phase, growing the context to dimension $b - f$), then calls g6k.shrink_left() repeatedly (the pump-down phase, inserting short vectors into the basis). Each extend_left is followed by a g6k.sieve() call to reduce the newly expanded database.

For attacking a lattice challenge (e.g. TU Darmstadt SVP Challenge dimension 100), the full pipeline is:

from g6k.algorithms import bkz_tours

# run 4 tours of BKZ-45 with g6k's pump as the SVP oracle
# params control sieve aggressiveness and database size
bkz_tours(g6k, tracer, 45, num_tours=4,
          pump_params={"down_sieve": True})

The tracer object records statistics (number of SVP calls, sieve iterations, wall time) and can produce a Gram–Schmidt profile plot. The down_sieve flag enables sieving during the pump-down phase as well; the pump-up phase always sieves progressively.

For a full lattice challenge workflow including basis loading, progressive BKZ, and solution verification, g6k ships the script svp_challenge.py which automates the end-to-end pipeline.

g6k-rs: Rust Implementation

g6k-rs is a Rust library for lattice reduction, enumeration and sieving, inspired by the problem space of the General Sieve Kernel. It is a research preview, not an official port or drop-in replacement for G6K, and it has not been audited. It covers:

• Lattice reduction: LLL, deep-insertion LLL, BKZ with enumeration or sieve SVP oracles, slide and self-dual reduction
• Sieving: BDGL, BGJ1 and HK3-style sieves, with multi-threaded paths and experimental Metal and CUDA backends
• CVP and enumeration: Babai nearest plane and rounding, exact and pruned Schnorr–Euchner enumeration
• Arbitrary precision: GMP-backed bases and reducers that keep the determinant exact
• Invariant checks: determinant preservation, integrality and LLL-reducedness can be verified independently

use g6k_rs::{LatticeBasis, bkz, lll};

fn main() {
    // Rows are basis vectors: a 4-dimensional lattice with determinant 757.
    let mut basis = LatticeBasis::from_integers(&[
        vec![1, 0, 0, 201],
        vec![0, 1, 0, 173],
        vec![0, 0, 1, 419],
        vec![0, 0, 0, 757],
    ]);

    let _ = lll(&mut basis);
    println!("after LLL:   ||b0|| = {:.2}", basis.norm_sq(0).sqrt());

    let _ = bkz(&mut basis, 4); // block size = full dimension: an exact SVP solve
    println!("after BKZ-4: ||b0|| = {:.2}", basis.norm_sq(0).sqrt());
    println!("b0 = {:?}", basis.basis[0]);
}

The example prints a shortest vector of length 4.69 for this lattice. For tested, copy-paste programs covering installation, progressive BKZ, sieve-backed BKZ, exact big-integer reduction, CVP and enumeration, see the g6k-rs recipes. The crate is on crates.io as g6k-rs, licensed under MIT or Apache-2.0, with source at github.com/ovasylenko/g6k-rs.