LATTICE CHALLENGE
Updated 30 days ago
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.