東京大學研究生院資訊理工學系研究科的坂田康亮特任研究員和高木剛教授發佈研究成果稱，在新一代密碼破譯大賽的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
