后量观点：对于格密码学近日的量子算法的讨论

2024年4月，清华大学交叉学科研究院陈一镭教授发布了预印本论文” Quantum Algorithms for Lattice Problems”（关于格问题的量子算法），声称找到了一种能攻击一般格问题的量子算法。由于最近20余年时间，密码学界的大量学术成果，诸如后量子密码学，全同态加密，零知识证明等，很多都和格密码学及其量子安全性有深刻的联系，格问题的量子安全性也是大家普遍相信的 (见https://arxiv.org/abs/quant-ph/0307220)。因此，这篇论文引起了学术界，工业界的广泛讨论。

很快，这个算法被找到了一个无法弥补的漏洞。在更新版的预印本论文中（https://eprint.iacr.org/2024/555），作者承认该算法的第九步存在问题（详见第37页3.5.9节）并且无法弥补，因此这个算法最后并不能使用。清华大学宣传这个结果的官方微信公众号也撤回了相关的文章。

事实上，试图寻找攻击格密码学的量子算法一直都是科学家勇于挑战的目标。在2016年，麻省理工学院量子计算的国际著名专家Peter Shor（Shor算法的创立者）和科学家Lior Eldar一起发布了论文“关于最近格矢量问题的一个变种的一个高效量子算法“https://arxiv.org/abs/1611.06999，也试图利用量子计算攻击一大类普遍的格密码学。很快，这个算法也被发现存在漏洞。原作者撤回了这篇论文。

总体来讲，格密码学是研究得最完备的后量子密码学技术，用到的知识也比较深刻，功能也最多（例如，格密码学是构造全同态加密的主要方法）。因此，大家对格密码学的安全性也是有很强的信心。陈教授的勇气值得赞许，他使用的算法技巧也有很多值得学习的地方，但格密码学再次经受住了时间的考验。

后量科技始终站在科学界和产业界对后量子密码学和量子科技的研究前沿，追逐最新动态，为算法安全性保驾护航，为广大用户负责。同时，后量科技选取的密码学组合也被国内国际的密码学标准化机构广泛接受。如果格密码学在量子计算机的算力下存在漏洞，后量科技也有大量的被认为更安全的密码学技术加以提供。例如，哈希密码学也是后量子密码学的主要成员之一。和格密码学建立在格问题的复杂度不同，哈希密码学建立在哈希函数的单向性上。如果（量子）单向函数不存在，那么将直接证明P=NP。这种可能性在学术界被认为是很小的因此，美国国家标准技术局（NIST）把哈希密码学算法SPHINCS+作为后量子四大候选算法之一，也是处于安全性和完备性的考虑。

后量科技将始终站在行业前沿，对量子科技，密码学技术和人工智能前沿做最深度的研究，为后量子时代的信息安全保驾护航。