KDDI综合研究所与东京大学研究生院信息理工学系研究科的若尾武史研究生（硕士二年级）、相川勇辅助教、高木刚教授组成的研究团队宣布，在美国推进标准化的新一代抗量子计算机密码（PQC：Post-Quantum Cryptography）解密竞赛“Challenges for code-based problems”中创下了世界纪录，首次成功破解了基于三元域的210维、220维、230维和240维编码密码。此外，该团队于2025年12月15日已通过此项成果证实，相较于美国标准PQC编码密码，基于三元域的编码密码仅需不到十分之一的维度（数据量）即可实现同等的安全性能。
图1：基于分割与并行处理方式实现破解的示意图（来源：KDDI综合研究所）
双方于2026年1月26日至30日在日本函馆市举办的“2026年密码与信息安全研讨会（SCIS 2026）”上公布了此次成果。
三元域是由“0”、“1”、“2”这三个元素构成的集合，是一种定义了加法与乘法的数学结构。由“0”、“1”构成的集合则为二元域。本次研究针对三元域上的编码密码，通过开发并实现基于分割与并行处理的高效算法，成功破解了此前无人能破解的密码。该成果不仅验证了用于详细评估基于二元域、三元域等密码安全性的理论框架的有效性，也为实现基于全新数学结构的密码方式铺平了道路。
研究团队表示，若将基于三元域的编码密码用于电子签名，与二元域相比可缩短签名长度，因此有望在智能卡、物联网传感器等数据容量受限的设备中得到应用。
本次挑战的难题是支撑三元域编码密码安全性的“伴随式译码问题”（Syndrome Decoding Problem, SDP），要求在给定的基于三元域的矩阵与矢量中，寻找一个满足特定条件的秘密矢量，相当于从编码密码的公钥中导出私钥。
作为解决该问题的标准方法，业界已知一种被称为Information Set Decoding（信息集解码）的解密算法。然而，该算法通常用于破解基于二元域的编码密码，因此，要破解基于三元域的编码密码，就需要开发更高效的解密算法及实现方案。
为此，研究团队将此前通过破解大赛积累的二元域算法拓展至三元域场景。此外，在搜索私钥的过程中，采用了结合二元域解密算法与三元域解密算法的分治法，从而提升了私钥的搜索效率。
随后，研究团队将扩展开发的解密算法部署在并行计算环境中，并构建了由最多7台台式电脑组成的计算平台。通过这些举措，破解处理速度提升了约1000倍，最终在数十分钟到数天以内成功破解了从210维到240维的编码密码。
基于这些成果，研究团队证实了基于三元域的编码密码在参数达到600维以上时，具备了128比特级别的高安全性。此外，研究团队还构建了涵盖过往破解的二元域编码密码及本次三元域密码在内的安全性评估理论，实现了对多种编码密码安全性能的精细化评估与验证。
原文：《科学新闻》
翻译：JST客观日本编辑部
