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γ...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.展开更多
Unique shortest vector problem(uSVP)plays an important role in lattice based cryptography.Many cryptographic schemes based their security on it.For the cofidence of those applications,it is essential to clarify the co...Unique shortest vector problem(uSVP)plays an important role in lattice based cryptography.Many cryptographic schemes based their security on it.For the cofidence of those applications,it is essential to clarify the complex-ity of uSVP with different parameters.However,proving the NP-hardness of usVP appears quite hard.To the state of the art,we are even not able to prove the NP-hardness of usVP with constant parameters.In this work,we gave a lower bound for the hardness of usVP with constant parameters,i.e.we proved that uSVP is at least as hard as gap shortest vector problem(GapSVP)with gap of O(√n/log(n)),which is in NP n coAM.Unlike previous works,our reduction works for paramters in a bigger range,especially when the constant hidden by the big-O in GapsVP is smallerthan1.展开更多
基金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.
基金This work is funded by National Natural Science Foundation of China(Grants No.62172405).
文摘Unique shortest vector problem(uSVP)plays an important role in lattice based cryptography.Many cryptographic schemes based their security on it.For the cofidence of those applications,it is essential to clarify the complex-ity of uSVP with different parameters.However,proving the NP-hardness of usVP appears quite hard.To the state of the art,we are even not able to prove the NP-hardness of usVP with constant parameters.In this work,we gave a lower bound for the hardness of usVP with constant parameters,i.e.we proved that uSVP is at least as hard as gap shortest vector problem(GapSVP)with gap of O(√n/log(n)),which is in NP n coAM.Unlike previous works,our reduction works for paramters in a bigger range,especially when the constant hidden by the big-O in GapsVP is smallerthan1.
