ノート:計算量的安全性を持つ暗号

量子コンピュータで、gloverのリスト探索アルゴリズムを用いると、全ての秘密鍵暗号の総当たり攻撃が数秒以内に出来る、と言われています。

そうなんですか？中途半端な知識をさらしてしまってすみません。

量子コンピュータは専門外なもので…。

ただ、gloverで何でもかんでも解けるというお話はにわかには信じがたいです。

gloverのアルゴリズム提案以後も「量子コンピュータでも解けない事を目指して作られた暗号方式」は幾つも提案されてますし…。

最近の成果なのでしょうか。

あと、公開鍵暗号方式は（公開鍵をも秘密にする事で）かならず秘密鍵暗号方式としても

用いる事ができるので、

秘密鍵暗号が全て解けるのなら公開鍵暗号方式も全て解けるはずですが…。

その辺の事情をご教授願えれば幸いです。

秘密鍵暗号方式も公開鍵暗号方式も、けた数の大きい数字の素因数分解は長い時間をかけなければコンピューターでも解くことができないことを利用しています。しかしながら量子コンピューターはショアのアルゴリズムを使って”ある数値=素因数分解の掛け算の結果”が可逆的に、かつ高速に演算できますのでこれらの暗号は保障できないものとなってしまいます。--Kikukikukikukikukiku 2007年10月17日 (水) 13:56 (UTC)[返信]

公開鍵暗号が素因数分解の安全性のみを根拠にしているというのは、間違いです。たとえば、DSAは離散対数問題を根拠にしています。 Trrlover 2007年10月25日 (木) 16:13 (UTC)[返信]

追加事項：ショアのアルゴリズムを少し改造することで離散対数問題も多項式時間で解く事ができるようになります。詳しくは量子コンピュータ#アルゴリズムをどうぞ。と言うことで、本文にも量子コンピューターにより解けてしまう暗号にDSAも入る必要がありますね。--Kikukikukikukikukiku 2007年10月25日 (木) 16:32 (UTC)[返信]

さらに追加：P≠NP予想#重要性に現代暗号に関する記述がありますが、、P=NPが正しくないのか、あるいは現代暗号の安全性がP≠NP予想に基づいてないのか説明をお願いいたします。--Kikukikukikukikukiku 2007年10月25日 (木) 16:37 (UTC)[返信]

ひとつめについて。その部分は確かに間違っているようです。お詫びします。

ふたつめについて。「全ての」というのは、とても広い言葉です。たとえば、ワンタイムパッドは、原理的に解読不可能です。

大体予想はできていたのですが、下記のような限定した表現であればよろしいですか?

本文追加事項「ただし、現代暗号において素因数分解および離散対数問題を基にして作られている暗号方式はP≠NP予想がP≠NPであること安全性の担保にしているため、この予想がP=NPと証明される場合にあってはこれらの暗号方式の安全性は崩れ去ることになる。」--Kikukikukikukikukiku 2007年10月25日 (木) 16:58 (UTC)[返信]

どうなんでしょうね。そこまで弱くすると、書く意味がないように思います。結局は、素因数分解の困難性を破ればRSAは解けるわけですし、P=NPがそれを含む、というだけのことで。 P=NPが成り立てば計算量的安全性がなくなるのであれば(これは真かどうか知りませんが)、それは書く意味があると思います。Trrlover 2007年10月25日 (木) 17:21 (UTC)[返信]

「公開鍵暗号が素因数分解の安全性のみを根拠にしているというのは、間違い」というご指摘について、このご指摘は正しいのではないでしょうか。まず、ショアのアルゴリズムが離散対数問題にも応用できるからといって、離散対数問題にもとづくDSAを指して「素因数分解を根拠にした暗号」とは言わないと思います。また、公開鍵暗号には、素因数分解問題や離散対数問題以外の問題（ナップザック問題とかラティス問題）にもとづくものもあり、量子コンピュータが実現された場合に公開鍵暗号が全滅するのかどうかは、まだ未解決問題であり、研究途中なのではないかと思っていました。もし結果がでているならば是非お知らせ頂ければと思います。

元々に書かれていた疑問は「秘密鍵暗号は量子コンピュータで解くことができるか？」でした。秘密鍵暗号についても効率的に多項式時間で解くアルゴリズムは見つかっていないのではないでしょうか？こちらもご存知でしたら、お知らせ頂ければと思います。

それと、P≠NP予想と現代暗号の関係についてならば、既にP≠NP予想の項目に記述されていますから、本項目（計算量的安全性）に記載するならば、もっと計算量的安全性の観点にあわせた内容や表現が望ましいと思います。この点で上記のTrrloverさんのご意見に賛成です。時間がとれたらまた記事本文に加筆してみたいと思っていますので、どうぞよろしく。Sina 2007年10月26日 (金) 13:09 (UTC)[返信]

それについてはこちら[1][2][3]をお読みください。なお2番目のホームページに紹介されている別の論文からも裏付けが取れるかと思います。厳密にNP困難の解を含まないNP完全問題に依存する方式であれば量子コンピュータでも難しいのでしょうけれども。--Kikukikukikukikukiku 2007年10月27日 (土) 08:45 (UTC)[返信]

どうもお返事ありがとうございます（一つ目のリンクは [4] が正解ですね？最後のエルがない）。ざっと見てみましたが、

(1つ目のリンク) 差分解読の解説。
(2つ目のリンク) 量子コンピュータの解説と、情報理論的安全性にもとづく電子署名方式の説明。
(3つ目のリンク) CRYPTO2000のレポート。とくに量子公開鍵暗号の解説あり。

ということで、先の疑問に対する答えとして「量子コンピュータが実現された場合に公開鍵暗号が全滅するのか」については、情報理論的安全性にもとづく公開鍵暗号方式や、量子公開鍵暗号があるので、Yes/No を答えるならば No（全滅するわけではない）であり、「秘密鍵暗号は量子コンピュータで解くことができるか」については未解決、ということでよろしいでしょうか。3つめのリンクに「NPはBQPに含まれない」という予想について説明がありますが、もしかしたらこれを否定する結果があるのかと思い、お尋ねしてみましたがそうでもなさそうなので安心(?)致しました。再度、ありがとうござます。Sina 2007年10月27日 (土) 10:28 (UTC)[返信]

ただ、どの方式にしても、情報理論的安全性とそれにあった適切な鍵に基づかなければやはり危険性があるのは十分に分かっていることです。秘密鍵暗号は特に鍵生成や鍵に問題があれば意味はないうえに、何を持って完全とするかは難しいところです。ただ、実装の問題となると秘密鍵暗号もかなり怪しくなる（つまり、ふるいをかけた後、総当りでやってしまえば有限時間内に回答可能）ことには注意が必要です。またNPとBQPの相関はまだ明らかにされていないのが真実であり、NPはBQPに含まれないのは予想の範疇です。これが証明できるとかの問題も解決できてしまうと思いますが。また、公開鍵暗号でも指摘方式以外の多くの方式は消えるでしょう。--Kikukikukikukikukiku 2007年10月27日 (土) 12:32 (UTC)[返信]

追加：この話題とは異なりますがバーナム暗号のノートにもかつて実装の話で疑問になった点を追記しておきましたのでよろしければお読みください。--Kikukikukikukikukiku 2007年10月27日 (土) 12:54 (UTC)[返信]