【作者】 洪浩； 胡予濮；

【Author】 Hong Hao Hu Yupu Key Laboratory of Computer Networks & Information Security of Ministry of Education,Xidian University,Xi’an,China,710071

【机构】 西安电子科技大学计算机网络与信息安全教育部重点实验室；

【摘要】 格基规约是格理论研究的一个重要内容,也是密码设计和分析中的一个重要工具。在理论研究中, 许多格上问题都可以通过规约来求解(或者近似求解)。在密码学应用中,对一些密码方案的分析最终都可以等价成一个格基规约问题。因此研究新型格基规约算法不仅具有理论价值,同时也具有重要的实用价值。文章提出了一种新型格基规约算法：SDR 算法,新算法将正交格理论融入 Schnorr 算法中,在相同的规约效果下,可将原有 Schnorr 算法中多项式时间因子 HKZ(2k)降为 HKZ(k)。更多还原

【Abstract】 Lattice reduction is not only an important task of lattice research but also a powerful tool for cryptology.Many lattice problems can be solved by lattice reduction directly,and even some NP-hard lattice problems can be approximately solved by reduction.On the other hand,some cryptanalysis can be reduced to lattice reduction problems.Therefore,to design new lattice reduction algorithms has great value in lattice research as well as in practical applications.In this paper,we suggest a new reduction algorithm SDR,which put the orthogonal lattice theory into Schnorr reduction algorithm.It is proved to decrease the poly time factor HKZ(2k)in Schnorr to HKZ(k)at the same effect of reduction.更多还原