LWE challenge: solve an instance beyond the current n and α frontier
Difficulty 27: the frontier advanced by several steps in 2025–26 with known BKZ and sieving attacks, so the next instance is mainly compute; marginally harder than the SVP record (25) because primal attacks need larger blocksizes at small α. Application value 30: calibration of LWE cost models. Leverage 20: one instance family, and the instance set is still being regenerated.
The problem
Recover a hidden secret from noisy equations at a size larger than any solved before.
- 1Noisy equations hide a secret
- 2Embed in a lattice
- 3Reduce with BKZ and sieving
- 4Check that b − As is small
The puzzle. Pick a secret vector of whole numbers. Publish a random matrix and the vector , where "mod " means clock arithmetic that wraps round at , and is a vector of small random errors. Without you could recover by Gaussian elimination, exactly as in first-year linear algebra. With , elimination amplifies the errors until the answer is meaningless, and for large enough no efficient method is known. This is (LWE), the problem behind ML-KEM, ML-DSA and homomorphic encryption.
Path to understanding
foundations → problemThe research entries this problem rests on, in the order to read them. Each links to its explainer.
- Start with
- Step 2
- Step 3
- Linear programmingAlgorithm
- Quantum algorithmsAlgorithm
- Step 4
- Step 5
- Lattice-based cryptography (LWE)Algorithm
- Step 6
State of the art
The Hall of Fame (October 2026) lists, as the largest n per α: n = 100 at α = 0.005 (Jintai Ding, 10 August 2026, error norm 5009.20); n = 75 at α = 0.010 and n = 65 at α = 0.015 (Ding and Zhao, 19 September 2025); n = 60 at α = 0.020 and n = 55 at α = 0.025 (Ding, 21 July 2026); n = 50 at α = 0.030 (Bai, Chen, Ge, He, Li, Sun and Yu, 16 July 2026); n = 45 at α = 0.035 and 0.040; n = 40 at α = 0.045 and 0.050. The challenge page states that the original instance generation was bugged, that all instances were removed and that the protocol is being rerun, with some (grey) instances still to be added; earlier records, such as the G6K-based ones of Albrecht et al. (2019), refer to the withdrawn set.
Realistic applications
Challenge records calibrate the cost estimators that justify the parameters of ML-KEM, ML-DSA and homomorphic encryption schemes. Standard parameters are far outside the reach of current attacks.
What counts as solved
A solution accepted by the LWE challenge submission page for an instance beyond the current frontier at its α, with the algorithm, hardware and time reported.
How it gets verified
Bound / recordA numeric bound or record checked from a certificate or recomputation.
Quantity: the largest secret dimension n solved per relative error α; frontier n = 100 at α = 0.005 (Ding, 2026-08-10). A solution is the secret vector s of an instance published at latticechallenge.org; the check is that b − As reduces to an error vector of the expected small Gaussian norm modulo q, which the submission page performs. State instance, algorithm, hardware and wall time. The challenge page does not describe the verification procedure in detail, and its instance list is subject to regeneration.
Claims under verification
+ add a claimNo claimed results on the Verification board for this problem yet.
Where the work is
Attacks combine BKZ/sieving subroutines with careful parameter choices; resources decide the frontier.
Bottlenecks
ranked by votes- #1ComputeExponential cost in n at small α
Instances with larger n at small relative error need larger blocksizes for lattice reduction; cost grows exponentially.
Community grades
Sign in to add your own grade.
Connected problems
Progress
- Aug 10, 2026n = 100, α = 0.005source
Jintai Ding solved the n = 100, α = 0.005 instance with error norm 5009.20.