ゼロ知識証明について

MarriageTheorem @MarriageTheorem

@river_jpn @MarriageTheorem 何故なら検証者自身はその記録を「自分が作った」（前者）か「別の誰かが作った」（後者）かを知っているのでフェアな識別になりません。こう考えると、ここでの「検証者が情報を得た/得ていない」は、あくまで「検証者以外の人から見て

MarriageTheorem @MarriageTheorem

@river_jpn @MarriageTheorem 「検証者は秘密の部分情報を得た」ように見えるか」という、第三者視点でしか語られていないと思われます。なので例えば、「検証者は実際には秘密の部分情報を得ているけれども、他の誰が見ても検証者は情報を得ていないようにしか見えない」

MarriageTheorem @MarriageTheorem

@river_jpn @MarriageTheorem といった状況をあり得ると考えるかどうか（これは突き詰めると「情報を得る」とは何ぞやという問いになると思います）によって、ゼロ知識性の定義が本当に「検証者が情報を得ていない」ことを意味するのか、の答えが変わるように思います。

MarriageTheorem @MarriageTheorem

@river_jpn @MarriageTheorem ちなみに、もし「検証者は実際には秘密の部分情報を得ているけれども、他の誰が見ても検証者は情報を得ていないようにしか見えない」としたら、検証者はその部分情報を利用しても何ら特になる行動はできない（もしできるなら、それ自体が

MarriageTheorem @MarriageTheorem

@river_jpn @MarriageTheorem 「検証者が情報を得た」ことの客観的証拠となってしまい矛盾する）はずなので、応用上は特に誰も困らないからそれはそれで問題ない、と考えられるのかもしれません。（以上は私の個人的理解なので、一般的な理解と合致するかは不明ですが…）

MarriageTheorem @MarriageTheorem

@river_jpn 例えば、もし仮に本物の対話記録に「今回は証明者が1ミリ秒で返答した」とあって、シミュレータが「1ミリ秒での返答」まで真似ないといけないとしたら、「成功するまで何度も巻き戻す」なんて悠長な真似をできないかも（けど実際はその心配はない）、といった気持ちでした。

りばー @river_jpn

@MarriageTheorem とてもわかりやすい説明である程度納得できるのですが、「検証者はその部分情報を利用しても何ら特になる行動はできない」の部分にやや疑問です。例えば証明者が別の人とその秘密の部分情報を秘密鍵とする暗号通信をしたときに、検証者はそれを盗聴して内容を（続）

りばー @river_jpn

@MarriageTheorem 得ることができるのではないでしょうか。（知るだけ知って何もしなければ客観的証拠は残らないが、明らかに防ぎたい行動）

りばー @river_jpn

@MarriageTheorem そもそも現実世界では巻き戻しは（時間遡行の特殊能力を習得しない限り）できないのではないですかね？

MarriageTheorem @MarriageTheorem

（もし「自分は確かにある情報を得ているのに、そのことを他の誰にも気付かせることができない」という状況が現実に生じたらちょっとしたホラーだなぁ）

MarriageTheorem @MarriageTheorem

@river_jpn その場合、検証者がその別の通信を盗聴して情報を得ても、その得た情報を使ってできる行動はせいぜい「他の何らかの情報を人知れずこっそり得る」ぐらいで、その得た情報を使ってできる行動はせいぜい（以下ループ）、となって結局外界に影響は出ない、という想像をしています。

MarriageTheorem @MarriageTheorem

@river_jpn あの「巻き戻し」というのは、現実の時間の進みを巻き戻すわけではなく、単にシミュレータが実行している「検証者アルゴリズム」の動きを巻き戻すだけ（それ以外の世界は普通に動き続ける、だからconcurrentの状況で困ったことになる）、と理解しています。

りばー @river_jpn

@MarriageTheorem ゼロ知識性の定義では識別者のインプットには通信系列までしか入らず、その後検証者がどんなことをするかはインプットに入らないので、仮に検証者がその後第三者からみても秘密を知ったことがわかる行動をとったとしても定義には矛盾しないのではないでしょうか。

りばー @river_jpn

いったん納得したけどやはりゼロ知識性は第三者からみた性質、という考え方は不自然なきがしてきたなぁ。やはりどんな検証者に対しても秘密の部分情報が漏れないというのが本質なように思う。大体頭の中でまとまってきた。

MarriageTheorem @MarriageTheorem

@river_jpn ここは私が言葉足らずだったと思うのですが、今の話で「検証者が秘密の部分情報を得る」という場合の「情報」は、あくまで「通信系列（対話記録）から得られる」情報を指しているつもりです。仰る通り、ゼロ知識性の定義で現れる識別者は「通信系列」しか見ませんので、（続く）

MarriageTheorem @MarriageTheorem

@river_jpn @MarriageTheorem 検証者が「通信系列」以外の手がかり（例えば実行時間）から情報を得ることは定義と矛盾しません。で、もし仮に「他の誰も気づかないけれども、実は検証者は通信系列から秘密の部分情報を得ている」として、検証者がその情報を基に（続く）

MarriageTheorem @MarriageTheorem

@river_jpn @MarriageTheorem 「第三者からみても秘密を知ったことがわかる行動」を取ったとしたら、「」内の行動そのものが現実とシミュレーションの識別に使えてしまう（シミュレーションの通信系列を基にその行動は取れないはずなので）ことになり矛盾、かと思います。

MarriageTheorem @MarriageTheorem

@river_jpn @MarriageTheorem （細かいことを言うと、計算量的なゼロ知識性の場合には、先程の「第三者からみても秘密を知ったことがわかる行動」がPPTの範囲で表せることを暗に仮定しています。）

りばー @river_jpn

ゼロ知識証明で考えてる仮想世界はシミュレータが時間を多項式分だけ巻き戻せる世界と考えるとちょっとしっくりきた。多項式時間巻き戻せようが、現実世界で多項式時間で解けない問題はやっぱりこの仮想世界でも解けないので、現実世界で多項式時間で求まらない秘密は仮想世界でも求まったらおかしい。

りばー @river_jpn

というわけで検証者が（多項式時間では求まらないような）秘密の部分情報を一切求めることはできないということはわかった。証明者が秘密を知っていること自体は秘密の部分情報ではないのでそれとは矛盾しないからおかしくないということか

りばー @river_jpn

@MarriageTheorem 「」内の行動は識別者（第三者）のインプットには入ってないから矛盾ではないのではないでしょうか？という質問でした。

MarriageTheorem @MarriageTheorem

@river_jpn はい、繰り返しになりますが、「」内の行動は「識別者のインプット」になるわけではなく、それ自身が一つの「識別者」として働く、という論法です。

りばー @river_jpn

いくらでも時間の巻き戻しが可能な世界を考えたら、その世界ではすべての計算可能問題が一瞬で解けることになって、その世界との識別不可能性をいったところで何も言えませんからね

MarriageTheorem @MarriageTheorem

（うん、まぁ、こんなにややこしけりゃ３回リジェクトされるわけだわ、というのが率直な感想）

りばー @river_jpn

@MarriageTheorem 識別者のインプットには「時間」は入らないはずなのにその検証者の「第三者からみても秘密を知ったことがわかる行動」を再現するためには「時間」の情報が必要ということになりませんか？