アカウント名:
パスワード:
凸版と NICT だから、ええかげんなもんは作らんと思うが、ソースを読んでも何がすごいかわからん。そもそも、量子コンピュータってちゃんと定義されてたっけ。
暗号では、秘密鍵を知らないと復号に時間がかかるが秘密鍵を知っていればすぐに復号できるという性質が要求される。この性質を実現するために、答を知らないと解くのにすごく時間がかかって、答をあらかじめ知っていればそれが正しいことをすぐに確認できる問題を使っている。答を知っていればそれが正しいことを確認できるというのは要するにNPで、解くのに時間がかかるというのは、多項式時間で解けるアルゴリズムが知られていないものになる。ところが、それらの問題は、量子計算機が実用化されると答を知らなくてもすぐ解けるようになる可能性がある。素因数分解を使っているものは、ショアのアルゴリズムで解けることが既にわかっている。
今のところNPに属する問題が量子計算機ですぐに解けることがわかっているわけではないけど、将来解法が見つかる可能性を考慮して、NPよりも難しい問題を使いたい。だけど、それは、たとえ答を知っていても正解かどうかの判別に時間がかかることを意味していて、復号に時間がかかってしまい、暗号として役に立たない。じゃ、どうすればいいの、というのが技術的に難しいところ。
それを解決する方法が、与えられた答が正しいかどうかを保証するのには時間がかかるけど、高い確率で当たる(つまり、ある確率で誤る)判断ならすぐにできる方法なら用意されている、という性質を持った問題を使うというもの。どういうことかというと、復号のための式に鍵と暗号文を突っ込むと答は出てくるんだけど、それが本当にもとの文章である保証はない(おそらく実装では、暗号化するときにその式で復号できることを確認するか、確率がものすごく高いものを使うかで復号できることを実質的に保証するのではないかと思う)。復号できていることが保証されたものを出そうとすると、非決定性チューリングマシンでも多項式時間では(多分)解けないというものになっている。
それは一般論だよね?今回のケースは何がすごいの?
今回のケースは、耐量子計算機暗号をICカードに実装しましたって話で、#4352084 もそれはわかってるでしょ。わからないところがあるとしたら耐量子計算機暗号は既存の暗号と比較して何が違うのかという話だと判断するのが普通では。
というか、あなたは、今回のケースが耐量子計算機暗号をICカードに実装しましたって話だとわからなかったのですか?
量子計算機が実用とは言い難い状態で、どのくらいの問題を解けるかも全貌が全然見えてなさそうなのにどうやって安全を確保するのかと思ったらそもそもが不確定な式を使って攻撃側が割り出すべき答えをブラして対処するのか……確かにそれっぽいけど、対応した量子計算手法が登場しない保証はまだ出来ないような気がしてならんね。
既存の暗号でも対応した計算手法が登場しない保証はなかったでしょう。既存の計算機でも使える手法がでてこない保証だってない。
素因数分解が解けるのはわかっているから置き換えは必須で、現状できる範囲で最善の方式を考えるしかなくて、NP よりも難しい問題を使うとするとこれ以外にないのでは。もっといい方法があるというなら提案してみればいいと思う。
訂正。
暗号化するときにその式で復号できることを確認する
ここでは公開鍵暗号を考えていて、暗号化は秘密鍵を知らない人が公開鍵でやるので、確認は不可能だった。とすると、暗号化では確率を高くするんだろうけど、あまりにも確率を高くしすぎると、非決定性チューリングマシンで正しい鍵を使った分岐だけ受理されてそれ以外は却下されちゃうので実質NPに落ちるという問題が生じそう。
暗号化ではなくて電子署名なら、秘密鍵で署名を生成したときにそれが公開鍵で確認できるか検証できるため、この問題は回避できる。この記事では次世代の電子署名方式を採用していると言っていて、対象が暗号化ではなく署名になっているのは、ひょっとするとそれが理由なのか?
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
※ただしPHPを除く -- あるAdmin
で、なにがすごいの? (スコア:0)
凸版と NICT だから、ええかげんなもんは作らんと思うが、
ソースを読んでも何がすごいかわからん。
そもそも、量子コンピュータってちゃんと定義されてたっけ。
Re:で、なにがすごいの? (スコア:0)
暗号では、秘密鍵を知らないと復号に時間がかかるが秘密鍵を知っていればすぐに復号できるという性質が要求される。この性質を実現するために、答を知らないと解くのにすごく時間がかかって、答をあらかじめ知っていればそれが正しいことをすぐに確認できる問題を使っている。答を知っていればそれが正しいことを確認できるというのは要するにNPで、解くのに時間がかかるというのは、多項式時間で解けるアルゴリズムが知られていないものになる。ところが、それらの問題は、量子計算機が実用化されると答を知らなくてもすぐ解けるようになる可能性がある。素因数分解を使っているものは、ショアのアルゴリズムで解けることが既にわかっている。
今のところNPに属する問題が量子計算機ですぐに解けることがわかっているわけではないけど、将来解法が見つかる可能性を考慮して、NPよりも難しい問題を使いたい。だけど、それは、たとえ答を知っていても正解かどうかの判別に時間がかかることを意味していて、復号に時間がかかってしまい、暗号として役に立たない。じゃ、どうすればいいの、というのが技術的に難しいところ。
それを解決する方法が、与えられた答が正しいかどうかを保証するのには時間がかかるけど、高い確率で当たる(つまり、ある確率で誤る)判断ならすぐにできる方法なら用意されている、という性質を持った問題を使うというもの。どういうことかというと、復号のための式に鍵と暗号文を突っ込むと答は出てくるんだけど、それが本当にもとの文章である保証はない(おそらく実装では、暗号化するときにその式で復号できることを確認するか、確率がものすごく高いものを使うかで復号できることを実質的に保証するのではないかと思う)。復号できていることが保証されたものを出そうとすると、非決定性チューリングマシンでも多項式時間では(多分)解けないというものになっている。
Re:で、なにがすごいの? (スコア:2)
それは一般論だよね?
今回のケースは何がすごいの?
Re: (スコア:0)
今回のケースは、耐量子計算機暗号をICカードに実装しましたって話で、#4352084 もそれはわかってるでしょ。わからないところがあるとしたら耐量子計算機暗号は既存の暗号と比較して何が違うのかという話だと判断するのが普通では。
というか、あなたは、今回のケースが耐量子計算機暗号をICカードに実装しましたって話だとわからなかったのですか?
Re: (スコア:0)
量子計算機が実用とは言い難い状態で、どのくらいの問題を解けるかも
全貌が全然見えてなさそうなのにどうやって安全を確保するのかと思ったら
そもそもが不確定な式を使って攻撃側が割り出すべき答えをブラして対処するのか……
確かにそれっぽいけど、対応した量子計算手法が登場しない保証はまだ出来ないような気がしてならんね。
Re: (スコア:0)
既存の暗号でも対応した計算手法が登場しない保証はなかったでしょう。既存の計算機でも使える手法がでてこない保証だってない。
素因数分解が解けるのはわかっているから置き換えは必須で、現状できる範囲で最善の方式を考えるしかなくて、NP よりも難しい問題を使うとするとこれ以外にないのでは。もっといい方法があるというなら提案してみればいいと思う。
Re: (スコア:0)
訂正。
ここでは公開鍵暗号を考えていて、暗号化は秘密鍵を知らない人が公開鍵でやるので、確認は不可能だった。とすると、暗号化では確率を高くするんだろうけど、あまりにも確率を高くしすぎると、非決定性チューリングマシンで正しい鍵を使った分岐だけ受理されてそれ以外は却下されちゃうので実質NPに落ちるという問題が生じそう。
暗号化ではなくて電子署名なら、秘密鍵で署名を生成したときにそれが公開鍵で確認できるか検証できるため、この問題は回避できる。この記事では次世代の電子署名方式を採用していると言っていて、対象が暗号化ではなく署名になっているのは、ひょっとするとそれが理由なのか?