The nearest-colattice algorithm

2020/06/10 by Thomas Espitau, Espitau, Thomas, Paul Kirchner +1
Computer Science · #Complexity and Algorithms in Graphs #Computational Geometry (cs.CG) #Cryptography and Data Security #Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Privacy-Preserving Technologies in Data

paper · pdf · doi:10.48550/arxiv.2006.05660

openalex publication_date 2020/06/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 ≈ β^(n)/(2β)\textrmcovol(Λ)^(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 ≈ n^\frac32β^(3n)/(2β) to the Shortest Vector Problem (SVP) in dimension β.

Citations

• A hierarchy of polynomial time lattice basis reduction algorithms
• On lattices, learning with errors, random linear codes, and cryptography
• Factoring polynomials with rational coefficients

Related

• Lattice Sparsification and the Approximate Closest Vector Problem
• Approximating the Closest Vector Problem Using an Approximate Shortest\n Vector Oracle
• On Beating 2ⁿ for the Closest Vector Problem
• Solving the Closest Vector Problem in 2ⁿ Time--- The Discrete Gaussian Strikes Again!
• Short Paths on the Voronoi Graph and the Closest Vector Problem with Preprocessing