KDDI・九州大学、暗号解読コンテストで世界記録を達成

株式会社KDDI研究所と国立大学法人九州大学は、暗号解読コンテスト「Thechnische Universitat Darmstadt Ideal Lattice Challenge」において、総当たり方式による計算では数万年かかるといわれている128次元のイデアル格子最短ベクトル問題を解読し、世界記録を達成した。

イデアル格子とは、格子暗号に利用される格子の種類の1つであり、暗号化処理を高速化し鍵長を削減できる方式として、特に注目を集めている。イデアル格子最短ベクトル問題は、このイデアル格子を対象としており、次元が増えるにしたがって難しくなる。今回、効率的な並列処理が困難とされていた解読アルゴリズムの高速化並びに並列化の開発に成功し、128次元のイデアル格子最短ベクトル問題を、商用クラウドの84台の仮想PCを利用して、約2週間で解読した。

本研究成果は、次世代公開鍵暗号として格子暗号を利用する際に、安全な鍵の長さを決めるための重要な情報となる。

■ニュースリンク先
http://www.kyushu-u.ac.jp/pressrelease/2013/2013_07_19_5.pdf