交互式证明系统

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

设输入是各有 $n$ 个顶点的两张图 $G_0,G_1$。验证者私下均匀选择 $b\in \{0,1\}$，再均匀选择顶点置换 $\pi$，只发送重标号图 $H=\pi (G_b)$。证明者回复一位 $b^{\prime }$，验证者恰在 $b^{\prime }=b$ 时接受。计算和发送 $H$ 都只需要多项式资源。

若两图非同构，它们的重标号集合不相交，全能证明者可以枚举置换辨认来源，正确率为 $1$。若两图同构，均匀重标号产生相同的分布：对任一收到的 $H$，秘密位 $b$ 仍然均匀。因此任何策略猜中概率至多 $1/2$，不是因为证明者算得不够快。连续做两轮、每轮使用新私有随机性且要求全对，即得可靠性误差 $1/4$；即使第二轮回答依赖第一轮对话，条件猜中率仍至多 $1/2$。

上述精确完备性1先采用均匀置换随机原语。公平 bit 的实现可以逐步抽取 Fisher–Yates 交换下标：每次整数拒绝采样最多尝试 $K=\lceil {\log }_2(6n)\rceil$ 轮，耗尽就拒绝，$n\ge 2$ 时两次协议的总抽样失败概率至多 $2n{2}^{-K}\le 1/3$。每个下标成功后的值仍精确均匀，成功概率只依赖下标范围，不依赖秘密位或所选置换。因此完成抽样后的来源仍不可区分，可靠性至多 $1/4$ 保持，而完备性至少 $2/3$；全部运行时间有多项式上界。少于两个顶点的图直接判定。

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

交互证明以随机验证理路随机化算法Randomized algorithm把随机比特作为额外输入并分析输出正确率或运行时间分布的算法。和语言理路形式语言Formal language · Language over an alphabet固定字母表上有限字的任意集合，是识别器、文法与判定问题共同描述的对象。为基础。算术化理路算术化Arithmetization把布尔关系嵌入有限域低次多项式，使离散正确性声明可由随机代数恒等式检查。把离散声明改写为低次多项式，Sum-check理路Sum-check 协议Sum-check protocol · Sumcheck protocol以逐变量低次多项式承诺和随机挑战验证 Boolean cube 上指数项多项式求和的交互协议。给出逐变量随机检查，二者共同进入IP = PSPACE理路IP = PSPACEIP equals PSPACE · Shamir's theorem多项式时间随机交互验证恰好能够判定全部多项式空间语言。 的证明；完整类等式由定理页承担，本页只定义 prover/verifier、轮数与 completeness/soundness。零知识理路零知识证明Zero-knowledge proof证明者使验证者相信陈述为真而不泄露额外知识的交互证明。另加信息泄露约束，Fiat–Shamir 则改变交互与安全模型。