Solving Closest Vector Instances Using an Approximate Shortest Independent Vectors Oracle  

作　　者：田呈亮 魏伟 林尔岱 

机构地区：[1]State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences Beijing 100093, China [2]Institute for Advanced Study, Tsinghua University, Beijing 100084, China

出　　处：《Journal of Computer Science & Technology》2015年第6期1370-1377,共8页计算机科学技术学报（英文版）

基　　金：This work is partially supported by the National Basic Research 973 Program of China under Grant No. 2011CB302400, the National Natural Science Foundation of China under Grant Nos. 61379139 and 61133013, and the Strategic Priority Research Program of the Chinese Academy of Sciences under Grant No. XDA06010701.

摘　　要：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.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.

关 键 词：LATTICE closest vector problem shortest independent vectors problem reduction 

分 类 号：O151.24[理学—数学] TP311.13[理学—基础数学]