Approximating the Closest Vector Problem Using an Approximate Shortest Vector Oracle

Abstract

We give a polynomial time Turing reduction from the ${\gamma }^2\sqrt{n}$-approximate closest vector problem on a lattice of dimension $n$ to a $\gamma$-approximate oracle for the shortest vector problem. This is an improvement over a reduction by Kannan, which achieved ${\gamma }^2{n}^{3/2}$.

10 pages, Published in APPROX 2011

Cited by in corpus (1)

• Solving the Closest Vector Problem in $2^n$ Time--- The Discrete Gaussian Strikes Again!