**Solving closest vector instances using an approximate shortest independent vectors oracle**

*Chengliang Tian and Wei Wei and Dongdai Lin*

**Abstract: **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.

**Category / Keywords: **foundations / lattice-based cryptography

**Date: **received 14 Jul 2014

**Contact author: **tcl0815 at gmail com

**Available format(s): **PDF | BibTeX Citation

**Version: **20140718:070941 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]