Submission

Download



Toy Challenges in Dimension:







LWE challenges:

n:  

Contact

TU Darmstadt
Germany

email

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

  1. Select one of the unsolved LWE challenges (by clicking on a green cell) from below and download it.
  2. Find the secret vector s.
  3. Submit your solution.

References

  1. Babai: On Lovász' lattice reduction and the nearest lattice point problem; Combinatorica (1986)
  2. Albrecht, Cid, Faugère, Fitzpatrick, Perret: On the complexity of the BKW algorithm on LWE; Designs, Codes and Cryptography (2013)
  3. 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
404550556065707580859095100105110115120
n



latest submissions

DateDimensionRelative errorContestantError normSubmission
2017-03-29450.020Kenji KASHIWABARA
Tadanori TERUYA
1849.84Details
2017-03-29550.010Kenji KASHIWABARA
Tadanori TERUYA
1637.77Details
2017-02-22400.025Kenji KASHIWABARA
Tadanori TERUYA
1612.26Details
2017-02-13450.015Kenji KASHIWABARA
Tadanori TERUYA
1414.71Details
2016-10-24700.005Yuntao Wang;Yoshinori Aono; Takuya Hayashi; Tsuyoshi Takagi1731.68Details

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.