§E15.15対話型証明

最終更新

対話型証明では、計算能力に制限のない prover が、確率的多項式時間の verifier とメッセージを交換する。正しい入力では、ある prover が高い確率で verifier を受理させることを完全性が要求する。誤った入力では、どのような prover も高い確率では受理させることができないことを健全性が要求する。二つの条件では prover に対する量化が逆になる。

1 プロトコルと量化

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

補題 2.2.n≥2n\ge2とし、

m=⌈log⁡2(8n(n−1))⌉m=\left\lceil\log_2\bigl(8n(n-1)\bigr)\right\rceil

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

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

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

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

∥P−Q∥TV=12∑ω∣P(ω)−Q(ω)∣\lVert P-Q\rVert_{\mathrm{TV}} =\frac12\sum_\omega|P(\omega)-Q(\omega)|

と定める。

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

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

となる。

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

Q=(1−ε)U+εRQ=(1-\varepsilon)U+\varepsilon R

である。よって

∥Q−U∥TV=ε∥R−U∥TV≤ε≤δn\lVert Q-U\rVert_{\mathrm{TV}} =\varepsilon\lVert R-U\rVert_{\mathrm{TV}} \le\varepsilon\le\delta_n

となる。

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

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

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

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

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

12+δn≤916\frac12+\delta_n\le\frac9{16}

である。

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

次にG0G_0とG1G_1が同型であるとする。G1=τ(G0)G_1=\tau(G_0)となる置換τ∈Sn\tau\in S_nを固定する。b=jb=jの条件下で送られるHHの分布をPjP_jとする。置換が一様分布UUに従う理想的な場合には、写像π↦πτ\pi\mapsto\pi\tauがSnS_n上の全単射であるため、b=0b=0とb=1b=1の送信グラフは同じ分布P∗P_*をもつ。

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

∥ϕ(P)−ϕ(Q)∥TV=12∑h∣∑ω:ϕ(ω)=h(P(ω)−Q(ω))∣≤12∑ω∣P(ω)−Q(ω)∣=∥P−Q∥TV.\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により

∥P0−P∗∥TV≤δn,∥P1−P∗∥TV≤δn.\lVert P_0-P_*\rVert_{\mathrm{TV}}\le\delta_n, \qquad \lVert P_1-P_*\rVert_{\mathrm{TV}}\le\delta_n.

三角不等式から∥P0−P1∥TV≤2δn\lVert P_0-P_1\rVert_{\mathrm{TV}}\le2\delta_nを得る。

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

12∑h(P0(h)1{f(h)=0}+P1(h)1{f(h)=1})≤12∑hmax⁡{P0(h),P1(h)}=12(1+∥P0−P1∥TV)≤12+δn.\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\max\{a,b\}=(a+b+|a-b|)/2を有限和へ適用した結果である。乱択 prover の受理確率も決定性の戦略の受理確率の加重平均なので、同じ上界を満たす。▨

例 2.4 (三角形と道に対するプロトコルの実行). 頂点集合[3][3]上で、G0G_0を辺{1,2},{2,3},{1,3}\{1,2\},\{2,3\},\{1,3\}をもつ三角形、G1G_1を辺{1,2},{2,3}\{1,2\},\{2,3\}だけをもつ道とする。頂点名の付け替えは辺の本数を変えないため、辺数33のG0G_0と辺数22のG1G_1は同型でなく、⟨G0,G1⟩∈GNI\langle G_0,G_1\rangle\in\mathsf{GNI}である。

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

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

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

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

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

b1,…,bk∈{0,1},π1,…,πk←LabelPermn,mb_1,\ldots,b_k\in\{0,1\}, \qquad \pi_1,\ldots,\pi_k\leftarrow\mathsf{LabelPerm}_{n,m}

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

(12+δn)k\left(\frac12+\delta_n\right)^k

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

(12+δn)2≤(916)2=81256<13\left(\frac12+\delta_n\right)^2 \le\left(\frac9{16}\right)^2 =\frac{81}{256}<\frac13

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

証明.G0,G1G_0,G_1が非同型ならば、正直な prover は各HiH_iがどちらのグラフと同型かを一意に決定し、ci=bic_i=b_iを全てのiiで返す。したがって、受理確率は11である。

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

α=12∑hmax⁡{P0(h),P1(h)}≤12+δn\alpha =\frac12\sum_h\max\{P_0(h),P_1(h)\} \le\frac12+\delta_n

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

Pr⁡[H⃗=h⃗∣b⃗]=∏i=1kPbi(hi)\Pr[\vec H=\vec h\mid\vec b] =\prod_{i=1}^kP_{b_i}(h_i)

である。

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

Pr⁡[f(H⃗)=B⃗]=2−k∑h⃗∑b⃗1{f(h⃗)=b⃗}∏i=1kPbi(hi)≤∑h⃗max⁡b⃗(2−k∏i=1kPbi(hi))=∏i=1k(12∑himax⁡bi∈{0,1}Pbi(hi))=αk≤(12+δn)k.\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行では、積を最大にする各bib_iを座標ごとに選ぶことができ、その後のh⃗\vec hに関する有限和が積へ分解されることを用いた。乱択 prover の成功確率は決定性の戦略の成功確率の加重平均なので、同じ上界を満たす。

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

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

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

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

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

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

4 演習

問題 4.1.

  1. 完全性の prover に対する量化が「あるPP」であり、健全性の prover に対する量化が「全てのP∗P^*」である理由を説明せよ。
  2. G0≅G1G_0\cong G_1の場合、二つの条件付き送信分布P0,P1P_0,P_1の全変動距離が2δn2\delta_n以下になる理由と、一回のビット推測成功確率が1/2+δn1/2+\delta_n以下になる理由を説明せよ。
  3. グラフ非同型プロトコルを三回独立に並列反復した場合の完全性と健全性上界を求めよ。
  4. verifier が置換π\piだけを公開し、選択ビットbbを隠した場合、この手続きが定義 1.2の公開コイン型プロトコルではない理由を説明せよ。
解答 (演習の要点).
  1. 正しい入力では証明を知る一つの戦略が成功すればよいが、誤った入力では verifier を欺こうとするどの戦略にも受理確率の上界を課す必要があるためである。
  2. 一様置換を使う理想分布P∗P_*は、π↦πτ\pi\mapsto\pi\tauの全単射性により二つの選択ビットで共通である。各PjP_jはP∗P_*から全変動距離δn\delta_n以下なので、三角不等式から∥P0−P1∥TV≤2δn\lVert P_0-P_1\rVert_{\mathrm{TV}}\le2\delta_nを得る。二分布を等確率で選んだ後の最適な推測成功確率は(1+∥P0−P1∥TV)/2(1+\lVert P_0-P_1\rVert_{\mathrm{TV}})/2なので、1/2+δn1/2+\delta_n以下である。
  3. 非同型の場合の完全性は11である。同型の場合の健全性は(1/2+δn)3≤(9/16)3=729/4096(1/2+\delta_n)^3\le(9/16)^3=729/4096である。
  4. verifier が判定に使う乱数(b,π)(b,\pi)のうちbbが prover に公開されていないためである。乱数から得た一部の情報を送るだけでは公開コイン型の定義を満たさない。

▨

参考文献

  1. Shafi Goldwasser, Silvio Micali, and Charles Rackoff, The Knowledge Complexity of Interactive Proof Systems, SIAM Journal on Computing 18 (1989), no. 1, 186–208.対話型証明系の完全性と健全性、および確率的検証者の形式化を参考にした。
  2. Oded Goldreich, Foundations of Cryptography: Basic Tools, vol. 1, Cambridge University Press, Cambridge, 2001.対話型証明、非公開コイン型・公開コイン型、およびグラフ非同型の基本プロトコルを参考にした。