格基规约算法研究进展

Research progress of lattice bases reduction algorithms

格是一种线性结构,基于格的密码具有无可比拟的低能耗优势,故而在未来的智能终端上将有很好的应用前景.相比传统的RSA,ECC密码体制,格问题可证明的安全性在后量子密码时代已经显示了重要的作用.格算法的核心问题归结为格基规约问题,20多年来,在LLL格基规约算法启发下,出现了各种更强、更快的规约算法,有精确的也有近似的,对密码分析和密码设计产生了重要的推动作用.对各种规约概念和算法进行了全面的分析和总结.

Lattice is a linear structure,cryptosystems based on lattice have the incomparable advantage of lower energy consumption,so in the future they will also have a wide range of use for intelligent terminal.Compared with traditional public key cryptosystems： RSA,ECC,the based lattice cryptosystems can be proved secure,it has shown the important role in post-quantum cryptography era.The core of the algorithm＇s problems is base reduction,there are some stronger and faster algorithms under the inspiration of LLL Lattice reduction algorithm in the latest 20 years,no matter in accurate or approximate,they play an important role in cryptanalysis and cryptosystem＇s design.This article attempts to give an analysis and survey of all kinds of lattice reduction algorithm.