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

~スーパーコンピューターでも一万年以上かかる問題を、約16日間で解読に成功!~

世界で誰にも解読されていない暗号問題を初めて解読!

2016年7月19日
株式会社KDDI研究所
国立大学法人九州大学

 

株式会社KDDI研究所(本社:埼玉県ふじみ野市、代表取締役所長:中島康之、以下「KDDI研究所」)と国立大学法人九州大学(本部:福岡市西区、総長 久保千春、以下「九州大学」)は、暗号解読コンテスト「TU Darmstadt Learning with Errors Challenge (注1)」において、これまで誰も解読に成功していなかった60次元のLearning with Errors (以下、LWE)問題を、世界で初めて(注2)解読しました。

 

LWE問題は、故意に誤差を付加した多元連立一次方程式を解く問題です。この問題を解くことは、多くの研究機関で研究が進められている格子暗号(注3)が解読できることに相当します。安全な暗号を実現するためには、LWE問題の次元(未知変数の個数)を高め、または誤差を大きくし、解読を困難にする必要があります。しかし、次元が高すぎると計算時間が増大し、誤差が大きすぎると正しい暗号処理が行えない確率が増大します。

 

このため、安全性が確保される最適な次元と誤差の大きさを求めるために、多くの研究機関で高速な解法の研究が進められています。

 

KDDI研究所と九州大学は、この度、解読アルゴリズムの高速化並びに並列化に成功し、商用クラウドの20台の仮想PCを利用することで、スーパーコンピューターを用いた総当たり方式による計算では一万年以上かかる(注4)60次元のLWE問題を、約16日間で解読しました。また、55次元以下の問題についても、KDDI研究所、九州大学により解読できました。

 

本研究成果は、次世代公開鍵暗号(注5)として格子暗号を利用する際に、安全な次元や誤差の大きさを決めるための重要な情報となります。

 

KDDI研究所と九州大学マス・フォア・インダストリ研究所は、引き続き解読アルゴリズムの高速化検討を進めるとともに、より高速で安全な次世代公開鍵暗号実現に向けた研究開発を推進していきます。また、本研究成果は、2016年10月11日~13日に秋田で開催されるコンピュータセキュリティシンポジウム2016にて報告予定です。

 

(注1) TU Darmstadt Learning with Errors Challengeはドイツのダルムシュタッド工科大学が主催するコンテスト。暗号解読をめぐって、世界中の暗号研究者の参加が見込まれる。

https://www.latticechallenge.org/lwe_challenge/challenge.php

 

(注2) 2016年7月19日時点。

 

(注3)格子暗号とは、LWE問題や格子の最短ベクトル問題などを安全性の根拠とする公開鍵暗号方式。次世代公開鍵暗号の有力な候補の一つで、現在使われているRSA暗号や楕円曲線暗号よりも安全かつ高速な方式として期待されている。格子暗号を用いると、暗号文の状態で様々な演算が可能になる完全準同型暗号など実用的な暗号システムを構成することができるため、多くの研究機関で研究が進められている。

 

(注4)解読アルゴリズムを利用せず、解となりうる全ての可能性を、2016年時点における世界最高性能のスーパーコンピューターで試した場合。

 

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

 


別 紙

 

【本件に関するお問い合わせ先】

株式会社KDDI研究所
営業・広報部 広報チーム
E-Mail: inquiry@kddilabs.jp

 

国立大学法人九州大学 マス・フォア・インダストリ研究所 数理IMI秘書室
TEL:092-802-4401

 

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