Approximating the Closest Vector Problem Using an Approximate Shortest Vector Oracle

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\mathrm{/}2}$.