ゼロ知識証明

ゼロ知識証明系の定義

ゼロ知識証明とは, 証明の有効性以外の情報を一切漏らさない対話証明系です。

定義（ゼロ知識証明系）

言語$L$に対するゼロ知識証明系(zero-knowledge proof system)とは, 対話証明系$\langle P,V \rangle$であって, 以下の性質を満たすものです:

  • (ゼロ知識性) 任意の乱択多項式時間機械$W$に対して, ある乱択多項式時間機械$M_{W}$が存在して, 二つの確率変数列

    \[\begin{align*} (M_{W}(x))_{x\in L}, \quad ([P(x),W(x)])_{x\in L} \end{align*}\]

    の分布が任意の多項式時間アルゴリズムにとって識別不可能です.

この機械$M_W$を$W$の模倣者(simulator)と呼びます.

出力値の識別不可能性の代わりに, 以下のようにメッセージ内容の識別不可能性で定義しても同値となります.

定義（ゼロ知識証明系）

乱択多項式時間で動く対話チューリング機械$W$およびそれらの共通入力$x$に対して, $\langle P,W\rangle(x)$を機械$W$の全てのread-onlyテープの内容の分布とします. 言語$L$に対するゼロ知識証明系(zero-knowledge proof system)とは, 対話証明系$\langle P,V \rangle$であって, 任意の乱択多項式時間で動く対話チューリング機械$W$に対してある乱択多項式時間機械$M_{W}$が存在して, 二つの確率変数列

\[\begin{align*} (M_{W}(x))_{x\in L}, \quad (\langle P,W \rangle (x))_{x\in L} \end{align*}\]

が任意の多項式時間アルゴリズムにとって識別不可能です.

要するに, 検証者の受信内容(=証明者の送信内容)が簡単に計算できることを意味します. 例えば充足可能性判定問題に対する素朴な対話証明系では, 証明者が充足割当の一つをメッセージとして提示しますが, 論理式$x$が与えられたときにその充足割当の一つを求めることはNP困難です.

Remark (完全なゼロ知識)

ゼロ知識性では二つの分布の計算量的識別不可能性を要求していますが, さらに強めて二つの分布が統計距離の意味で一致するとき, これを完全なゼロ知識性(perfect zero-knowledge)と呼びます.

グラフ同型性問題に対するゼロ知識対話証明系

グラフ同型性判定問題はNPに属するため自明に対話証明系を構築できますが, 一方でゼロ知識性を持つ対話証明系を構築することは非自明です. この節では, そのようなグラフ同型性判定問題に対する非自明なゼロ知識性を持つ対話証明系を構築します.

対話証明系2

入力: 二つのグラフ $G_0=(V,E_0),G_2=(V,E_1)$ (これらは同型とする)

補助入力: $G_1 = \phi(G_0)$ (この写像$\phi$は無限の計算能力を持つ証明者があらかじめ計算しておくことができるが, ゼロ知識性を保つため検証者には秘匿).

  • (P1). 頂点集合$V$上の順列$\pi$を一様ランダムに選び, グラフ$H=\pi(G_1)$を送信します.
  • (V1). 一様ランダムなビット$\alpha \in \binset$を選び, このビットを送信します.

  • (P2). ビット$\alpha$を受信し, 写像

    \[\begin{align*} \psi = \begin{cases} \pi & \text{if } \alpha = 1 \\ \pi \circ \phi & \text{otherwise} \end{cases} \end{align*}\]

    を送信します (ただし$\circ$は写像の合成を表します).

  • (V2). 受信した写像$\psi$が$G_\alpha$と$H$の間の同型写像でない (i.e., $H\ne\psi (G_\alpha)$)ならば検証者は拒否し, そうでなければ(P1)から繰り返します.
ゼロ知識性の直感的説明

イメージとしては, 証明者は検証者に「二つのグラフ$G_0,G_1$いずれかを指定してください. 指定されたグラフから$G_1$への同型写像を探してご覧に入れましょう」と言っています.

  • 確かに$G_0$と$G_1$が同型ならば, その同型写像$\phi$を使って証明者は確率$1$で検証者を受理させることができます.
  • 一方で$G_0$と$G_1$が同型でないならば, ステップ(V1)で$\alpha=0$が選択された場合に$H=\pi(G_1)$と$G_\alpha=G_0$が同型ではないので検証者は拒否します. この事象は確率$1/2$で発生するので, 十分な回数を繰り返せば健全性を持つことが示せます.

さて, 同型写像を渡してしまうとゼロ知識性を持たないので, 秘密の同型写像を一様ランダムな置換$\pi$でマスクすることによって, 証明者は$\phi$の情報を秘匿することができます. $\pi$でマスクするのに伴って証明者は$H=\pi(G_1)$を渡す必要があります.

ステップ(V1)の$\alpha$がどちらの値であろうともステップ(P2)で構成される写像$\psi$は($\pi$のランダムネスにおいて)周辺分布が一様分布となり, しかも$\alpha$とは独立です. このため, 検証者が見るメッセージ$(\alpha,\pi)$の分布は独立一様ランダムとなるので, 確かにゼロ知識性を満たします (フォーマルな証明は割愛; 元論文のTheorem 2を参照).