基于格的公钥密码体制的安全性分析

Lattice-based public-key cryptosystems have drawn considerable attention for these years, since they are not only one of the main post-quantum public-key cryptosystems, but also the main way to construct fully homomorphic encryption. It is well known that the security decides the practicality of a cryptosystem essentially, so it is necessary and important to analyze the security of lattice-based public-key cryptosystems. In this project, we will analyze their security by studying both the general lattice algorithm and the concrete cryptographic attack. We plan to propose a new lattice basis reduction algorithm, a more efficient random sieve algorithm for ideal lattice, and more efficient attacks against some important lattice-based public-key cryptosystems. These results will help us understand the security of lattice-based public-key cryptosystems better, choose more appropriate parameters for them, apply them more reasonably in practice, develop new cryptanalytic tools and improve the lattice-based public-key cryptosystems.

基于格的公钥密码体制不仅是后量子时代最有前途的公钥密码体制之一，也为全同态加密体制的构造提供了重要的解决途径，因此受到了国际密码学界的极大关注。众所周知，密码体制的安全性是决定该体制能否应用的最根本因素之一。因此，对格密码体制的安全性进行分析就是一项十分必要且重要的工作。本项目拟从构造普遍的格算法和实施具体的密码攻击两个方面对一些格密码的安全性进行分析。项目预期将提出新的格基约化算法，提出更有效的针对理想格的随机筛法，实现对某些重要格密码体制更有效的攻击。项目的研究成果将对了解格密码的安全性产生十分重要的理论意义, 对格密码的参数选取、现实中的合理应用有着重要的现实意义，并有助于提出新的密码分析工具，促进格密码的进一步发展。

格密码被公认为是最有前途的后量子密码体制之一，因此对其安全性进行分析具有十分重要的理论意义和现实意义。本项目围绕格密码所基于的数学难题和具体构造方式展开，深入探讨格密码的安全性，主要取得了如下结果：提出了求解SVP问题的三层筛算法，进一步降低了已有算法的时间复杂度；得到了用任意p范数SVP谕言机能求解的随机子集和问题的密度上界，填补了空白；详细讨论了如何利用SVP谕言机来求解多重随机子集和问题；改进了SVP问题不同版本之间的归约关系；证明了任意整格都存在两类特殊近似正交格基，并提出了相应的算法；给出了随机Hermite标准型的统计性质。这些结果有助于我们进一步认识格密码的安全性，对格密码在现实应用中的参数选取具有重要的指导意义。