International Association
for Cryptologic Research

Given a lattice $L\\subset\\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 $\\SIVP_\\gamma$ oracle and Babai\'s nearest plane algorithm, we can solve $\\CVP_{\\gamma\\sqrt{n}}$ in deterministic polynomial time.

Specially, if the approximate factor $\\gamma\\in(1,2)$ in the

$\\SIVP_\\gamma$ oracle, we obtain a better reduction factor for CVP.