Approximating the Closest Vector Problem Using an Approximate Shortest\n Vector Oracle

2011/06/14 by Chandan K. Dubey, Dubey, Chandan, Thomas Holenstein +2
Computer Science · Engineering · #Advanced Control Systems Optimization #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Cryptography and Data Security #Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Fault Detection and Control Systems #Rough Sets and Fuzzy Logic #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1106.2619

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

Abstract

We give a polynomial time Turing reduction from the\n\γ²\√(n)-approximate closest vector problem on a lattice of dimension\nn to a \γ-approximate oracle for the shortest vector problem. This is\nan improvement over a reduction by Kannan, which achieved \γ²n^3/2.\n

Citations

• A hierarchy of polynomial time lattice basis reduction algorithms
• Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem

Related

• The nearest-colattice algorithm
• Lattice Sparsification and the Approximate Closest Vector Problem
• Solving the Closest Vector Problem in 2ⁿ Time--- The Discrete Gaussian Strikes Again!
• Improved algorithms for the Shortest Vector Problem and the Closest Vector Problem in the infinity norm
• Qubo model for the Closest Vector Problem