INFORMATION
Unfortunately, the creation of the LWE instances was bugged and resulted in unbreakable challenges. We removed all challenges from the web page and are currently rerunning the protocol to create new instances. The available instances are already updated, the missing (grey) instances will be added soon. Sorry for any inconveniences.
introduction
Welcome to the Learning With Errors (LWE) challenge.
The LWE problem is to recover s, given an instance (A, b), where A is an m×n matrix over ℤq and b = As + e is a vector of length m over ℤq. Both the matrix A and the target vector s are sampled uniformly random, while the error vector e is sampled from the Gaussian distribution with parameter σ.
This page presents sample instances for testing algorithms that solve the LWE problem. The main goal of this challenge is to help assessing the hardness of the LWE problem in practice. Furthermore, it is designed to provide a comparison of different types of LWE solvers, like Babai's Nearest Plane [1], BKW [2], or reduction to the Shortest Vector Problem [3].
Since current results seem to imply that the hardness of LWE instances mainly depends on the "relative error size" α = σ / q and the dimension n, this page provides LWE instances for a wide range of α and n. All challenges were created using a multi-party computation protocol executed by the Eindhoven University of Technology, the University of California, San Diego and the Technische Universität Darmstadt. The protocol ensures that none of the participating parties has additional information about the solutions.
How to participate
- Select one of the unsolved LWE challenges (by clicking on a green cell) from below and download it.
- Find the secret vector s.
- Submit your solution.
References
- Babai: On Lovász' lattice reduction and the nearest lattice point problem; Combinatorica (1986)
- Albrecht, Cid, Faugère, Fitzpatrick, Perret: On the complexity of the BKW algorithm on LWE; Designs, Codes and Cryptography (2013)
- Albrecht, Fitzpatrick, Göpfert: On the efficacy of solving LWE by reduction to unique-SVP; ICISC (2013)
challenge table
Here is an overview of all challenges. By clicking on an a green cell (representing an unsolved challenge), you can either download the instance or go directly to the submission page to submit a solution. Clicking on a red cell (representing a solved instance), on the other hand, allows to either download the instance or see details of the submission. Cells in grey are still under generation and will be updated, once they are generated by the participating parties.
| α | ||||||||||||||||||
| 0.070 | ||||||||||||||||||
| 0.065 | ||||||||||||||||||
| 0.060 | ||||||||||||||||||
| 0.055 | ||||||||||||||||||
| 0.050 | ||||||||||||||||||
| 0.045 | ||||||||||||||||||
| 0.040 | ||||||||||||||||||
| 0.035 | ||||||||||||||||||
| 0.030 | ||||||||||||||||||
| 0.025 | ||||||||||||||||||
| 0.020 | ||||||||||||||||||
| 0.015 | ||||||||||||||||||
| 0.010 | ||||||||||||||||||
| 0.005 | ||||||||||||||||||
| 40 | 45 | 50 | 55 | 60 | 65 | 70 | 75 | 80 | 85 | 90 | 95 | 100 | 105 | 110 | 115 | 120 | ||
| n | ||||||||||||||||||
latest submissions
| Date | Dimension | Relative error | Contestant | Error norm | Submission |
|---|---|---|---|---|---|
| 2022-10-15 | 40 | 0.040 | Leizhang Wang Wenwen Xia Yuntao Wang Baocang Wang Geng Wang Dawu Gu | 2646.77 | Details |
| 2022-07-10 | 50 | 0.025 | Wang Leizhang Xia Wenwen Wang Geng Gu Dawu Wang Baocang | 3187.98 | Details |
| 2022-07-06 | 55 | 0.020 | Wang Leizhang Xia Wenwen Wang Geng Gu Dawu Wang Baocang | 3285.06 | Details |
| 2022-06-12 | 90 | 0.005 | Xia Wenwen Wang Leizhang Wang Geng Gu Dawu Wang Baocang | 3689.52 | Details |
| 2022-06-02 | 45 | 0.030 | L. Ducas E. Postlethwaite M. Stevens W. van Woerden | 2754.02 | Details |
Only the five latest successful submissions are shown here. The full hall of fame can be found here. Toy challenges are excluded from both lists.