introduction
Welcome to the lattice challenge.
Building upon a popular paper by Ajtai [1], we have constructed lattice bases for which the solution of SVP implies a solution of SVP in all lattices of a certain smaller dimension. This does not mean that one can solve all instances simultaneously, but rather that one can solve even the worst case instances. We think these lattice bases are hard instances and most fitting to test and compare modern lattice reduction algorithms.
We show how these lattice bases were constructed and prove the existence of short vectors in each of the corresponding lattices in [2]. We challenge everyone to try whatever means to find a short vector. There are two ways to enter the hall of fame:
- Tackle a challenge dimension that nobody succeeded in before;
- Find an even shorter vector in one of the dimensions listed in the hall of fame.
References
- Ajtai: Generating Hard Instances of Lattice Problems, STOC 1996
- Buchmann, Lindner, Rückert: Explicit Hard Instances of the Shortest Vector Problem, PQCrypto 2008
hall of fame
| Position | Dimension | Euclidean norm | Contestant | Submission |
|---|---|---|---|---|
| 1 | 1100 | 175.40 | Yao Sun | Details |
| 2 | 1050 | 165.68 | Yao Sun | Details |
| 3 | 1025 | 149.71 | Xiaohan Zhang Renjie Jin Zijian Zhou Longjiang Qu Chao Li | Details |
| 4 | 1000 | 155.21 | Yao Sun | Details |
| 5 | 975 | 144.55 | Yao Sun | Details |
The hall of fame lists the five highest dimensions, in which at least one contestant ever succeeded, along with the best solution in each of them. Toy challenges are excluded from the list. Here is the full list.
participate
What you need to do to participate
- Download a lattice challenge of a suitable dimension m
- Find a lattice vector with Euclidean norm less than n
- Submit your solution vector to us by using submission form