NPに対するゼロ知識対話証明系

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証明を補助的な入力として与えられたとき証明者は多項式時間で動く.