NPに対するゼロ知識証明
あるNP完全である言語のゼロ知識証明システムを構築すれば、任意のNP言語のゼロ知識証明システムを構築できます。さらに大抵のステートメントは「NP言語の要素である」というステートメントに変換できるため、NP完全のゼロ知識証明システムを構築することは有用です。
この章では、NP完全であるグラフ三彩色問題（graph 3-coloring problem）を例に取り、グラフ三彩色に対するゼロ知識証明システムを構成します。まずは、前提知識となるコミットメントスキームについて説明します。
コミットメントスキーム
コミットメントスキームとは、ある値を秘匿したままコミットし、後でその値をオープン（公開）できるプロトコルです。コミット時の値を変更することはできません。特にその値がビット（ \(0\) あるいは \(1\) ）であるものをビットコミットメントスキームと呼びます。
ビットコミットメントスキーム
確率的多項式時間対話型マシンの組 \((S,R)\) であり、以下で定義するコミットフェーズとオープンフェーズの2段階に分かれている2者間プロトコルをビットコミットメントスキームという。ここで、送信者を \(S\) とし、受信者を \(R\) とし、コミットメントの計算を行う2入力の関数を \(\operatorname{com}(\cdot,\cdot)\) とし、プロトコルの失敗を \(\perp\) で表すとする。
コミットフェーズ: 送信者 \(S\) は、入力 \(\sigma\ (\in \lbrace 0,1 \rbrace)\) 受け取り、乱数 \(r\) を生成して、コミットメント \(c=\operatorname{com}(\sigma, r)\) を計算して、受信者 \(R\) に \(c\) を送る。
オープンフェーズ: 送信者 \(S\) は、受信者 \(R\) に \(\sigma,r\) を送信する。受信者 \(R\) は \(\operatorname{com}(\sigma,r)\) を計算して、それがコミットフェーズで受け取った \(c\) と一致するかどうか確認し、一致するならば \(\sigma\) を出力して、そうでなければ \(\perp\) を出力する。
ここで、関数 \(\operatorname{com}(\cdot,\cdot)\) は以下で説明する秘匿性と束縛性という2つの性質を持つ関数である。
秘匿性（hiding）: 任意の確率的多項式時間アルゴリズムが \(\operatorname{com}(\sigma,r)\) から \(\sigma\) を逆算できない。すなわち、 \(\operatorname{com}(0,r_0)\) と \(\operatorname{com}(1,r_1)\) が確率変数として、計算量的識別不可能であること。
束縛性（binding）: 任意の確率的多項式時間アルゴリズムがnegligibleな確率の例外を除いて、 \(c=\operatorname{com}(0,r_0)=\operatorname{com}(1,r_1)\) を満たす \(c,r_0,r_1\) を生成できないこと。
秘匿性は悪意ある受信者に対する耐性であり、束縛性は悪意ある送信者に対する耐性となっています。
秘匿性と束縛性にはトレードオフがあります。秘匿性を達成するには、コミットメント \(\operatorname{com}(\sigma,r)\) に \(\sigma\) の情報を残さないようにしないといけませんが、 そのように関数を構築しようとすると、そのコミットメントを別の \(\sigma'\) でも求められるようになってしまう傾向にあります。
一方向性置換とそのハードコア述語を利用することで、秘匿性と束縛性を満たすコミットメントスキームを構築できます。 \(f\) を一方向性置換とし、 \(b\) をそのハードコア述語とすると、次の式で定義する関数 \(\operatorname{com}(\cdot,\cdot)\) は秘匿性と束縛性を満たします。
秘匿性を満たすことは、ハードコア述語の性質から与えられた \(f(r)\) から \(b(r)\) を求めることが困難であり、 \(\sigma\) と \(b(r)\) の排他的論理和も求めることが困難であることからわかります。
束縛性を満たすことは、一方向性置換の性質から与えられた \(f(r)\) に対応する定義域の元は \(r\) のみであるため、 \(\operatorname{com}(\sigma,r)=\operatorname{com}(\sigma,r')\) かつ \(r\neq r'\) である \(r'\) を生成できないことからわかります。
秘匿性は計算量的識別不可能である一方、束縛性はnegligibleな例外を除いてパーフェクト識別不可能です。通常ビットコミットメントスキームといえば、この定義のことを指しますが、秘匿性をパーフェクト識別不可能であるとし、束縛性を計算量的識別不可能とした定義も考えることができます。そのビットコミットメントスキームをパーフェクト秘匿ビットコミットメントスキームと呼び、後で説明するパーフェクトゼロ知識アーギュメントの定義に利用します。パーフェクト秘匿性とパーフェクト束縛性の両方を満たすコミットメントスキームは構成不可能であることが知られています。
ビットコミットメントスキームは、一方向性関数が存在するという仮定のもとで構成できることが知られています。また、ビットコミットメントスキームから任意の文字列のコミットメントスキームを構成できることは明らかです。
グラフ三彩色のゼロ知識証明
グラフ三彩色問題とは、与えられたグラフの頂点を、隣接する頂点の色が同じにならないように、三色で塗り分ける問題です。形式的にはグラフの三彩色は次のように定義します。
グラフの三彩色
グラフ \(G\coloneqq (V,E)\) が三彩色可能であるとは、任意の \((u,v)\in E\) に対して \(\phi(u)\neq \phi(v)\) となるような写像 \(\phi : V\to \lbrace 1,2,3 \rbrace\) が存在することである。この写像のことをグラフの三彩色という。
グラフ三彩色のゼロ知識証明システムは、証明者がグラフの三彩色を秘匿したまま、そのグラフにグラフ三彩色が存在することを検証者に示すことができます。グラフ三彩色のゼロ知識証明システムを次のように構成できます。
グラフ三彩色のゼロ知識証明システムの構成例
次のプロトコルを複数回実行することで、グラフ三彩色のゼロ知識証明システムを構成できる。
- 証明者が知っているグラフの三彩色を \(\phi\) とする。証明者はその三彩色の色をシャッフルする（例えば「赤の全頂点を青に、青の全頂点を黄に、黄の全頂点を赤に」のようなこと）。形式的には \(\lbrace 1,2,3\rbrace\) のランダムな置換 \(\pi\) を利用して、新しい三彩色 \(\phi'(v) = \pi(\phi(v))\) を求める。証明者は全ての頂点に対して、その色 \(\phi(v)\) をコミットメントスキームにより秘匿してコミットする。
- 検証者は、ランダムに辺 \((u,v) \in E\) を選び、その頂点 \(u,v\) の色 \(\phi'(u),\phi'(v)\) を教えるように証明者に伝える。
- 証明者は、頂点 \(u,v\) の色 \(\phi'(u),\phi'(v)\) を知るために必要な情報を検証者に送る。
- 検証者は、頂点 \(u,v\) の色 \(\phi'(u),\phi'(v)\) を調べます。 \(\phi'(u)\neq \phi'(v)\) であれば受理する。
このシステムの正当性を説明します。
完全性: 証明者がグラフの三彩色を知っていれば、検証者は明らかに受理します。よって完全性を満たします。
健全性: 証明者がグラフの三彩色を知っておらず、不正な彩色をコミットしている場合は、少なくとも1つの辺の彩色が不正であるため、検証者は確率 \(\frac{1}{|E|}\) で却下します。このプロトコルを不正な証明者に対して \(n\) 回行ったとき、検証者が全て受理する確率は \(\left( \frac{|E|-1}{|E|} \right)^n\) となり、 \(n\) を大きな値にすると、 \(0\) に近づいていくことがわかります。よって健全性を満たします。
ゼロ知識性: プロトコルを実行するたびに三彩色の色は置換されるため、頂点 \(u,v\) の彩色が異なるかどうかという1ビットの情報以外の情報は得られません。よってゼロ知識性を満たします。厳密な証明はシミュレーションパラダイムで与えることができますが、ここでは省略します。コミットメントスキームの秘匿性が計算量的識別不可能であり、このゼロ知識性はそのコミットメントスキームに依存していることから、このゼロ知識性は計算量的ゼロ知識性です。
以上で、グラフ三彩色の計算量的ゼロ知識証明システムを構成できたので、 \(\mathrm{NP}\) の全ての言語に対して計算量的ゼロ知識証明システムを構成できることがわかります。
ゼロ知識証明の限界
ゼロ知識証明に関して、次の3つの否定的な予想がされています。
- \(\mathrm{NP}\) に対する計算量的ゼロ知識証明システムの存在を、一方向性関数の存在などの仮定なしに証明できない。
- \(\mathrm{NP}\) に対するパーフェクトゼロ知識証明システムは、合理的な仮定のもとで存在しない。
- \(\mathrm{NP}\) に対するエラーの無いゼロ知識証明システムは、存在しない。