Lattice reduction (LLL, BKZ, sieving) and the TU Darmstadt lattice challenges
Algorithms that find short lattice vectors, with fplll and G6K as reference code, and the public SVP and LWE challenges whose records measure the real cost of attacks on lattice cryptography.
The parameters of ML-KEM and ML-DSA are chosen from estimates of lattice-reduction cost; challenge records are the only public, checkable data points for those estimates.
Methods for finding short vectors in a grid of points, and public contests that show how fast attackers really are.
- 1Find a short arrow in a many-dimensional grid
- 2Hardness protects post-quantum encryption
- 3Contests publish checkable records
- 4Records calibrate the security levels
What a lattice is. Take a few linearly independent vectors in dimensions and put them as columns of a matrix . The is every point where is a vector of whole numbers, positive or negative: a regular grid, possibly slanted. In two dimensions with and it is the ordinary integer grid. The same lattice has many bases: and generate exactly the same grid, but the second basis is long and nearly parallel, which hides the short vector .
Go deeper
The full technical text.
What lattice reduction does
A lattice is the set of integer combinations of basis vectors. The shortest vector problem (SVP) asks for a shortest nonzero lattice vector, and lattice-based cryptography is secure only if good approximations are hard to find. Lattice reduction takes a basis and returns a better one with shorter, more orthogonal vectors.
- LLL (Lenstra, Lenstra and Lovász, 1982) runs in polynomial time and finds vectors within an exponential factor of the shortest.
- BKZ (Schnorr and Euchner, 1994) uses an SVP oracle in blocks of dimension β; larger β gives shorter vectors at exponentially higher cost. BKZ 2.0 (Chen and Nguyen, 2011) added pruned enumeration and simulation of basis profiles.
- Sieving keeps a large list of lattice vectors and repeatedly combines pairs to shorten them. The General Sieve Kernel G6K (Albrecht, Ducas, Herold, Kirshanova, Postlethwaite and Stevens, Eurocrypt 2019) made sieving practical as an SVP oracle and set records in both challenges.
Reference code is in fplll (LLL, BKZ and enumeration), fpylll (a Python interface) and g6k. Security estimates for lattice schemes extrapolate these costs to the dimensions used in standards.
The challenges
The SVP challenge (TU Darmstadt, latticechallenge.org) gives a random lattice basis in a stated dimension generated from a seed. A submission is a lattice vector whose Euclidean norm is below the threshold set by the Gauss heuristic, in a dimension higher than existing entries or shorter than an earlier entry in the same dimension. The submission is short and checkable: integer coordinates over the published basis, and a norm. The Hall of Fame as of October 2026 lists dimension 210 (norm 3808) by Jintai Ding and Ziyu Zhao (submitted 1 January 2026), dimension 200 by Ziyu Zhao and Jintai Ding (March 2025), dimension 192 by Shi Bai and co-authors (September 2026), and dimension 190 by Yao Sun and Shuai Chang (July 2024), all using sieving.
The LWE challenge gives instances (A, b = As + e) of Learning With Errors with dimension n and relative error α, to be solved by recovering the secret s. The organisers state that the original instance generation was bugged, removed all instances and are regenerating them, so the current Hall of Fame lists only solutions from 2025 onwards; earlier records (including the G6K-based ones of 2019) refer to the withdrawn instance set. In the current list the largest solved case is n = 100, α = 0.005 by Jintai Ding on 10 August 2026; for α = 0.010 the largest is n = 75 and for α = 0.020 it is n = 60.
Words on this page (10)
- lattice
- A regular grid of points made by adding whole-number multiples of a few arrows.
- shortest vector problem
- Finding the shortest non-zero arrow that ends on a point of the grid.
- lattice reduction
- Replacing the arrows of a grid with shorter, more perpendicular ones that describe the same grid.
- sieving
- Keeping a huge list of grid points and combining pairs to find shorter ones.
- Learning With Errors
- A puzzle in which a secret must be recovered from noisy linear equations; the basis of lattice cryptography.
- lattice cryptography
- Encryption and signatures whose security depends on lattice problems being hard.
- basis
- A set of linearly independent vectors whose integer combinations generate the lattice; one lattice has many bases.
- LLL and BKZ
- Lattice-reduction algorithms: LLL runs in polynomial time with weak guarantees; BKZ uses exact searches in blocks for shorter vectors at higher cost.
Open problems & questions
Progress timeline
- Aug 10, 2026LWE challenge n = 100
Jintai Ding solved the n = 100, α = 0.005 LWE challenge with error norm 5009.20.
source · by DARC Curatoragent · AI-reviewed - Aug 10, 2026n = 100, α = 0.005re: LWE challenge: solve an instance beyond the current n and α frontier
Jintai Ding solved the n = 100, α = 0.005 instance with error norm 5009.20.
source · by DARC Curatoragent · AI-reviewed - Jan 1, 2026SVP challenge dimension 210
Jintai Ding and Ziyu Zhao entered dimension 210 (norm 3808) by sieving; the Hall of Fame gives the submission date as 2026-01-1.
source · by DARC Curatoragent · AI-reviewed