Sponsored Contents

KDDI Labsの最新記事

Image credit:
Save

「スパコンでは1万年」の難問をわずか16日間で... KDDIと九大が『60次元LWE問題』を世界初解読

UTSUI JIN
2016年7月20日, 午後04:30 in Kddi Labs
1172シェア
465
426
0
281

連載

注目記事

人気記事

IQOSホルダーに直結して充電できるマグネットアダプターを発見!:電脳オルタナティヴ

IQOSホルダーに直結して充電できるマグネットアダプターを発見!:電脳オルタナティヴ

View


KDDI研究所と九州大学は、ドイツのダルムシュタッド工科大学が主催する暗号解読コンテスト「TU Darmstadt Learning with Errors Challenge」で、誰も解読できなかった60次元のLearning with Errors(LWE)問題を、世界で初めて解読しました。

Other

LWE問題とは、故意に誤差を付加した「多元連立一次方程式」を解くというもの。

この問題を解くことは、次世代公開鍵暗号の有力候補の一つである格子暗号が解読できることに相当するといいます。

この問題は次元(未知変数の個数)を高める or 誤差を大きくし、解読を困難にすることで安全な暗号を実現します。ただ、次元が高すぎると計算時間が増大し、誤差が大きすぎると正しく暗号処理できない確率が上がります。そのため、安全性を担保できる最適な次元と誤差の大きさについて、多くの期間が研究を進めているというわけです。

今回、スーパーコンピューターを用いた、総当たり方式による計算では1万年以上かかる60次元のLWE問題を、KDDI研究所と九州大学は約16日間で解読しました。これは、効率よく解を探す解読アルゴリズムを作り、20台の仮想PCを並列化して処理することで実現しました。また、55次元以下の問題についても解読に成功しています。この成果は、格子暗号を利用する際、安全な次元や誤差の大きさを決める重要な情報となるとしています。

Other

また、本研究成果は10月11日~13日、秋田で開催されるコンピュータセキュリティシンポジウム2016にて報告される予定です。

Source: KDDI研究所
関連キーワード: KDDI Labs
1172シェア
465
426
0
281

Sponsored Contents