A tight analysis of the Iterative Slicer to solve the Closest Vector Problem

Abstract

We consider the Iterative Slicer algorithm to solve the Closest Vector Problem with Preprocessing. The success probability of this algorithm depends heavily on the size of the preprocessed work, but so far only two non-tight heuristic lower bounds for this probability are known. In this talk we consider an asymptotic analysis that is tight under the Gaussian Heuristic. Using the Gaussian Heuristic we reinterpret the problem as a random walk. Determining the success probability then boils down to finding the highest probable path to our goal. We apply some classical numerical methods that converge to the optimal path and even find an explicit analytical solution. During this talk one will get familiar with some heuristics that are generally used to analyse lattice based algorithms. These heuristics give results that are much closer to practice than their provable counterparts, which makes them important in the context of cryptanalysis.