ゼロ知識証明 - 基礎から発展的内容まで(1)
https://gyazo.com/85e46e03dd7c3bc7c3c4a61e7b87d5dc
ゼロ知識証明を体系的に理解するには？
学問の文脈的に
計算複雑性理論
確率的アルゴリズム（確率的多項式時間の計算クラス）
対話的証明
ゼロ知識証明
この流れで理解するのが良さそう（大変...)
ゼロ知識証明とは?
ある知識を持っていることを、その知識に関する何の情報も明らかにすることなく証明すること。
ゼロ知識という概念と対話証明 という概念の複合 ⇠ この誕生の経緯を把握していると理解しやすい
#対話証明 ... 確率の導入により従来の計算量のクラスを自然に拡張したもの Prover ... 証明者 知識を持っていることを主張する人
Verifier ... 証明者を検証する人
Set ... 証明者と検証者が共有する知識の体系を表す概念
数独の解を知っていることの証明ならば数独のルール
電子投票で不正が行われていないことの証明ならば電子投票のスキーム
普通 信頼できるSetが仮定される (Set自体がバグってると死ぬ)
という理解だが、厳密ではないかも
ゼロ知識証明の歴史
1982年に論文自体がGoldwasser, Micali and Rackoffにより完成される
1985年３回のリジェクトを経て上記の3人がSTOCで発表
2002年に誕生20周年を記念してGoldwasserがチュートリアル論文を発表
数学を使わない例:
洞窟の比喩
P ... 洞窟の中にある扉を空ける合言葉を知っている
V ... 合言葉を売って売って欲しいと申し出ている
洞窟の比喩の問題設定
PはAにお金を払って合言葉を教えてもらいたいが、Pが嘘をつく可能性がある。逆に、Pが先に教えるとVはカネを払わない可能性がある。お互いに上手く取引をしたい。
つまり、Aは合言葉を教えずにVに本当の合言葉を知っていることを示したい。
洞窟の構造 : (入り口) ============ (扉) =============== (出口=もう一つの入り口)
証明方法
Aはどちらかの入り口から洞窟に入る（コミットメント)
Vはどちらかの入り口をランダムに選び、そこから出てくるようにAに指示する
AはVに言われた方の出口から出てくる
Aが合言葉を知らない場合は = AがVに言われた出口から出てこれる確率は、試行回数をnとすると
$ (\frac{1}{2})^{n}
となり、nが大きければこれは0に近づく。よって、本当の合言葉知っていることを確率的に証明できるが、AはVに「合言葉を知っているかいないか」という1bitの情報しか与えていない
ZCashのトランザクション
PはV(またはVの集団に）トランザクションの内容を明かすことなく、そのトランザクションを確かに自分が提出したことを証明したい
（送金履歴は全く開示したくないが、送金記録を分散的に記録したい）
数学を使う例
平方剰余に関するゼロ知識証明 (Shamir Protocol)
TBD
数独のゼロ知識証明
各種用語
STARK
- Zero-Knowledge Scalable Transparent ARguments of Knowledge)
SNARK
- Zero-Knowledge Succinct Non-Interactive Argument of Knowledge
- ZeroCashの人曰くPracticalな方法らしい@ zeroknowledge fm
- 証明のサイズがSuccinctになることを追求している
コミットメント
証明者が検証者に対して提出する値
チャレンジ
コミットメントを見た検証者が証明者に返却する値
レスポンス
検証者のチャレンジに対して証明者が返却する値
シミュレーション
ゼロ知識性の証明に用いる
秘匿すべき知識を知らなくてもコミットメント -> チャレンジ -> レスポンスのプロセスで生成される情報と同じ情報しか得ることができないということの証明に使う
具体的には、秘匿すべき知識を知らない証明者をシミュレートする存在を仮定するようだ
Commitment -> Challenge -> Responseの3ステップで進む証明の方式をΣ Protocolという
xxx-Protocol
- 〜に対するゼロ知識証明のことをxxx-Protocolという ⇠本当か確認中
- 平方剰余問題に対するゼロ知識証明 ... Fiat-Shamir Protocol
- 離散対数問題に対するゼロ知識証明 ... Schnorr Protocol