The nearest-colattice algorithm

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 }}\text{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^{\frac{3}{2}}{\beta }^{\frac{3n}{2\beta }}$ to the Shortest Vector Problem (SVP) in dimension $\beta$.

19 pages, presented at the Algorithmic Number Theory Symposium (ANTS 2020)

References in corpus (1)

• Improved Analysis of Kannan's Shortest Lattice Vector Algorithm