Paper 2014/545

Solving closest vector instances using an approximate shortest independent vectors oracle

Chengliang Tian, Wei Wei, and Dongdai Lin

Abstract

Given a lattice $L\subset {\text{R}}^n$ and some target vector, this paper studies the algorithms for approximate closest vector problem (CVP${}_{\gamma }$) by using an approximate shortest independent vectors problem oracle (SIVP${}_{\gamma }$). More precisely, if the distance between the target vector and the lattice is no larger than $\frac{c}{\gamma n}{\lambda }_1(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 ${\lambda }_n(L)$, using ${\text{SIVP}}_{\gamma }$ oracle and Babai's nearest plane algorithm, we can solve ${\text{CVP}}_{\gamma \sqrt{n}}$ in deterministic polynomial time. Specially, if the approximate factor $$ in the $$ oracle, we obtain a better reduction factor for CVP.