Improving on the Voronoi cell based techniques of [28, 24] , we give a Las Vegas O(2 n ) expected time and space algorithm for CVPP (the preprocessing version of the Closest Vector Problem, CVP). This improves on the O(4 n ) deterministic runtime of the Micciancio Voulgaris algorithm [24] (henceforth MV) for CVPP 1 at the cost of a polynomial amount of randomness (which only affects runtime, not correctness). As in MV, our algorithm proceeds by computing a short path on the Voronoi graph of the lattice, where lattice points are adjacent if their Voronoi cells share a common facet, from the origin to a closest lattice vector. Our main technical contribution is a randomized procedure that given the Voronoi relevant vectors of a lattice -the lattice vectors inducing facets of the Voronoi cell -as preprocessing and any "close enough" lattice point to the target, computes a path to a closest lattice vector of expected polynomial size. This improves on the O(2 n ) path length given by the MV algorithm. Furthermore, as in MV, each edge of the path can be computed using a single iteration over the Voronoi relevant vectors. As a byproduct of our work, we also give an optimal relationship between geometric and path distance on the Voronoi graph, which we believe to be of independent interest.
In REF , a 3-step "perturbed" line path was analyzed to navigate over the Voronoi graph of the lattice, where lattice points are connected if their associated Voronoi cells touch in a facet.
Short Paths on the Voronoi Graph and the Closest Vector Problem with Preprocessing
ArXiv
ArXiv
Mathematics Computer Science