  In this work, we exhibit a hierarchy of polynomial time algorithms solving
approximate variants of the Closest Vector Problem (CVP). Our first
contribution is a heuristic algorithm achieving the same distance tradeoff as
HSVP algorithms, namely $\approx
  \beta^{\frac{n}{2\beta}}\textrm{covol}(\Lambda)^{\frac{1}{n}}$ for a random
lattice $\Lambda$ of rank $n$. Compared to the so-called Kannan's embedding
technique, our algorithm allows using precomputations and can be used for
efficient batch CVP instances. This implies that some attacks on lattice-based
signatures lead to very cheap forgeries, after a precomputation. Our second
contribution is a proven reduction from approximating the closest vector with a
factor $\approx n^{\frac32}\beta^{\frac{3n}{2\beta}}$ to the Shortest Vector
Problem (SVP) in dimension $\beta$.
