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

New Lattice Reduction Algorithm Based on Gauss and LLL Reduction

作　　者：白健[1,2] 刘念[2] 李子臣[1,2] 刘慧[1,2] 

机构地区：[1]西安电子科技大学通信工程学院,西安710071 [2]北京电子科技学院,北京100070

出　　处：《计算机工程》2013年第11期147-149,162,共4页Computer Engineering

基　　金：国家自然科学基金资助项目“后量子数字签名算法研究与设计”(61070219)

摘　　要：格是多维空间中点的规则排列,基于格的公钥密码体制是密码学中研究的热点。针对传统格基规约算法效率较低、消耗时间较长的问题,分析Gauss和LLL规约算法,在此基础上提出一种新型格基规约算法(Gauss-LLL),对算法进行正确性验证,并给出实现伪码。该算法可对格的任意一组基进行规约,最终获得一组长度较短的规约基。分析结果表明,与LLL算法相比,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规约算法 格 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]