【情報】イデアル格子最短ベクトル問題　128次元の暗号解読　次世代公開鍵実用化に寄与/KDDI研・九州大

ＫＤＤＩ研と九大、１２８次元の暗号解読−次世代公開鍵実用化に寄与
掲載日 2013年07月19日

ＫＤＤＩ研究所（埼玉県ふじみ野市、中島康之所長、<電話：引用元参照>）は、
クラウド環境のデータ処理などの安全性を高めると期待される次世代公開鍵暗号研究の一環として、
規則的に並んだ点の集合である「格子」を用いた１２８次元の暗号を九州大学と協力して解読した。
新たな暗号の安全性を高めるために、暗号がどの程度の時間で解読できるかを調べる作業が重要で、
今回の解読も次世代公開鍵暗号の実用化に寄与する。
　
ＫＤＤＩ研は九大と連携し、ドイツのダルムシュタット工科大学が主催する暗号コンテストに参加。
格子暗号を解読する難しさと同等の難易度を持つと考えられ、格子暗号の安全性の根拠となる
１２８次元の「イデアル格子最短ベクトル問題」と呼ばれる問題を解読した。
　
複数のパソコンによる並列処理をしやすくするために共同開発したアルゴリズムを使い、
８４台の仮想パソコンを用いて２週間で解読した。
＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿

▽記事引用元　日刊工業新聞2013年07月19日配信記事
http://www.nikkan.co.jp/news/nkx0220130719bjae.html

▽関連
九州大学　プレスリリース2013年7月19日
次世代暗号を対象とした解読コンテストで世界記録を達成
http://www.kyushu-u.ac.jp/pressrelease/2013/2013_07_19_5.pdf

Σ(ﾟ◇ﾟ；)ﾏｼﾞﾃﾞｯ!?

さっぱり分からん。日本語で記事にしろ

>>3
すっごいよ

1次元が点
2次元は面
3次元は立体

128次元ってどうなってんの？

>８４台の仮想パソコンを用いて２週間で解読した。
実物を84台つないだら遅いの？

>>1
84台で２週間かー実質的には安全かなー

>>6
逆に84台で2週間掛けられたら一巻の終わりじゃね？

暗号の有効期限を1週間にすれば問題無いだろ

PC1台10万として1000万でいけるのか
重要な情報には使えんな

>>8
一週間したら腐るような内容にしか使えないってことじゃん。

つまり、最高難度のセキュリティに転用が可能ということ！
中韓のサイバーテロによる攻撃への防御になる！
今後、日本から技術を盗むことが不可能になるね

>>5

実世界の話じゃないんだから、この場合の次元というのは
独立した要素という意味。

例えばの話。何かの味を表すのに
甘さ、辛さ、塩からさ、酸味、苦味
のパラメータで表現するとしたら、5次元で表現した、となる。

数学で次元というのは、とくに空間の方向を示すというものではない。

さっぱりわからない


実に面白い

>>12
128元方程式って事？

アルゴリズムを公開してからだろ

>>14
方程式なら5次元以上に解はないよ。
層って言ったほうがわかりやすいかな。

>>14
それを言うなら128次方程式。
身近なものではandroidの一筆書きロック画面が低位の格子最短ベクトル問題。

>>16
解はあるだろw
解を求める公式がないだけ

>>18
数値解析なら公式だってあるだろ？代数的に解けないだけ。

おまえらのせいで128元と128次とこんがらがってきたじゃねえか

>>17
128元であってんじゃね？　俺の中高時代と違うの？

2週間で浮気がばれちゃうじゃん。使えない暗号

ほれぇ、相対論終わりましたー

行列の（）の中がものすごいことになってるわけね

> ８４台の仮想パソコンを用いて２週間で解読した。
スパコン使えば数時間で溶けちゃうんじゃない？

>>12
分かった気がする
項目数って理解した

でも明日になったら忘れてそうｗ

セールスマン最短巡回問題とか思い出した

　　　　　　　　　　　　　　　 　 _,,､--――-- ､,
　　　　　　　　　　　　　　　/´::::::::::::::::::::::::::::::::::::｀',
　　　　　 ,r''j´￣ ｀ヽ､　　/::::_;;､--――-- ､;;;:::::::l
　　　　 / /　 　 　 　 ヽ /ﾞ´,,. --―――-- ､,,｀ﾞヽ!
　　　　l /　　　　　　　 |l;:´---;=ｔ;;ｧ┬┬ｔ;;ｫ､､,_｀ヽ|
　　　　l,　　　　　　　　,'::ハ,ﾞ´　　　 ﾉ,､ l, 　 　 ヽ,ﾞl::〉‐､
　　　　人 　 　 　 　 ノ '　　ヽ､...　'r'ﾞ　ヽヽ､.... -'　 Y 〈
　　　/ 　 ｀''┬―‐'´ヽ-､ l''ｰ;=､;_―ﾞﾆﾞ-----__,ﾆ''　|　ヽ
　　/　　　　　 ｀''ｰ､,､　　｀ト-!､__|￣Τ￣｢￣|__,/　 j　 ﾉ
　./　　　,　　　　　/　,､ 　 ﾊ;ト ､,.二,＾,二,二´,./　　/-ﾍ
　|　　　　｀''ー---|. 〈　ヽｲ　＼､L.,,__|__,,.｣...／ 　 ,ｲ:::::::::ﾞi,
　|　　　　　　　　 ,ハ､,Уヽヽ､.｀''ー---‐''ﾞ´ _,,／/|:::::::::::: l,
　 ＼　 ''ー――'　）/::l　　 V:::｀`ヽ､＿,,. -'´l　／ .|:::: _,､-┘
　 　 ト､,＿＿ ,∠／::::|　　　.l､:::::::::::::::::::::::::::/´　　 !:::::｀''ｰ-､
　 　l:::::::::::::::::::::| :::::::::::|　　／:::::ヽ､::::::::;､‐'´l,　　　 l::::::::::::::: /
　　,':::::::::::::::::::::::l ::::::::::l　 /:::::::::::::::::￣::::::::::::::｀i　　,'::::::::::::: /
　　!:::::::::::::::::::::::::l ::::::::::|　|:::::::::::::::::::::::::::::::::::::::ﾉ 　 j:::::::::::: /
　　|::::::::::::::::::::::::::l ::::::::::!./:::::::::::::::::::::::::::::::::::/　 　 !:::::::::: /



電子化されたものは必ず解読される運命にあるのです

>>25
本文読んでないから詳しく分からんけど
わざわざ仮想パソコンを使ってるあたりから推測すると
攻撃者がbotnetを使うこと想定してんじゃね？

真っ当な犯罪者はスパコン用意できないし、
費用対効果が割に合わん

既にIBMからGPLv2でライブラリが出てるんだね。
完全準同型暗号ライブラリ HElib
暗号化したまま乗算・加算とも可能か。便利だな

よくわからん
食えるのか？

>>31
食えない

うおお、すげー！
これ、コンピュータ・アーキテクチャの根本設計概念が一変する革命だぞ！

まじだよすげーよ、これはコンピュータアーキテクチャの根本設計
概念が根底から覆る新発見であり量子暗号の安全性が

>>33
そうなる理由を駄菓子屋の婆ちゃんにもわかるよう教えてくれ

128次元？128ビットと違うの？

>>5
数学的には、変わりない

>>7
一定の期間だけ保てればＯＫ

>>38
この程度のリソースで突破できるなら実用の暗号としては弱すぎて全然ダメだという評価だぞ

解読できることを証明したのか
だめじゃん

で、復号化の演算量は実用的なのか？

>>41
そーゆー核心は本人に直接聞いてくらさいデス

ttp://dl1.getuploader.com/g/Elixir/5286/20130721_180047.jpg

解読する方より強力な暗号を作る方に労力を使えよ

>>44
強力な暗号だと証明する為に解読を試みる必要があるんだろ

実際的には政府の意思決定に重要な役割を持つ人とか
産業で重要な技術にかかわってる人とか、大金持ちとか
そういう人をそれなりの組織がピンポイントで狙えば
暗号は容易く解けるよということで

おいらみたいな貯金もない技術もない低所得者層の
家賃振り込んで残金数万円やら好いた惚れたのメールやら暴いても
かえってコストがかかってしょうがない話ではある

なんか凄そうなのは分かった

１２８次元って事は１２８次元配列なのか？

array[0][1][2][3][4][5][6][7][8][9]・・・・[64]・・・・[128]
って感じの

なんである、アイデアル

やっぱり素数の掛け算を使ったのが最強なの？

量子コンピュータまだか？

PCの進歩は早いからなあ
現時点で解読に天文学的な時間がかかるものじゃないと、
普及する頃にはPC1台で数時間で解読出来るようになってました、って事になりかねない

>>38
＞>>7
＞一定の期間だけ保てればＯＫ

Amazonなどのクラウド借りれば500コアとか簡単に安く使える

仮想パソコンとあるからクラウド使ったんだろうな。
KDDIと共同だからAmazonということはないだろうが。

ここの紙に書け！

アクセラレータは11次元までしか反射できないのにな

>>54
この場合は分散コンピューティングだとおもう
クラウドは大雑把すぎるわ

ああ〜はいはい。イデアル格子最短ベクトル問題ね。
あれはやっかいだよね。
俺も苦労させられたよ。イデアル格子最短ベクトル問題には。

KDDはフロッピーに１分の動画詰め込んだ職人がいる

僕のアナルも解読されそうです

>>57
分散コンピューティングのほうが意味不明

クラウドコンピューティング：コンピュータリソースやサービスをオンデマンドに提供するサービス
分散コンピューティング：複数のコンピュータで並列処理

クラウドで８４台用意して共同開発したアルゴリズムで分散処理

イデアルとかいう単語がでているうちは
結局、大きな数や多項式が割り切れるかどうかとか、素因数／既約元かどうか
そういう基本的なところは変わらないんだろうな
量子コンピュータが使えるものになってきたらこういう暗号は使い物になるんかね？

イデアルって何だっけ。代数学のところで出てきたような

128次元で、何時間で解読されるから
じゃあ、例えば1000次元なら安全だねみたいなことを見積もるためのコンテストだぞ。

128次元が実用時間で解読されることは想定されている。
最初から解読できない長さでやったら、見積もりができない。

ところでイデアル格子ってなんですか
英語版wikipediaに項目があったから開いてみたけれど
難しすぎてなんだかわからん

>>5
＞ 暗号コンテスト
の募集要項がスパコン使用だったのだと思われ

>>1なるほど！そうだったのか！・・・・・・グーグー

2週間で解読されるようじゃ暗号には使えないか
それともコンテスト用に解きやすい問題を用意したのか

ナンデアル
あイデアル

>>5
ここではベクトルのことだと思う

>>69
次元が一つ増えたら倍かかるとかじゃない？
100次元ぐらいにしたら、解読不可能になるんじゃないかな。

同時に復号不能になったりして

>>55
余白が少ないから（ｒｙ