このページを印刷する
耐量子計算機暗号の米国標準として選定されたHQCの安全性検証を完了
～暗号解読コンテストで3,846次元の解読に成功～
2025年4月30日
株式会社KDDI総合研究所
KDDI総合研究所は2025年4月25日、耐量子計算機暗号（以下 PQC：Post-Quantum Cryptography）の米国標準として選定されたHQC（注1）の安全性の検証を完了し、指定された鍵の長さにおいて安全性のマージンが約50,000倍であることを明らかにしました。これは暗号解読に使用できるコンピューターや、現時点で想定されている量子コンピューターの性能が50,000倍に向上した場合でも、暗号の安全性は維持されることを表します。
今回の成果は、フランス国立情報学自動制御研究所（以下 INRIA）が主催する暗号解読コンテスト「Challenges for code-based problems（注2）」にチャレンジし、世界で初めてHQCの3,846次元（鍵の長さ）の暗号解読に成功したことにより導き出されたもので（注3）、安全な鍵の長さの選択や適切な鍵の交換時期を試算する技術的根拠として、日本を含む各国の政府機関や国際標準化機関において活用されます。
＜図 米国標準PQCであるHQCの安全性検証結果＞
■ 背景
ネットショッピングやネットバンキングをはじめとする現代の情報サービスを利用する際に、個人情報をオンライン上でやり取りする機会が増えています。これらのサービスを安心・安全に利用できるようにするには、暗号技術による情報セキュリティの確保が重要です。
近年量子コンピューターが登場し、2030年代には実用化が見込まれているなか、将来的に暗号強度が不足する可能性が指摘されています。アメリカ国立標準技術研究所（以下 NIST）は、量子コンピューターの処理能力にも耐えうるPQCの検討を進めています。NISTは2024年8月に米国標準PQCとして3方式の正式な技術規格を公開（注4）しており、2035年までに現行の公開鍵暗号からPQCへの移行を完了すると宣言しています。さらに2025年3月に、HQCを追加の米国標準PQCに選定しています。
暗号技術が破られた場合には多大な損害が発生します。こうしたリスクを防ぐためにも、新しい暗号技術の実用化に先立ち、暗号の高い安全性（暗号の強度）を正確に検証することが求められます。暗号の強度は、暗号解読に必要な計算量が指標となり、計算量を突き止めることは、安全性と性能を両立する最適な鍵の長さの導出につながります。HQCでは35,338次元以上の暗号が米国標準として選定されています。
この妥当性を検証するために、国際的な暗号解読コンテストが開催されています。次世代暗号の研究を行う企業や団体はより高速な暗号解読手法の開発を進め、難度の高い暗号解読にチャレンジしています。KDDI総合研究所は継続的に暗号解読コンテストに参加しており、これまでに世界記録を15回更新しています。
■ 今回の成果
KDDI総合研究所は、INRIAが主催する暗号解読コンテスト「Challenges for code-based problems」に挑戦し、米国標準のPQCとして選定されたHQCの3,846次元の暗号解読に世界で初めて成功しました。
3,846次元の暗号は、10の136乗通りの解の候補が存在し、総当たりによる探索では解読に1兆年以上かかるため、解読困難とされてきました。今回、暗号の繰り返しのパターンを活用して、解読に使うことのできる方程式の数を増やすことにより鍵の探索アルゴリズムを効率化しました。さらに、探索結果の集計時に利用するデータ構造を改良して排他制御を不要とすることでGPUによる並列処理の効果を向上しました。以上の取り組みにより3,846次元のHQCを66.2日で解読しました。この解読の結果、指定された鍵の長さ（35,338次元）において安全性のマージンが約50,000倍であり、NISTによる推奨の約30,000倍を上回ることを検証しました。
＜図 暗号の繰り返しパターンを活用した解読方法＞
■ 今後の取り組み
KDDI総合研究所は、引き続き暗号解読コンテストにチャレンジしPQCの安全性の検証を行うとともに、これまで培った暗号解読のノウハウをもとにPQC実装時に必要な暗号の高速軽量化技術の研究開発に取り組んでいきます。今後も、量子コンピューターの実用化が見込まれる2030年代に向けて世界中のお客さまに安心・安全な通信サービスを提供できるよう貢献していきます。
（注1）正式名称はHamming Quasi-Cyclic。符号暗号の1方式であり、鍵の長さが小さいことが特徴。
（注2）フランス国立情報学自動制御研究所（INRIA）が主催する暗号解読コンテスト。2019年7月21日にウェブサイトが公開され、コンテストが開始された。符号暗号に関連する計5種類の問題が出題され、世界中の暗号研究者が参加している。
Welcome to the code-based challenges webpage!
（注3）世界記録が掲載された暗号解読コンテスト公式ウェブサイト
「Challenges for code-based problems」
（注4）米国標準PQCとして選定ずみのML-KEM、ML-DSA及びSLH-DSAの連邦情報処理標準（FIPS：Federal Information Processing Standards）を公開
NIST Releases First 3 Finalized Post-Quantum Encryption Standards
※ニュースリリースに記載された情報は、発表日現在のものです。 商品・サービスの料金、サービス内容・仕様、お問い合わせ先などの情報は予告なしに変更されることがありますので、あらかじめご了承ください。