3602次元の次世代暗号を解読、耐量子暗号の米国標準最終候補である3方式の安全性検証を完了

#テクノロジー

KDDI株式会社
株式会社KDDI総合研究所

KDDIとKDDI総合研究所は2025年1月6日、暗号解読コンテスト「Challenges for code-based problems（注1）」において、次世代暗号として米国で標準化が進められているBIKE（注2）およびHQC（注3）の3602次元（鍵の長さ）の暗号解読に世界で初めて（注4）成功しました。
両社は、1409次元のClassic McEliece（注5）の安全性も検証しており（注6）、今回の成果と合わせて、耐量子暗号の米国標準の最終候補である符号暗号（注7）3方式の安全性検証を完了したことになります。
一連の成果は、これらの符号暗号が耐量子暗号として成り立つ次元を精緻に見積もるための指標を明らかにしたもので、安全な鍵の長さの選択や適切な鍵の交換時期を試算する技術的根拠として、日本を含む各国の政府機関や国際標準化機関において活用されます。
量子コンピューターの普及により、将来的に現在の暗号技術の安全性が脅かされる可能性があるなか、一連の成果は量子コンピューターでも解読困難な次世代暗号の実用化に貢献します。

■背景

ネットショッピングやネットバンキングをはじめとする現代の情報サービスを利用する際に、個人情報をオンライン上でやりとりすることが増えています。これらのサービスを安全安心に利用できるようにするには、暗号技術による情報セキュリティーの確保が重要です。
近年量子コンピューターが登場し、2030年代には実用化が見込まれているなか、将来的に暗号強度が不足することが指摘されています。アメリカ国立標準技術研究所（以下 NIST）は、量子コンピューターの処理能力にも耐えうる耐量子暗号の検討を進めています。NISTは2024年8月に米国標準の耐量子暗号3方式の正式な技術規格を公開しており、2035年までに耐量子暗号への移行を完了すると宣言しています。さらに現在、Classic McEliece、BIKEおよびHQCの符号暗号3方式を、追加の標準候補として評価しています。
新しい暗号技術を実装するには、現実的な時間内での解読が困難な高い安全性（暗号の強度）が求められます。暗号の強度は、暗号解読に必要な計算量が指標となります。計算量を突き止めることは、安全性と性能を両立する最適な鍵の長さの導出につながります。現在、Classic McElieceでは3488次元以上の暗号、BIKEでは24646次元以上の暗号、HQCでは35338次元以上の暗号が標準候補として提案されています。
この妥当性の検証に向けて、国際的な暗号解読コンテストが開催されており、次世代暗号の研究を行う企業や団体はより高速な暗号解読手法の開発を進めて、より難度の高い暗号解読にチャレンジしています。KDDI総合研究所は継続的に暗号解読コンテストに参加しており、これまでに世界記録を14回更新しています。

■今回の成果

KDDIとKDDI総合研究所は、フランス国立情報学自動制御研究所（INRIA）が主催する暗号解読コンテスト「Challenges for code-based problems」に挑戦し、耐量子暗号として標準化が進められている暗号方式BIKEおよびHQCの3602次元の暗号解読に世界で初めて成功しました。
3602次元の暗号は10の131乗通りの解の候補が存在し、総当たりによる探索では解読に1兆年以上かかるため、解読困難とされてきました。両社は、独自の解読アルゴリズムにより解の候補を10の10乗（=100億）通り程度に絞り込むことで解読の難しさを引き下げました。さらに約8,000万の解読処理を同時に実行できる並列コンピューティング環境を構築、活用することで、3602次元のBIKEとHQCを63.5日で解読しました。この解読の結果を通じ、3602次元のBIKEとHQCの暗号の解読に要する計算量が2の69乗であることを実証し、その暗号の強度を突き止めたことになります。

＜BIKE/HQCの構造を利用した独自の解読アルゴリズムと並列コンピューティング技術＞

なお、本成果については2025年1月28日から2025年1月31日に福岡県北九州市で開催される「2025年暗号と情報セキュリティシンポジウム（SCIS 2025）」（注8）で発表を行う予定です。

■今後の取り組み

両社は、引き続き暗号解読コンテストへの挑戦を通じて、耐量子暗号の国際標準化、実用化に貢献していきます。今後も、量子コンピューターの実用化が見込まれる2030年代にも世界中のお客さまに安全安心な通信サービスをご利用いただけるよう、引き続き研究開発に取り組んでいきます。

注1）フランス国立情報学自動制御研究所（INRIA）が主催する暗号解読コンテスト。2019年7月21日にウェブサイトが公開され、コンテストが開始された。符号暗号に関連する計5種類の問題が出題され、世界中の暗号研究者が参加している。
- https://decodingchallenge.org
注2）正式名称はBit Flipping Key Encapsulation。符号暗号の1方式であり、鍵の長さが小さいことが特徴。
注3）正式名称はHamming Quasi-Cyclic。符号暗号の1方式であり、鍵の長さが小さいことが特徴。
注4）世界記録が掲載された暗号解読コンテスト公式ウェブサイト「Challenges for code-based problems」
注5）符号暗号の1方式であり、暗号化されたデータのサイズが小さいことが特徴。
注6）
- 1409次元の次世代暗号を世界で初めて解読、耐量子暗号の実用化に向け前進
注7）符号理論に関連する問題を安全性の根拠とする公開鍵暗号方式。次世代公開鍵暗号の有力な候補の一つで、現在最も広く使用されているRSA暗号よりも安全かつ高速な方式として期待されている。符号暗号は、シンプルな演算による暗号の処理が可能であり、かつ並列化による高速化も容易となる。このため、特に処理能力に制約のあるIoT機器や組み込み機器などへの搭載が期待されている。
注8）
- 2025年暗号と情報セキュリティシンポジウム（SCIS2025）