UC San Diego

The shortest vector problem (SVP) and closest vector problem (CVP) are the most widely known problems on point lattices. SVP and CVP have been extensively studied both as purely mathematical problems, being central in the study of the geometry of numbers and as algorithmic problems, having numerous applications in communication theory and computer science. There are two main algorithmic techniques for solving exact SVP and CVP: enumeration and sieving. The best enumeration algorithm was given by Kannan in 1983 and solves both problems in n̂{O(n)} time, where n is the dimensionality of the lattice. Sieving was introduced by Ajtai, Kumar and Sivakumar in 2001 and lowered the time complexity of SVP to 2̂{O(n)} , but required $2̂{O(n)}$ space and randomness. This result posed a number of important questions: Could we get a \emph{deterministic} 2̂{O(n)} algorithm for SVP? Is it possible to acquire a 2̂{O(n)} algorithm for CVP?. In this dissertation we give new algorithms for SVP and CVP and resolve these questions in the affirmative. Our main result is a \emph{deterministic} Õ(2̂{2n}) time and Õ(2n̂) space that solves both SVP and CVP and by reductions of (Micciancio, 2008) most other lattice problems in NP considered in the literature. In the case of CVP the algorithm improves the time complexity from n̂{O(n)} to 2̂{O(n)}, while for SVP we achieve single exponential time as sieving, but without using randomization and improving the constant in the exponent from 2.465 (Pujol and Stehl\ 'e, 2010) to 2. The core of the algorithm is a new method to solve the closest vector problem with preprocessing (CVPP) that uses the Voronoi cell of the lattice (described as intersection of half-spaces) as the result of the preprocessing function. We also present our earlier results on sieving algorithms. Although the theoretical analysis of the proposed sieving algorithm gives worse complexity bounds than our new Voronoi based approach, we show that in practice sieving can be much more efficient. We propose a new heuristic sieving algorithm that performed quite well in practice, with estimated running time 2̂{0.52n} and space complexity 2̂{0.2n}