零知识证明

零知识要求验证者在交互后得到的完整视图，可由一个不知道见证的模拟器高效生成。若真实视图和模拟视图不可区分，验证者便没有获得模拟器凭公开陈述和辅助输入无法产生的额外信息。声明为真、验证是否成功和消息长度仍可公开；零知识并不是“交互完全没有信息”。

完备性、可靠性、知识可靠性与零知识是不同轴。一个协议可以不泄露见证，却不能证明发送者确实“知道”见证；后者需要知识证明理路知识证明Proof of knowledge · PoK要求任何以超过知识误差的概率说服验证者的证明者，都对应一个能提取有效见证的算法。的 extractor、knowledge error 与运行时间条件。反过来，可提取协议也可能直接泄露 witness，故 PoK 不蕴含 ZK。

图同构的一轮协议与模拟 ​

公开同顶点数的图 $G_0,G_1$，证明者持有同构 $\phi :G_0\to G_1$。一轮按以下次序进行：

1. 证明者均匀抽取顶点置换 $\rho$，发送 $H=\rho (G_0)$。
2. 诚实验证者均匀发送挑战 $b\in \{0,1\}$。
3. 证明者发送 $\tau =\rho \circ {\phi }^{-b}$；验证者检查 $\tau$ 是置换且 $\tau (G_b)=H$。

当 $b=0$ 时回应为 $\rho$；当 $b=1$ 时先用 ${\phi }^{-1}$ 回到 $G_0$，再用 $\rho$。所以真命题总被接受。若同一个 $H$ 的两种挑战都能被回答，${\tau }_1^{-1}\circ {\tau }_0$ 就是 $G_0\to G_1$ 的同构；非同构输入至多能应付一种挑战，单轮可靠性误差至多 $1/2$。新鲜随机币的顺序重复 $k$ 轮将误差降至 $2^{-k}$。

诚实验证者模拟器不需要见证：先均匀选 $b$ 和置换 $\tau$，再令 $H=\tau (G_b)$，输出 $(H,b,\tau )$。对真命题，固定 $b$ 后真实回应也是均匀置换，所以两种 transcript 分布完全相同。这里以均匀置换抽样为原语，具体证明的是完美 HVZK。用公平比特精确生成均匀置换可通过期望多项式时间的拒绝抽样实现，因此本段精确分布比较选择 expected-PPT 模拟器；若要求最坏时间有界，则须截断抽样并另计统计误差。恶意验证者可能依 $H$ 选挑战，不能沿用“先选 $b$”的一步模拟，须另证 rewinding 的分布和期望运行时间。见 Goldreich 第一卷 §4.3.2。

若可靠性只约束高效作弊证明者，所得对象是 argument 而非 proof。rewinding 模拟通常对会话调度敏感，安全会话任意并发后可能不再零知识。针对一般关系的非交互零知识通用构造通常引入 CRS、随机预言机或其他 setup；Fiat–Shamir 之类变换只能在相应附加模型中分析。仅说“transcript 没有直接出现见证”也不够，因为验证者的随机性和最终内部状态同样属于 view。

交互式证明理路交互式证明系统Interactive proof system · IP由计算受限的概率验证者与计算无界证明者多轮交互定义的证明模型。提供完备性与可靠性框架，Sigma 协议理路Sigma 协议Sigma protocol · Σ-protocol具有首消息—随机挑战—响应三步结构，并满足特殊可靠性与诚实验证者零知识的公开币协议。是常用三步构造，Fiat–Shamir理路Fiat–Shamir 变换Fiat–Shamir transform · Fiat–Shamir heuristic用哈希输入与承诺生成挑战，把公开币交互证明转化为非交互证明或签名。可在 ROM 等附加模型中非交互化。身份认证、匿名凭证、隐私交易、MPC理路安全多方计算Secure multiparty computation · MPC以理想功能规定允许泄漏，用完整视图的模拟证明多方计算没有额外泄漏。 与可验证计算都使用零知识隐藏私密见证；使用组合定理前必须核对 stand-alone/并发环境、setup、腐化能力与模拟器资源，不能从单会话 view 模拟自动推出 UC 结论。