Abstract

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 }^{n∕\left(2\beta \right)}covol{\left(\Lambda \right)}^{1∕n}$ for a random lattice $\Lambda$ of rank $n$. Compared to the so-called Kannan’s embedding technique, our algorithm allows the use of 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^{3∕2}{\beta }^{3n∕\left(2\beta \right)}$ to the shortest vector problem (SVP) in dimension $\beta$.

Keywords

Mathematical Subject Classification 2010

Milestones

Authors