格基约化算法及其在密码分析中的应用综述

Review of Lattice Reduction Algorithms and Their Applications in Cryptanalysis

格基约化算法是密码分析中的一个重要工具,在RSA、DSA和背包体制等经典公钥密码算法的安全性分析和一些新型格密码体制的安全参数评估中发挥着重要作用。首先,给出格的一些基本概念并介绍格中一些困难问题;其次,归纳整理已有格基约化算法并总结梳理格基约化算法在密码分析中的应用;最后,对格基约化算法研究重点和趋势进行了总结和展望。

Lattice reduction algorithm is an important tool for cryptanalysis,which plays an important role in analyzing classic cryptosystems such as RSA,DSA and knapsack cryptosystems,and also possesses key position in the security estimation of many lattice-based cryptosystems.In this paper,we first recall the basic mathematical definitions related with lattice,and introduce basic hard problems of lattice.Then we categorize various lattice reduction algorithms and summarize their applications in cryptanalysis.Finally,we present several prospective directions worthy of future research.