株式会社KDDI総合研究所 このページを印刷する

耐量子署名の暗号解読において世界記録を達成

~量子コンピューター時代に必要な次世代暗号の実用化に向け貢献~

2024年8月23日
KDDI株式会社
株式会社KDDI総合研究所

KDDIとKDDI総合研究所は2024年6月27日、暗号解読コンテスト「Challenges for code-based problems(注1)(以下 本コンテスト)」の量子コンピューターに耐性を持つ電子署名方式(耐量子署名)に関する問題において、従来の世界記録であった解よりも4~10倍の計算量を要する、より探索が難しい解の発見に世界で初めて成功しました(注2)。
今回取り組んだ問題は、電子署名で使用される暗号技術における公開鍵から秘密鍵を計算する問題に相当します。この成果は、標準化が進められている暗号方式が耐量子署名として成り立つためのパラメータを精緻に見積もるために活用されます。
KDDIとKDDI総合研究所は、耐量子暗号の実用化に向けた取り組みの一環として、本コンテストに継続して参加しています。

 

■ 背景
電子署名は、電子文書や電子データの送受信において、送信元が正しいことや送信内容に改ざんがないことを数学的に証明する技術です。電子署名はアプリケーションやソフトウエアの安全な配布、公的サービスにおける個人認証、電子契約などにも利用されています。現在実装されている電子署名は、秘密鍵と公開鍵のペアを用いた暗号技術により、通信相手のサーバが正しいことの確認や、通信内容の盗聴や改ざんを防ぎます。一方、攻撃者が電子署名の秘密鍵を入手すると、電子文書やデータに対する電子署名を偽造することが可能となるため、他人へのなりすましやマルウェアの配布、電子契約書の改ざんなどが行われる危険があります。
今後、量子コンピューターが登場することにより、現在使用されている暗号が現実的な時間内で解読されてしまうことで安全性が損なわれる可能性があり、アメリカ国立標準技術研究所(以下 NIST)は量子コンピューターに耐性を持つ耐量子暗号の標準化を進めています。NISTは2022年7月に耐量子暗号の米国標準として4つの方式を選定し、現在、米国標準に追加する耐量子署名の選定を行っています。

 

 

 

<電子署名の利用例>

 

 

耐量子暗号を実用化するためには、現実的な時間内での解読が困難な高い安全性(暗号の強度)が求められます。実際の暗号では最高の処理能力を有するコンピューターで解読した場合でも、数億年以上という時間がかかることを想定し、パラメータを設定します。この想定が正しいかを確認するために、多数の研究者が現実的な時間で解読できるパラメータ値での暗号の解読にチャレンジし、その解読時間に関する情報を集約することで、使用するパラメータ値での解読時間を推定し安全性を検証します。

 

■ 今回の成果
KDDIとKDDI総合研究所は2024年6月27日、「Low-weight Codeword問題」(以下 本問題)において、従来の世界記録であった解よりも4~10倍の計算量を要する、より探索が難しい解の発見に世界で初めて成功しました。今回取り組んだ「Low-weight Codeword問題」は、「0」と「1」の二種類の数字で構成される長さ1,280の線形符号において、含まれる「1」の個数(ハミング重み)がより少ない符号語を探索する問題です。線形符号内の「1」の個数(ハミング重み)が少なくなるにつれ、条件を満たす解が少なくなるため、解の探索における難易度が向上し、かかる時間も長くなります。
今回、本問題に適したデータ構造を設計して解の探索範囲を大幅に絞りこむとともに、探索処理に最適な並列実装を見いだしました。その結果、合計7,600万の探索処理を同時に実行できるようになり、ハミング重み210と209の解の発見に世界で初めて成功しました。従来の世界記録はハミング重み211の解であり、今回の発見はその難易度の高さから世界記録を達成しました。またハミング重み210と209の解を、従来の世界記録(ハミング重み211)の解読に要した時間の1/15以下となる、それぞれ22.7時間と64.1時間で求めることに成功しました。
今回の解読結果をもとに、耐量子署名として使用が想定されているハミング重み値の秘密鍵の計算時間を推定した結果、量子コンピューターを用いた場合でも10億年程度が必要であることを確認し、その安全性を検証しました。今回の成果は、NISTが選定を進めている符号暗号に基づく電子署名方式において、安全性と効率性を両立するパラメータの選択などにも活用されます。

 

 

 

<本問題の解読アルゴリズムの概要>

 

 

■ 今後の取り組み
KDDIとKDDI総合研究所は、暗号解読コンテストへの挑戦を通じて、耐量子暗号の実用化に貢献していきます。また、耐量子暗号の安全性検証や高速軽量な暗号の実装に向け、必要となる最先端の知見の蓄積を図ります。両社は、6G時代に向けて2Tbpsの処理性能を実現する共通鍵暗号「Rocca-S」(注3)の実用化にも取り組んでいます。今後も、通信サービスに必要不可欠な暗号技術の取り組みを通じて、お客さまが安全安心なサービスを利用できる環境を提供していきます。

 

 

(参考)

■「KDDI SUMMIT 2024」での展示について
耐量子暗号の取り組みや生体認証の体験を、2024年9月3日から9月4日に開催されるKDDIグループ最大級のビジネスイベント 「KDDI SUMMIT 2024」の虎ノ門ヒルズフォーラム会場で公開します。ご参加には事前の参加登録(無料)が必要ですので、「KDDI SUMMIT」特設サイトからご登録ください。

 

 

 

(注1)フランス国立情報学自動制御研究所(INRIA)が主催する符号暗号に関する暗号解読コンテスト。
2019年7月21日にウェブサイトが公開され、コンテストが開始されました。
KDDI総合研究所が解読したLow-weight Codeword問題を含む計5種類の問題が出題され世界中の暗号研究者が参加しています。
Challenges for code-based problems

(注2)2024年8月23日時点。解読における難易度の高さから世界記録を達成しました。
世界記録が掲載されたウェブサイト
Challenges for code-based problems

(注3)2023年9月19日KDDI総合研究所 トピックス
超高速共通鍵暗号アルゴリズム「Rocca-S」が世界最速となる2Tbpsの処理性能を達成

 

※ニュースリリースに記載された情報は、発表日現在のものです。 商品・サービスの料金、サービス内容・仕様、お問い合わせ先などの情報は予告なしに変更されることがありますので、あらかじめご了承ください。