The Micciancio-Voulgaris Algorithm for CVP

We review algorithms presented in the paper:

A Deterministic Single Exponential Time Algorithm for Most Lattice Problems based on Voronoi Cell Computations https://cseweb.ucsd.edu/~pvoulgar/files/voronoi_full.pdf

Three components:

1. An  -time algorithm to solve the *closest vector problem with preprocessing * where the output of the preprocessing function is the Voronoi cell of the input lattice, described as the intersection of half-spaces.
2. A rank reduction procedure that solves CVP on a  -rank lattice  with  calls to a CVP oracle for  where  an LLL reduced basis for 
3. A procedure for computing the Voronoi cell of a lattice  by  calls to a CVP oracle for  and polynomial time computations.

Voronoi cells

The (open) Voronoi cell of a lattice  is the set

of all points that are closer to the origin than to any other lattice point. The closed Voronoi cell  as the topological closure of . The Voronoi cell of a lattice point  is defined similarly, and equals . For any (lattice) point  define the half-space

Clearly,  is the intersection of  for all  The minimal set of lattice vectors  such that  is called the set of Voronoi relevant vectors.

CVP with preprocessing (CVPP)

An algorithm that on input an  -rank lattice  a list  of the Voronoi relevant vectors of  and a target vector  computes a lattice point closest to  in time 

1.  a  algorithm for the special case where 
2. solve the general CVPP problem with polynomially many calls to 

The relation between the Voronoi cell and CVPP is well known. In CVPP, we want to find the lattice point closest to a given target vector . It is easy to see that this is equivalent to finding a lattice vector  such that  belongs to the (closed) Voronoi cell of the lattice. In other words, CVP can be equivalently formulated as the problem of finding a point in the set .

Rank reduction

A procedure that given a basis  for a  -rank lattice  and an integer  such that  solves a CVP instance on  with  calls to CVP on the  -rank sub-lattice 

 is the covering radius of  and  the component of  orthogonal to  .

1. A polynomial time preprocessing step that outputs a basis  for the input lattice such that, the ratio  is bounded by  for every  This can be achieved by simply running the LLL algorithm.
2. The actual rank reduction procedure that given an integer  such that  solves a CVP instance on  with  calls to  on .

Combining the two steps gives a reduction from a CVP in  to  s in 

Computing the Voronoi cell

This component computes the relevant vectors of a lattice  by  calls to  all for the same lattice, plus  polynomial time computations. Computes the relevant vectors in two steps:

1. First it runs the  procedure that, given a lattice  outputs a list  of size  that contains all the relevant vectors, with the help of  CVP queries.
2. Then it feeds the output list  to the  procedure.  discards the non-relevant points from a list of lattice points  that contains all the relevant vectors in time  Notice that  therefore this step takes  time.