【入門】ゼロ知識証明（Zero-knowledge Proof）を分かりやすく解説してみた

■証明方法
1 盗賊はどちらかの入口から洞窟に入る。
2 商人がランダムに選んだ入口から出てくるよう盗賊に指示する。
3 盗賊は商人に言われた方の出口から出る。
4 ①～③を繰り返す。

1 完全性（completeness）
証明者の主張が正しいのであれば、検証者はその主張の正しさを高確率で検証できる。

2 健全性（soundness）
証明者の主張が間違っているのであれば、証明者がどのように振る舞ったとしても、検証者はその主張が偽りであることを見抜くことができる。

3 ゼロ知識性（zero knowledge）
検証者が証明者から他の知識（情報）を盗もうとしても、証明者の主張が正しいこと以外の知識（情報）を得ることはできない。

※洞窟の例では、証明者＝盗賊、検証者＝商人となる。

CRSモデル
1 証明者と検証者の間に信頼できる第三者を置く。
2 第三者が「証明に利用するための公開情報」を証明者と検証者に送る。
3 証明者はその公開情報を使って正しい情報を持っているという証明を生成する。
4 証明者は③の証明を一度だけ検証者に送る。
5 検証者は④で送られきた証明を検証する。