知识证明

形式陈述 ​

设 $R\subseteq \{0,1{\}}^{\ast }\times \{0,1{\}}^{\ast }$ 是可高效判定的关系公理库关系Relation · Binary relation带源集与目标集的二元关系，其底层关系图是 A×B 的子集。，语言 $L_R=\{x:\mathrm{\exists }w,R(x,w)=1\}$。知识证明先是一项交互协议公理库交互式证明系统Interactive proof system · IP由计算受限的概率验证者与计算无界证明者多轮交互定义的证明模型。 $(P,V)$：诚实证明者持有 witness $w$，验证者持有 statement $x$ 和安全参数 $1^{\lambda }$。知识完整性要求对所有合法 $(x,w)$，诚实交互以 $1-\mathrm{negl}(\lambda )$ 的概率接受。

知识可靠性不只限制假语句上的接受率。协议具有 knowledge error $\kappa (\lambda )$，若存在 extractor $E$，使对每个允许的作弊证明者 $P^{\ast }$、辅助输入 $z$ 和 statement $x$，当

$$\epsilon =\text{Pr}[⟨P^{\ast }(z),V⟩(x,1^{\lambda })=1]>\kappa (\lambda )$$

且差距 $\epsilon -\kappa (\lambda )$ 非可忽略时，具有 oracle 访问 $P^{\ast }$ 的 $E^{P^{\ast }}(x,z)$ 能输出 $w$ 满足 $R(x,w)=1$。典型黑盒定义把期望提取时间界为

$$\frac{\mathrm{poly}(\lambda ,|x|,T_{P^{\ast }})}{\epsilon -\kappa (\lambda )},$$

所以当接受率只比 knowledge error 高一个逆多项式量时，提取仍为期望多项式时间。不同文献对严格/期望时间、提取成功概率与知识误差的形式略有差异，引用定理必须给出所用版本，而不能只写“存在 extractor”。

Extractor 可按模型黑盒运行、重置或 rewind $P^{\ast }$，并控制验证者随机挑战；非黑盒定义还可能读取 $P^{\ast }$ 的代码。它不是现实协议参与者，不从单次线上 transcript 中凭空恢复 witness。并发会话、不可重置设备和非交互证明都会改变可用的访问方式，因而需要专门知识定义。

这里没有隐藏 bit 或 $1/2$ 猜测基线。关键安全量是接受概率 $\epsilon$ 相对 $\kappa$ 的超额，以及提取器输出无效 witness 的失败概率；后者应在提取器和证明者全部随机币上可忽略。若把两个世界写成区分游戏，仍需另行说明归一化，不能把 IND 优势公式机械套到知识可靠性。

若知识可靠性量化任意证明者策略，通常称 proof of knowledge；若只要求对 PPT $P^{\ast }$ 可提取，则称 argument of knowledge，其结论依赖计算限制与底层假设。两者都不同于普通 soundness：soundness 只说假 statement 难以被接受，PoK 还要求真 statement 上任何显著成功的策略都蕴含某个 witness。

直觉 ​

“证明者知道 witness”不能通过查看它的内心定义，只能用可操作的反事实刻画：若它确实能稳定回答验证者随机挑战，就应能把这项应答能力转化为一个 witness。Extractor 正是这种转化算法；知识误差则标出完全靠猜挑战也可能通过的基线。

提取通常需要让同一承诺面对不同挑战。一次成功对话只说明证明者猜中或正确回答了一个分支，未必暴露足够代数信息；重绕把它带回分叉点，收集多个彼此一致的成功分支，才可能解出 witness。

例子与边界 ​

Schnorr Sigma 协议中，prover 证明知道 $x$ 使 $y=g^x$。它发送承诺 $a=g^r$，收到随机挑战 $c\in {\mathbb{Z}}_q$ 后回复 $z=r+cxmodq$，验证者检查 $g^z=a{y}^c$。若能获得同一 $a$ 下两个不同挑战 $c\ne c^{\prime }$ 的接受 transcript $(a,c,z)$ 与 $(a,c^{\prime },z^{\prime })$，则

$$x=(z-z^{\prime })(c-c^{\prime }{)}^{-1}modq$$

是有效 witness。这项 special soundness 是提取器的代数核心；单轮均匀挑战下，单靠预先准备一个可回答分支的策略仍约有 $1/q$ 成功率，对应 knowledge error。

单个接受 transcript 通常不能提取 Schnorr witness。诚实验证者 transcript 甚至可以在不知道 $x$ 时通过先选 $c,z$、再令 $a=g^z{y}^{-c}$ 来模拟；若“看到一次接受就能提取”，它会与这种模拟性质冲突。PoK 声称的是从可重复交互的成功策略中提取，不是从任意孤立证明记录中恢复秘密。

知识证明与零知识公理库零知识证明Zero-knowledge proof证明者使验证者相信陈述为真而不泄露额外知识的交互证明。正交。PoK 限制 prover 的能力来源，ZK 限制 verifier 学到的内容；一个协议可以可提取却泄漏整个 witness，也可以零知识却没有所需的知识可靠性。称为 zero-knowledge proof of knowledge 时，两套定义及其对手模型都必须分别成立。

Fiat–Shamir 把挑战改成 transcript 的哈希后，普通交互重绕不再直接适用。随机预言机中的 forking 或 oracle programming 可以在特定条件下恢复不同挑战，但提取概率、查询次数和并发行为都需重新分析；经典 ROM 结果也不能原样覆盖量子查询。

并发协议是另一边界。一个黑盒 extractor 在重绕某次会话时可能扰动其他会话，导致分布和运行时间失控。没有说明 stand-alone、并发或可组合模型的 PoK 结论，只能按其原始执行模型使用。

推论与应用 ​

知识证明用于身份认证、凭证展示、可验证计算和零知识论证。它把“能成功响应”连接到“存在可提取 witness”，从而支持协议证明中关于密钥占有、签名知识或约束满足解的推理，而无需把 witness 直接发送给验证者。

Sigma 协议公理库Sigma 协议Sigma protocol · Σ-protocol具有首消息—随机挑战—响应三步结构，并满足特殊可靠性与诚实验证者零知识的公开币协议。的 special soundness、rewinding 和分叉引理是常见提取技术。实际系统还需报告 knowledge error、挑战长度、重复方式、提取器访问模型和具体成功损失；仅把挑战空间放大或把协议非交互化，不会自动保留原知识定理。

参考资料

• Mihir Bellare and Oded Goldreich, “On Defining Proofs of Knowledge,” CRYPTO 1992。
• Ronald Cramer, Ivan Damgård, and Berry Schoenmakers, “Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols,” CRYPTO 1994，Sigma-protocol techniques。
• Ivan Damgård, “On Σ-Protocols,” lecture notes, 2010，special soundness, honest-verifier zero knowledge, and extraction。