零知识证明 | Codeboy's Blog

形式陈述

对语言 $L$ 的交互系统 $(P,V)$ ，验证者 $V$ 是使用私有随机币的随机算法。首先固定系统是 proof 还是 argument：proof 的可靠性量化计算无界欺骗证明者，argument 只量化计算受限证明者。完备性要求 $x\in L$ 时诚实证明者使验证者以压倒性概率接受；可靠性要求 $x\notin L$ 时欺骗证明者的接受概率至多为规定误差。

零知识是基于模拟的安全性在证明系统中的实例。定义还要先选模拟器资源类 $\mathsf{Sim}$ ：严格多项式时间模拟使用 $\mathsf{Sim}=\mathrm{PPT}$ ，允许 rewinding 导致期望运行时间时则使用 expected-PPT。对恶意验证者的量词为

\forall V^*\in\mathrm{PPT}\ \exists S\in\mathsf{Sim} \forall x\in L\ \forall z_x: \quad \operatorname{View}^{P,V^*}(x,z_x) \approx_{|x|} S(x,z_x),

其中 $(z_x)$ 是任意长度由 $|x|$ 的多项式所界的辅助输入族。两侧分布随安全参数 $|x|$ 组成 ensemble； $\approx_{|x|}$ 必须明确选为完美相同、统计不可区分或计算不可区分。 $\operatorname{View}$ 包含 $V^*$ 的辅助输入、随机币、收到的消息与最终状态；模拟器不取得见证，而且只须为 $x\in L$ 模拟，假命题由可靠性处理。

只对按协议行动的验证者模拟得到 honest-verifier ZK。黑盒或非黑盒模拟、单会话、顺序组合、并发组合以及是否有 CRS 等 setup 都是会改变定义的独立维度，不能从上述单会话恶意验证者定义自动推出。

直觉

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

完备性、可靠性、知识可靠性与零知识是不同轴。一个协议可以不泄露见证，却不能证明发送者确实“知道”见证；后者需要知识证明的 extractor、knowledge error 与运行时间条件。反过来，可提取协议也可能直接泄露 witness，故 PoK 不蕴含 ZK。

图同构零知识交互，以及真实验证者视图与不使用见证的模拟器输出之间的不可区分关系 — 零知识：真实 view 与模拟 view

例子与边界

图同构协议中，证明者随机重标号其中一张图，验证者挑战它来自哪一边，证明者再用同构回答。诚实验证者版本的模拟器可先猜挑战并构造一致 transcript；重复执行降低作弊成功率，但从 HVZK 升级到恶意验证者零知识仍需额外论证。

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

推论与应用

交互式证明提供完备性与可靠性框架，Sigma 协议是常用三步构造，Fiat–Shamir可在 ROM 等附加模型中非交互化。身份认证、匿名凭证、隐私交易、MPC 与可验证计算都使用零知识隐藏私密见证；使用组合定理前必须核对 stand-alone/并发环境、setup、腐化能力与模拟器资源，不能从单会话 view 模拟自动推出 UC 结论。

参考资料

Dan Boneh and Victor Shoup, A Graduate Course in Applied Cryptography, version 0.6, 2023, Chapters 19–20.
Oded Goldreich, Foundations of Cryptography, Vol. 2, Cambridge University Press, 2004, Chapters 4–5.

形式陈述 ​

反向链接

形式陈述