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

電子署名は、電子文書や電子データの送受信において、送信元が正しいことや送信内容に改ざんがないことを数学的に証明する技術です。電子署名はアプリケーションやソフトウエアの安全な配布、公的サービスにおける個人認証、電子契約などにも利用されています。現在実装されている電子署名は、秘密鍵と公開鍵のペアを用いた暗号技術により、通信相手のサーバーが正しいことの確認や、通信内容の盗聴や改ざんを防ぎます。一方、攻撃者が電子署名の秘密鍵を入手すると、電子文書やデータに対する電子署名を偽造することが可能となるため、他人へのなりすましやマルウェアの配布、電子契約書の改ざんなどが行われる危険があります。
今後、量子コンピューターが登場することにより、現在使用されている暗号が現実的な時間内で解読されてしまうことで安全性が損なわれる可能性があり、アメリカ国立標準技術研究所（以下 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）の実用化にも取り組んでいます。今後も、通信サービスに必要不可欠な暗号技術の取り組みを通じて、お客さまが安全安心なサービスを利用できる環境を提供していきます。