交互式证明系统 | Codeboy's Blog

形式陈述

对语言 $L\subseteq\{0,1\}^*$ ，交互式证明系统由诚实证明者 $P$ 与概率验证者 $V$ 的多轮消息协议组成。验证者在输入 $x$ 上运行概率多项式时间，证明者通常不受计算资源限制；协议还把交互轮数以及验证者会读取和处理的消息长度限制在 $|x|$ 的多项式内，超出接口长度的内容可被忽略或直接拒绝。这个通信界是模型条件，不能只从作弊证明者也会自觉发送短消息推出。记 $\langle P,V\rangle(x)$ 为一次交互，并以 $V$ 最终输出 $1$ 表示接受。

标准常数误差定义要求：

x\in L \Longrightarrow \Pr[\langle P,V\rangle(x)=1]\ge \frac23,

x\notin L \Longrightarrow \forall P^*,\quad \Pr[\langle P^*,V\rangle(x)=1]\le \frac13.

第一式是完整性，使用协议指定的诚实证明者；第二式是可靠性，量化所有证明者策略，包括计算无界的作弊者。概率至少取自验证者的私有随机性，也包括协议若允许的证明者随机性。常数 $2/3$ 与 $1/3$ 不是本质选择：通过使用独立随机性的适当重复和聚合，可把误差降至可忽略量而仍保持多项式通信与验证时间。复杂性类 $\mathrm{IP}$ 收集具有这类协议的语言。

直觉

交互式证明把静态证明串变成验证者与证明者的多轮对话。验证者用随机挑战抽查一个自己无法完整计算的全局事实；证明者若不知道后续问题，就必须让先前回答与许多可能挑战同时相容。诚实证明者可以利用无限计算能力组织答案，复杂度只要求验证者和整个接口保持高效。完整性回答“真命题是否能被说服”，可靠性回答“假命题能否被任何策略伪装成真”，两者的量词方向不能交换。

例子与边界

图非同构的经典协议中，verifier 随机选一张图并随机重标号，prover 要判断来源；若两图非同构，全能 prover 总能分辨，若同构则挑战分布相同，作弊成功率至多 $1/2$ ，重复可放大。

证明者计算无界不代表能读取验证者尚未公开的私有随机位；若挑战提前公开，许多协议会失去可靠性。普通交互式证明的可靠性约束所有作弊证明者，因而是信息论性质，不依赖计算困难假设。若只要求概率多项式时间的作弊证明者难以欺骗，则得到的是计算可靠的 argument，其安全参数、对手类和困难假设必须另行声明。

推论与应用

交互证明以随机验证和语言为基础。算术化把离散声明改写为低次多项式，Sum-check给出逐变量随机检查，二者共同进入IP = PSPACE 的证明；完整类等式由定理页承担，本页只定义 prover/verifier、轮数与 completeness/soundness。零知识另加信息泄露约束，Fiat–Shamir 则改变交互与安全模型。

参考资料

Sanjeev Arora, Boaz Barak, Computational Complexity: A Modern Approach (2009), interactive proofs.
Shafi Goldwasser, Silvio Micali, Charles Rackoff, The Knowledge Complexity of Interactive Proof Systems (1989), interactive proofs and knowledge complexity.

形式陈述 ​

反向链接

形式陈述