アカウント名:
パスワード:
凸版と NICT だから、ええかげんなもんは作らんと思うが、ソースを読んでも何がすごいかわからん。そもそも、量子コンピュータってちゃんと定義されてたっけ。
暗号では、秘密鍵を知らないと復号に時間がかかるが秘密鍵を知っていればすぐに復号できるという性質が要求される。この性質を実現するために、答を知らないと解くのにすごく時間がかかって、答をあらかじめ知っていればそれが正しいことをすぐに確認できる問題を使っている。答を知っていればそれが正しいことを確認できるというのは要するにNPで、解くのに時間がかかるというのは、多項式時間で解けるアルゴリズムが知られていないものになる。ところが、それらの問題は、量子計算機が実用化されると答を知らなくてもすぐ解けるようになる可能性がある。素因数分解
訂正。
暗号化するときにその式で復号できることを確認する
ここでは公開鍵暗号を考えていて、暗号化は秘密鍵を知らない人が公開鍵でやるので、確認は不可能だった。とすると、暗号化では確率を高くするんだろうけど、あまりにも確率を高くしすぎると、非決定性チューリングマシンで正しい鍵を使った分岐だけ受理されてそれ以外は却下されちゃうので実質NPに落ちるという問題が生じそう。
暗号化ではなくて電子署名なら、秘密鍵で署名を生成したときにそれが公開鍵で確認できるか検証できるため、この問題は回避できる。この記事では次世代の電子署名方式を採用していると言っていて、対象が暗号化ではなく署名になっているのは、ひょっとするとそれが理由なのか？
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
私は悩みをリストアップし始めたが、そのあまりの長さにいやけがさし、何も考えないことにした。-- Robert C. Pike
で、なにがすごいの？ (スコア:0)
凸版と NICT だから、ええかげんなもんは作らんと思うが、
ソースを読んでも何がすごいかわからん。
そもそも、量子コンピュータってちゃんと定義されてたっけ。
Re: (スコア:0)
暗号では、秘密鍵を知らないと復号に時間がかかるが秘密鍵を知っていればすぐに復号できるという性質が要求される。この性質を実現するために、答を知らないと解くのにすごく時間がかかって、答をあらかじめ知っていればそれが正しいことをすぐに確認できる問題を使っている。答を知っていればそれが正しいことを確認できるというのは要するにNPで、解くのに時間がかかるというのは、多項式時間で解けるアルゴリズムが知られていないものになる。ところが、それらの問題は、量子計算機が実用化されると答を知らなくてもすぐ解けるようになる可能性がある。素因数分解
Re:で、なにがすごいの？ (スコア:0)
訂正。
ここでは公開鍵暗号を考えていて、暗号化は秘密鍵を知らない人が公開鍵でやるので、確認は不可能だった。とすると、暗号化では確率を高くするんだろうけど、あまりにも確率を高くしすぎると、非決定性チューリングマシンで正しい鍵を使った分岐だけ受理されてそれ以外は却下されちゃうので実質NPに落ちるという問題が生じそう。
暗号化ではなくて電子署名なら、秘密鍵で署名を生成したときにそれが公開鍵で確認できるか検証できるため、この問題は回避できる。この記事では次世代の電子署名方式を採用していると言っていて、対象が暗号化ではなく署名になっているのは、ひょっとするとそれが理由なのか？