Conversation

Notices

Masanori Ogino ???? (omasanori@mstdn.maud.io@mstdn.maud.io)'s status on Saturday, 16-Feb-2019 13:07:30 JST Masanori Ogino ????

共通鍵暗号は十分大規模・高性能な量子コンピューターによってセキュリティレベルが半分になるといわれているけれど、それなら鍵長を倍にすればいいので公開鍵暗号ほどの大きな転換は必ずしも必要ではない

In conversation Saturday, 16-Feb-2019 13:07:30 JST from mstdn.maud.io permalink
- Masanori Ogino ???? (omasanori@mstdn.maud.io@mstdn.maud.io)'s status on Saturday, 16-Feb-2019 13:36:35 JST Masanori Ogino ????
  - 名前欄には名前を書こうキャンペーン
  @ltzz 「セキュリティレベルが半分になる」というのは具体的には量子コンピューター上でN個の候補に対して時間計算量O(N^(1/2))の探索アルゴリズムであるGroverのアルゴリズムを総当たり攻撃に応用することを指していて、鍵長lに対して鍵候補が2^l個となることを踏まえるとここでいうセキュリティレベルと鍵長がそのまま対応することがわかります。
  ただし、これはどの暗号アルゴリズムに対しても同じ関係が成り立つという話ではありませんし、特定の共通鍵暗号に対して量子コンピューター上でもっと効率的な攻撃が今後見つかる可能性がないと保証されているわけでもありません（古典コンピューター上でそうであるのと同様）
  
  In conversation Saturday, 16-Feb-2019 13:36:35 JST permalink
  
  Masanori Ogino ???? repeated this.
- Masanori Ogino ???? (omasanori@mstdn.maud.io@mstdn.maud.io)'s status on Saturday, 16-Feb-2019 13:38:15 JST Masanori Ogino ????
  in reply to
  - 名前欄には名前を書こうキャンペーン
  @ltzz もっと端的に書けば「共通鍵暗号に限って、現時点では、はい」
  
  In conversation Saturday, 16-Feb-2019 13:38:15 JST permalink
- Masanori Ogino ???? (omasanori@mstdn.maud.io@mstdn.maud.io)'s status on Saturday, 16-Feb-2019 13:51:33 JST Masanori Ogino ????
  - 名前欄には名前を書こうキャンペーン
  @ltzz 探索問題についてはそうですね
  
  In conversation Saturday, 16-Feb-2019 13:51:33 JST permalink
- Masanori Ogino ???? (omasanori@mstdn.maud.io@mstdn.maud.io)'s status on Saturday, 16-Feb-2019 14:00:55 JST Masanori Ogino ????
  - 名前欄には名前を書こうキャンペーン
  @ltzz というよりは、量子コンピューターはあらゆる問題を劇的に簡単にするというわけでもないし、量子コンピューターが古典コンピューターに比べて計算量複雑性の観点からどうなのかという点については未解決問題もまだ残っているし、まるであらゆる暗号がとても近い将来壊されるかのように怯えている人もいるけれど現時点でそういう結論は出ていないし……という気持ちですね
  
  In conversation Saturday, 16-Feb-2019 14:00:55 JST permalink
- Masanori Ogino ???? (omasanori@mstdn.maud.io@mstdn.maud.io)'s status on Saturday, 16-Feb-2019 14:04:55 JST Masanori Ogino ????
  in reply to
  - 名前欄には名前を書こうキャンペーン
  @ltzz 先程の説明後半部は「あらゆる暗号系はビット数を倍にするだけで量子コンピューター時代でも問題なく使える」という誤解を防ぐためのもので……
  
  In conversation Saturday, 16-Feb-2019 14:04:55 JST permalink
- Masanori Ogino ???? (omasanori@mstdn.maud.io@mstdn.maud.io)'s status on Saturday, 16-Feb-2019 14:25:11 JST Masanori Ogino ????
  - 名前欄には名前を書こうキャンペーン
  @ltzz 共通鍵暗号以外だと、Shorのアルゴリズム（とその変形）で素因数分解（RSA）や離散対数問題（（EC）DH、（EC・Ed）DSA）を多項式時間で解けることが分かっていて、最近ポスト量子暗号が盛んなのはこれらの置き換えが現実的な課題になってきたためですね
  
  In conversation Saturday, 16-Feb-2019 14:25:11 JST permalink

Public

Notices

Feeds