交互式证明

交互式证明系统（Interactive Proof System），是计算复杂理论中的一类计算模型。Goldwasser 等人在 [GMR85] 中从密码学的角度考虑交互证明并且给出了正式的定义。

简单来讲，交互证明首先是一个“证明”，证明的目的就是为了让人相信某个 陈述（statement）是正确的，而交互证明中的“交互”是指在证明的过程中，证明陈述的一方（记为证明者 Prover，P）与听证明陈述的一方（记为验证者 Verifier，V）存在交互，也就是 V 会时不时提出一些问题，而 P 会回答这些问题。

什么是陈述？

在上面不怎么正式的定义中提到的陈述（statement），其实在计算复杂理论中有一个对应概念：语言（Language）。

语言可以表示为二进制位串（string）的集合，即 $L \subseteq \{0, 1\}$*。那么一个陈述就是描述某个对象 $x$ 和这个语言 $L$ 的所属关系，即 $x \in L$ 。如果对象 $x$ 确实属于语言 $L$，那么这个陈述就是真的，反之如果对象 $x$ 不属于语言 $L$，那么这个陈述就是假的。

举个例子，陈述为：“5是奇数”。那么对象就是“5”，语言就是“奇数的集合”，显然这个陈述是真的。

为什么需要交互？

在非正式定义中的提到的 Prover 和 Verifer 是交互证明的主体。从抽象的角度，我们可以把这两者看成是算法，他们有共同的输入 $x$ 和 $L$，他们之间可以相互收发消息，最终由 V 输出对陈述的验证结果。

那么，为什么我们需要 P 和 V 交互呢？没有交互的证明——我们可以想象一下 P 直接把证明过程写在一张纸上然后交给 V——也称为一次性证明（One-shot proof）有什么缺陷呢？

答案是：交互使得可以被证明的陈述范围大大增加。没有交互的证明系统的证明范围只局限在 NP 之中，而交互证明系统的证明范围（记为 IP）可以扩展到 PSPACE。事实上，Shamir 在 [Shamir92] 中严谨地证明了 $IP=PSPACE$。

非交互证明“P 直接把证明过程写在一张纸上然后交给 V”的场景需要有一个前提条件：能直接写出来的证明过程是存在的。比如说 NP 问题，定义中的证据（witness） 就可以被直接写下来当作证明；但是很多的非 NP 问题，并没有这样一个能直接给出来的证明。

下面就举一个很有趣的例子，我们可以称它为“盲人袜子”问题。

“盲人袜子”问题

有这样一个问题：有两只除了颜色外完全一样的袜子，如何向盲人证明这两只袜子确实颜色不同？在这个场景里，我们是 P，盲人是 V。很显然，不管我们向盲人说什么都无法让盲人相信这两只袜子颜色不同，因为我们和盲人在视觉上的能力存在差异。交互证明可以很好地解决这个问题：盲人需要自己参与到证明中来才能相信这个陈述。

以下是具体的交互证明：

---

1. P 和 V 首先有一个共同的输入，即“$W_1$（假设是红色）和 $W_2$（假设是绿色）这两只袜子颜色不一样”这样一个陈述。

2. V 把（$W_1$, $W_2$）作为初始状态 $S_0$ 发送给 P。

3. V 随机地 （比如说可以通过抛硬币）决定自己要不要改变这样的状态：

   • 如果决定改变，那么就把（$W_2$, $W_1$）发送给 P；
   • 如果决定不改变，那么就还是把（$W_1$, $W_2$）发送给 P。

   注意到盲人 V 虽然无法分清楚颜色，但他可以通过改变两只袜子的相对位置来改变状态。

   假设 V 最后发送给 P 的状态记为 $S_1$。

4. P 收到 V 发来的状态 $S_1$，对比初始状态 $S_0$：

   • 如果 $S_1 = S_0$，那么就回复 1 给 V；
   • 如果 $S_1 \neq S_0$，那么就回复 0 给 V。

   注意到如果两只袜子颜色是一样的，那么即使是非盲人 P 也无法区分状态（$W_1$, $W_2$）和状态（$W_2$, $W_1$）。

5. V 收到 P 的回复，结合自己在步骤 3 的选择，判断：

   • 如果自己在步骤 3 中确实改变了状态且收到的回复是 0，或者自己在步骤 3 中没有改变状态且收到的回复是 1，那么就相信两只袜子不一样这个陈述，输出 1。
   • 反之，如果自己在步骤 3 中确实改变了状态但收到的回复是 1，或者自己在步骤 3 中没有改变状态但收到的回复是 0，那么说明 P 回答错误，V 就不相信这两只袜子不一样的陈述，输出 0。

---

上述的交互证明能够保证，在陈述正确时，诚实的 P 能让 V 相信这个陈述是正确的。这是交互证明的 完备性（Completeness）。

但是如果是陈述不正确时，即两只袜子颜色一样但是 P 想骗盲人 V 这两只袜子颜色不一样呢？

注意到在步骤 4 中，如果两只袜子颜色是一样的，那么那么即使是非盲人 P 也无法区分状态（$W_1$, $W_2$）和状态（$W_2$, $W_1$），也就是说 P 在这一步骤中只能瞎猜 V 在步骤 3 中到底有没有改变初始状态，显然 P 这么做得逞的概率就是 $\frac{1}{2}$。这是一个不小的概率，那么有没有方法能减小这个概率呢？

有的并且很简单，就是不断地重复步骤 2 ~ 步骤 5，P 总不能一直瞎猜蒙混过关都得逞吧？

严谨一点分析，假设重复了 $n$ 次上述证明过程，那么 P 不露馅每一次都能成功猜对的概率仅为 $(\frac{1}{2})^n$，当 $n$ 很大时，这是一个小到可以忽略的数字。所以完善后的交互证明能够保证在陈述不正确时，任何 P 都无法骗取盲人 V 的信任让 盲人 V 相信这个陈述正确。这是交互证明的 可靠性（Soundness）。

交互证明的定义

现在我们可以抽象地给出交互证明的正式定义。

---

（定义：交互证明） 给定语言 $L$，如果算法 $P$ 和 $V$ 满足：

• 完备性：$\forall x \in L$，

$$Pr[<P, V>(x) = 1] \ge \frac{2}{3}$$

• 可靠性：$\forall \notin L$， $\forall$ 算法 $P$*，

$$Pr[<P^*, V>(x) = 1] \le \frac{1}{3}$$

就说算法元组（$P$，$V$）是语言 $L$ 的交互式证明系统。

---

注意到定义中的常数项 $\frac{2}{3}$ 和 $\frac{1}{3}$ 是任意选取的，因为就像在盲人袜子的例子中那样，我们可以通过不断重复证明过程来将完备性的常数项 $\frac{2}{3}$ 加强到 1，而将可靠性的常数项 $\frac{1}{3}$ 加强到 0。

一般而言，交互证明中的 P 的 计算能力是无限的（Computational unbounded），而 V 的 计算能力是有限的（Computational bounded）。比如在盲人袜子的例子中，证明者 P 和验证者盲人 V 在视觉上的能力是存在差异的，否则如果两者能力相同的话，就不需要P 去向 V 证明袜子是不同颜色的了，V 自己也能看到这个事实。

另外，交互证明系统中，V 在和 P 交互中需要做出随机的决定，就像盲人袜子中盲人在步骤 3 做的那样。如果 V 的决定不是随机的，而是遵循着某种规律，那么这样的交互证明就退化成非交互证明了，因为 P 自己可以遵循着同样的规律（即 P 可以 模拟 V 发送给它的消息）而不需要真正地与 V 交互。

下面举一个经常出现的用来说明交互证明的例子作为本文的结束。

图不同构问题

给定两个图 $G_0$，$G_1$，判断两者是否是同构的，即是否存在映射 $\pi$ 使得 $G_0 = \pi (G_1)$。

判定图同构问题（Graph Isomorphism，GI）被认为是属于 NP 问题，同构映射关系 $\pi$ 就是就是证据（witness）同时也是可以当作证明；但是判断 图不同构问题（Graph Non-Isomorphism，GNI）是否属于 NP 还未知，穷举地说明 $G_0$ 与 $G_1$ 不存在同构映射关系是不合适的，也不能当作证明。有了交互证明后，可以肯定的是，GNI 问题一定属于 IP。

以下为 GNI 的交互证明：

参考资料

[GMR85]: Shafi Goldwasser, Silvio Micali, and Charles Rackoff. “The knowledge complexity of interactive proof-systems.” symposium on the theory of computing (1985): 291-304. pdf: http://groups.csail.mit.edu/cis/crypto/classes/6.876/papers/gmr-ZK.pdf

[Shamir92]: Adi Shamir. “IP = PSPACE.” JACM 39, 4 (October 1992), 869–877. DOI: https://doi.org/10.1145/146585.146609