本稿では、この論文の解説を行います。
ZKPCP
ゼロ知識証明(ZK)の歴史から・・・
1. ZKとNP困難
・NP問題はゼロ知識(ZK)で証明できることが示された[27]
・PSPACE(多項式量のメモリで判定可能な問題のクラス)の下で、任意の言語にも拡張された。[8]
・NP問題のZKProof達成の為にMulti Interactive Prover(MIP)モデルが考案された。MIPモデルで証明できる問題全てに対してのZKプロトコルが作られた。[9]
2. MIPモデルとPCP
・MIPモデル=オラクルが確率的チェック可能な証明(PCP)をコード化し、効率的なランダム化された検証者によって照会されるモデル[23]
Proverとpcpオラクルの違いは、proverは内部状態を維持するので質問に対する答えが、他の質問に依存する可能性があること。
よって、pcpオラクルの健全性(proofが偽ならば検証者は高い確率で偽だと見抜けること)＞悪意のあるproverかも
←PCP定理と関係あり
3. ZKPCPとPCPの比較
・ZK-PCPは任意の(悪意ある)検証者の見解を小さな統計的距離まで効率的にシミュレートできる+PCP標準的な定義
・PCPモデルは証明者の力を弱くするので、健全性は上がるが、ゼロ知識を達成するのは困難。
４. 三色問題のZKプロトコルとその改良
・[19]で、PCP定理を使って改善されたZKプロトコルにより、NPのための多項式長で一定のアルファベットサイズのZK-PCPの性質が3つ示された。
(1)PCPは任意の組の問い合わせをする検証者に対してゼロ知識。
(2)健全性エラーの確率は一定で、zkを維持しながらこれ以上小さくすることはできない。
(3)多項式長を持ち、悪意のある検証者が証明文字列全体を読み込むと、ゼロ知識で無くなる。→任意の多項式時間の検証者に対しては、ゼロ知識でない。
5. 更なる改良
・悪意のある検証者を持ちながら、先の制限を回避し安全性のあるZK-PCPが考案された。[40]
2値アルファベット上の多項式長のPCPを、ゼロ知識で、固定多項式回しか質問できない悪意のある検証者に対して、無視できるほどの健全性エラーを持つ。・・・bounded query ZK
・NEXP言語の場合にもこの構築をスケールアップでき、任意の多項式時間の検証者に対し健全性が保持されるZK-PCPが得られる。このPCPオラクルはNP言語であるが、多項式時間で計算できない。（ランダム性、入力、NP-witness、検証者のqueryから多項式時間で計算可能な関数を出力することはできない。）
本論文の議題と結果
・多項式時間の検証者に対して、統計的にゼロ知識であるNPのための効率的に計算可能なPCPは存在するのか。
結果；存在しない
・効率的なbounded-query ZK-PCPを用いて、Kilian [39]のサブリニア通信ゼロ知識引数構造をブラックボックス化することができる。
Kilianの構築は、衝突に強いハッシュ関数の存在を前提としているが、ブラックボックスではない方法でハッシュ関数を使用する。また、この結果の定数ラウンドの変種と、ランダムオラクルモデルにおける無条件の非対話的変種を得た。
