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 SVPChallenge.

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 main contribution. Given a BKZ index $\kappa$ and parameters $f$ (down) and $b$ (block size), a pump:

1. Pumps down: extends the sieve database from dimension $1$ to dimension $f$, inserting vectors one by one and sieving after each insertion. This produces a rich database in dimension $f$.

2. Runs the sieve in the full local dimension to find short vectors in the projected sublattice ${\pi }_{\kappa }$.

3. Pumps up: shrinks the database back, lifting the short projected vector to a full-dimensional lattice vector and inserting it into the BKZ basis.

The pump achieves the same reduction quality as BKZ-$b$ with a local SVP oracle, but the cost is parameterized continuously by $f$ — allowing 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 also implements dual sieving — sieving in the dual lattice ${\Lambda }^{\ast }$ to attack LWE in the dual domain. The MATZOV report (2022) used a dual attack based on g6k to reassess the security of Kyber, demonstrating that hybrid attacks combining lattice reduction with meet-in-the-middle can reduce security margins.

This led the NIST standardization process to re-examine parameters and informed the final parameter sets in ML-KEM (Kyber).

Records and Impact

Using g6k, the authors solved SVP challenges in dimensions 150–180 that were previously out of reach. The key record: dimension-180 SVP solved in approximately $2^{90}$ operations, consistent with the BDGL complexity formula.

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 thepump 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 down-parameter $f$ and block size $b$:

from g6k import Siever
from g6k.algorithms import pump

# 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, down parameter f=10, block b=40
# this is roughly equivalent to one BKZ-40 SVP call
kappa, b, f = 0, 40, 10
pump(g6k, 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 "down" phase, building up the database from dimension 1 to $f$), then runs the sieve, then calls g6k.shrink_left() (the "up" phase, projecting back). Eachextend_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 down phase rather than only at the bottom — the progressive strategy that amortizes sieve costs across tours.

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.