Zero-Knowledge Proofs and the Complexity of Interactive Proof Systems

Zero-Knowledge Proofs and the Complexity of Interactive Proof Systems

Info

authors: Oded Goldreich, Silvio Micali, Avi Wigderson
publication: JACM(1991)

全体の要約

ゼロ知識証明系とは, ある命題が真であることを証明する際に, その証明それ自体以外の情報を一切漏らさない証明方法です. 論文の結果は以下の通り:

全てのNPに属する問題に対するゼロ知識対話証明系を構築　(ただし, 安全な暗号化関数の存在を仮定)
グラフ同型性問題とグラフ非同型性問題に対するゼロ知識対話証明系を構築 (暗号化関数を用いない).

対話証明系とは?

NP（非決定性多項式時間）を, メンバーシップを主張する短い証明を持つ言語のクラスとして捉えたとき, その証明を, 強力な証明者と確率的多項式時間検証者の間の相互作用に拡張した概念が対話証明系です.

定義（対話チューリング機械; Interactive Turing Machine）
対話チューリング機械(interactive Turing machine)とは, 以下の六つのテープからなる決定的チューリング機械です:
入力テープ (read-only)
ランダムシードテープ (read-only)
作業テープ (read/write)
受信テープ (read-only)
送信テープ (write-only)
出力テープ (write-only)
送信テープと受信テープをまとめて通信テープ(communication tape)と呼ぶこともあります.
対話するチューリング機械の組 (interactive pair of Turing machines)とは, 通信テープを共有している二つの対話チューリング機械$M_1,M_2$からなる組$\langle M_1,M_2 \rangle$であり, 次の性質を満たします:
一方の送信テープは他方の受信テープと同期しており, 逆もまた然りです.
各計算ステップにおいて, どちらか一方の機械はactiveと呼ばれる状態にあり, もう一方の機械はidleという. activeな機械がidle状態に遷移したとき, もう一方の機械はactive状態になり, その機械は自信の入力テープ, 受信テープ, ランダムシードテープの内容に基づき計算を行います. この際に受信テープに書かれている文字列をメッセージと呼びます.
対話するチューリング機械の組$\langle A,B \rangle$に対し, $[A(x),B(y)]$を計算が終了した際の$B$の出力テープの内容とします ($A$の出力テープの内容は無視しています).

対話チューリング機械

図1: 対話チューリング機械の構造

定義（対話証明系）
言語$L$に対する対話証明系(interactive proof system)とは, 対話するチューリング機械の組$\langle P,V \rangle$であって, 以下の性質を満たすものです:
$V$は乱択多項式時間アルゴリズムです
(完全性) 任意の定数$c>0$および十分長い文字列$x\in L$に対して
\[\begin{align*} \Pr \qty[ [P(x),V(x)] = 1 ] \ge 1 - |x|^{-c}. \end{align*}\]
(健全性) 任意の定数$c>0$および任意の対話チューリング機械$P^*$, そして十分長い文字列$x\notin L$に対して
\[\begin{align*} \Pr \qty[ [P^*(x),V(x)] = 1 ] \le |x|^{-c}. \end{align*}\]

対話証明系

図2: 対話証明系の構造

例えば充足可能性判定問題に対する対話証明系は, 証明者が充足する割り当てを提示し, 検証者がその割り当てが充足することを確認することによって得られます. つまり,

$P(x)$ : 入力として与えられた論理式$x$に対し, その充足割り当てのうち一つ$a$を送信テープに記述してidle状態になります.
$V(x)$ : $P(x)$が送信した割り当て$a$を受信し, その割り当てが確かに$x$を充足するかどうかを確認します.

上記の対話証明系では, 検証者は論理式$x$が充足可能であるという事実に加え, その充足割り当てが何かという情報も得ることができます. ゼロ知識証明とは, このような余分な情報の漏洩は許さず, 証明が有効であること以外には何も情報を漏らさないような対話証明です.

定義（ゼロ知識証明系）
言語$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)と呼びます.

グラフ同型性判定問題に対する対話証明系

ここでは対話証明系の代表的な例としてグラフ同型性判定問題を取り上げます.

定義（グラフ同型性判定問題）
同一の頂点集合$V$を持つ二つのグラフ$G_0=(V,E_0),G_1=(V,E_1)$を考えます. 頂点集合$V$上のある順列$\pi$が存在して, 全ての${i,j}\in\binom{V}{2}$に対して${i,j}\in E_0 \iff {\pi(i),\pi(j)}\in E_1$が成り立つとき, 二つのグラフ$G_0$と$G_1$は同型であるといいます.
二つの無向グラフ$G_0=(V,E_0),G_1=(V,E_1)$が与えられたとき, これらが同型であるならばYes, そうでなければNoを返す問題をグラフ同型性判定問題(GI; graph isomorphism problem)と呼びます.
答えのYes/Noを反転させた問題, すなわち二つのグラフが同型でないならばYes, 同型ならばNoを返す問題をグラフ非同型性判定問題 (GNI; graph non-isormophism problem)と呼びます.

グラフ非同型性問題に対する対話証明系

グラフ同型性判定問題は「同型である」ということの証拠として同型写像を提示すれば良いのでNPに属することは明らかです. 一方で「同型でない」ことの証拠が存在するかは不明ですので, グラフ非同型性判定問題の方はNPに属するかどうかは分かりません. ところが, 実は対話証明を用いれば効率的に非同型性を検証することができます. これは対話証明系の代表的な例として有名です.

グラフ$G=(V,E)$を$V$上の置換$\pi\colon V \to V$でラベルを付け替えて得られるグラフを$\pi(G)$とします. すなわち$\pi(G)$は辺集合が$\set{\set{\pi(u),\pi(v)}\colon \set{u,v} \in E}$で表されるグラフです.

対話証明系1
入力: 二つのグラフ $G_1=(V,E_1),G_2=(V,E_2)$
(V1). 頂点集合$V$上の順列$\pi$とビット$b\in\binset$をそれぞれ一様ランダムに選び, グラフ$\pi(G_b)$を送信テープに書き込みます.
(P1). グラフ$H$を受信し, それが$G_0$と$G_1$のどちらと同型かを判定します. グラフ$G_a$と同型であったときに$a\in\binset$を送信テープに書き込みます.
(V2). ビット$a$を受信し, $b=a$であるならば受理. そうでなければ拒否します.

入力$(G_1,G_2)$が非同型ならば証明者は受信したグラフ$H$が$G_0$と$G_1$のどちらと同型かを知ることができるので, このプロトコルは健全性を満たします. 一方で$G_0$と$G_1$が同型である場合, 一様ランダムな$\pi$に対して$\pi(G_0)$と$\pi(G_1)$の分布は同一なので, 特に証明者が(P1)で送信する$a\in\binset$が$b$と一致する確率は$1/2$です. 従ってこのプロトコルは(何度も繰り返すことによって)完全性を満たします.

text

図3: グラフ非同型性判定問題に対する対話証明系

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

グラフ同型性判定問題は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を参照).

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

対話証明系3
入力: 二つのグラフ $G_1=(V,E_1),G_2=(V,E_2)$
(V1). 頂点集合$V$上の順列$\pi$とビット$\alpha\in\binset$をそれぞれ一様ランダムに選び, グラフ$H=\pi(G_\alpha)$を計算する (このグラフを質問と呼ぶ). また, 各$i=1,\dots,n^2$に対して独立にランダムビット$b_i$と二つのランダム置換$\pi_{i,0},\pi_{i,1}$を生成し,
\[\begin{align*} (T_{i,0},T_{i,1}) = \begin{cases} (\pi_{i,0}(G_0),\pi_{i,1}(G_1)) & \text{if } b_i=1 \\ (\pi_{i,0}(G_1),\pi_{i,1}(G_0)) & \text{if } b_i=0 \end{cases} \end{align*}\]
として$n^2$個のグラフのペア $(T_{i,0},T_{i,1})$ を生成します ($i\in[n^2]$). これらをテストペアと呼びます. 最後に質問$H$とテストペアの集合$(H,(T_{i,0},T_{i,1}))$を送信します.
(P1). 一様ランダムな部分集合$I\subseteq[n^2]$を選び, これを送信する.
(V2). 部分集合$I$を受信し, 各$i\in[n^2]$に対して以下を計算します:
$i\in I$ならば, $i$番目のテストペアを構成するのに用いた$(b_i,\pi_{i,0},\pi_{i,1})$を送信テープに書き込みます.
$i\not\in I$ならば, $i$番目のテストペア$(T_{i,0},T_{i,1})$のうち$H$と同型なもの(すなわち$T_{i,\alpha\oplus b_i}$)に対し, $(\alpha\oplus b_i,\pi_{i,\alpha\oplus b_i}\circ\pi^{-1})$を送信テープに書き込みます. この写像は
\[\begin{align*} \pi_{i,\alpha\oplus b_i}\circ\pi^{-1}(H)=\pi_{i,\alpha\oplus b_i}(G_\alpha)=T_{i,\alpha\oplus b_i} \end{align*}\]
より, $H$から$T_{i,\alpha\oplus b_i}$への同型写像となります.
(P2). 受信した情報を元に, 各$i\in I,j\in\binset$に対して$\pi_{i,j}$が$G_{j\oplus b_i}$と$T_{i,j}$の間の同型写像になっているかどうかを確認します. 同様に, 各$i\not\in I$に対して$\pi_{i,\alpha\oplus b_i}\circ\pi^{-1}(H)$が$H$と$T_{i,\alpha\oplus b_i}$の間の同型写像になっているかどうかを確認します. これらの条件が満たされない場合は拒否します. そうでない(条件が満たされる)場合, ビット$\beta\in\binset$を, $G_\beta$と$H$が同型となるようなビットとして, これを送信します (そのようなビット$\beta$が存在しない場合は$\beta=0$とする.)
(V2). $\alpha=\beta$かどうかによって受理/拒否を決定します.

3. NPに対するゼロ知識対話証明系 (安全な暗号化関数の仮定)

安全な暗号化関数の存在を仮定して, すべてのNP言語に対してゼロ知識インタラクティブ証明系を構築する方法を示します. 具体的には, グラフ3彩色問題に対するゼロ知識対話証明系を構成します.

定義（3彩色問題）
グラフ$G=(V,E)$は, ある関数$\phi\colon V \to \set{1,2,3}$が存在して, 任意の${u,v}\in E$に対して$\phi(u)\ne\phi(v)$が成り立つとき, 3彩色可能であるといい, この関数$\phi$を3彩色といいます. グラフ$G$が3彩色可能であるかどうかを判定する問題を3彩色問題といいます.

以後では特に断りなく, 3彩色問題はNP完全であるという事実を用います.

3彩色問題に対する「物理的な」ゼロ知識対話証明系

まずは以下の仮想的なプロトコルを考えます.

対話証明系4
入力: 3彩色問題のグラフ$G=(V,E)$
補助入力として, 証明者は$G$の3彩色$\phi$を受け取ります (実際には証明者は無限の計算能力を使って$\phi$を計算できる).
以下を$|E|^2$回繰り返します:
(P1). 集合$\set{1,2,3}$上の一様ランダムな置換$\pi$を選び, 各$u\in V$に対して$(\pi(\phi(u)))_{u\in V}$と書かれた紙をラベル$u$の「封筒」に入れて封をする. これらの封筒を送信します (封筒の鍵は送らない).
(V1). 一様ランダムな辺$\set{u,v}\in E$を選び, その辺を送信します.
(P2). 辺${u,v}$を受信し, ラベル$u$と$v$の二つの封筒の鍵を送信します (受信した文字列がグラフの辺でない場合は終了).
(V2). 受信した二つの鍵を用いて封筒の中身を見る. これらの値が同じ値であったならば拒否し, そうでなければパスして次の反復に進みます (全ての反復においてパスしたならば受理).

上記の対話証明系では「封筒」という物理的なデバイスに依存したプロトコルとなっています. 証明者が知っている彩色を$\pi$でランダムに置換することによって, 元の彩色の情報を秘匿したまま, その彩色が3彩色であることを検証者に示すことができます.

暗号化関数

暗号化関数は, 封筒という物理的なデバイスを実装するために用います. 「色の情報を記した紙を封筒に入れる」という操作は「色を暗号化する」に対応します. ここでは3彩色問題を考えるため, 以下の定義では色の情報のみを暗号化することを考えます.

定義（安全な暗号化関数）
関数$f\colon \set{0,1,2,3} \times \binset^{\ast} \to \binset^{\ast}$ は, 任意の$x\ne y\in\set{0,1,2,3}$と任意の$r,s\in\binset^{\ast}$に対して$f(x,r)\ne f(y,s)$を満たすとき, 暗号化関数(encryption function)といいます.
セキュリティパラメータ$n\in\Nat$に対し, $r\sim\binset^n$, $f_n(x)=f(x,r)$として得られる確率変数$f_n(x)$を確率的な暗号化 (probabilistic encryption)といいます.
暗号化関数$f\colon \set{0,1,2,3}\times\binset^\ast\to\binset^\ast$は, 全ての$x\ne y \in\set{0,1,2,3}$に対して, 二つの確率的な暗号化$(f_n(x))_n$と$(f_n(y))_n$が任意の多項式時間アルゴリズムにとって識別不可能なとき, 安全(secure)という. つまり, 任意の多項式時間アルゴリズム$A$と十分大きな$n\in\Nat$に対して
\[\begin{align*} \abs{ \Pr[A(f_n(x))=1] - \Pr[A(f_n(y))=1] } \le n^{-\omega(1)} \end{align*}\]
を満たすことを意味します.

3彩色問題に対するゼロ知識対話証明系

対話証明系4’
入力: 3彩色問題のグラフ$G=(V,E)$
補助入力として, 証明者は$G$の3彩色$\phi$を受け取ります (実際には証明者は無限の計算能力を使って$\phi$を計算できる). また, $f\colon\binset\to\binset^*$を安全な暗号化関数とし, 特に多項式時間で計算できるものとします.
以下を$|E|^2$回繰り返します:
(P1). 集合$\set{1,2,3}$上の一様ランダムな置換$\pi$を選び, 各$u\in V$に対して$r_u\sim\binset^n$とし, $F_u := f(\pi(\phi(u)),r_u)$とし, $(F_u)_{u\in V}$を送信する.
(V1). 一様ランダムな辺$\set{u,v}\in E$を選び, その辺を送信します.
(P2). 辺${u,v}$を受信し, $F_u,F_v$の計算に用いた$f$への入力, すなわち$(\pi(\phi(u)),r_u),(\pi(\phi(v)),r_v)$を送信します.
(V2). 受信した二つのペア$(\pi(\phi(u)),r_u),(\pi(\phi(v)),r_v)$を用いて$F_u,F_v$を計算し, これらの値が同じ値であったならば拒否し, そうでなければパスして次の反復に進みます (全ての反復においてパスしたならば受理).

この対話証明系4’のゼロ知識性は暗号化関数の安全性によって保証されます.

対話証明系4’では, NP証明を補助的な入力として与えられたとき証明者は多項式時間で動く.