计算机工程

• 安全技术 • 上一篇    下一篇

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

白 健1,2,刘 念2,李子臣1,2,刘 慧1,2   

  1. (1. 西安电子科技大学通信工程学院,西安 710071;2. 北京电子科技学院,北京 100070)
  • 收稿日期:2012-09-04 出版日期:2013-11-15 发布日期:2013-11-13
  • 作者简介:白 健(1989-),男,硕士研究生,主研方向:密码学;刘 念,讲师、博士;李子臣,教授、博士生导师;刘 慧,硕士研究生
  • 基金项目:
    国家自然科学基金资助项目“后量子数字签名算法研究与设计”(61070219)

New Lattice Reduction Algorithm Based on Gauss and LLL Reduction

BAI Jian 1,2, LIU Nian   2, LI Zi-chen 1,2, LIU Hui 1,2   

  1. (1. School of Teclcommunications Engineering, Xidian University, Xi’an 710071, China; 2. Beijing Electronic Science and Technology Institute, Beijing 100070, China)
  • Received:2012-09-04 Online:2013-11-15 Published:2013-11-13

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

关键词: 公钥密码体制, Gauss规约算法, LLL规约算法, Gauss-LLL规约算法,

Abstract: 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.

Key words: public key cryptosystem, Gauss reduction algorithm, LLL reduction algorithm, Gauss-LLL algorithm, lattice

中图分类号: