公钥密码体制的格分析方法研究

In the past thirty years, the lattice-based analysis method has successfully assessed the security of knapsack-type cryptosystem, RSA and DSA under special circumstances, and other public key cryptosystems since LLL lattice reduction algorithm was proposed. The basic idea of lattice-based analysis method is that one can convert the security of public key cryptosystem into the short lattice vector problem which can be solved by lattice reduction algorithms. There's no doubt that the lattice reduction algorithms are the basic tools for lattice-based analysis method. In this project, we will firstly study the special feature of the cryptographical lattices which are closely associated with the public key schemes security, and then focus on the lattice reduction algorithms to solve the short vector problem of such lattices. Finally, we will achieve more accurate assessments of the security of the existing public key schemes. More specifically, on one hand, we will improve the general lattice reduction algorithms and try to propose new ones. On the another hand, we will utilize the special structure of lattice basis matrix, such as ideal lattice, cyclic lattice et al. and the inherent character to find a more efficient, more individualized algorithm. This project will study the lattice-based analysis method on the security of public-key cryptosystem under the circumstances, such as broadcast attacks, replay attacks, et al. We will present more precise analysis of the security assessment of public key schemes, and gather experience for the public key schemes design and how to choose the security parameters.

随着 LLL 格基约化算法的提出，在过去的三十多年里格分析方法成功对背包型密码体制、特殊情形下的 RSA、DSA 等多个公钥密码体制的安全性进行了评估。格分析方法的基本思想是将影响公钥密码体制的安全性的核心数学问题转化成格基约化算法可求解的短向量等问题来解决。格基约化算法是格分析方法的基本工具，本项目将从与密码体制安全性紧密相关的密码格的特殊性质入手，着重研究求解密码格的短向量等问题的格基约化算法，进而达到更精确评估现有公钥密码体制安全性的研究目标。除了对现有算法优化和改进，并探索新的格基约化算法外，本项目还将利用理想格、循环格等密码格的特殊结构、格不变量间的固有性质等，给出更有针对性、更有效的格基约化算法。通过研究公钥密码体制在广播攻击、重放攻击等分析模型下的格分析方法的安全性，旨在给出从格分析的角度更精确的公钥密码体制的安全性评估，为将来公钥密码体制的设计及安全参数的选取积累经验。

在过去的三十多年里，格分析方法成功对多个著名的公钥密码体制的安全性进行了评估。格基约化算法是格分析方法的基本工具，本项目从与密码体制安全性紧密相关的密码格的特殊性质入手，着重研究求解密码格的短向量等问题的格基约化算法，进而达到更精确评估现有公钥密码体制安全性的研究目标。首先，本项目利用格分析方法对基于近似公因子问题的全同态加密算法、基于 Ring-LWE 问题的轻量级公钥加密算法等多个密码体制的安全性进行评估；其次，本项目对现有的经典格基约化算法的性质及典型困难问题的计算复杂度进行了估计；最后，利用特殊格的性质，给出了利用这些性质分析解决相应的困难问题的各种应用。. 本项目通过着重对求解密码格的短向量问题的格基约化算法进行研究，从格分析方法的角度对公钥密码体制特别是格公钥密码体制的安全性进行分析，为将来公钥密码体制的设计及安全参数的选取积累经验。