[Resource Topic] 2020/694: The nearest-colattice algorithm

Welcome to the resource topic for 2020/694

Title:
The nearest-colattice algorithm

Authors: Thomas Espitau, 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.

ePrint: https://eprint.iacr.org/2020/694

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .