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 .