このページを印刷する
- 先端技術研究所
世界初、570次元の符号暗号を解読！
～符号暗号解読コンテスト全体を通じ、最も困難な問題の解読に成功～
2023年4月21日
株式会社KDDI総合研究所
KDDI総合研究所は、2023年4月17日、暗号解読コンテスト「Challenges for code-based problems（注1）」において、570次元のSyndrome Decoding（以下「SD」）問題を世界で初めて（注2）解読しました。
570次元のSD問題は、同コンテスト全体を通じ、これまで解読された問題の中で、解読に最も大きな計算量を必要とする（注3）問題です。解読にあたり、KDDI総合研究所は、解読アルゴリズム処理やデータ構造を最適化するとともに、GPUサーバー1台当たり約1300万のマルチスレッド・マルチコア並列化を行いました。その結果、570次元のSD問題の解読に45日で成功しました。
図：解読アルゴリズムの概要
本成果は、次世代公開鍵暗号として符号暗号を利用する際に、安全な次元の大きさを決めるための非常に重要な情報となります。KDDI総合研究所は、継続して難関の暗号解読コンテストに挑戦することで、解読アルゴリズムの高速化検討を進めるとともに、より高速で安全な次世代公開鍵暗号実現に向けた研究開発を推進していきます。
【関連する研究成果】
・「世界初、510次元の符号暗号を解読！～10の80乗通りの候補が存在する前人未到の問題を、約593時間で成功！～」（2021年９月30日発表）
・「世界初、540次元の符号暗号を解読！～符号暗号解読コンテスト全体を通じ、最も困難な問題の解読に成功～」（2022年2月9日発表）
【KDDI総合研究所の取り組み】
KDDIとKDDI総合研究所は、2030年を見据えた次世代社会構想「KDDI Accelerate 5.0」を策定し、その具体化に向け、イノベーションを生むためのエコシステムの醸成に必要と考えられる「将来像」と「テクノロジー」の両面についてBeyond 5G/6Gホワイトペーパーにまとめました。両社は新たなライフスタイルの実現を目指し、7つのテクノロジーと、それらが密接に連携するオーケストレーション技術の研究開発を推進します。
今回の成果は7つのテクノロジーの中の「セキュリティ」に該当します。
【参考】
・公開鍵暗号技術：
インターネットをはじめとする情報通信システムの安心・安全を支える基盤技術であり、ネットショッピングやICカードなどで日常的に利用されています。現在最も広く利用されているRSA暗号も公開鍵暗号方式であり、大きな数の素因数分解の困難性をその安全性の根拠としています。しかし近年、実用的な量子コンピューターの登場により、素因数分解が高速に計算できるようになり、今後は量子コンピューターに対しても安全性を確保できる公開鍵暗号方式が必要とされてきます。米国では、アメリカ国立標準技術研究所が主導する耐量子暗号の標準化プロジェクト（NIST-PQC）において、次世代の公開鍵暗号の選定が進められています。
・SD問題：
係数、定数項および解が0と1のみで構成される多元連立1次方程式です。また、解における「1」の個数は問題ごとに与えられている定数以下となる必要があります。この問題は量子コンピューターを用いても効率的に解読できないとされており、その難しさは、NIST-PQCの最終候補に選定されたClassic McEliece暗号を含む符号暗号（注4）の安全性の根拠となっています。安全な符号暗号を実現するためには、SD問題の次元（未知変数の個数）を高め、解読を困難にする必要がありますが、次元が大きすぎると暗号の処理時間が増大します。このため、安全性が確保される最適な次元を求めるために、高速な解法の研究が進められています。
（注1） フランス国立情報学自動制御研究所（INRIA）が主催する符号暗号に関する暗号解読コンテスト。2019年7月21日にウェブサイトが公開され、コンテストが開始された。KDDI総合研究所が解読したSD問題を含む計5種類の問題が出題され、世界中の暗号研究者が参加している。
Welcome to the code-based challenges webpage!
（注2）2023年4月17日時点。
世界記録が掲載されたウェブサイト
Syndrome Decoding Problem
（注3）2023年4月17日時点。Finding Low Weight Codewords問題の解読に要する計算量は独自の分析による。今回解読したSD問題を含む、その他4種類の問題の解読に要する計算量はコンテスト主催者による公表に基づく。
（注4） SD問題など符号理論に関連する問題を安全性の根拠とする公開鍵暗号方式。次世代公開鍵暗号の有力な候補の一つで、現在最も広く使用されているRSA暗号よりも安全かつ高速な方式として期待されている。符号暗号は、シンプルな演算による暗号の処理が可能であり、かつ並列化による高速化も容易である。このため、特に処理能力に制約のあるIoT機器や組み込み機器などへの搭載が期待されている。
※ニュースリリースに記載された情報は、発表日現在のものです。 商品・サービスの料金、サービス内容・仕様、お問い合わせ先などの情報は予告なしに変更されることがありますので、あらかじめご了承ください。