ゼロ知識証明について

りばー @river_jpn

ゼロ知識証明って通信系列が秘密なしでも生成できるから秘密情報を何も漏らしてないって説明されて、だいたいそれで納得するんだけど、じゃあなんで相手が秘密を知っていたということはわかってしまうの？なんでそれ以外のことは何もわからないって言い切れるんですか。

りばー @river_jpn

単なる情報と、誰がどういう情報を持っているかという情報は別の階層のものだから別々に考えないといけないということかな。よくわからなくなってきた起床10分後。

りばー @river_jpn

以前聞いた問題で、「囚人が100人いて赤か白の帽子をかぶせられているが自分のは見えず他の人のは見える。自分の色がわかったら毎日1度だけある決まった時間に王様に報告にいけば釈放される。（ほかの人が報告に行ったかは見える）ここで、実は囚人は全員赤の帽子をかぶされていたとする。（続く）

りばー @river_jpn

そして王様は初めに『この中に少なくとも1人は赤の帽子をかぶっている人がいる』と言いました。このあとどうなるでしょう？」（ただし囚人は十分賢く、釈放を望んでいるものとする）

りばー @river_jpn

はじめから「少なくとも1人は赤がいること」なんてほかの人を見れば全員が知ってるはずなのに、その情報によって状況が動くのはおかしいのではないか？情報理論的にいうとどうなるの？（情報理論無知勢）

ymd.sht @iedcba

@river_jpn この問題二通りの矛盾した解答例（情報増えてないから何も起きないor数学的帰納法っぽく考えて全員釈放）があってどっちが本当か本気でわからないんだけど。もしわかるなら解説してくれますか？

りばー @river_jpn

@iedcba たぶん帰納法的に100日後に全員釈放が正解。はじめの状態では他人が赤が一人以上いるという情報を持っていることの情報がなかったのに対し、王様の発言により全員がその情報を持っているという情報が得られるので情報は増えている。なんかちょっと釈然としませんが。

ymd.sht @iedcba

@river_jpn うーん、やっぱちょっと釈然としないですね、、王様の発言によって情報が増えてないような気がします。

りばー @river_jpn

@iedcba 誰がどれくらい情報を持っているかの情報を情報とよんでよいのならば増えてますよね。

りばー @river_jpn

@iedcba あ、ちょっと勘違いしてました。それをさらに高階層化していけぱ。

ymd.sht @iedcba

@river_jpn 赤が少なくとも一人はいることは全員が知っている、ということは全員知っているよね。高階層化というのは、知っていることを知っていることを知っている、というような感じ？

りばー @river_jpn

@iedcba 三人の例で言えば、はじめはAは「CがBが赤が一人以上いることを知っていることを知っていること」の情報がないのに対し、王様の発言によりそれが保証される。

りばー @river_jpn

@niwasaa それで正解なんですが、はじめからみんな赤が一人以上いることは知っているはずなのに、なぜそのヒントだけで自分のがわかってしまうのかというパラドックス的な問題なのです。

ymd.sht @iedcba

@river_jpn なるほど、ありがとう。結構考えたらわかってきた気がします。一般の場合の完全な理解はしてないけど。その解答はリバークワーティ君オリジナルのもの？

りばー @river_jpn

@iedcba この問題を聞いたときに、出題者の人がこんなニュアンスのことを言ってたのでそれを自分なりに考え直しただけです。

りばー @river_jpn

で、僕はこの囚人の問題とゼロ知識証明の話がちょっと似てると思ったんだけどどうなんでしょうね。

あんごうりろんトラベラー @sj_green_eyed

@river_jpn 秘密を知っていたことは検証式による1bitの情報と健全性から保証される．

あんごうりろんトラベラー @sj_green_eyed

@river_jpn 計算量的ゼロ知識証明だと，秘密以外のことは何もわかっていないと言い切っているというよりは，有意だと識別できる情報が得られないということではないでしょうか．完全ゼロ知識証明だと確率分布が全く同一なのでゼロと言い切れるのですがね．

あんごうりろんトラベラー @sj_green_eyed

@river_jpn 計算量的ゼロ知識証明は，その定義によって1bit以外の情報はもれていないことと同一視しよう，ということなのだと思います．

りばー @river_jpn

@sj_green_eyed まず、完全ゼロ知識証明のみを考えます。少し違和感を持っているのは「秘密なしでも、実際のプロトコルと全く同じ確率分布の通信系列を生成できるから何の情報も漏らしていない」という理屈の部分です。

りばー @river_jpn

@sj_green_eyed 感覚的にはなんとなく納得はするのですが、だとするとなぜ秘密を知っていたという情報だけは漏れているのか納得できません。

りばー @river_jpn

ゼロ知識証明について考えていたら復号オラクルは秘密鍵の情報を一切漏らさないことの（当然誤った）証明ができてしまった。復号オラクルとのやりとりは、平文を作ってから暗号文を作ることで秘密鍵なしでシミュレート可能なので（ryという感じ。攻撃者の本来のクエリ分布と一致させられない点が誤り

りばー @river_jpn

と、すると、逆に言えば攻撃者のクエリ分布が、ある効率的にサンプル可能な平文分布を暗号化したような分布に従っているとすれば復号オラクルはなんの意味もないということなのかな？自分で書いてて何言ってるかわかんなくなってきたけど。

MarriageTheorem @MarriageTheorem

@river_jpn CCA安全な公開鍵暗号を作るときに「攻撃者が対応する平文を知らない限りvalidな復号クエリは不可能」なように作る、というのはその思想に近いのではないかと思いました。

りばー @river_jpn

@MarriageTheorem なるほど、確かに同じような証明になりますね