Enumerative Algorithms for the Shortest and Closest Lattice Vector Problems in Any Norm via M-Ellipsoid Coverings
Daniel Dadush, Chris Peikert, Santosh Vempala · arXiv (Cornell University) · 2010
We give an algorithm for solving the exact Shortest Vector Problem in n-dimensional lattices, in any norm, in deterministic 2 O(n) time (and space), given poly(n)-sized advice that depends only on the norm. In many norms of interest, including all ℓp norms, the advice is efficiently and deterministically computable, and in general we give a randomized algorithm to compute it in expected 2 O(n) time. We also give an algorithm for solving the exact Closest Vector Problem in 2 O(n) time and space, when the target point is within any constant factor of the minimum distance of the lattice. Our approach may be seen as a derandomization of ‘sieve ’ algorithms for exact SVP and CVP (Ajtai, Kumar, and Sivakumar; STOC 2001 and CCC 2002), and uses as a crucial subroutine the recent deterministic algorithm of Micciancio and Voulgaris (STOC 2010) for lattice problems in the ℓ2 norm. Our main technique is to reduce the enumeration of lattice points in an arbitrary convex body K to enumeration in 2 O(n) copies of an M-ellipsoid of K, a classical concept in asymptotic convex geometry. Building on the techniques of Klartag (Geometric and Functional Analysis, 2006), we also give an expected 2 O(n)-time algorithm to compute an M-ellipsoid covering of any convex body, which may be of independent interest.