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客觀日本編輯部
