Paper 2020/694
The nearestcolattice 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 socalled Kannan's embedding technique, our algorithm allows using precomputations and can be used for efficient batch CVP~instances. This implies that some attacks on latticebased 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$.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Published elsewhere. Minor revision. Algorithmic Number Theory Symposium (ANTS 2020)
 Keywords
 lattice algorithmlattice reduction
 Contact author(s)
 t espitau @ gmail com
 History
 20200610: received
 Short URL
 https://ia.cr/2020/694
 License

CC BY
BibTeX
@misc{cryptoeprint:2020/694, author = {Thomas Espitau and Paul Kirchner}, title = {The nearestcolattice algorithm}, howpublished = {Cryptology ePrint Archive, Paper 2020/694}, year = {2020}, note = {\url{https://eprint.iacr.org/2020/694}}, url = {https://eprint.iacr.org/2020/694} }