概念

交互式证明

IP 系统通过多轮问答验证命题，零知识性质保证验证者除命题真假外一无所获，图同构等 NP 问题都有零知识证明。

阅读路径

参考可汗学院 Get ready 机制：先修概念 → 当前概念 → 进阶概念，✓ 表示已读。

交互式证明密码学

01定义

交互式证明（IP）让证明者与验证者多轮问答：完备性保证真命题可被说服，可靠性保证假命题骗不过人，零知识性质保证验证者除命题真假外一无所获。图同构等 NP 问题都有零知识证明——「证明」成了可设计的信息流。

交互式证明：质询-应答的多轮博弈

存在模拟器能不看证明就生成与真实对话同分布的记录——验证者「学到的一切」皆可自造，故实际未获知识；数学上精确的「不泄露」。

Goldwasser-Micali-Rackoff 1985 年定义 ZK；Goldreich-Micali-Wigderson 证明任何 NP 命题（承诺 schemes 存在时）都有零知识证明——密码学可行性的分水岭。

多 prover 与量子版本不断扩展边界：IP = PSPACE（Shamir 1992）、MIP* = RE（2020，解决 Connes 嵌入猜想）——交互证明理论直抵算子代数深处。

\Pr[V\ \text{接受}\mid x\in L]\geq\tfrac23,\quad \Pr[V\ \text{接受}\mid x\notin L]\leq\tfrac13

Goldwasser、Micali、Rackoff 1985 年论文发明零知识概念（2012 哥德尔奖）；Shamir 证明 IP=PSPACE；MIP*=RE 是 2020 年代理论计算机科学的里程碑。

隐私认证的数学基础、区块链 zk-Rollup 扩容、身份验证协议（不泄露口令）、同态加密的可验证性补充。

零知识三染色：每轮只开一条边换轮次：证明者每轮重排颜色，验证者抽查一条边——泄露为零

轮次1