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.展开更多
NTRU(Number Theory Research Unit)是一种新型的公钥密码体制,因其高效、快速和运算简单等特点,已得到越来越广泛的应用.其安全性建立在大维数格中的数学难题之上,为此,在研究NTRU算法和格理论的基础上,设计了一种建立在最近向量难题...NTRU(Number Theory Research Unit)是一种新型的公钥密码体制,因其高效、快速和运算简单等特点,已得到越来越广泛的应用.其安全性建立在大维数格中的数学难题之上,为此,在研究NTRU算法和格理论的基础上,设计了一种建立在最近向量难题上的数字签名方案.展开更多
The restricted parameter range set cover problem is a weak form of the NP-hard set cover problem with the restricted range of parameters. We give a polynomial time algorithm for this problem by lattices.
基金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.
基金Acknowledgements This work was supported by the National Natural Science Foundation of China （Grant No. 11371138）.
文摘The restricted parameter range set cover problem is a weak form of the NP-hard set cover problem with the restricted range of parameters. We give a polynomial time algorithm for this problem by lattices.
