対話証明系の定義

対話チューリング機械

対話証明系を理解するために、まず対話チューリング機械の概念を導入します。

定義（対話チューリング機械; Interactive Turing Machine）

対話チューリング機械(interactive Turing machine)とは, 以下の六つのテープからなる決定的チューリング機械です:

  1. 入力テープ (read-only)
  2. ランダムシードテープ (read-only)
  3. 作業テープ (read/write)
  4. 受信テープ (read-only)
  5. 送信テープ (write-only)
  6. 出力テープ (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$が充足可能であるという事実に加え, その充足割り当てが何かという情報も得ることができます. ゼロ知識証明とは, このような余分な情報の漏洩は許さず, 証明が有効であること以外には何も情報を漏らさないような対話証明です.

グラフ非同型性問題の例

グラフ非同型性判定問題に対する対話証明系は、対話証明系の代表的な例として有名です。

定義（グラフ同型性判定問題）

同一の頂点集合$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: グラフ非同型性判定問題に対する対話証明系