东京大学研究生院信息理工学系研究科的坂田康亮特任研究员和高木刚教授发布研究成果称，在新一代密码破译大赛的MQ挑战赛中创下了世界纪录，达成了迄今为止从未被破译过的维度。MQ挑战赛是一项旨在评估量子计算机也无法破解的后量子密码安全性的破译大赛，题目为使用多变量多项式的密码学破译问题。此次，研究人员通过阐明破译问题的数理特征，提出一种新的高速算法，并创下了世界纪录。相关成果由日本信息处理学会于10月30日至11月2日在Acros福冈（福冈市中央区天神）等举办的计算机安全研讨会（CSS2023）上发表。
图1：提案算法示意图（供图：东京大学）
当量子计算机达到实用水平后，目前使用的密码将很容易被破解，因此美国国家标准与技术研究院（NIST）正在推进即使是量子计算机也很难破解的抗量子计算机安全密码。
抗量子计算机密码的一种类型是被称为多变量多项式密码的密码方式，其破译问题被认为是求解联立二次多变量多项式的问题（MQ问题）。
已知的求解MQ问题的标准方法为F4，是一种求解多变量联立方程式时使用的计算格罗布纳基（Gröbner Basis）的算法，破解时需要计算巨大的矩阵。
此次研究团队通过希尔伯特级数（可为多变量多项式集合定义的单变量级数，并具有该集合代数结构的信息）阐明了MQ问题的数理特性，并构建了使计算的多项式的数量最小化的算法。
计算结果显示，通过计算从F4生成的矩阵中仅提取了必要计算区域的小矩阵，成功实现了高速化。
高木教授表示：“在量子计算机时代可以安全使用的加密技术正受到广泛关注，美国政府也在推进标准化工作等。此次破译世界纪录的研究成果将使我们获得严密的安全评估方法，为安全可靠的新一代密码的开发做出贡献。”
原文：《科学新闻》
翻译：JST客观日本编辑部
【论文信息】
会议：Computer Security Symposium(CSS 2023)
论文：Efficient algorithm for solving MQ problem using Hilbert series and its implementation
