パスワードを忘れた? アカウント作成
12851952 story
スパコン

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および九州大学が開発した手法についての詳細は明らかにされていないが、分枝限定法という、解を探索しながら条件を満たす解の候補の集合を小さくしていく手法に分類されるもののようだ。

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
  • by Anonymous Coward on 2016年07月22日 12時42分 (#3051597)

    ちょっと前の記事で google がポスト量子暗号 New hope を試験的に採用したってありましたが、あれもこのLWEが解けると解読されます。
    実際には、暗号に使うのはもっとずっと大きいサイズの問題だと思うので、すぐさま駄目ってことにはならないのでしょうが、この手法が高い次元でも効率的に枝刈りをしてくれるとすると暗号に使う問題サイズを大きくしないといけないでしょうね。
    そうすると、ただでさえ問題なメモリ使用量の問題が悪化しそうですね。
    まあ、非専門家なのでこのプレスリリースが吹かしているだけなのか判別つかないですけどね。

    • by Anonymous Coward

      商用クラウドの20台の仮想PCを利用することで、スーパーコンピューターを用いた総当たり方式による計算では一万年以上かかる(注4)60次元のLWE問題を、約16日間で解読しました。

      わずか20台のPCで16日間で解読ですから、これが暗号アルゴリズムの堅牢さの基礎だとすると、素人目にはちょっと心配になりますね。
      専門家の見解が聞きたいところです。

  • by nemui4 (20313) on 2016年07月22日 8時06分 (#3051421) 日記

    解読できるのかな

    • by Anonymous Coward

      山師の作った無意味な羅列を、未だに暗号だと思ってる奴おったんか。

      • by Anonymous Coward

        亜書みてーなもんか

      • by Anonymous Coward

        ガセネタ信じられるって幸せだよな

        • by Anonymous Coward

          あぁ、あれって結論出てたんだっけ?
          知らんかったわ。
          で、どんな結論なん?

    • by Anonymous Coward

      論理記号が二つだけで関係代名詞が十三重以上の言語も解読してほしい。

    • by Anonymous Coward

      同じ字面の言葉ででも、一般会話で使われる場合と特定分野の技術用語や学問で使われる場合では意味が大きく異なることがある
      というのを知りましょう。

      情報処理で言う解読が困難な暗号とは、暗号化の方式は公知という前提で、それでも暗号化に使った鍵がわからないと
      解くのに非常に時間がかかるというもの。それをいかに短時間で解く方法を見つけるかというのが研究になる。
      その解法は、その暗号方式に依存したもの。他の暗号方式に適用できるものではない。
      どんな暗号でも解ける万能解法や万能解読マシーンなんてものは存在しない。

      当然、ヴォイニッチ写本のような、そもそもどういうルールで暗号化したのか判っていないようなものは
      完全に対象外。

  • by Anonymous Coward on 2016年07月22日 21時50分 (#3051930)

    KDDI研究所と九州大学マス・フォア・インダストリ研究所は、引き続き解読アルゴリズムの高速化検討を進めるとともに、より高速で安全な次世代公開鍵暗号実現に向けた研究開発を推進していきます。

    九州大学はマス・フォア・インダストリ研究所というのを設立したという話でしたが、
    数学研究に力を入れている成果が出ているということでしょうか。

    もちろん研究者一人一人が頑張らなければどうにもならないですが、組織的な支えが有ると無いとでは大違いでしょう。
    日本の研究者の水準は高いので、後は支える側の問題ですね。

  • by Anonymous Coward on 2016年07月22日 10時31分 (#3051513)

    タイトルを誤読してしまった・・・おのれケブンリッジ大め!

    • by Anonymous Coward

      ✕ケブンリッジ大
      ○ケブンッリジ だがいく

  • by Anonymous Coward on 2016年07月22日 10時32分 (#3051515)

    タレコミの説明だけだと、
    x=0, e=b っていう解でも条件満たしてしまう。
    e についての追加の制約がいろいろあるんでしょうね。
    eの分散を最小にするのなら、最小二乗法と一緒で、線形時間で解けるし、なんかもっと複雑なんだろうね。

  • by Anonymous Coward on 2016年07月22日 11時33分 (#3051553)

    私はとっくに解読していたけどね。

typodupeerror

吾輩はリファレンスである。名前はまだ無い -- perlの中の人

読み込み中...