概略とLocking scheme
1. ZKPCPとの比較
ZK-PCP・・・任意の(悪意ある)検証者の見解を小さな統計的距離まで効率的にシミュレートできる +PCP標準的な定義
↔︎PCPモデルは証明者の力を弱くするので、健全性は上がるが、ゼロ知識を達成するのは困難
→→→Bounded Query ZK-PCPの考案
悪意のある検証者を持ちながら、先の制限を回避し安全性のあるZK-PCPが考案された。
2値アルファベット上の多項式長のPCPを、ゼロ知識で、固定多項式回しか質問できない悪意のある 検証者に対して、無視できるほどの健全性エラーを持つ。
2.スケールアップできる
NEXP言語の場合にもこの構築をスケールアップでき、任意の多項式時間の検証者に対し健全性が 保持されるZK-PCPが得られる。このPCPオラクルはNP言語であるが、多項式時間で計算できない。 (ランダム性、入力、NP-witness、検証者のqueryから多項式時間で計算可能な関数を出力すること はできない。)
3.Locking Scheme
ZKPCPプロトコルの中核をなすのがLocking Scheme
内容；
送信者は秘密の w を保持し，ランダムに効率的な受信機は、オラクルσwへのアクセスによってwの情報を知ることはできません。一方で送信者は後で受信者にキーを送信して値 w を破棄することができます。
また、構築した後で、送信者が値 w を変えることができない。
元ネタは、Moni Naor. Bit commitment using pseudorandomnessに載っています。
4.応用例
非常に効率的な検証（正直な検証者の仕事に相当）と、多数の共謀サーバの存在下での秘密保持（悪意のある検証者の有界問い合わせに相当）を同時にサポートする方法で、NP-witnessを多数のサーバ間で分散させるという目標を考えることができる。
プロトコル
パーティは疑似乱数生成器 f : {0, 1}n→ {0, 1}3n にアクセスすることができ、プロトコルは以下のように動作する。
受信者はランダムな「シフト」r ← {0,1}rを選択し、それを送信者に送信する。
秘密の入力ビット b を保持している送信者は、ランダムなシード s ← {0,1}n を選択し、f(s) + b - r = t を受信者に送信します (加算と乗算はバイナリフィールド上で成分的に行われます)。
デコミットメントの段階では、送信者は単に(b,s)を受信者に送信し、受信者は f(s) + b - r = t がデコミットされた値を受け入れるために保持されていることを確認します。
