Classic McEliece暗号解読の世界記録（次元）の推移と計算量
KDDIとKDDI総合研究所は12月26日、暗号解読コンテスト「Challenges for code-based problems」において、次世代暗号として標準化が進められているClassic McElieceの1409次元の暗号解読にKDDI総合研究所が世界で初めて成功し、11月13日に世界記録を更新したことを発表した。
1409次元の暗号は10の56乗（＝100兆×100兆×100兆×100兆）通りの解の候補が存在し、総当たりでは解読に1兆年以上かかるとされてきた。今回、両社は独自の解読アルゴリズムで計算対象を大幅に絞り込み、およそ2700万の解読処理を同時に実行できる並列コンピューティング環境を構築・活用することで、29.6時間で暗号を解読。これまで1347次元だった世界記録を更新した。
これにより、1409次元の暗号を解読するために必要な計算量（処理の繰り返し回数）が2の63乗であることを実証し、この次元を上回れば暗号の解読が困難という目安である暗号の強度を突き止めた。
暗号処理の並列実装最適化技術を開発
近年、量子コンピューターの登場により、将来的には暗号強度が不足する可能性が指摘されている。アメリカ国立標準技術研究所（NIST）は、量子コンピューターに耐えうる耐量子暗号の検討を進めており、その方式の一つであるClassic McElieceでは、現在、3488次元以上の暗号が標準候補として提案されている。
暗号の強度は、暗号解読に必要な計算量が指標となり、計算量を把握し、安全性と性能を両立する耐量子暗号の最適な次元を導出することが重要となる。国際的な暗号解読コンテストも開催され、次世代暗号を研究する企業や団体はより高速な暗号解読手法の開発を進めている。KDDI総合研究所も暗号解読コンテストに参加し、世界記録を9回更新している。
今回の成果は、Classic McEliece暗号が耐量子暗号として成り立つ次元を精緻に見積もるための指標を明らかにしたもので、安全な鍵長の選択や適切な鍵の交換時期を試算する技術的根拠として、各国の政府機関や国際標準化機関において活用される。
週刊アスキーの最新情報を購読しよう
本記事はアフィリエイトプログラムによる収益を得ている場合があります