基于Gauss和LLL规约的新型格基规约算法

摘要

Lattice is a regular alignment of points in multi-dimensional. There are many people researching the public-key cryptosystem based on lattice recently. This paper introduces the basic knowledge of reduced basis of the lattice and analyzes the Gauss algorithm and LLL algorithm. On this basis, it presents the Gauss-LLL algorithm. It proves that algorithm’s validity and gives its realization pseudo code. Gauss-LLL algorithm can reduce arbitrarily set of base for lattice, and eventually get a shorter length lattice. Analysis result shows that Gauss-LLL algorithm not only can get a better reduced basis of the lattice, but also can be faster than the LLL algorithm.%格是多维空间中点的规则排列，基于格的公钥密码体制是密码学中研究的热点。针对传统格基规约算法效率较低、消耗时间较长的问题，分析Gauss和LLL规约算法，在此基础上提出一种新型格基规约算法(Gauss-LLL)，对算法进行正确性验证，并给出实现伪码。该算法可对格的任意一组基进行规约，最终获得一组长度较短的规约基。分析结果表明，与LLL算法相比，Gauss-LLL算法得到的规约基较优，规约效率较高。