The nearest-colattice algorithm
This work addresses lattice-based cryptography attacks, enabling efficient forgeries in signatures after precomputation, but it is incremental as it builds on existing techniques like HSVP and Kannan's embedding.
The paper tackles the approximate Closest Vector Problem (CVP) by introducing a hierarchy of polynomial-time algorithms, with a heuristic achieving a distance tradeoff of ≈ β^(n/(2β)) covol(Λ)^(1/n) for random lattices and a proven reduction from CVP to SVP with a factor ≈ n^(3/2) β^(3n/(2β)).
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 β^{\frac{n}{2β}}\textrm{covol}(Λ)^{\frac{1}{n}}$ for a random lattice $Λ$ 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 proven reduction from approximating the closest vector with a factor $\approx n^{\frac32}β^{\frac{3n}{2β}}$ to the Shortest Vector Problem (SVP) in dimension $β$.