ゼロ知識証明

同義語:zero-knowledge proofゼロ知識対話証明zero-knowledge interactive proof

概要

ゼロ知識証明(zero-knowledge proof)とは、計算能力に制限のない証明者が確率的な多項式時間の検証者と対話して命題が正しいことを納得させる対話証明のうち、規定から外れた検証者を含むどの検証者についても、検証者が受け取るものの分布を証明者なしで期待多項式時間で作れる(模倣者がある)ものである。グラフ同型は、ランダムな同型の写しを送り検証者の問いに応じて置換を明かす対話で、完全ゼロ知識の証明をもつ。適当な暗号の仮定のもとで NP のすべての言語は計算量的ゼロ知識の証明をもつが、NP 完全な言語が統計的ゼロ知識の証明をもてば多項式階層が潰れる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: グラフ同型, NP完全, P対NP問題

ゼロ知識証明(zero-knowledge proof)とは、命題が正しいことを相手に納得させながら、それが正しいという事実以外の情報を相手に何も与えない対話の手順である。たとえば 2 つのグラフが同型であることを、同型写像そのものを見せずに確信させることができる。
NP の言語では、証明者は証拠(同型写像、充足する割り当てなど)を送り、検証者がそれを確かめる。これでは証拠そのものが相手に渡る。ゼロ知識証明では、検証者が乱数を使って問いを出し、証明者が答える 対話 を何度か行う。正しくない命題では高い確率で嘘が見破られ、正しい命題では、検証者が受け取るものの分布を、検証者が証明者なしで自分で作れる。この「自分で作れる」を 模倣者 の存在として定式化するのがゼロ知識の定義である。
この記事では、対話証明を定義し、グラフの非同型の対話証明を与え、ゼロ知識を定義して、グラフ同型の対話証明が完全ゼロ知識であることを証明する。NP のすべての言語がゼロ知識証明をもつこと(暗号の仮定のもとで)と、ゼロ知識の限界は主張として述べる。証明を局所的に読む検証は PCP定理 で扱う。

対話証明

以下、多項式時間とは入力の長さ $|x|$ の多項式の時間のことである。

対話証明

証明者 $P$ と 検証者 $V$ が共通の入力 $x$ を見ながら交互に文字列を送り合い、最後に $V$ が受理か拒否を出力する手順を 対話 という。$V$ は確率的な多項式時間の機械で、自分の乱数は相手に見せない。$P$ の計算能力には制限を置かない。言語 $L$ の 対話証明 とは、次の 2 条件を満たす $(P,V)$ のことである。

  1. 完全性. $x\in L$ なら、$V$ が $P$ と対話して受理する確率は $2/3$ 以上である。
  2. 健全性. $x\notin L$ なら、どの証明者 $P^*$ と対話しても、$V$ が受理する確率は $1/3$ 以下である。
    対話証明をもつ言語のクラスを $\mathrm{IP}$ と書く(AB07 Definition 8.5、p. 149。GMW91 Definition 2、p. 694)。

$L\in\mathrm{NP}$ なら、$P$ が証拠を送り $V$ がそれを確かめる対話は、誤りのない対話証明である。よって $\mathrm{NP}\subset\mathrm{IP}$ である。逆に、$V$ が乱数を使わなければ、対話の記録全体が $V$ の判定できる証拠になり、対話証明をもつ言語はちょうど NP の言語になる(AB07 Theorem 8.3、p. 148。GMW91 Remark 4、p. 695)。乱数を使うと、NP に属するかどうか分かっていない言語にも対話証明がある。
以下、グラフはすべて同じ $n$ 元集合 $W$ を頂点集合とする。$W$ の置換 $\pi$ とグラフ $G=(W,E)$ について、$\pi G$ を辺の集合が $\{\pi(u)\pi(v):uv\in E\}$ のグラフとする。$\pi$ は $G$ から $\pi G$ への同型であり(グラフ同型)、$G_0\cong G_1$ とは $G_1=\varphi G_0$ となる置換 $\varphi$ があることである。$\pi$ を $W$ の置換全体 $\mathrm{Sym}(W)$ から一様に選ぶとき、$\pi G$ を $G$ の ランダムな同型の写し という。

グラフの非同型の対話証明

非同型なグラフの組の言語 $\mathrm{GNI}=\{(G_0,G_1):G_0\not\cong G_1\}$ は次の対話で対話証明をもつ(GMW91 Protocol 1 と Theorem 1、p. 701)。$m\ge2$ とする。

  1. $V$ は独立に一様なビット $i_1,\dots,i_m\in\{0,1\}$ と置換 $\sigma_1,\dots,\sigma_m$ を選び、$H_k:=\sigma_kG_{i_k}$ を $P$ に送る。
  2. $P$ はビット $j_1,\dots,j_m$ を返す。
  3. $V$ はすべての $k$ で $j_k=i_k$ なら受理する。
    完全性の確率は $1$、健全性の誤りは $2^{-m}$ である。
同型なら問いから答えが分からない
証明を開く

完全性.$G_0\not\cong G_1$ なら、$H_k$ は $G_{i_k}$ と同型で $G_{1-i_k}$ とは同型でない。$P$ は計算能力に制限がないので、$H_k$ がどちらと同型かを調べて $j_k:=i_k$ を返せる。

健全性.$G_1=\varphi G_0$ とする。$\sigma$ が一様なら $\sigma\varphi$ も一様なので、$\sigma G_1=(\sigma\varphi)G_0$ と $\sigma G_0$ は同じ分布をもつ。よって $(H_1,\dots,H_m)$ の分布は $(i_1,\dots,i_m)$ によらず、両者は独立である。証明者 $P^*$ の答え $(j_1,\dots,j_m)$ は $(H_1,\dots,H_m)$ と $P^*$ 自身の乱数だけから決まるので、$(i_1,\dots,i_m)$ と独立である。$(i_1,\dots,i_m)$ は一様なので、答えが一致する確率はちょうど $2^{-m}$ である。$\square$

GNI が NP に属するかは AB07 §8.3(p. 150)の時点で分かっていない。対話証明の力はさらに大きく、$\mathrm{IP}=\mathrm{PSPACE}$ である(Lund–Fortnow–Karloff–Nisan、Shamir。AB07 Theorem 8.17、p. 157。この記事では証明せず、IP=PSPACE で証明する)。また、検証者が乱数をすべて公開する対話(Arthur–Merlin 型)に制限しても、対話の回数を $2$ 増やすだけで同じ言語が認識できる(Goldwasser–Sipser。AB07 Theorem 8.8、p. 152。GMW91 Remark 3、p. 695)。2 回の公開乱数の対話で認識できる言語のクラスを $\mathrm{AM}$ と書く(AB07 Definition 8.7、p. 151)。

ゼロ知識の定義

検証者は規定どおりに動くとは限らない。規定から外れて情報を引き出そうとする検証者に対しても、何も漏れないことを要求する。

見え方と模倣者

$(P,V)$ を $L$ の対話証明とする。確率的な多項式時間の機械 $V^*$(規定の $V$ とは違ってよい)が入力 $x$ で $P$ と対話するとき、$V^*$ の乱数 $r$ と $V^*$ が受け取った通信の列の組 $(x,r,\text{通信})$ の分布を $V^*$ の見え方 といい、$\mathrm{view}_{V^*}(x)$ と書く。$V^*$ の 模倣者 とは、$P$ と対話せずに入力 $x$ だけから文字列を出力する確率的な機械 $S$ で、実行時間の期待値が $|x|$ の多項式でおさえられるものをいう。

ゼロ知識

$L$ の対話証明 $(P,V)$ が

  1. 完全ゼロ知識 であるとは、どの多項式時間の $V^*$ にも模倣者 $S$ があって、すべての $x\in L$ について $S(x)$ と $\mathrm{view}_{V^*}(x)$ の分布が一致することをいう。
  2. 統計的ゼロ知識 であるとは、分布の一致を、両者の全変動距離が $|x|$ のどの多項式の逆数よりも十分大きな $|x|$ で小さいことに弱めたものをいう。
  3. 計算量的ゼロ知識 であるとは、分布の一致を、どの多項式時間の判定法も両者を区別する確率の差が $|x|$ のどの多項式の逆数よりも十分大きな $|x|$ で小さいことに弱めたものをいう。
    単に ゼロ知識 といえば計算量的ゼロ知識を指す(Goldwasser–Micali–Rackoff による定義。GMW91 Definitions 3–5 と Remark 7、pp. 696–697)。

$V^*$ の出力は見え方から計算できるので、模倣者があれば、$V^*$ が対話で得て計算できるものは何でも、対話なしでも期待多項式時間で計算できる。$\mathrm{BPP}$ の言語は、証明者が何もしない対話で自明に完全ゼロ知識である。一方、証明者からの通信が 1 回だけのゼロ知識証明をもつ言語は、確率的な多項式時間で判定できる(GMW91 Remark 9、p. 698)。対話が本質的なのはこのためである。
GMW91 は $V^*$ の時間も期待値で測るが、この記事では $V^*$ は乱数 $q(|x|)$ ビット、時間 $q(|x|)$ 以下($q$ は多項式)で必ず止まるものとする。模倣者の時間を期待値で測ることは、次の定理で分布をちょうど一致させるのに必要だと考えられている(GMW91 Remark 11、p. 706)。

グラフ同型の完全ゼロ知識証明

グラフ同型の言語 $\mathrm{GI}=\{(G_0,G_1):G_0\cong G_1\}$ は NP に属し、同型写像 $\varphi$ を送れば対話証明になる。しかしそれでは $\varphi$ が漏れる。次の対話では、証明者は $\varphi$ を知っている多項式時間の機械でよく、$\varphi$ を一切見せない。

グラフ同型のゼロ知識証明

$m\ge2$ とする。共通の入力 $(G_0,G_1)$ について、証明者は $G_1=\varphi G_0$ となる $\varphi$ を知っているとし、次の 1 回分を独立に $m$ 回くり返す(GMW91 Protocol 2、p. 702)。

  1. $P$ は置換 $\pi$ を一様に選び、$H:=\pi G_1$ を送る。
  2. $V$ はビット $\alpha\in\{0,1\}$ を一様に選んで送る($\{0,1\}$ 以外の通信は $\alpha=0$ とみなす)。
  3. $P$ は、$\alpha=1$ なら $\psi:=\pi$、$\alpha=0$ なら $\psi:=\pi\varphi$ を送る。
  4. $V$ は $H=\psi G_\alpha$ でなければ拒否して止まる。
    $m$ 回すべて通れば $V$ は受理する。これは $\mathrm{GI}$ の対話証明で、完全性の確率は $1$、健全性の誤りは $2^{-m}$ 以下であり、完全ゼロ知識である(GMW91 Theorem 2、pp. 703–705)。
問いを当てたときだけ記録する

完全性. $\alpha=1$ なら $\psi G_1=\pi G_1=H$、$\alpha=0$ なら $\psi G_0=\pi\varphi G_0=\pi G_1=H$ なので、規定どおりの $P$ は毎回通る。
健全性. $G_0\not\cong G_1$ とし、$P^*$ を任意の証明者とする。各回で $P^*$ が送る $H$ は $G_0$ と $G_1$ の高々一方としか同型でない。$\alpha$ はそれまでの対話と $H$ に独立で一様なので、$H\not\cong G_\alpha$ となる確率は、それまでの対話がどうであっても $1/2$ 以上で、そのとき $P^*$ はどんな $\psi$ を送っても通らない。よって $m$ 回とも通る確率は $2^{-m}$ 以下である。
模倣者. $G_0\cong G_1$ とし、$G_1=\varphi G_0$ とする。$V^*$ を多項式時間の検証者とする。$V^*$ の乱数 $r$ と、それまでに受け取った通信の列 $h$ を固定すると、$V^*$ の次の問いは受け取った $H$ だけの関数になる。これを $a(H)\in\{0,1\}$ と書く。模倣者 $S$ は次のように動く。

  1. $r\in\{0,1\}^{q(|x|)}$ を一様に選んで固定し、$h$ を空列とする。
  2. 各回で、ビット $\beta$ と置換 $\psi$ を一様に選び、$H:=\psi G_\beta$ とする。$V^*$ を $r,h$ と $H$ で走らせて問い $a(H)$ を得る。$a(H)=\beta$ なら $h$ の末尾に $(H,\psi)$ を加えて次の回へ進む。$a(H)\ne\beta$ ならこの回をやり直す。
  3. $m$ 回が終わったら $(x,r,h)$ を出力する。

分布が一致すること. $r,h$ を固定し、$S_{r,h}:=\{(H,\psi):H=\psi G_{a(H)}\}$ とおく。実際の対話でのこの回の通信 $(H,\psi)$ は、一様な $\pi$ から $(\pi G_1,\psi)$ として決まる。$\pi\mapsto(\pi G_1,\psi)$ は $\mathrm{Sym}(W)$ から $S_{r,h}$ への全単射である。実際、$\psi$ は $a(H)=1$ なら $\pi$、$a(H)=0$ なら $\pi\varphi$ なので $\pi$ が復元でき単射である。また $(H,\psi)\in S_{r,h}$ に対し $\pi:=\psi$($a(H)=1$ のとき)または $\pi:=\psi\varphi^{-1}$($a(H)=0$ のとき)とおくと $\pi G_1=H$ となり全射である。よって実際の通信は $S_{r,h}$ 上で一様に分布し、$|S_{r,h}|=n!$ である。
一方、模倣者の 1 回の試行では、$(\beta,\psi)$ の $2\cdot n!$ 通りが等確率で、$(H,\psi)=(\psi G_\beta,\psi)$ が記録されるのは $\beta=a(H)$ のときで、それはちょうど $(H,\psi)\in S_{r,h}$ のときである。$(H,\psi)\in S_{r,h}$ からは $\beta=a(H)$ が決まるので、記録される各元はそれぞれ確率 $1/(2\cdot n!)$ で出る。よって 1 回の試行が成功する確率は $n!/(2\cdot n!)=1/2$ で、成功したときの記録は $S_{r,h}$ 上で一様である。
$r$ は両者で一様であり、$r,h$ を固定したときの次の回の通信の条件つき分布が両者で同じなので、回の数についての帰納法で、$(x,r,h)$ の分布は実際の見え方と一致する。
時間. 各回の試行は独立に確率 $1/2$ で成功するので、1 回あたりの試行回数の期待値は $2$ で、$V^*$ を走らせる回数の期待値は $2m$ である。各試行は $V^*$ の 1 回分の実行と多項式時間の計算からなるので、$S$ の時間の期待値は多項式である。$\square$

模倣者は検証者の問いを推測し、当たったときだけ記録する。当たり外れが $V^*$ からは区別できない($H$ が $\beta$ について何も教えない)ことが要である。$V^*$ が規定どおりなら証明は簡単で、$V$ が受け取る $(H,\psi)$ は一様な $\psi$ と $\psi G_\alpha$ の組にすぎない。困難は、$V^*$ が $H$ を見て問いを選べることにある。
$m$ 回を順にではなく同時に行う並列版でも健全性の誤りは $2^{-m}$ だが、ゼロ知識になるかは GMW91 の時点で分かっていなかった。上の模倣者は、ある回の問いがそれより前の $H$ だけで決まることを使っている。並列版では、模倣者が検証者を部分ルーチンとして呼ぶだけの方法ではゼロ知識を示せないことが、$\mathrm{GI}\in\mathrm{BPP}$ でないかぎり知られている(Krawczyk–Goldreich。GMW91 Remark 10、p. 706)。GNI も完全ゼロ知識証明をもつ(GMW91 Theorem 3、p. 708)。

NP の言語はすべてゼロ知識証明をもつ

グラフの 3 彩色可能性(頂点を 3 色で塗り、どの辺の両端も異なる色にできるか。彩色)は NP完全 である。これにゼロ知識証明を与えれば、多項式時間の帰着を通して NP のすべての言語に広がる。考え方は、中身を後から変えられない鍵つきの箱(コミットメント)を使う次の対話である(GMW91 Protocol 4、p. 713)。$G=(W,E)$ の 3 彩色 $c\colon W\to\{1,2,3\}$ を証明者が知っているとする。

  1. $P$ は 3 色の置換 $\tau$ を一様に選び、各頂点 $w$ の色 $\tau(c(w))$ を、頂点の番号をつけた箱に入れて鍵をかけ、すべての箱を送る。
  2. $V$ は辺 $uv\in E$ を一様に選んで送る。
  3. $P$ は $u,v$ の箱の鍵を渡す。$V$ は 2 つの色が $\{1,2,3\}$ に属し、互いに異なることを確かめる。
    $G$ が 3 彩色できなければ、箱の中身がどんな塗り方でも、両端が同じ色になるか色でないものが入った辺が少なくとも 1 本ある。箱は辺を選ぶ前に送られ中身を変えられないので、1 回で見破られる確率は $1/|E|$ 以上で、$m|E|$ 回くり返すと通る確率は $(1-1/|E|)^{m|E|}\le e^{-m}$ 以下である。$G$ が 3 彩色できるなら、開かれる 2 色は $\tau$ のために異なる 2 色の一様な組で、塗り方について何も教えない。模倣者は、辺を推測して両端だけに異なる色を入れ、当たったときだけ記録すればよい。
    実際の計算では、箱を暗号化で実現する。そのとき箱の中身は計算量的にしか隠れないので、得られるのは計算量的ゼロ知識である。
NP のゼロ知識証明

多項式の大きさの回路の族に対しても安全な暗号化関数(GMW91 の nonuniformly secure encryption function)が存在するなら、NP のすべての言語はゼロ知識証明をもつ。さらに証明者は、NP の証拠を補助の入力として受け取る多項式時間の機械にとれる(Goldreich–Micali–Wigderson。GMW91 Theorem 5、p. 722 と Theorem 6、p. 723。この記事では証明しない)。

GMW91 は、必要なのはビットを秘めて約束する方式であり、それは一方向関数から作れると述べている(§1.3、p. 698)。

ゼロ知識の限界

完全・統計的ゼロ知識の力には制限がある。$L$ が統計的ゼロ知識の対話証明をもてば $L\in\mathrm{AM}\cap\mathrm{coAM}$ である(Fortnow、Aiello–Håstad。GMW91 §1.5、p. 699。この記事では証明しない)。一方、$\mathrm{coNP}\subset\mathrm{AM}$ なら多項式階層は第 2 層に潰れる(Boppana–Håstad–Zachos。GMW91 Corollary 2 の証明、p. 702)。$\mathrm{AM}$ は多項式時間の帰着で閉じているので、NP 完全な言語 $L$ が統計的ゼロ知識証明をもてば、$\overline{L}\in\mathrm{AM}$ から $\mathrm{coNP}\subset\mathrm{AM}$ となり、多項式階層が潰れる。したがって thm-zk-np の計算量的ゼロ知識を、多項式階層を潰さずに統計的ゼロ知識へ強めることはできない。
健全性を多項式時間の証明者 $P^*$ に対してだけ要求するものを 議論(argument)という。議論では、素因数分解が難しいという仮定のもとで、NP のすべての言語が完全ゼロ知識をもつ(Brassard ら。GMW91 §1.4、p. 698)。上の限界は対話証明についてのもので、議論には当てはまらない。
PCP定理 の検証者も乱数を使うが、書かれた証明を数か所読むだけで対話はしない。PCP が問うのは検証に何ビット読めば足りるかであり、ゼロ知識が問うのは検証で何が漏れるかである。

反例:仮定を 1 つ外すと

次の表は、thm-zk-gi の対話から仮定を 1 つだけ外した例である。2 行目と 4 行目の「失われる」は、模倣者があれば、同型なグラフの組から同型写像を期待多項式時間で確率 $1/2$ 以上で求める算法が得られる、という意味である(同型写像を確率的な多項式時間で求める算法は、GMW91 の時点で知られていない(§2、p. 700、Remark 10、p. 706)。AB07 §8.3(pp. 150–151)も、グラフ同型の判定が $\mathrm{P}$ に属するかは分かっていないとする)。

外す仮定例失われる性質
検証者の問い $\alpha$ が一様$V$ が常に $\alpha=0$ を送る健全性。$G_0\not\cong G_1$ でも $P^*$ は $H:=\pi G_0$ を送り $\psi:=\pi$ と答えて毎回通る
証明者の $\pi$ が一様$\pi$ を恒等置換に固定し、常に $H=G_1$ を送るゼロ知識。$\alpha=0$ の回に $\psi=\varphi$ そのものが送られる
$H$ を問いの前に送る$V$ が先に $\alpha$ を送り、$P$ が後から $H$ を送る健全性。$P^*$ は $\alpha$ を見て $H:=\pi G_\alpha$ とし $\psi:=\pi$ で通る
模倣者をすべての $V^*$ に求める対話に「$\alpha=2$ なら $\varphi$ を送る」を加えるゼロ知識。規定の $V$ の見え方は変わらないが、$\alpha=2$ を送る $V^*$ は $\varphi$ を得る

4 行目は、規定どおりの検証者に対してだけ模倣者を求める弱い性質(正直な検証者に対するゼロ知識)では、ゼロ知識が保証されないことの例になっている。

関連項目

参考文献

[1]
Sanjeev Arora; Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009, 頁は Web draft 2007-01-08 の通し頁:Theorem 8.3 p. 148、Definition 8.5 p. 149、§8.3 pp. 150–151、Definition 8.7 p. 151、Theorem 8.8 p. 152、Theorem 8.17 p. 157
[2]
Oded Goldreich; Silvio Micali; Avi Wigderson, Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems, Journal of the ACM, 1991, pp. 691–729。Definition 2 p. 694、Remarks 3–4 p. 695、Definitions 3–5 と Remark 7 pp. 696–697、Remark 9 と §1.3–§1.4 p. 698、§1.5 p. 699、§2 p. 700、Protocol 1 と Theorem 1 p. 701、Corollary 2 と Protocol 2 p. 702、Theorem 2 pp. 703–705、Remarks 10–11 p. 706、Theorem 3 p. 708、Protocol 4 p. 713、Theorem 5 p. 722、Theorem 6 p. 723

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する