一种新型l次格基规约算法

寻找格中的非零短向量是格理论应用于密码学研究常常遇到的一个问题。一般通过各种格基规约算法来得到格中的近似最短向量。本文在标准LLL规约算法7]的基础上,首次提出了l次规约的概念,并且设计了一种新型的l次规约算法。利用这种新型算法找到的短向量比使用标准LLL规约算法求得的短向量更加接近格中的最短非零向量。算法在一定范围内具有计算花费时间和规约结果质量之间可以相互转化的特点,可以通过牺牲更多的运算时间来获得质量更优的规约基。通过大量的数值测试,本文比较了l次规约算法和标准LLL规约算法的实际性能,验证了对l次规约算法的理论分析。最后,本文提出了进一步改进l次规约算法的两个思路。

A New l-reduced Lattice Reduction Algorithm

To find out short nonzero vectors from a random lattice is an important subject of crypto applications based on the lattice theory.Usually,approximate short vectors are got by lattice reduction algorithms.Based on the standard LLL algorithm,the conception of l-reduced lattice reduction is proposed in this paper for the first time,and a new l-reduced lattice reduction algorithm is presented.This l-reduced lattice reduction algorithm can find vectors shorter than ones got by the standard LLL algorithm which is widely used in this field.An interesting property of this algorithm is that a better reduced lattice base can be got if a lager l is chosen,while the time cost increased.Numerical tests have been carried out to study the different performances of the l-reduced algorithm and standard LLL algorithm.Results for the l-reduced algorithm are found to be close to the experimental data. The two possible methods to improve this algorithm are presented at the end of this paper.