次世代暗号の「解読の限界」に挑む新アルゴリズムを開発

～従来より約47,000倍難しいMQ問題を解読し、世界記録を達成～

【注目の成果：共同研究・産学連携のためのチェックポイント】

次世代暗号の安全性評価に関わる「MQ問題」を高速に解く新しいアルゴリズムを開発

【産学連携対象全学共通分野 Discovery Saga】

情報学数物系科学工学

【Sagaキーワード】

アルゴリズム/量子コンピュータ/量子暗号/安全性評価

2026/07/22

概要

東京大学大学院情報理工学系研究科の坂田康亮特任研究員と高木剛教授は、次世代暗号の安全性評価に関わる「MQ問題」を高速に解く新しいアルゴリズムを開発しました。
MQ問題は、多変数の二次方程式を同時に解く問題であり、量子コンピュータでも解読が難しいと期待されるポスト量子暗号の安全性を評価する上で重要です。従来の解読手法では、計算途中に巨大な行列が現れることが大きな課題でした。
本研究では、ヒルベルト級数と呼ばれる数理的な道具を用いて、計算に本当に必要な組合せを見極め、計算過程全体で行列を小さく保つ新手法を提案しました。その結果、従来記録より約47,000倍難しいとされるMQ問題の解読に成功しました。

従来より約47,000倍難しいとされるMQ問題を解読
本成果は、暗号研究の国際会議CHES2026に採択され、今後のポスト量子暗号の安全な設計や安全性評価への貢献が期待されます。
この研究成果は、英国夏時間2026年7月17日付で「IACR Transactions on Cryptographic Hardware and Embedded Systems 2026 (TCHES2026)」に掲載されました。
研究成果についての詳細は【情報理工_プレスリリース_20260722】をご覧下さい。

論文情報

雑誌名：IACR Transactions on Cryptographic Hardware and Embedded Systems 2026 (TCHES2026)
題　名：An Efficient Variant of F4 Algorithm for Solving MQ Problem
著者名：Kosuke Sakata, Tsuyoshi Takagi
DOI:https://doi.org/10.46586/tches.v2026.i3.1284-1309
URL:https://tches.iacr.org/index.php/TCHES/article/view/13150