We use cookies to improve your experience with our site.

最短线性无关向量谕示下求解最近向量问题实例的有效算法

Solving Closest Vector Instances Using an Approximate Shortest Independent Vectors Oracle

  • 摘要: 给定任一n维格L以及某一目标向量, 本文研究了在最短线性无关向量谕示下求解最近向量问题实例的有效算法。具体地, 对任意大且有限的常数c>0, 若目标向量距格的距离不超过c/(γnλ1(L), 我们给出了求解距目标向量最近格点的随机及确定多项式时间归约算法, 而之前已知的随机归约算法的距离因子为1/(2γnλ1(L)。此外, 若目标向量与格的距离大于与λn(L)有关的某一量时, 利用SIVPγ谕示及Babai的最近平面算法, 给出了求解CVPγn的确定多项式时间算法。特别地, 当γ∈(1, 2)时, 我们给出了更好的归约结果。

     

    Abstract: Given an n-dimensional lattice L and some target vector, this paper studies the algorithms for approximate closest vector problem (CVPγ) by using an approximate shortest independent vectors problem oracle (SIVPγ). More precisely, if the distance between the target vector and the lattice is no larger than c/(γn)λ1(L) for arbitrary large but finite constant c > 0, we give randomized and deterministic polynomial time algorithms to find a closest vector, while previous reductions were only known for 1/(2γn)λ1(L). Moreover, if the distance between the target vector and the lattice is larger than some quantity with respect to λn(L), using SIVPγ oracle and Babai's nearest plane algorithm, we can solve CVPγn in deterministic polynomial time. Specially, if the approximate factor λ∈(1, 2) in the SIVPγ oracle, we obtain a better reduction factor for CVP.

     

/

返回文章
返回