KDDI総合研究所と東京大学(東大)の両者は1月9日、次世代暗号として米国で標準化が進められている「耐量子計算機暗号」(PQC)を題材とした、フランス国立情報学自動制御研究所主催の暗号解読コンテスト「Challenges for code-based problems」において、0、1、2の3要素からなる3元体に基づく210次元・220次元・230次元・240次元の符号暗号の解読に成功したと共同で発表した。
また今回の成果により、3元体に基づく符号暗号は米国標準のPQCと比較して1/10以下のデータサイズ(次元数)で同等の安全性を満たすことを確認したことも併せて発表された。
-
分割統治法と並列処理を組み合わせた符号暗号解読のイメージ(出所:東大プレスリリースPDF)
同成果は、KDDI総合研究所と、東大大学院 情報理工学系研究科の若尾武史大学院生、同・相川勇輔助教、同・高木剛教授らの共同研究チームによるもの。詳細は、1月26～30日に函館市で開催される「2026年 暗号と情報セキュリティシンポジウム(SCIS 2026)」にて発表する予定としている。
効率的な次世代暗号実現に向けて前進
実用的な量子コンピュータの登場が2030年代に予想される中、従来の暗号では強度が不足する懸念がある。そのため、米国国立標準技術研究所(NIST)は、量子コンピュータを利用した攻撃に耐え得るPQCとして、2024年8月に3方式の技術規格を公開した。2035年までの移行完了を目指すほか、2025年3月には符号暗号「HQC」を追加選定するなど、標準化を加速させている。さらに現在は、署名長の短い方式の評価・選定を実施中だ。
暗号の普及後に安全性が低下すれば多大な損害を招く恐れがあるため、実用化に際しては暗号強度の正確な検証が欠かせない。強度は解読に必要な計算量が指標となり、それを明確にすることで安全性と性能を両立する適切な鍵長を導き出せるようになる。アルゴリズムの進展で強度が低下した場合は、鍵長を大きくして安全性を確保することが不可欠なプロセスとなる。
-
解読技術の進展に伴う適切な鍵長の設定プロセス(出所:東大プレスリリースPDF)
新しい暗号の安全性を多角的に検証するため、国際的な暗号解読コンテストが開催されている。KDDI総合研究所は継続的にそれに参加しており、これまでに世界記録を計19回更新。現在、コンテストで出題されている5種類すべての問題において世界記録を保持するという圧倒的な実績を誇る。
-
符号暗号解読コンテストで達成された主な世界記録の推移(出所:東大プレスリリースPDF)
そして今回研究チームが挑んだのは、3元体に基づく符号暗号の安全性の根拠となる「シンドローム復号問題」である。これは、与えられた3元体に基づく行列とベクトルに対し、条件を満たす秘密のベクトルを探索する問題だ。符号暗号における公開鍵から秘密鍵を求める高低に相当し、その難しさが安全性の担保となる。
シンドローム復号問題を解く標準的な手法に、解読アルゴリズム「Information Set Decoding」(ISD)がある。通常、ISDは2元体上の符号暗号解読に用いられるが、3元体上の符号暗号に対しては、より効率的な解読アルゴリズムとその実装を開発が必要だった。そこで今回の研究では、これまで研究チームが培ってきた2元体用ISDを3元体用に拡張したという。
今回は、2元体用ISDの拡張に加え、秘密鍵の探索時に2元体用と3元体用の解読アルゴリズムを組み合わせて利用する分割統治法が適用された。これにより、探索効率の劇的な向上に成功。開発したアルゴリズムを最大7台のデスクトップPCによる並列計算環境に実装したところ、解読処理速度は約1000倍に向上し、210次元から240次元の符号暗号を数十分から数日で解読することに成功したとしている。
-
3元体上のシンドローム復号問題と今回の解読アプローチの概要(出所:東大プレスリリースPDF)
この成果により、3元体に基づく符号暗号は600次元以上のパラメータにおいて、128ビット級の高い安全性を有することが実証された。また、過去に解読した2元体に基づく符号暗号と、今回の暗号を含めた安全性評価のための理論を構築。多様な符号暗号の精緻な安全性が評価・実証された。
研究チームは、今後もコンテストを通じてPQCの安全性検証を進めると共に、得られた知見を活用し、PQC実装時に求められるアルゴリズムの高速実装や、スマートカード・IoT機器向けの軽量実装の研究開発にも取り組んでいく方針とした。2030年代を見据え、安心・安全な通信サービスを提供するための研究・技術開発を継続していくとしている。
KDDI総合研究所など、耐量子計算機暗号解読コンテストで世界記録を達成
