格上最短向量问题的求解算法研究

The Shortest Vector Problem (SVP) is one of the most famous hard problems in lattice, whose hardness is the foundation for the security of almost all lattice-based public-key cryptosystems. Lattice-based public-key cryptosystems are widely believed to be the most hopeful post-quantum cryptosystems and have been playing an very important role both in theory and practice. It is obvious that the study on the algorithms for solving SVP is vital for the security of lattice-based cryptosystems, and hence becomes more and more hot these years. Moreover, lattice basis reduction algorithms has been used widely in cryptanalysis. Therefore, we plan to study the enumeration algorithm and discrete Gaussian sample algorithm for solving SVP, and also design more efficient lattice basis reduction algorithms for NTRU lattice and Coppersmith algorithm in this project. We expect to obtain some better algorithms for SVP in theory or practice, together with better algorithms to solve NTRU lattice with higher dimension and to improve the efficiency of Coppersmith algorithm. These results will at least help us understand the security of lattice-based public-key cryptosystems better and improve the cryptanalytic tools for public-key cryptosystems.

最短向量问题（SVP）是格中最著名的困难问题之一，其困难性是几乎所有格密码体制的安全性基础，而格密码目前被广泛认为是后量子时代最有希望的公钥密码体制，在理论密码学和现实应用中占据着十分重要的地位。显然，对SVP求解算法的研究直接关系着格密码的安全性，因此是一项极其重要的工作，也一直是国际格密码研究中的热点和难点。除此之外，格基约化算法在公钥密码分析中也有十分广泛的应用。因此，本项目拟研究如何更好地利用枚举算法和离散高斯采样算法来求解SVP，并为NTRU格和Coppersmith算法定制更有效的格基约化算法。项目预期提出更好的求解SVP算法，求解更高维数NTRU格中的近似短向量，并提高Coppersmith算法的运行效率，从而实现我们对格密码安全性更深层次的认识，以及促进公钥密码分析工具的进一步发展。

格密码目前被广泛认为是最有希望的后量子公钥密码算法之一，其安全性基础是格上的最短向量问题。本项目围绕格上最短向量问题的求解展开，主要包括其求解算法的研究及其在NTRU的安全性分析和Coppersmith算法中的应用，后量子密码算法的设计和安全性分析，主要取得了如下成果：利用Coppersmith算法在一定条件下有效求解了模逆隐藏数问题，在大模数情况下证伪了Boneh等人在2001年提出的猜想；提出了计算整数矩阵Hermit标准型的新型快速算法，其启发式时间复杂度与矩阵乘法相当，从而在实践中加速了Hermite标准型求解算法，也为从理论上降低Hermite标准型求解算法的时间复杂性提供了可行的途径；分析了NIST后量子密码标准化中的3个首轮候选算法，攻破了Liu, Li, Kim和Nepal等提交的基于格的Compact-LWE加密方案，致使其被淘汰，在现实中彻底攻破Hecht和Kamlofsky提交的HK17密钥交换协议，该算法最终被提交者主动撤回，指出Melchor等提交的HQC加密算法并不能达到IND-CPA安全，且其用于安全性证明的困难性假设不成立；降低了Nuñez等人提出的基于NTRU的代理重加密方案的安全性；第一次给出了对NewHope等Regev型密码现实可用的Klepto攻击，成功地在其密钥生成过程中植入了后门；设计了4个基于格的密码算法，2个算法获得全国密码算法设计竞赛(公钥算法)三等奖。项目的研究成果，为后量子密码算法的设计与安全性分析提供了必要的理论支持和技术储备，为保护我们在量子时代的信息安全，积累了有益经验，并提供了可行的解决方案。