The nearest-colattice algorithm: Time-approximation tradeoff for approx-CVP
Thomas Espitau, Paul Kirchner · The Open Book Series · 2020
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 ≈ β n/(2β) covol( ) 1/n for a random lattice of rank n.Compared to the socalled Kannan's embedding technique, our algorithm allows the use of 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 proven reduction from approximating the closest vector with a factor ≈ n 3/2 β 3n/(2β) to the shortest vector problem (SVP) in dimension β. LLL algorithm).On CVP-solving algorithms.There are three families of algorithms solving CVP: Enumeration algorithms.These consist in recursively exploring all vectors in a set containing a closest vector.Kannan's algorithm takes time n O(n) and polynomial space [24].This estimate was later refined to n n/2+o(n) by Hanrot and Stehlé [21].