1409次元の次世代暗号を世界で初めて解読、耐量子暗号の実用化に向け前進

■背景

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

■今回の成果

KDDIとKDDI総合研究所は2023年11月13日、フランス国立情報学自動制御研究所（INRIA）が主催する暗号解読コンテスト「Challenges for code-based problems」に挑戦し、耐量子暗号として標準化が進められている暗号方式Classic McElieceにおいて、1409次元の暗号の解読に世界で初めて成功し、これまで1347次元だった世界記録を更新しました。
1409次元の暗号は10の56乗（＝100兆×100兆×100兆×100兆）通りの解の候補が存在し、総当たりによる探索では解読に1兆年以上かかるため、解読困難とされてきました。
両社は、独自の解読アルゴリズムにより解の候補を10の36乗（＝1兆×1兆×1兆）分の1程度に絞り込むことで解読の難しさを引き下げました。さらに約2,700万の解読処理を同時に実行できる並列コンピューティング環境を構築、活用することで、1409次元のClassic McElieceを29.6時間で解読することに世界で初めて成功しました。また、この解読の結果を通じ、1409次元のClassic McElieceの暗号の解読に要する計算量が2の63乗であることを実証し、その暗号の強度を突き止めたことになります。本成果は、Classic McEliece暗号が耐量子暗号として成り立つ次元を精緻に見積もるための指標を明らかにしたもので、安全な鍵長の選択や適切な鍵の交換時期を試算する技術的根拠として、各国の政府機関や国際標準化機関において活用されます。

■今後の取り組み

KDDIとKDDI総合研究所は、引き続き暗号解読コンテストへの挑戦を通じて、耐量子暗号の国際標準化、実用化に貢献していきます。さらに、暗号解読の高速化技術は安全な暗号の設計や暗号処理の高速化などの技術とも密接な関係にあるため、これらの取り組みを通じて、耐量子暗号に関する安全性評価や暗号処理の高速化に関わる設計・実装・検証ノウハウの蓄積を図っていきます。6G時代に向けて高速な通信処理にも適用可能な新たな共通鍵暗号アルゴリズム「Rocca-S」（注6）や、プライバシーを守りながら企業間のデータ利活用を推進するための次世代暗号方式「完全準同型暗号」（注7）のそれぞれの実用化にも取り組んでいます。
今後も、情報サービスの利用に必要不可欠な暗号技術の取り組みを通じて、お客さまが安全安心なサービスを利用できる環境を提供していきます。

（参考）