このページを印刷する
- 先端技術研究所
世界初、510次元の符号暗号を解読！
～10の80乗通りの候補が存在する前人未到の問題を、約593時間で成功！～
2021年9月30日
株式会社KDDI総合研究所
2021年9月19日、KDDI総合研究所は、暗号解読コンテスト「Challenges for code-based problems（注1）」において、510次元のSyndrome Decoding（以下、SD）問題を世界で初めて（注2）解読しました。今回解読した510次元の問題は、2021年1月に解読した1161次元の問題（注3）に比べ次元は低いものの、解の探索空間が広いためより難しい問題となります。解読アルゴリズムの改良と並列マルチスレッド環境の最適化により解読処理を約700倍に高速化し、商用クラウドの8台の仮想PCでも、1台当たりの並列数を約2,000,000とした解読を行うことで、10の80乗（=1垓×1垓×1垓×1垓）通りの候補が存在し、総当たり方式による計算では1億年以上かかる（注4）510次元のSD問題の解読を、約593時間で成功しました。
図：解読アルゴリズムの概要
今回KDDI総合研究所が解読したSD問題は、係数、定数項および解が0と1のみで構成される多元連立1次方程式です。また、解における「1」の個数は問題ごとに与えられている定数以下である必要があります。この問題は量子コンピュータを用いても効率的に解読できないとされており、その難しさは、アメリカ国立標準技術研究所が主導する耐量子暗号の標準化プロジェクト（NIST-PQC）の最終候補に選定されたClassic McEliece暗号を含む符号暗号（注5）の安全性の根拠となっています。安全な符号暗号を実現するためには、SD問題の次元（未知変数の個数）を高め、解読を困難にする必要がありますが、次元が大きすぎると暗号の処理時間が増大します。このため、安全性が確保される最適な次元を求めるために、高速な解法の研究が進められています。今回解読した510次元のSyndrome Decoding問題は、2021年1月に解読した1161次元のSyndrome Decoding in the Goppa-McEliece Settingよりも難しい問題であり、解の候補数は約10の32乗（1京×1京）倍となります。
本成果は、次世代公開鍵暗号として符号暗号を利用する際に、安全な次元の大きさを決めるための非常に重要な情報となります。KDDI総合研究所は、安心して利用できる情報通信システムの構築に貢献するため、引き続き解読アルゴリズムの高速化検討を進めるとともに、より高速で安全な次世代公開鍵暗号実現に向けた研究開発を推進していきます。
<KDDI総合研究所の取り組み>
KDDIとKDDI総合研究所は、経済発展と社会的課題の解決を両立する持続可能な生活者中心の社会「Society 5.0」の実現を加速する、2030年を見据えた次世代社会構想「KDDI Accelerate 5.0」を策定しました。両社は、ネットワーク、プラットフォーム、ビジネスの3レイヤの環境整備を進めると共に、3つのレイヤを支える先端技術となる7つの分野のテクノロジーと、それらが密接に連携するオーケストレーション技術の研究開発を推進します。
今回の成果は7分野のテクノロジーの中の「セキュリティ」に該当します。
（注1） フランス国立情報学自動制御研究所（INRIA）が主催する符号暗号に関する暗号解読コンテスト。2019年7月21日にウェブサイトが公開され、コンテストが開始された。KDDI総合研究所が解読したSD問題を含む計5種類の問題が出題され、世界中の暗号研究者が参加している。
Welcome to the code-based challenges webpage!
（注2）2021年9月20日時点
世界記録が掲載されたウェブサイト
Syndrome Decoding Problem
（注3）2021年1月14日プレスリリース
「世界初、1161次元の符号暗号を解読！
～10の48乗通りの候補が存在する前人未到の問題を、約375時間で成功！～」
（注4）解読アルゴリズムを利用せず、解となりうる全ての可能性を、2021年時点における世界最高性能のスーパーコンピューターで試した場合。
（注5）SD問題など符号理論に関連する問題を安全性の根拠とする公開鍵暗号方式。次世代公開鍵暗号の有力な候補の一つで、現在最も広く使用されているRSA暗号よりも安全かつ高速な方式として期待されている。符号暗号は、シンプルな演算による暗号の処理が可能であり、かつ並列化による高速化も容易である。このため、特に処理能力に制約のあるIoT機器や組み込み機器などへの搭載が期待されている。
※ニュースリリースに記載された情報は、発表日現在のものです。 商品・サービスの料金、サービス内容・仕様、お問い合わせ先などの情報は予告なしに変更されることがありますので、あらかじめご了承ください。