ゼロ知識証明について

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

@river_jpn 乱数テープの固定は必要です．たまたま当たるまで巻き戻しを繰り返してしまうと，健全性を保ったままゼロ知識性を（平均的）多項式時間で証明できなくなる可能性があります．（シミュレータが多項式時間でシミュレーションできない）

りばー @river_jpn

@sj_green_eyed 検証式が成り立ったという情報が得られるのはどちらの世界でも同じで、現実世界ではそれプラス物理的に巻き戻しは不可能という事実を利用して証明者が秘密を知っているとわかるってことだと思うのですが、その事実によりもっと余計なことがわかることはないのでしょうか

りばー @river_jpn

@sj_green_eyed 僕の脳内で検証者のチャレンジが選ばれる空間が多項式（というか定数）のものしかイメージしてなかったからそう思っただけかもしれません。一般にはそうではないのですね。

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

@river_jpn シミュレーションの世界はあくまでゼロ知識性を示すための想像上の世界である，といったほうがいいのかな？ なんかまどまぎの最後のキュウべえのセリフ思い出し始めたｗ

りばー @river_jpn

暗号学的には時間巻き戻す能力はなくても時間を止める能力があれば計算量的な安全性に頼ってる部分は全部破れるな

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

@river_jpn チャレンジ空間が定数だと健全性が成立しませんよ．インチキしようとする証明者はチャレンジをguessすればよいので

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

@river_jpn 健全性が成立しないというのは言い過ぎでしたか．誤り確率が無視出来るほど小さくない，ということです

りばー @river_jpn

@sj_green_eyed 定数のやつを何回も繰り返すということを想定していました

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

@river_jpn あ，それでOKです．そこで乱数テープの固定が重要になります．固定しておけば，途中まで正しく予測したチャレンジを再利用できます．再利用できないとすれば，すべてを一度に正しく予測しなければならなくなり，多項式時間でシミュレーションが終わりません．

りばー @river_jpn

@tkys_007 いや、基本的に巻き戻せるほうが強い。特にdioは定数時間しか止められないから弱い。いくらでも巻き戻せるならそれが最強では。

りばー @river_jpn

@sj_green_eyed 仮想世界では秘密を知らずにできることをするだけで現実世界では秘密を知ってることの証明になるのが少し納得できてないんですよねえ。でもだいぶわかってきました。これ以上聞いても同じ問答を繰り返しそうなのでもう少し考えてみます。何度もありがとうございました！

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

@river_jpn いえいえ．またいつでもどうぞ．

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

さっきの問答で，ゼロ知識証明の論文がFOCS, STOC, FOCSと3度落ちた末のSTOCという伝説の論文であることを思い出した．やはり最初は受け入れがたいというか，納得しにくいのかもしれない．

りばー @river_jpn

買ったきり本棚に放置してあったＧｏｌｄｒｅｉｃｈの本のゼロ知識証明の章を読んでみよう

MarriageTheorem @MarriageTheorem

ゼロ知識証明に関する個人的な理解だと、ゼロ知識性の言わんとしていることは「検証者は、証明者との対話の記録のみを材料として、「自分が秘密に関する情報を得た」と「第三者に客観的に主張する」ことができるか？」ということだと思っている。ゼロ知識性の定義の条件が成り立っている場合、（続）

MarriageTheorem @MarriageTheorem

（続き）検証者が証明者との対話の記録を第三者に見せて秘密の情報を得たと主張しても「お前それ自分一人ででっちあげた偽の記録だろ」と言われてしまい、検証者にはそれを否定する術は無い（シミュレーションが可能なので）。（続く）

MarriageTheorem @MarriageTheorem

（続き）一方、健全性については、証明者が秘密を知っていることを「検証者自身が」納得できればよい。ここで検証者は、（たとえそれを第三者に証明できなくとも）自分自身が正しくプロトコルを実行した事実を知っており、まさにその事実ゆえに証明者が秘密を知っていると納得するのである。

りばー @river_jpn

@MarriageTheorem その理屈だと検証者が（自分自身で）秘密の部分情報を一切得られないことの理由づけにはなってないのではないでしょうか。

MarriageTheorem @MarriageTheorem

なお、ゼロ知識性を「検証者と証明者の対話記録から秘密に関する情報が何も得られない」性質と定式化すると、対話記録には各ラウンドで証明者の応答にかかった時間の情報は記録しない（ことになっている）ので、シミュレータは応答のタイミングのことは気にせずに心おきなく「巻き戻し」できる。（続）

MarriageTheorem @MarriageTheorem

（続き）一方、ゼロ知識性の素朴な説明である「検証者は対話の過程で証明者の秘密の情報を何も得られない」という表現を聞くと、例えば証明者の応答にかかった時間の長短などを考慮に入れてもなお情報が何も漏れないかのように思えるし、そうなると「巻き戻し」なんてとても許されないような（続く）

MarriageTheorem @MarriageTheorem

（続き）気がしてくる。個人的に、ゼロ知識証明がわかりづらい理由の一つは、「素朴な説明」と「定式化された内容」との間に先程のような差異があることなのではないかと想像している。ちなみに、concurrentな場合云々という件は、まさにその「証明者の応答のタイミング」を考慮に（続く）

MarriageTheorem @MarriageTheorem

（続き）入れた、元々の「定式化された内容」よりも「素朴な説明」により近い状況を考えているのだと思えばごく自然な問題意識と言えるのかもしれない。（肝心の論文を読んでいないので勘違いしているかもしれないけど。）

りばー @river_jpn

@MarriageTheorem 「シミュレータは応答のタイミングのことは気にせずに心おきなく「巻き戻し」できる。」の部分がちょっとよくわからないのですがどういう意味ですか？

MarriageTheorem @MarriageTheorem

@river_jpn 多分、そのあたりは先程も書いたようなゼロ知識性についての「素朴な理解」と「実際に定式化された内容」の食い違いに関係するのだろうと思います。「定式化の内容」を噛み砕いてみると、「検証者が実際に証明者と対話した記録」と「シミュレータが独力で生成した記録」とが

MarriageTheorem @MarriageTheorem

@river_jpn @MarriageTheorem （例えば計算量的に）識別不可能、という定義なわけですが、この「識別」は具体的には、前者の記録か後者の記録かわからない記録を識別者が受け取ってどちらの記録か推測する行為なわけです。この識別者は検証者自身ではないはずです、