Solving all lattice problems in deterministic single exponential time

03/22/2011 - 12:15pm
03/22/2011 - 1:10pm
Daniele Micciancio (UC San Diego)

We give deterministic exp(n)-time algorithms to solve all the most important computational problems on point lattices in NP, including the Shortest Vector Problem (SVP), Closest Vector Problem (CVP), and Shortest Independent Vectors Problem (SIVP). This improves the exp(n*log(n)) running time of the best previously known algorithms for CVP (Kannan, 1987) and SIVP (Micciancio, 2008), and gives a deterministic alternative to the randomized SVP algorithm (Ajtai, Kumar and Sivakumar, 2001). The core of our 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. Talk based on joint work with P. Voulgaris presented at STOC 2010.

Millikan 208 (Pomona College)