Paper 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$.

Metadata
Available format(s)
PDF
Category
Public-key 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
2020-06-10: received
Short URL
https://ia.cr/2020/694
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/694,
      author = {Thomas Espitau and Paul Kirchner},
      title = {The nearest-colattice 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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.