基于格的密码分析方法研究

Lattice-based cryptanalysis method is one of the main methods in public-key cryptanalysis. It plays an important role in analyzing the security of many public-key cryptosystems, including many widely-deployed ones in real life. In this project we will study the following problems: (1) Coppersmith's method is a lattice-based method which is depend on the assumption of algebraic independence. But this assumption is fail in some cases. We will study the reasons and look for solutions to the problem. (2) In studying the partial key exposure attacks on RSA and its variants, we will introduce optimization techniques to the specific problems and apply them to other problems. (3) The Φ-hiding assumption is at the security base of many cryptosystems. We will study its security via different lattice-based methods. The results will have an effect on the parameter settings in the systems basing on this assumption. (4) Certified trapdoor permutations are usually used to design cryptographic protocols. We will study an open problem in certifying RSA function as a trapdoor permutation and propose feasible solutions. These studies will help improving the lattice-based methods and promote the development of the research on their applications.

基于格的密码分析方法是公钥密码分析中一种主要的方法，在分析公钥密码方案（包括许多实际中被广泛使用的方案）的安全性方面发挥了非常重要的作用。本项目主要研究内容包括：一、格分析方法——Coppersmith方法需要依赖多项式代数无关假设，但是这个假设有时候并不成立，我们将结合实验和理论分析揭示其原因并提出可行的解决方法；二、研究对RSA算法及其变体的部分私钥泄露攻击，我们将针对具体问题提出对Coppersmith方法的优化技术，该技术可以用于分析其他问题；三、Φ隐藏假设是许多密码方案的安全性基础，我们将运用多种格分析方法研究其安全性，结果将影响基于该假设的密码方案具体参数的设置；四、可证明的陷门置换常被用于设计密码协议，我们将对RSA函数是可证明的陷门置换研究中的公开问题，提出方法证明RSA函数是可证明的陷门置换。这些研究将有助于完善格分析方法，并推动其应用研究的发展。

基于格的密码分析方法是公钥密码分析中一种主要的方法，在分析公钥密码方案（包括许多实际中被广泛使用的方案）的安全性方面发挥了非常重要的作用。本项目主要研究内容包括：一、代数困难问题——模逆隐藏数问题（MIHNP）的分析以及相关的逆同余伪随机数生成器（ICG）的分析，我们对Boneh等人以前的分析结果给出了具体的格构造方法方法，并把分析方法应用于分析逆同余伪随机数生成器，得到了更好的分析结果和更高的攻击效率，我们通过实验验证了我们的方法的正确性和有效性。二、研究对RSA算法及其变体CRT-RSA的安全性分析，优化了对CRT-RSA小解密指数攻击的分析结果。三、研究了RSA算法的部分私钥泄露攻击，改进了理论分析结果。我们的结果对更好地利用格方法做密码分析有重要意义。