東京大学大学院情報理工学系研究科の坂田康亮特任研究員と高木剛教授は7月22日、次世代暗号(耐量子計算機暗号)の安全性評価に使う「MQ問題」の解読アルゴリズムで新記録を樹立したと発表した。MQ問題の解読難度を競う国際コンテスト「Fukuoka MQ Challenge」において、2023年に同チームが解読した問題と比べて約47,000倍計算が困難な問題(Type VI, m=24)を突破したという。

MQ問題とは何か

量子コンピュータが実用化されても解読されにくいとされる「耐量子計算機暗号(ポスト量子暗号)」の一方式に、多変数多項式を使う「多変数多項式暗号」がある。この暗号の安全性の裏付けとなっているのが、多数の多変数二次方程式を同時に解く数学的な難問「MQ問題」だ。MQ問題がどれだけ効率的に解けるかを調べることは、暗号の鍵長やパラメータを適切に設計するうえで欠かせない基礎研究にあたる。

今回の技術的なポイント

MQ問題を解く標準的な手法は、グレブナ基底を計算する「F4」というアルゴリズムだが、計算の途中で扱う行列が巨大化し、メモリと計算時間を圧迫することが長年の課題だった。研究チームは2023年、「ヒルベルト級数」という数理的な道具を使って計算に本当に必要な項の組み合わせを絞り込み、行列を小さく保つ手法を発表、当時最難関だった問題を約9時間で解読していた。

今回はその発展として、計算の前半はヒルベルト級数に基づく組み合わせの絞り込みを、後半は行列が肥大化しにくい組み合わせを優先的に選ぶ手法を組み合わせることで、計算の最初から最後まで一貫して行列サイズを抑えることに成功した。この改良により、従来なら手が届かなかった規模の問題を現実的な時間で解けるようになった。

日本のセキュリティ業界が押さえておきたい点

耐量子計算機暗号は、NIST(米国立標準技術研究所)が標準化を進めている分野で、金融・行政システムを含む幅広い領域で今後数年かけて移行が進む見込みだ。MQ問題の解読限界がどこにあるかを正確に見積もる研究は、暗号方式そのものの選定や、実装すべき鍵長・パラメータの安全マージンに直結する。今回のような解読記録の更新は、裏を返せば「これまで安全とされていたパラメータの一部が将来的に見直しを迫られる可能性がある」というシグナルでもある。自社システムでポスト量子暗号への移行を検討しているエンジニアは、採用予定の方式がどのパラメータセットに基づいているか、今後の動向を定期的にチェックしておく価値がある。

筆者の見解

暗号の数学的な安全性評価という地味だが極めて重要な基礎研究で、日本の大学発チームが世界記録を更新したというのは素直に誇っていい成果だ。日本のIT業界全体を見渡すと技術的な地力の底上げが急務だと感じる場面が多いなか、こうした基礎研究がきちんと世界水準で戦えている事実は心強い。

実務エンジニアの立場では、この種の理論的な最先端を逐一追いかける必要はない。むしろ大事なのは、NISTなどが定める標準が固まった段階で、自社のシステムにきちんと実装し運用に落とし込むことだ。情報を追いかけることに時間を使いすぎるより、標準化の節目節目で「今何を実装すべきか」を判断し、実際に手を動かして移行を進める姿勢のほうが、この分野では価値を生む。

出典: この記事は 東大が暗号解読の世界記録。従来より約47,000倍難しい問題を突破 の内容をもとに、筆者の見解を加えて独自に執筆したものです。