On Beating 2 n for the Closest Vector Problem
Amir Abboud, Rajendra Kumar · Society for Industrial and Applied Mathematics eBooks · 2025
The Closest Vector Problem (CVP) is a computational problem in lattices that is central to modern cryptography. The study of its fine-grained complexity has gained momentum in the last few years, partly due to the upcoming deployment of lattice-based cryptosystems in practice. A main motivating question has been if there is a (2 — ε)n time algorithm on lattices of rank n, or whether it can be ruled out by SETH.