Solving Closest Vector Instances Using an Approximate Shortest Independent Vectors Oracle

Given an n-dimensional lattice L and some target vector, this paper studies the algorithms for approximate closest vector problem (CVP_γ) by using an approximate shortest independent vectors problem oracle (SIVP_γ). More precisely, if the distance between the target vector and the lattice is no larger than c/(γn)λ₁(L) for arbitrary large but finite constant c > 0, we give randomized and deterministic polynomial time algorithms to find a closest vector, while previous reductions were only known for 1/(2γn)λ₁(L). Moreover, if the distance between the target vector and the lattice is larger than some quantity with respect to λ_n(L), using SIVP_γ oracle and Babai's nearest plane algorithm, we can solve CVP_γ√n in deterministic polynomial time. Specially, if the approximate factor λ∈(1, 2) in the SIVP_γ oracle, we obtain a better reduction factor for CVP.