KDDIとKDDI総合研究所は12月26日、次世代暗号(耐量子暗号)として標準化が進められている「Classic McEliece」方式において、これまでは総当たりによる探索での解読には1兆年以上要するとされてきた1409次元の暗号を、わずか29.6時間で解読に成功し、2023年11月13日に世界記録を更新したことを共同で発表した。詳細は、2024年1月23～26日に長崎で開催される「2024年 暗号と情報セキュリティシンポジウム(SCIS2024)」で発表される予定。

量子コンピュータの性能が向上した将来、現在の方式では暗号強度が不足することが指摘されており、アメリカ国立標準技術研究所(NIST)は2030年ごろに向けて、将来の量子コンピュータの性能にも耐えうる耐量子暗号の検討を進めている。NISTは2022年7月に、耐量子暗号の標準として4つの暗号方式を選定しており、さらに現在はClassic McElieceを含む4方式を追加の標準候補として評価を行っている最中だという。

新しい暗号技術を実装するには、現実的な時間内での解読が困難な高い安全性(暗号強度)が求められ、暗号強度は解読に必要な計算量が指標となるほか、計算量を突き止めることは安全性と性能を両立する耐量子暗号としての最適な次元の導出につながるとのこと。Classic McElieceでは現在、3488次元以上の暗号が標準候補として提案されているところだという。

この妥当性の検証に向け起点となる計算量を把握するべく、国際的な暗号解読コンテストが開催されており、KDDI総合研究所も継続的にコンテストに参加、これまでに世界記録を9回更新してきた実績を有している。

そして今回、フランス国立情報学自動制御研究所(INRIA)が主催する暗号解読コンテストのChallenges for code-based problemsに挑戦し、そこで上述した標準化が進められている暗号方式のClassic McElieceにおいて、1409次元の暗号の解読に世界で初めて成功し、これまで1347次元だった世界記録を大きく更新する結果を残した。

  • Classic McEliece暗号解読の世界記録(次元)の推移と計算量

    Classic McEliece暗号解読の世界記録(次元)の推移と計算量(出所:KDDI Webサイト)

1409次元の暗号とは、10の56乗(=1阿僧祇(あそうぎ)=100兆×100兆×100兆×100兆)通りの解の候補が存在し、現在の最速のスーパーコンピュータを用いたとしても、総当たりによる探索で解読するには1兆年以上かかるため、解読困難とされてきた。

今回の挑戦では、まず独自開発の解読アルゴリズムが用いられ、解の候補を10の36乗(1澗(かん)=1兆×1兆×1兆)分の1程度にまで絞り込むことで解読の難しさを引き下げるところからスタート。さらに、約2700万の解読処理を同時に実行できる並列コンピューティング環境を構築。その結果、1409次元のClassic McElieceを29.6時間で解読し、世界記録を樹立した。またこの解読の結果を通じ、1409次元のClassic McElieceの暗号の解読に要する計算量が2の63乗であることが実証され、その暗号強度が突き止められたとした。

今回の成果は、Classic McEliece暗号が耐量子暗号として成り立つ次元を精緻に見積もるための指標となり、安全な鍵長の選択や適切な鍵の交換時期を試算する技術的根拠として、各国の政府機関や国際標準化機関において活用されることになる。

  • 今回、暗号処理の並列実装最適化技術が開発された

    今回、暗号処理の並列実装最適化技術が開発された(出所:KDDI Webサイト)

両者は、今後も引き続き暗号解読コンテストへの挑戦を通じて、耐量子暗号の国際標準化、実用化に貢献していくとしている。さらに、暗号解読の高速化技術は安全な暗号の設計や暗号処理の高速化などの技術とも密接な関係にあるため、これらの取り組みを通じて、耐量子暗号に関する安全性評価や暗号処理の高速化に関わる設計・実装・検証ノウハウの蓄積を図っていくとした。

また今後の6G時代に向け、両者が開発した、暗号化されたデータを解読せずにそのまま分析することで、プライバシーを守りながら企業間のデータ利活用を推進できる次世代暗号方式「完全準同型暗号」や、KDDI総合研究所が兵庫県立大学と共同開発した、高速な通信処理にも適用可能な新たな共通鍵暗号アルゴリズム「Rocca-S」の実用化にも取り組んでいくとしている。