**The nearest-colattice algorithm **

*Thomas Espitau and Paul Kirchner*

**Abstract: **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 \emph{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$.

**Category / Keywords: **public-key cryptography / lattice algorithm, lattice reduction

**Original Publication**** (with minor differences): **Algorithmic Number Theory Symposium (ANTS 2020)

**Date: **received 9 Jun 2020

**Contact author: **t espitau at gmail com

**Available format(s): **PDF | BibTeX Citation

**Version: **20200610:064439 (All versions of this report)

**Short URL: **ia.cr/2020/694

[ Cryptology ePrint archive ]