Interactive Proof System

我彷佛有了偷窃的癖好，透过纸张窥探他人的思想。但我又好像什么都没偷到，只在心头平添了几片乌云。

# dIP，IP，AM，MA

考虑两个函数$f,g:\{0,1\}^*\rightarrow\{0,1\}^*$，记号$\langle f,g\rangle(x)$ 表示了从$f$ 开始的若干次轮流计算：

$$\begin{aligned} & a_1=f(x)\\ & a_2=g(x,a_1)\\ & ...\\ & a_{k-1}=f(x,a_1,...,a_{k-2})\\ & a_k=g(x,a_1,...,a_{k-1}) \end{aligned}$$

而$\langle f,g\rangle_f(x)$ 表示，这么多组轮询后，最后一次$f$ 的输出，即$a_{k-1}$。同理$\langle f,g\rangle_g(x)=a_k$ 表示最后一次$g$ 的输出。

Proof：$\textnormal{dIP}\subseteq\textnormal{NP}$：对于$L\in \textnormal{dIP}$，存在函数$V,P:\{0,1\}^*\rightarrow\{0,1\}^*$，使得$\langle V,P\rangle_V(x)=1$。

而$\langle V,P\rangle_V(x)$ 有一个多项式级别的轮询计算结果$(x,a_1,a_2,...,a_{O(n^c)})$，很显然他就可以作为 NP 问题的一个 certificate，用于验证。

反之$\textnormal{NP}\subseteq \textnormal{dIP}$ 就是因为 NP 问题的 verification 实际上就是一轮的$\langle V,P\rangle_V(x)$。

故证毕

我们以一个例子来说明$\textnormal{IP}$ 这个 complexity class。考虑如下语言：

$$\textnormal{GNI}=\{\langle G_1,G_2\rangle\;|\;G_1\textnormal{ is NOT isomorphic to }G_2\}$$

我们证明，$\textnormal{GNI}\in \textnormal{IP}$。

• 尝试 1：

  对于输入$x=\langle G_1,G_2\rangle$，Verifier 直接把$x$ 输出给 Prover。

  由于 Prover 是全知全能的，我们假设它很快正确地分辨出$G_1,G_2$ 是否同构，并把结果返回给 Verifier。

  最后 Verifier 直接输出与 Prover 相反的结果。

​ 这个 protocol 我认为可以帮助理解交互式证明的过程。上述 protocol 是错误的。它满足了 completeness，很显然存在一个函数$P:\{0,1\}^*\rightarrow\{0,1\}^*$，满足$P(G_1,G_2)=G_1,G_2$ 是否同构，存在这样一个正确的函数。但是它不满足 Soundness！很显然，如果 Prover 胡言乱语瞎输出，Verifier 最后直接输出与 Prover 相反的结果并不是一个负责任的行为，也不合理。对于随便一个 Prover，Verifier 显然最后会输出错误的结果。

• 尝试 2：

  对于输入$\langle G_1,G_2\rangle$，Verifier 首先随机抛硬币进入两个分支：

  • 分支 1: Verifier 随机地重新排列$G_1$ 的顶点，得到一个与$G_1$ 同构的图$G_1'$，并将$\langle G_1',G_1\rangle$ 发送给 Prover。
  • 分支 2: Verifier 随机地重新排列$G_2$ 的顶点，得到一个与$G_2$ 同构的图$G_2'$，并将$\langle G_2',G_1\rangle$ 发送给 Prover。

  然后 Prover 返回得到的两个图是否同构，如果同构，则回复 1，反之回复 2。

  最后 Verifier 检查，如果 Prover 多次能得出和抛硬币一样的结果，那就接受。否则就拒绝。

​ 这个 protocol 为什么是正确的呢？我们考虑 completeness 和 soundness 两方面。

​ 对于 completeness，显然$\forall x\in \textnormal{GNI}$，即$G_1,G_2$ 不同构时，存在一个 Prover，这个 Prover 函数就是：$P(F,G)=F,G$ 同构。那么若投硬币进入分支 1，因为$G_1'\cong G_1$，故 Prover 返回 1；若投硬币进入分支 2，因为$G_2'\cong G2\not\cong G_1$，故 Prover 返回 2。显然，Prover 百分之一百会回复让 Verifier 接受的。

​ 对于 soundness，显然$\forall x\notin \textnormal{GNI}$，即$G_1,G_2$ 同构时，对于任意一个 Prover，即使他全知全能他都无法保证让 verifier 接受。因为 prover 得到了两个同构的图，它无法进行任何辨别。所以实际上，如果是均匀随机的话，会导致$Pr[\textnormal{Verifier accept}]=\frac{1}{2}$。我们只需要重复进行多轮问询，一旦有一轮 Prover 回复了错误的答案就直接拒绝，否则运行$k$ 轮 Prover 回答都正确才接受，这样$Pr[\textnormal{Verifier accept}]=1-\frac{1}{2}^k$ 就会很小了。

---

需要注意，还有一个$\textnormal{IP}^*$，就是在$\textnormal{IP}$ 的基础上，要求有 perfect soundness，即：

$$\forall x\notin L,\forall P:\{0,1\}^*\rightarrow\{0,1\}^*,Pr[\langle V,P\rangle_V(x)=1]=0$$

这其实会影响 complexity class 的大小。但是 perfect completeness，即：

$$\forall x\in L,\exists P:\{0,1\}^*\rightarrow\{0,1\}^*,Pr[\langle V,P\rangle_V(x)=1]=1$$

却不会影响！

事实上，我们可以给定一个 verifier $V$ 和一个输入$x$，我们都可以在$O(poly(|x|))$ 的空间内，寻找到一个最优的 prover，使得 verifier accept 的概率最大。

其实我们可以写出一个等价的、更数学和形式化的定义：

1. 我们称语言$L\in\textnormal{MA}$ 当且仅当存在一个概率型图灵机$M$，$M$ 根据$y$ 的取值进行概率选择，使得：

   $$\begin{aligned} & \forall x\in L,\exists z\in\{0,1\}^{O(|x|^c)},Pr_{y\in\{0,1\}^{O(|x|^c)}}[M(x,y,z)=1]\geq\frac{2}{3}\\ & \forall x\notin L,\forall z\in\{0,1\}^{O(|x|^c)},Pr_{y\in\{0,1\}^{O(|x|^c)}}[M(x,y,z)=1]\leq\frac{1}{3} \end{aligned}$$

   注意$z$ 是 Prover Merlin 首先根据输入 send 给 Verifier Arthur 的 string。

   然后 Verifier Arthur 再根据掷硬币结果$y$，输入$x$ 以及 Prover 的 string $z$ 进行判定。

2. 我们称语言$L\in\textnormal{AM}$ 当且仅当存在一个概率型图灵机$M$，$M$ 根据$y$ 的取值进行概率选择，使得：

   $$\begin{aligned} & \forall x\in L,Pr_{y\in\{0,1\}^{O(|x|^c)}}[\exists z\in\{0,1\}^{O(|x|^c)},M(x,y,z)=1]\geq\frac{2}{3}\\ & \forall x\notin L,Pr_{y\in\{0,1\}^{O(|x|^c)}}[\forall z\in\{0,1\}^{O(|x|^c)},M(x,y,z)=1]\leq\frac{1}{3} \end{aligned}$$

   注意$y$ 此时是 Verifier Arthur 先决定掷硬币结果，然后告诉 Prover Merlin，然后 Merlin 根据输入$x$ 和掷硬币结果$y$ 计算出一个$z$ 返回给 Verifier Arthur。

显然地，我们有：

$$\forall k,\textnormal{AM}[k]\subseteq \textnormal{IP}[k]$$

因为$\textnormal{AM}$ 就是在$\textnormal{IP}$ 的基础上，要求第一步附加了掷硬币结果。

# Protocol: Goldwasser-Sipser Set Lowerbound

考虑这样一个问题，假设给定常数$K$ 和一个集合$S$，我们希望：

• $|S|\geq K$ 时，Verifier accept。
• $|S|\leq \frac{K}{2}$ 时，Verifier reject。
• 其余情况 Verifier 作出什么反应都行。

可以看作下面这个语言：

$$L_K=\{S\;|\;|S|\geq K\}$$

的判定问题，而且我们放松了一点条件，就是当$|S|\leq\frac{K}{2}$，即$S$ 离属于这个语言很远时，才要求很高概率拒绝。

注意：这里的集合$S$ 往往是用描述性语刻画的。譬如$S=$"大于 3 的数"，而不是一一列举集合内的元素。这样的集合有一个特点：集合本身可能很大，但是描述的语言很短，而且判断一个元素是否在集合中很容易。

记一个常数$k$，使得$2^{k-2}\leq K\leq 2^{k-1}$，即$k=\lceil\log_2K\rceil+1$。然后 protocol 描述如下：

• Verifier 随机选择一个 pairwise independent hash function $h:\{0,1\}^m\rightarrow \{0,1\}^k$ 和随机一个$y\in\{0,1\}^k$，并将$h,y$ 发送给 Prover。
• Prover 寻找一个$x\in S$，使得$h(x)=y$，并将$x$ 发送给 Verifier。
• Verifier 验证是否$h(x)=y$，如果是则 accept，否则 reject。

其中，pairwise independent hash function 描述如下：

这个定义其实说的是，对于$x,x'\in\{0,1\}^n,x\neq x'$，我们均匀随机选择一个$h$ 的话，会使得二元组$(h(x),h(x'))$ 也是$\{0,1\}^k\times\{0,1\}^k$ 上的均匀分布。一个 pairwise independent function collections 的简单构造就是利用有限域$\textnormal{GF}(2^n)$:

$$\mathcal{H}_{n,n}=\{h_{a,b}\},a,b\in \textnormal{GF}(2^n)\\ h_{a,b}(x)=ax+b$$

我们简单证明下这个确实是 pairwise independent 的：

$$\begin{aligned} & \because h(x)=y\wedge h(x')=y'\\ & \therefore \begin{cases}a\cdot x+b=y\\a\cdot x'+b=y'\end{cases}\\ & \therefore \begin{cases}a=(y-y')\cdot(x-x')^{-1}\\b=y-a\cdot x\end{cases} \end{aligned}$$

所以对于给定的$x,x',y,y'$，均匀随机选择一个$h_{a,b}\in\mathcal{H}_{n,n}$，选到满足上述条件的$a,b$ 的概率为$\frac{1}{2^n}\cdot\frac{1}{2^n}=2^{-2n}$。

---

下面我们回到 Protocol: Goldwasser-Sipser Set Lowerbound 正确性的讨论。

• Soundness 是简单的。当$|S|\leq\frac{K}{2}$，会有$|h(S)|\leq\frac{K}{2}$。所以从$\{0,1\}^k$ 中均匀随机选择一个$y$，那么$y\in h(S)$ 的概率就最多是$\frac{K}{2^{k+1}}$。故存在$x$，使得$h(x)=y$ 的概率也最多是$\frac{K}{2^{k+1}}$，即 Verifier accept 的概率也不超过$\frac{K}{2^{k+1}}\leq\frac{1}{4}$。

• Completeness 需要一定证明。首先，不失一般性地，我们假设$K\leq |S|\leq 2^{k-1}$。因为当$|S|>2^{k-1}$ 时，Verifier 可以找到一个子集$T\subseteq S$ 并且$|T|\leq 2^{k-1}$。然后如果 Prover 能让 Verifier 相信$|T|\geq K$，那么 Verifier 也就应该相信$|S|\geq K$ 了。

  我们证明，对于每一个$y\in\{0,1\}^k$，都有：

  $$\textnormal{Pr}_h[\exists x\in S,h(x)=y]\geq\frac{3}{4}\frac{|S|}{2^k}$$

  根据抽屉原理，其实有：

  $$\begin{aligned} \textnormal{Pr}_h[\exists x\in S,h(x)=y] &=\textnormal{Pr}_h[\bigvee_{x\in S}h(x)=y]\\ &\geq\sum_{x\in S}\textnormal{Pr}_h[h(x)=y]-\frac{1}{2}\sum_{x\neq x'\in S}\textnormal{Pr}_h[h(x)=y\wedge h(x')=y]\\ &=|S|\cdot\frac{1}{2^k}-\frac{|S|(|S|-1)}{2}\cdot\frac{1}{2^{2k}}\\ &>\frac{|S|}{2^k}(1-\frac{|S|}{2^{k+1}})\\ &>\frac{|S|}{2^{k}}(1-\frac{2^{k-1}}{2^{k+1}})\\ &=\frac{3}{4}\frac{|S|}{2^k} \end{aligned}$$

  注意，其中第三行是因为，给定一个$x\in S$ 和$y\in\{0,1\}^k$，那么随机选择一个$h$ 使得$h(x)=y$ 的概率为$2^{-k}$，实际上是一个 sound 的（和随机无法分辨的）hash function 就有给定$x\in A,y\in B,\textnormal{Pr}_h[h(x)=y]=\frac{1}{|B|}$，而且 k-wise independent 其实就是要求：

  $$\textnormal{Pr}_h[h(x_1)=y_1\wedge ...\wedge h(x_n)=y_n]=\prod_{i=1}^n\textnormal{Pr}_h[h(x_i)=y_i]=\frac{1}{|B|^n}$$

  此时因为$|S|\geq K$，所以:

  $$\frac{3}{4}\frac{|S|}{2^k}\geq \frac{3K}{2^{k+2}}$$

下面我们思考一个事情。令$p=\frac{K}{2^k}$，那么有：

• 当$|S|\leq\frac{K}{2}$ 时，对于任意 Prover，一轮交互下来，Verifier 只随机选了一个函数，Verifier accept 的概率不超过$\frac{1}{2}p$。
• 当$|S|\geq K$ 时，存在一个 Prover，一轮交互下来，Verifier 只随机选了一个函数，Verifier accept 的概率大于等于$\frac{3}{4}p$。

我们希望通过一次选择$M$ 个函数，把这个概率差距拉大。我们考虑如下 protocol：

• Verifier 随机选择$M$ 个 pairwise independent hash function $h_1,...,h_M:\{0,1\}^m\rightarrow \{0,1\}^k$ 和随机$M$ 个$y_1,...,y_M\in\{0,1\}^k$，并将$h_1,...,h_M,y_1,...,y_M$ 发送给 Prover。
• Prover 寻找$M$ 个$x_1,...,x_M\in S$，使得$\forall i,h(x_i)=y_i$，并将$x_1,...,x_M$ 发送给 Verifier。
• Verifier 验证，若有$\frac{3Mp}{4}$ 个以上的满足$h(x_i)=y_i$，则接受。否则如果有小于等于$\frac{Mp}{2}$ 个$h(x_i)=y_i$ 的话，就拒绝。

我们可以通过选择$M$，使得：

1. $|S|\geq K$ 且没有$\frac{3Mp}{4}$ 个以上的满足，这件事概率很小。
2. $|S|\leq\frac{K}{2}$ 且有$\frac{Mp}{2}$ 个以上的满足，这件事概率也很小。

随着$M$ 的增加，那么 1. 和 2. 的概率将越变越小。

# 一些结论

$$\begin{aligned} & \textnormal{coNP}\subseteq\textnormal{IP}\\ & \forall k,\textnormal{AM}[k]\subseteq \textnormal{IP}[k]\subseteq AM[k+2]\\ & \forall k\geq 2,\textnormal{AM}[k]=\textnormal{AM}[2] \end{aligned}$$