Solving closest vector instances using an approximate shortest independent vectors oracle.
Chengliang Tian, Wei Wei, Dongdai Lin · 2014
Given a lattice L ⊂ Rn 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 n1(L) for any constant c> 0, we give randomized and deterministic polynomial time algorithms to find a closest vector, which improves the known result by a factor of 2c. 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 pn in deterministic polynomial time. Specially, if the approximate factor ∈ (1; 2) in the SIVP oracle, we obtain a better reduction factor for CVP.