対話型証明 | 計算理論

1 プロトコルと量化

入力 $x$ と、それまでに交換したメッセージ列を記録という。prover の戦略 $P$ は、入力と記録から次のメッセージを選ぶ関数である。 $P$ の計算時間には制限を課さない。verifier $V$ は、入力、記録、および verifier 自身の乱数テープから次のメッセージまたは受理・拒否を計算する確率的 TM である。

ここで確率的 TM とは、決定性 TM に読取り専用の一方向乱数テープを加えた機械である（§E18.14 定義 1.1）。乱数テープの各マスには互いに独立で公平なビットが置かれ、機械はビットを一つ読むたびに乱数ヘッドを右へ一マス進める。入力と乱数列を固定すると、一つの prover 戦略に対する対話の計算は決定的になる。定義 1.1 条件 (a)により対話全体は $p(|x|)$ 段以内に終わるため、verifier が読む乱数は高々 $p(|x|)$ ビットである。したがって、対話の結果に関する事象の確率は、長さ $p(|x|)$ のビット列全体のうち、その事象を満たすものの割合として定める。

定義 1.1. 言語 $L\subseteq\Sigma^*$ に対する対話型証明系の verifier (interactive-proof verifier) は、確率的 verifier $V$ であって、ある多項式 $p$ が存在して次を満たすものである。確率は verifier の乱数 $r$ だけに関して取る。

$V$ は全ての入力 $x$ 、全ての乱数列、および全ての prover 戦略に対し、全対話を $p(|x|)$ 段以内に終える。したがって、ラウンド数と $V$ が読み書きする通信量も $p(|x|)$ 以下である。
完全性 (completeness) として $\text{ある }P\text{ が存在し、全ての }x\in L\text{ について}\quad \Pr_r[\langle P,V\rangle(x;r)\text{ が受理する}]\ge\frac23$ が成り立つ。
健全性 (soundness) として $\text{全ての }P^*\text{ と全ての }x\notin L\text{ について}\quad \Pr_r[\langle P^*,V\rangle(x;r)\text{ が受理する}]\le\frac13$ が成り立つ。

完全性の $P$ を正直な prover (honest prover)、健全性で量化する $P^*$ を不正な prover (cheating prover) と呼ぶ。

完全性の $P$ は verifier の定義に固定された成分ではなく、完全性条件の内側で存在量化される。

prover が内部乱数を使う場合でも、健全性では決定性の戦略だけを調べれば十分である。実際、prover の内部乱数を固定するごとに決定性の戦略が一つ定まり、乱択 prover の受理確率はそれらの受理確率の加重平均である。全ての決定性の戦略の受理確率が $1/3$ 以下なら、その加重平均も $1/3$ 以下である。

定義 1.2. verifier の乱数テープの内容が prover から隠され、verifier が乱数から計算したメッセージだけが prover に渡される対話を非公開コイン型（private-coin）プロトコル (private-coin protocol) という。

verifier が各ラウンドで送るメッセージが、新しく生成した公平な乱数ビット列そのものであり、送信した乱数を prover も全て知る対話を公開コイン型（public-coin）プロトコル (public-coin protocol) という。verifier は最後の判定で、公開した乱数、入力、および全記録を使用することができる。

公開コイン型であるためには、乱数から計算した像だけを送るのではなく、判定に用いる乱数自体を公開する必要がある。乱数を隠すことが健全性の根拠になるプロトコルは、そのままでは公開コイン型プロトコルではない。

2 グラフ非同型の非公開コイン型プロトコル

有限単純無向グラフ $G$ の頂点集合を $[n]=\{1,\ldots,n\}$ とする。置換 $\pi\in S_n$ によって頂点名を付け替えたグラフを $\pi(G)$ と書く。二つのグラフ $G_0,G_1$ が同型であるとは、ある $\pi\in S_n$ について $\pi(G_0)=G_1$ となることをいう。

定義 2.1 (グラフ非同型言語).

\mathsf{GNI} =\{\langle G_0,G_1\rangle:G_0\text{ と }G_1\text{ は同型でない}\}

と定める。この言語をグラフ非同型言語 (graph nonisomorphism language) という。頂点数が異なる二グラフは同型でない。不正なグラフ符号は言語に含めない。

厳密な一様置換を、有限個の公平な乱数ビットだけで最悪時多項式時間内に生成することは一般にはできない。実際、固定長の公平なビット列から得る各出力確率は $2$ の冪を分母にもつが、 $1/n!$ は $n\ge3$ でその形にならない。そこで、固定長のラベルから近一様な置換を作る。

補題 2.2. $n\ge2$ とし、

m=\left\lceil\log_2\bigl(8n(n-1)\bigr)\right\rceil

と置く。各頂点 $v\in[n]$ に、独立で一様な $m$ ビット整数 $A_v$ を割り当てる。全てのラベルが異なれば、ラベルの小さい順に頂点を並べる置換 $\pi$ を出力し、衝突があれば恒等置換を出力する。この手続きを $\mathsf{LabelPerm}_{n,m}$ と書く。

この手続きは必ず $nm$ 個の乱数ビットを読んで多項式時間で停止する。出力分布を $Q$ 、 $S_n$ 上の一様分布を $U$ とすると、

\lVert Q-U\rVert_{\mathrm{TV}}\le\delta_n, \qquad \delta_n=\frac{n(n-1)}{2^{m+1}}\le\frac1{16}<\frac1{12}

である。ただし、有限集合上の全変動距離を

\lVert P-Q\rVert_{\mathrm{TV}} =\frac12\sum_\omega|P(\omega)-Q(\omega)|

と定める。

証明. 異なる二頂点 $u,v$ について $\Pr[A_u=A_v]=2^{-m}$ である。いずれかの衝突が起こる確率 $\varepsilon$ は、頂点対に関する和集合評価により

\varepsilon \le\binom n2 2^{-m} =\frac{n(n-1)}{2^{m+1}} =\delta_n \le\frac1{16}

となる。

衝突がないという条件の下では、ラベルの相対順序は $S_n$ 上で一様である。実際、各 $\sigma\in S_n$ について、 $\sigma(1),\ldots,\sigma(n)$ の順に増加する相異なるラベルの選び方は $\binom{2^m}{n}$ 個であり、 $\sigma$ によらない。したがって、衝突時の出力分布を $R$ とすれば

Q=(1-\varepsilon)U+\varepsilon R

である。よって

\lVert Q-U\rVert_{\mathrm{TV}} =\varepsilon\lVert R-U\rVert_{\mathrm{TV}} \le\varepsilon\le\delta_n

となる。

手続きは $nm$ ビットを一度だけ読み、全ての頂点対のラベルを比較して衝突を検査し、例えば選択ソートで相対順序を求める。比較回数は $O(n^2)$ 、一回の比較時間は $O(m)$ なので、最悪時時間は $O(n^2m)$ である。 $m=O(\log(n+1))$ であるため、グラフの符号長に関する多項式時間である。▨

同じ頂点数 $n\ge2$ の二グラフに対し、次の一回プロトコルを考える。

verifier は $b\in\{0,1\}$ を一様に選び、 $\pi\leftarrow\mathsf{LabelPerm}_{n,m}$ を独立に生成する。
verifier は $H=\pi(G_b)$ を prover へ送るが、 $b$ 、ラベル、および $\pi$ は送らない。
prover はビット $c$ を返す。
verifier は $c=b$ の場合に限って受理する。

頂点数が異なる場合には verifier は直ちに受理し、不正な符号は直ちに拒否する。 $n\le1$ では二つの正しいグラフは必ず同型なので、verifier は直ちに拒否する。

定理 2.3. 上の一回プロトコルは、 $\langle G_0,G_1\rangle\in\mathsf{GNI}$ の場合に完全性 $1$ をもち、 $\langle G_0,G_1\rangle\notin\mathsf{GNI}$ となる正しいグラフ符号に対し、任意の prover の受理確率が高々

\frac12+\delta_n\le\frac9{16}

である。

証明. 最初に $G_0$ と $G_1$ が非同型であるとする。送られた $H$ は $G_b$ と同型である。 $H$ が $G_{1-b}$ とも同型ならば、同型写像を合成することで $G_0$ と $G_1$ が同型となり、仮定に反する。したがって、 $H$ は $G_0,G_1$ のちょうど一方と同型である。計算能力に制限のない正直な prover は、全ての置換を調べて $H$ がどちらと同型かを決定し、その添字 $c=b$ を返すことができる。したがって、verifier は全ての乱数選択で受理し、完全性は $1$ である。

次に $G_0$ と $G_1$ が同型であるとする。 $G_1=\tau(G_0)$ となる置換 $\tau\in S_n$ を固定する。 $b=j$ の条件下で送られる $H$ の分布を $P_j$ とする。置換が一様分布 $U$ に従う理想的な場合には、写像 $\pi\mapsto\pi\tau$ が $S_n$ 上の全単射であるため、 $b=0$ と $b=1$ の送信グラフは同じ分布 $P_*$ をもつ。

置換をグラフへ写す操作は、全変動距離を増加させない。実際、写像 $\phi$ による像分布について、

\begin{aligned} \lVert\phi(P)-\phi(Q)\rVert_{\mathrm{TV}} &=\frac12\sum_h \left|\sum_{\omega:\phi(\omega)=h}(P(\omega)-Q(\omega))\right|\\ &\le\frac12\sum_\omega|P(\omega)-Q(\omega)| =\lVert P-Q\rVert_{\mathrm{TV}}. \end{aligned}

したがって、補題 2.2により

\lVert P_0-P_*\rVert_{\mathrm{TV}}\le\delta_n, \qquad \lVert P_1-P_*\rVert_{\mathrm{TV}}\le\delta_n.

三角不等式から $\lVert P_0-P_1\rVert_{\mathrm{TV}}\le2\delta_n$ を得る。

決定性の prover の返答を $c=f(H)$ と書く。 $b$ は一様なので、受理確率は

\begin{aligned} \frac12\sum_h\bigl( P_0(h)\mathbf1_{\{f(h)=0\}} +P_1(h)\mathbf1_{\{f(h)=1\}}\bigr) &\le\frac12\sum_h\max\{P_0(h),P_1(h)\}\\ &=\frac12\bigl(1+\lVert P_0-P_1\rVert_{\mathrm{TV}}\bigr)\\ &\le\frac12+\delta_n. \end{aligned}

最後から二つ目の等号は $\max\{a,b\}=(a+b+|a-b|)/2$ を有限和へ適用した結果である。乱択 prover の受理確率も決定性の戦略の受理確率の加重平均なので、同じ上界を満たす。▨

例 2.4. 頂点集合 $[3]$ 上で、 $G_0$ を辺 $\{1,2\},\{2,3\},\{1,3\}$ をもつ三角形、 $G_1$ を辺 $\{1,2\},\{2,3\}$ だけをもつ道とする。頂点名の付け替えは辺の本数を変えないため、辺数 $3$ の $G_0$ と辺数 $2$ の $G_1$ は同型でなく、 $\langle G_0,G_1\rangle\in\mathsf{GNI}$ である。

$n=3$ なので $m=\lceil\log_2 48\rceil=6$ であり、verifier は選択ビット $b$ に $1$ ビット、三つのラベルに $18$ ビットの乱数を読む。たとえば $b=1$ を選び、ラベルが衝突なく $A_1=41$ 、 $A_2=13$ 、 $A_3=27$ と得られたとする。ラベルの小さい順は頂点 $2,3,1$ であるから、生成される置換は $\pi(2)=1$ 、 $\pi(3)=2$ 、 $\pi(1)=3$ である。verifier は $H=\pi(G_1)$ 、すなわち辺 $\{3,1\},\{1,2\}$ をもつグラフを送る。

prover は $H$ の辺数 $2$ を数える。同型なグラフの辺数は等しいから、 $H$ と同型であり得るのは $G_1$ だけである。prover は $c=1$ を返し、 $c=b$ なので verifier は受理する。 $b=0$ の場合も、送られるグラフの辺数が $3$ になるため、同じ返答規則が $c=0=b$ を与える。どの乱数選択でも $c=b$ が成り立つため、この入力に対する受理確率は $1$ であり、定理 2.3の完全性を与える。

一方、 $G_0$ と $G_1$ がともに同じ三角形である入力は $\mathsf{GNI}$ に属さない。三角形は任意の置換で三角形のまま変わらないため、 $H$ は $b$ によらず同じグラフであり、 $b$ の情報を一切運ばない。返答 $c=f(H)$ は $b$ と独立な一つのビットに定まり、 $b$ は一様であるから、どの返答規則でも受理確率はちょうど $1/2$ である。これは定理 2.3の上界 $1/2+\delta_3$ の中に収まる。

一回の健全性上界 $9/16$ は定義 1.1の $1/3$ 以下という規約を満たさない。そこで、verifier は独立な二回以上の課題を同時に送り、全ての返答が正しい場合だけ受理する。

定理 2.5. 正の整数 $k$ に対し、verifier が独立に

b_1,\ldots,b_k\in\{0,1\}, \qquad \pi_1,\ldots,\pi_k\leftarrow\mathsf{LabelPerm}_{n,m}

を生成し、 $H_i=\pi_i(G_{b_i})$ を全て送るとする。prover は $c_1,\ldots,c_k$ を返し、verifier は全ての $i$ で $c_i=b_i$ の場合に限って受理する。このプロトコルは、非同型グラフ対に対して完全性 $1$ をもち、同型グラフ対に対して任意の prover の受理確率が

\left(\frac12+\delta_n\right)^k

以下である。特に $k=2$ なら完全性は $1$ であり、健全性は

\left(\frac12+\delta_n\right)^2 \le\left(\frac9{16}\right)^2 =\frac{81}{256}<\frac13

であるため、 $\mathsf{GNI}$ の対話型証明系を与える。

証明. $G_0,G_1$ が非同型ならば、正直な prover は各 $H_i$ がどちらのグラフと同型かを一意に決定し、 $c_i=b_i$ を全ての $i$ で返す。したがって、受理確率は $1$ である。

$G_0,G_1$ が同型であるとし、一回の条件付き送信分布を前定理と同じ $P_0,P_1$ とする。一回の最適なビット推測確率を

\alpha =\frac12\sum_h\max\{P_0(h),P_1(h)\} \le\frac12+\delta_n

と置く。各回は互いに素な乱数ビット区間を使うので、ランダムなビットベクトルを $\vec B$ と書き、その値を $\vec b$ 、送信グラフの値を $\vec h$ とした条件付き確率は

\Pr[\vec H=\vec h\mid\vec b] =\prod_{i=1}^kP_{b_i}(h_i)

である。

決定性の prover の返答を $\vec c=f(\vec h)$ とする。 $\vec h$ を固定したとき、この返答が当たる項を、全ての候補 $\vec b$ のうち最大の一項で上から抑える。全て有限和なので、積の分配法則を用いて

\begin{aligned} \Pr[f(\vec H)=\vec B] &=2^{-k}\sum_{\vec h}\sum_{\vec b} \mathbf1_{\{f(\vec h)=\vec b\}} \prod_{i=1}^kP_{b_i}(h_i)\\ &\le\sum_{\vec h} \max_{\vec b}\left( 2^{-k}\prod_{i=1}^kP_{b_i}(h_i)\right)\\ &=\prod_{i=1}^k \left(\frac12\sum_{h_i}\max_{b_i\in\{0,1\}}P_{b_i}(h_i)\right)\\ &=\alpha^k \le\left(\frac12+\delta_n\right)^k. \end{aligned}

第3行では、積を最大にする各 $b_i$ を座標ごとに選ぶことができ、その後の $\vec h$ に関する有限和が積へ分解されることを用いた。乱択 prover の成功確率は決定性の戦略の成功確率の加重平均なので、同じ上界を満たす。

各回はちょうど $nm$ 個の乱数ビットを読み、近一様置換の生成、隣接行列の頂点名変更、および返答ビットの比較は最悪時多項式時間で終わる。固定した $k=2$ では verifier の時間と通信量も入力長の多項式であり、上で示した健全性は $1/3$ 未満である。▨

3 非公開コイン型であることの役割

命題 3.1. グラフ非同型プロトコルで verifier が $H$ とともに $b$ を prover へ公開すると、同型グラフ対に対する受理確率を $1$ にする prover が存在する。したがって、その変更後の手続きは $\mathsf{GNI}$ の健全な証明系ではない。

証明. prover はグラフ $H$ を調べず、公開された $b$ をそのまま $c$ として返す。このとき全ての入力と全ての verifier の乱数について $c=b$ なので、verifier は確率 $1$ で受理する。特に $G_0\cong G_1$ という言語外の入力でも受理確率が $1$ となり、健全性上界 $1/3$ に反する。▨

上のプロトコルで verifier のメッセージ $H$ は乱数 $(b,\pi)$ から計算した像であり、乱数そのものではない。したがって、このプロトコルは非公開コイン型プロトコルである。上の命題により示されるのは、この構成で乱数を公開するだけでは、このプロトコルを公開コイン型へ変換することができないという事実である。グラフ非同型について別の公開コイン型プロトコルが存在するかどうかについては、この命題から結論は得られない。

注意 3.2 (本記事で扱わない分類定理). 対話型証明系を一つの計算量クラスとして集め、既存の決定性または非決定性計算量クラスと比較するには、本記事の一プロトコルの確率解析とは別の一般的なシミュレーション定理が必要になる。本記事ではそのようなクラス全体の特徴付けを主張にも証明にも用いない。

4 演習

問題 4.1.

定義 1.1 条件 (c)の「全ての $P^*$ 」を、定義 1.1 条件 (b)で存在を仮定した同じ $P$ だけに置き換えた条件を考える。任意の言語 $L\subseteq\Sigma^*$ について、この弱めた条件と定義 1.1 条件 (a)、定義 1.1 条件 (b)を満たす verifier と prover の組が存在することを示せ。
有限集合 $\Omega$ 上の確率分布 $P_0,P_1$ と写像 $f\colon\Omega\to\{0,1\}$ について、 $b\in\{0,1\}$ を一様に選んで $h$ を $P_b$ に従って選ぶとき $f(h)=b$ となる確率を $\operatorname{succ}(f)$ とする。 $\max_f\operatorname{succ}(f)=\bigl(1+\lVert P_0-P_1\rVert_{\mathrm{TV}}\bigr)/2$ であることを示し、最大値を与える $f$ を一つ求めよ。
グラフ非同型プロトコルを三回独立に並列反復した場合の完全性と健全性上界を求めよ。
乱数を一つも読まない verifier をもつ対話型証明系を決定性対話型証明系という。言語 $L$ が決定性対話型証明系をもつことと $L\in\mathsf{NP}$ が同値であることを示せ。

解答 (演習の要点).

verifier $V$ を、prover から一ビット $c$ を受け取り、 $c=1$ ならば受理し、 $c=0$ ならば拒否する機械とする。 $V$ は乱数を読まず、定数段で停止するので定義 1.1 条件 (a)を満たす。prover $P$ を、 $x\in L$ ならば $1$ 、 $x\notin L$ ならば $0$ を送る戦略とする。prover の計算には制限がないので、 $L$ が決定不能であってもこの戦略は関数として定まる。 $x\in L$ では受理確率が $1$ であるから定義 1.1 条件 (b)が成り立ち、 $x\notin L$ では同じ $P$ との受理確率が $0$ であるから弱めた条件が成り立つ。よって弱めた条件はすべての言語について満たされ、言語について何も主張しない。本来の健全性では、常に $1$ を送る $P^*$ に対しても $x\notin L$ の受理確率が $1/3$ 以下でなければならず、この $V$ はそれを満たさない。
定義により
$\operatorname{succ}(f)=\frac12\sum_{h\in\Omega}\bigl(P_0(h)\mathbf1_{\{f(h)=0\}}+P_1(h)\mathbf1_{\{f(h)=1\}}\bigr)\leq\frac12\sum_{h}\max\{P_0(h),P_1(h)\}$
であり、定理 2.3の証明のとおり $\max\{a,b\}=(a+b+|a-b|)/2$ を用いると右辺は $(1+\lVert P_0-P_1\rVert_{\mathrm{TV}})/2$ に等しい。 $f^\ast(h)=0$ （ $P_0(h)\geq P_1(h)$ のとき）、 $f^\ast(h)=1$ （それ以外）と定めると、各 $h$ で $P_0(h)\mathbf1_{\{f^\ast(h)=0\}}+P_1(h)\mathbf1_{\{f^\ast(h)=1\}}=\max\{P_0(h),P_1(h)\}$ であるから、上の不等式は等号で成り立つ。よって $\max_f\operatorname{succ}(f)=\operatorname{succ}(f^\ast)=(1+\lVert P_0-P_1\rVert_{\mathrm{TV}})/2$ である。とくに $P_0=P_1$ ならば最大値は $1/2$ であり、どの返答規則も推測の成功確率を $1/2$ より大きくすることができない。
非同型の場合の完全性は $1$ である。同型の場合の健全性は $(1/2+\delta_n)^3\le(9/16)^3=729/4096$ である。
$L\in\mathsf{NP}$ とし、§E18.11 定理 3.1により多項式時間検証器 $W$ と長さ上界 $p$ を取る。verifier $V$ は prover から語 $y$ を受け取り、 $|y|\leq p(|x|)$ でなければ拒否し、そうでなければ $W(x,y)$ を模倣してその結論を出力する。乱数は読まない。 $x\in L$ ならば、 $W$ が受理する証明書を送る prover により受理確率は $1$ である。 $x\notin L$ ならば、どの prover が送るどの $y$ についても $W(x,y)$ は拒否するので受理確率は $0$ である。よって $L$ は決定性対話型証明系をもつ。

逆に、 $L$ が決定性対話型証明系 $V$ と多項式 $p$ をもつとする。乱数を読まないので、prover の決定性の戦略を固定すると対話は一つに定まり、受理確率は $0$ か $1$ である。完全性により、 $x\in L$ ならばある $P$ について受理確率は $2/3$ 以上、すなわち $1$ である。健全性により、 $x\notin L$ ならばすべての $P^*$ について受理確率は $1/3$ 以下、すなわち $0$ である。証明書を、対話で prover が送るメッセージの列 $(m_1,\ldots,m_j)$ を区切り記号で連結した語とする。定義 1.1 条件 (a)により通信量は $p(|x|)$ 以下であるから、証明書の長さは多項式で抑えられる。検証器は、 $V$ を模倣し、 $V$ が prover のメッセージを待つたびに証明書の次の成分を与え、 $V$ の結論を出力する。 $x\in L$ ならば、受理する対話の prover のメッセージの列が証明書になる。 $x\notin L$ ならば、どのメッセージの列も、それを送る prover の戦略に対応するので受理されない。検証器は $p(|x|)$ 段の模倣で停止するので多項式時間検証器であり、§E18.11 定理 3.1により $L\in\mathsf{NP}$ である。したがって、乱数を用いない verifier では、 $\mathsf{NP}$ に属さない言語に対話型証明系を与えることはできない。

▨

§E18.15対話型証明

1 プロトコルと量化

2 グラフ非同型の非公開コイン型プロトコル

3 非公開コイン型であることの役割

4 演習

参考文献