KDDIおよび九大の研究チーム、「世界で誰にも解読されていない」という暗号問題を初めて解読 26
ストーリー by hylom
手法が凄いのか実装が凄いのか 部門より
手法が凄いのか実装が凄いのか 部門より
KDDI研究所と九州大学の研究チームが、「これまで誰も解読に成功していなかった」という60次元のLearning with Errors(LWE)問題の解読に成功したと発表した。
n次元のLWE問題とは、m×nサイズの行列Aとn×1サイズのベクトルbが与えられた場合にA・x+e=bを満たすxを求めるというものである。Aおよびe、bがすべて既知であれば単純な問題であるが、LWE問題ではAおよびbのみが与えられ、eについては未知(非公開)であることがポイントとなる。
現在、この問題を解くためのコンテスト「TU Darmstadt Learning with Errors Challenge」が行われており、KDDI研究所と九州大学だけが解読に成功している状況だ。このコンテストでは次元数およびeの分散が異なる複数の問題が用意されているが、次元数や分散が多いほど解を得るのが難しく、60次元のLWE問題を解いたのは同チームが初めてだという。
KDDIおよび九州大学が開発した手法についての詳細は明らかにされていないが、分枝限定法という、解を探索しながら条件を満たす解の候補の集合を小さくしていく手法に分類されるもののようだ。
google のポスト量子暗号が破られた か? (スコア:2, 興味深い)
ちょっと前の記事で google がポスト量子暗号 New hope を試験的に採用したってありましたが、あれもこのLWEが解けると解読されます。
実際には、暗号に使うのはもっとずっと大きいサイズの問題だと思うので、すぐさま駄目ってことにはならないのでしょうが、この手法が高い次元でも効率的に枝刈りをしてくれるとすると暗号に使う問題サイズを大きくしないといけないでしょうね。
そうすると、ただでさえ問題なメモリ使用量の問題が悪化しそうですね。
まあ、非専門家なのでこのプレスリリースが吹かしているだけなのか判別つかないですけどね。
Re: (スコア:0)
商用クラウドの20台の仮想PCを利用することで、スーパーコンピューターを用いた総当たり方式による計算では一万年以上かかる(注4)60次元のLWE問題を、約16日間で解読しました。
わずか20台のPCで16日間で解読ですから、これが暗号アルゴリズムの堅牢さの基礎だとすると、素人目にはちょっと心配になりますね。
専門家の見解が聞きたいところです。
ヴォイニッチ写本 (スコア:1)
解読できるのかな
Re: (スコア:0)
山師の作った無意味な羅列を、未だに暗号だと思ってる奴おったんか。
Re: (スコア:0)
亜書みてーなもんか
Re: (スコア:0)
ガセネタ信じられるって幸せだよな
Re: (スコア:0)
あぁ、あれって結論出てたんだっけ?
知らんかったわ。
で、どんな結論なん?
Re: (スコア:0)
悪魔の証明は不可能
Re: (スコア:0)
論理記号が二つだけで関係代名詞が十三重以上の言語も解読してほしい。
Re:ヴォイニッチ写本 (スコア:1)
関係代名詞が何個以上になると人間には理解できなくなるという話をどっかで聞いたっけ・・・
山田正紀さんのSF(エイダか神狩?)だったかな。
Re:ヴォイニッチ写本 (スコア:1)
そもそも
>論理記号が二つだけで関係代名詞が十三重以上
が「神狩り」に出てきた古代文字。
で関係代名詞が七重以上になると人間には理解できない(山田正紀さんによる「神狩り」での創作)
らじゃったのだ
Re:ヴォイニッチ写本 (スコア:1)
おお、そうでしたかすっかり忘れてました。
あらすじも、結末もすっかり忘れてるしいつか読み返さねば。
そして、神狩2も読んでない・・・
Re: (スコア:0)
同じ字面の言葉ででも、一般会話で使われる場合と特定分野の技術用語や学問で使われる場合では意味が大きく異なることがある
というのを知りましょう。
情報処理で言う解読が困難な暗号とは、暗号化の方式は公知という前提で、それでも暗号化に使った鍵がわからないと
解くのに非常に時間がかかるというもの。それをいかに短時間で解く方法を見つけるかというのが研究になる。
その解法は、その暗号方式に依存したもの。他の暗号方式に適用できるものではない。
どんな暗号でも解ける万能解法や万能解読マシーンなんてものは存在しない。
当然、ヴォイニッチ写本のような、そもそもどういうルールで暗号化したのか判っていないようなものは
完全に対象外。
九州大学マス・フォア・インダストリ研究所 (スコア:1)
九州大学はマス・フォア・インダストリ研究所というのを設立したという話でしたが、
数学研究に力を入れている成果が出ているということでしょうか。
もちろん研究者一人一人が頑張らなければどうにもならないですが、組織的な支えが有ると無いとでは大違いでしょう。
日本の研究者の水準は高いので、後は支える側の問題ですね。
KDDI のび太の研究チーム、 (スコア:0)
タイトルを誤読してしまった・・・おのれケブンリッジ大め!
Re: (スコア:0)
✕ケブンリッジ大
○ケブンッリジ だがいく
x=0, e=b ではダメなの? (スコア:0)
タレコミの説明だけだと、
x=0, e=b っていう解でも条件満たしてしまう。
e についての追加の制約がいろいろあるんでしょうね。
eの分散を最小にするのなら、最小二乗法と一緒で、線形時間で解けるし、なんかもっと複雑なんだろうね。
Re:x=0, e=b ではダメなの? (スコア:2)
いえいえ、暗号ですから、bが暗文、xが平文、eが鍵です。
逆に言うと絶対に0を暗号化できない(してはいけない)?
なんか、結構弱鍵とか出てきそうで怖い。
Re:x=0, e=b ではダメなの? (スコア:2, 参考になる)
> いえいえ、暗号ですから、bが暗文、xが平文、eが鍵です。
全然違います
https://en.wikipedia.org/wiki/Learning_with_errors [wikipedia.org]
https://en.wikipedia.org/wiki/Ring_learning_with_errors_key_exchange [wikipedia.org]
LWE problemの定義は以下の通りです
https://www.latticechallenge.org/lwe_challenge/challenge.php [latticechallenge.org]
> The LWE problem is to recover s, given an instance (A, b), where A is an m×n matrix over ℤq and b = As + e is a vector of length m over ℤq. Both the matrix A and the target vector s are sampled uniformly random, while the error vector e is sampled from the Gaussian distribution with parameter σ.
Re: (スコア:0)
自己訂正
線形時間で解けるは、嘘だ。
多項式時間で解ける、、だね。
Re: (スコア:0)
たとえば、大きな数Xを素因数a、bに分解する(X=ab)のに時間がかかるから安全な暗号だ、というときに、
「両辺に0をかければ0=0でもう計算する必要なくね?」
って言い出すくらい的外れ。
あれ? (スコア:0)
私はとっくに解読していたけどね。
Re: (スコア:0)
へー、すごいね
Re: (スコア:0)
夏だな……
submit まだ~? (スコア:0)
口だけなら誰でも言えるわ。
Re: (スコア:0)
私=NSAなら充分あり得そう。