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

项目名称： 公钥密码体制的格分析方法研究

项目编号： No.61502269

项目类型： 青年科学基金项目

立项/批准年度： 2016

项目学科： 自动化技术、计算机技术

项目作者： 毕经国

作者单位： 清华大学

项目金额： 20万元

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

中文关键词： 格基约化算法；短向量问题；公钥密码体制；安全性评估

英文摘要： 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.

英文关键词： lattice reduction algorithm;short vector problem;public key scheme;security assessment