プレスリリース

次世代暗号の解読コンテストで世界記録を達成～量子コンピュータも解読できないポスト量子暗号への挑戦～

現在、私たちの生活のいたるところに暗号技術が使用されています。しかし、現在使用されている暗号は量子コンピュータによって簡単に解読されてしまうことが知られています。そこで、量子コンピュータでも解読が困難な暗号の安全性を保障するため、最も効率的な攻撃アルゴリズムを評価する研究が進められています。

情報理工学系研究科の坂田康亮特任研究員と高木剛教授は、次世代暗号の解読コンテストであるＭＱチャレンジにおいて、これまでに解かれたことがない次元の解読世界記録を達成しました。今回、解読問題の数理的な特性を解明することで新しい高速アルゴリズムを提案し、世界記録の達成に繋がりました。考案したアルゴリズムでは、計算途中に現れる巨大な行列のうち、出力結果に影響する最低限の領域だけを切り出し、解読に必要となる最小の行列を構成するよう工夫しています。さらに、提案アルゴリズムを大規模な並列計算機にプログラミング実装することにより、これまでに解かれたことのない次元の暗号解読を可能としました。

今後、この新しいアルゴリズムの詳細を評価し、現在進められている次世代暗号の標準化規格における安全なパラメータの提案を進めます。
この研究成果は、情報処理学会主催のコンピュータセキュリティシンポジウム「Computer Security Symposium(CSS 2023)」(2023年10月30日‐11月2日 福岡開催)で発表しました。

世界記録を達成した方法：計算途中に現れる巨大な行列のうち、出力結果に影響する最低限の領域だけを切り出し、解読に必要な最小の行列を構成する。

この研究成果についての詳細は【情報理工_プレスリリース_20231023】pdfをご覧下さい。

論文情報

学会名：コンピュータセキュリティシンポジウム2023（CSS2023）
論文タイトル：Hilbert級数を用いたＭＱ問題の高速解法とその実装
Efficient algorithm for solving MQ problem using Hilbert series and its implementation
著者名：Kosuke Sakata and Tsuyoshi Takagi