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\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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
lattice-based cryptography
Contact author(s)
tcl0815 @ gmail com
History
2014-07-18: received
Short URL
https://ia.cr/2014/545
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/545,
      author = {Chengliang Tian and Wei Wei and Dongdai Lin},
      title = {Solving closest vector instances using an approximate shortest independent vectors oracle},
      howpublished = {Cryptology ePrint Archive, Paper 2014/545},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/545}},
      url = {https://eprint.iacr.org/2014/545}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.