Cryptology ePrint Archive: Report 2020/694

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 ]