Welcome to the resource topic for 2014/545
Title:
Solving closest vector instances using an approximate shortest independent vectors oracle
Authors: Chengliang Tian, Wei Wei, 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.
ePrint: https://eprint.iacr.org/2014/545
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .