Abstract:
The most famous lattice problem is the Shortest Vector
Problem (SVP),
which has many applications in cryptology.
The best approximation algorithms known for SVP in high dimension
rely on a subroutine for exact SVP in low dimension.
In this paper,
we assess the practicality of the best (theoretical) algorithm
known for exact SVP in low dimension:
the sieve algorithm proposed by Ajtai, Kumar and Sivakumar (AKS)
in 2001. AKS is a randomized algorithm of time and space complexity
$2^{O(n)}$,
which is theoretically much lower than the super-exponential
complexity of all alternative SVP algorithms.
Surprisingly, no implementation and no practical analysis of AKS has
ever been reported.
It was in fact widely believed that AKS was impractical:
for instance, Schnorr claimed in 2003 that the constant hidden in
the $2^{O(n)}$ complexity was at least 30.
In this paper, we show that AKS can actually be made practical:
we present a heuristic variant of AKS whose running time is $(4/3+
\eps)^{n}$ polynomial-time operations,
and whose space requirement is $(4/3+\eps)^{n/2}$ polynomially
many bits.
Our implementation can experimentally find shortest lattice vectors
up to dimension 50,
but is slower than classical alternative SVP algorithms in these
dimensions.
Bibtex:
@article{NgVi08,
title={Sieve Algorithms for the Shortest Vector Problem are Practical},
author={P. Q. Nguyen and T. Vidick},
journal={J. of Mathematical Cryptology},
volume=2,
number=2,
year=2008
}