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

世界初、540次元の符号暗号を解読!

~符号暗号解読コンテスト全体を通じ、最も困難な問題の解読に成功~

2022年2月9日
株式会社KDDI総合研究所

株式会社KDDI総合研究所(本社:埼玉県ふじみ野市、代表取締役所長:中村 元、以下「KDDI総合研究所」)は、2022年2月1日、暗号解読コンテスト「Challenges for code-based problems(注1)」において、540次元のSyndrome Decoding(以下「SD」)問題を世界で初めて(注2)解読しました。
540次元のSD問題は、同コンテスト全体を通じ、これまで解読された問題の中で、解読に最も大きな計算量を必要とする(注3)問題です。解読にあたり、KDDI総合研究所は、解読アルゴリズム処理やデータ構造を最適化するとともに、GPUサーバー1台当たり約600万のマルチスレッド・マルチコア並列化を行いました。その結果、通常の解読アルゴリズムの226倍の処理速度を達成し、540次元のSD問題の解読に79日で成功しました。

 

 

 

図:解読アルゴリズムの概要

 

 

公開鍵暗号(注4)技術はインターネットをはじめとする情報通信システムの安心・安全を支える基盤技術であり、ネットショッピングやICカードなどで日常的に利用されています。現在最も広く利用されているRSA暗号も公開鍵暗号方式であり、大きな数の素因数分解の困難性をその安全性の根拠としています。しかし近年、実用的な量子コンピューターの登場により、素因数分解が高速に計算できるようになり、今後は量子コンピューターに対しても安全性を確保できる公開鍵暗号方式が必要とされてきます。米国では、アメリカ国立標準技術研究所が主導する耐量子暗号の標準化プロジェクト(NIST-PQC)において、次世代の公開鍵暗号の選定が進められています。

 

今回KDDI総合研究所が解読したSD問題は、係数、定数項および解が0と1のみで構成される多元連立1次方程式です。また、解における「1」の個数は問題ごとに与えられている定数以下となる必要があります。この問題は量子コンピューターを用いても効率的に解読できないとされており、その難しさは、NIST-PQCの最終候補に選定されたClassic McEliece暗号を含む符号暗号(注5)の安全性の根拠となっています。安全な符号暗号を実現するためには、SD問題の次元(未知変数の個数)を高め、解読を困難にする必要がありますが、次元が大きすぎると暗号の処理時間が増大します。このため、安全性が確保される最適な次元を求めるために、高速な解法の研究が進められています。

 

本成果は、次世代公開鍵暗号として符号暗号を利用する際に、安全な次元の大きさを決めるための非常に重要な情報となります。KDDI総合研究所は、安心して利用できる情報通信システムの構築に貢献するため、引き続き解読アルゴリズムの高速化検討を進めるとともに、より高速で安全な次世代公開鍵暗号実現に向けた研究開発を推進していきます。

 

【関連する研究成果】
「世界初、510次元の符号暗号を解読!~10の80乗通りの候補が存在する前人未到の問題を、約593時間で成功!~」(2021年9月30日発表)
・2021年10月27日に、530次元のSD問題の解読に成功
Syndrome Decoding Problem

 

【KDDI総合研究所の取り組み】
KDDIとKDDI総合研究所は、2030年を見据えた次世代社会構想「KDDI Accelerate 5.0」を策定し、その具体化に向け、イノベーションを生むためのエコシステムの醸成に必要と考えられる「将来像」と「テクノロジー」の両面についてBeyond 5G/6Gホワイトペーパーにまとめました。両社は新たなライフスタイルの実現を目指し、7つのテクノロジーと、それらが密接に連携するオーケストレーション技術の研究開発を推進します。
今回の成果は7つのテクノロジーの中の「セキュリティ」に該当します。

 

 

 

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

 

(注2)2022年2月1日時点。
世界記録が掲載されたウェブサイト
Syndrome Decoding Problem

 

(注3)2022年2月1日時点。Finding Low Weight Codewords問題の解読に要する計算量は独自の分析による。今回解読したSD問題を含む、その他4種類の問題の解読に要する計算量はコンテスト主催者による公表に基づく。

 

(注4) 二つの鍵(AとA')を作成し、一方の鍵Aで暗号化し、もう一方の鍵A’で復号するという仕組み。自分あてに情報を送るための暗号化用の鍵(A)は世間に広く公開しておき(公開鍵)、その鍵(A)を使って暗号化して送ってもらう。復号するためには、公開してある鍵ではないもう一方の鍵(A’)で復号する。この復号するための鍵(秘密鍵)は復号する本人しか知らないので、復号できるのは本人のみとなる。この二つの鍵は、数学的な関係があるので、関係のない他の鍵で復号することはできない。RSA暗号や楕円曲線暗号などが主流となっており、ネットショッピングにおける個人情報のやり取りなどに使われている。

 

(注5) SD問題など符号理論に関連する問題を安全性の根拠とする公開鍵暗号方式。次世代公開鍵暗号の有力な候補の一つで、現在最も広く使用されているRSA暗号よりも安全かつ高速な方式として期待されている。符号暗号は、シンプルな演算による暗号の処理が可能であり、かつ並列化による高速化も容易である。このため、特に処理能力に制約のあるIoT機器や組み込み機器などへの搭載が期待されている。

 

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