KDDI株式会社
株式会社KDDI総合研究所
～量子コンピューターでも解読困難な暗号実用化に貢献し、安全安心な通信サービスを提供～
KDDIとKDDI総合研究所では次世代暗号（耐量子暗号）の実用化に取り組んでおり、暗号解読コンテスト「Challenges for code-based problems（
注1）」において、次世代暗号として標準化が進められているClassic McEliece（注2）の1409次元（注3）の暗号解読にKDDI総合研究所が世界で初めて（注4）成功し、2023年11月13日に世界記録を更新したこと（以下 本成果）をお知らせします。
1409次元の暗号は、総当たりでは解読に1兆年以上かかるとされてきましたが、今回、独自の解読アルゴリズムで計算対象を大幅に絞り込み、約2,700万の解読処理を同時に実行できる並列コンピューティング環境を構築・活用することで、29.6時間で暗号を解読しました。これにより、1409次元の暗号を解読するために必要な計算量（処理の繰り返し回数）が2の63乗であることを実証し、この次元を上回れば暗号の解読が困難という目安である暗号の強度を突き止めました。
量子コンピューターの普及により、将来的に現在の暗号技術の安全性が脅かされる可能性があります。本成果は、量子コンピューターでも解読困難な次世代暗号の実用化に貢献します。
両社は、世界中の暗号研究者が参加しているコンテストへの挑戦を通じ、得られた最先端の暗号技術に関する知見を自社のサービスに還元するだけでなく、量子コンピューターの実用化が見込まれる2030年代にも世界中のお客さまに安全安心な通信サービスをご利用いただけるよう、引き続き研究開発に取り組んでいきます。
なお、本成果については2024年1月23日から2024年1月26日に長崎で開催される「2024年 暗号と情報セキュリティシンポジウム（SCIS2024）」（注5）で発表を行う予定です。
＜Classic McEliece暗号解読の世界記録（次元）の推移と計算量＞
■背景
ネットショッピングやネットバンキングをはじめとする現代の情報サービスを利用する際に、個人情報をオンライン上でやりとりすることが増えています。これらのサービスを安全安心に利用できるようにするには、暗号技術による情報セキュリティーの確保が重要です。
近年、量子コンピューターの登場により、将来的に暗号強度が不足することが指摘されています。アメリカ国立標準技術研究所（以下 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）のそれぞれの実用化にも取り組んでいます。
今後も、情報サービスの利用に必要不可欠な暗号技術の取り組みを通じて、お客さまが安全安心なサービスを利用できる環境を提供していきます。
（参考）
■KDDIとKDDI総合研究所の取り組み
KDDIとKDDI総合研究所は、KDDI VISION 2030「『つなぐチカラ』を進化させ、誰もが思いを実現できる社会をつくる。」を掲げ、豊かなコミュニケーション社会の発展に向けてさまざまな事業に取り組んでいます。重要なライフラインを担う事業者の責任として、お客さまが通信サービスを安心して利用できるよう、最新の脅威に対応するための技術やノウハウを常に磨き、いつでも安定した通信サービスを提供することを目指します。
- 注1）
- フランス国立情報学自動制御研究所（INRIA）が主催する符号暗号に関する暗号解読コンテスト。2019年7月21日にウェブサイトが公開され、コンテストが開始された。KDDI総合研究所が解読したSD問題（注8）を含む計5種類の問題が出題され、世界中の暗号研究者が参加している。
https://decodingchallenge.org
- 注2）
- 暗号文が短いことを特徴として持つ情報を特定の規則に従って変換し、効率的な伝送と信頼性を確保する基礎理論である符号理論に基づいて構成された耐量子暗号の1つ。
- 注3）
- 秘密鍵の長さのこと。
- 注4）
- 2023年11月13日時点。世界記録が掲載されたウェブサイト
- 注8）
- 係数、定数項および解が0と1のみで構成される多元連立1次方程式で、解における「1」の個数は問題ごとに与えられている定数以下となる必要があります。この問題は量子コンピューターを用いても効率的に解読できないとされており、その難しさは、符号暗号（注9）の安全性の根拠となっています。安全な符号暗号を実現するためには、SD問題の次元（未知変数の個数）を高め、解読を困難にする必要がありますが、次元が大きすぎると暗号の処理時間が増大します。そのため、安全性が確保される最適な次元を求めるために、高速な解法の研究が進められています。
- 注9）
- SD問題など符号理論に関連する問題を安全性の根拠とする公開鍵暗号方式。次世代公開鍵暗号の有力な候補の一つで、現在最も広く使用されているRSA暗号よりも安全かつ高速な方式として期待されています。符号暗号は、シンプルな演算による暗号の処理が可能であり、かつ並列化による高速化も容易です。このため、特に処理能力に制約のあるIoT機器や組み込み機器などへの搭載が期待されています。
- ※この記事に記載された情報は、掲載日時点のものです。
商品・サービスの料金、サービス内容・仕様、お問い合わせ先などの情報は予告なしに変更されることがありますので、あらかじめご了承ください。
