KDDI総合研究所と東京大学のチームが、耐量子計算機暗号の解読コンテストで世界記録を達成

　KDDI総合研究所と東京大学大学院情報理工学系研究科（以下、東京大学）の修士2年 若尾武史氏（大学院生）、相川勇輔氏（助教）、高木剛氏（教授）は、耐量子計算機暗号（PQC）の暗号解読コンテスト「Challenges for code-based problems」において、3元体にもとづく210次元、220次元、230次元、240次元の符号暗号の解読に成功した。

　また、2025年12月15日、この成果により3元体にもとづく符号暗号は、米国標準PQCの符号暗号と比べ、10分の1以下の次元数（データサイズ）で同等の安全性を満たすことを確認したという。

　今回、KDDI総合研究所と東京大学は、3元体上の符号暗号に対し分割・並列処理による効率的なアルゴリズムを開発・実装することで、これまで誰も解けなかった暗号を解読したとのことだ。

　同成果により、2元体や3元体などにもとづく暗号の安全性を詳細に評価するための理論的枠組みの有効性を実証し、新たな数学的構造を用いた暗号方式を実現する道筋を開いたとしている。3元体にもとづく符号暗号を電子署名に利用した場合、2元体に比べ署名長を短くできるという特徴があり、スマートカードやIoTセンサーといった、データサイズに制約のある機器での活用が期待されるとのことだ。

　なお、同成果の一部は、科学技術振興機構（JST）経済安全保障重要技術育成プログラム（JPMJKP24U2）の支援を受けて行ったとしている。

背景

　米国立標準技術研究所（以下、NIST）は、量子コンピューターの処理能力にも耐えうるPQCの検討を進めており、2024年8月には米国標準PQCとして3方式の正式な技術規格を公開している。2035年までには、現行の公開鍵暗号からPQCへの移行を完了する予定だ。

　また、2025年3月には符号暗号であるHQCを、追加の米国標準PQCに選定しているという。加えて、現在NISTは署名長の短い方式を米国標準に追加するための評価・選定を行っているとのことだ。

　暗号の普及によるリスクを防ぐためには、新しい暗号技術の実用化に先立ち、暗号の高い安全性（暗号の強度）を正確に検証することが求められる。暗号の強度は、暗号解読に必要な計算量が指標となり、この計算量を明らかにすることで、安全性と性能を両立する適切な鍵の長さ（鍵長）の導出につながるという。

　たとえば、図2のように解読アルゴリズムの進展によって暗号の強度が低下した場合には、鍵長を大きくして安全性を確保する必要があるという。

　PQCをはじめとする新しい暗号の安全性を十分に検証するために、国際的な暗号解読コンテストが開催されている。次世代暗号の研究を行う企業や団体は、より高速な暗号解読手法の開発を進め、難易度の高い暗号解読に挑戦しているとのことだ。KDDI総合研究所は継続的に暗号解読コンテストに参加し、これまでに世界記録を計19回更新しているという。また、現在コンテストで出題されている5種類すべての問題で世界記録を保持したとのことだ。

成果について

　今回挑戦した問題は、3元体にもとづく符号暗号の安全性の根拠となる「シンドローム復号問題」と呼ばれるもの。これは、与えられた3元体にもとづく行列とベクトルに対して、条件を満たす秘密のベクトルを探索する問題であり、符号暗号の公開鍵から秘密鍵を求めることに相当するという。

　シンドローム復号問題を解く標準的な手法として、Information Set Decodingと呼ばれる解読アルゴリズムが知られている。通常、このアルゴリズムは2元体上の符号暗号を解読するために使用されるため、3元体上の符号暗号に対しては、より効率的な解読アルゴリズムとその実装を開発する必要があったという。

　そこで今回は、これまでの解読コンテストを通じて研究開発を行ってきた2元体用Information Set Decodingを3元体用に拡張。また、秘密鍵の探索時に2元体上の解読アルゴリズムと3元体用の解読アルゴリズムを組み合わせて利用する分割統治法を適用することで、秘密鍵の探索効率を向上させたという。開発した解読アルゴリズムを並列コンピューティング環境上に実装し、最大7台のデスクトップパソコンからなる計算環境を構築したとしている。これらの取り組みにより、解読処理を約1,000倍高速化したとのことだ。

　その結果、210次元から240次元の符号暗号を数十分から数日で解読することに成功。同成果をもとに、3元体にもとづく符号暗号が600次元以上のパラメータに対して128ビット級の高い安全性を有することを実証したと述べている。

　また、過去に解読した2元体にもとづく符号暗号と今回の暗号を含む符号暗号の安全性評価のための理論を構築し、多様な符号暗号の精緻な安全性を評価・実証したとのことだ。

【関連記事】
・Colt、量子セキュリティやAI時代のインフラ需要に対応へ　西日本エリアへの投資拡大などにも言及
・富士通と産総研、日本の量子コンピューター技術の優位性確立に向け連携へ
・FortiOSに「耐量子セキュリティ機能」実装、従来の公開鍵暗号と量子鍵の統合も──Fortinet