知识证明 | Codeboy's Blog

形式陈述

设 $R\subseteq\{0,1\}^*\times\{0,1\}^*$ 是可高效判定的关系，本页取见证长度由公开输入长度多项式界定的版本，语言 $L_R=\{x:\exists w,\,R(x,w)=1\}$ 。固定一项交互协议 $(P,V)$ ，其验证者、消息长度与轮数受多项式界控制：诚实证明者持有 witness $w$ ，验证者持有 statement $x$ 和安全参数 $1^\lambda$ 。知识完整性要求对所有合法 $(x,w)$ ，诚实交互以 $1-\operatorname{negl}(\lambda)$ 的概率接受。

下面选定一个明确的、覆盖所有 statement 的黑盒知识提取版本。按安全实验固定接受事件，令 $0\le\kappa(\lambda)<1$ 为 knowledge error。存在同一概率 oracle 算法 $E$ 与固定多项式 $p$ ，使对每个允许的作弊证明者 $P^*$ 、其私有辅助输入 $z$ 和 statement $x$ ，当

\varepsilon =\Pr[\langle P^*(z),V\rangle(x,1^\lambda)=1] >\kappa(\lambda)

时， $E^{P^*(z)}(1^\lambda,x)$ 最终输出一个有效 $w$ ，满足 $R(x,w)=1$ ，其期望 oracle 步数至多

\frac{p(\lambda,|x|)} {\varepsilon-\kappa(\lambda)},

这里每次对可重置证明者的 oracle 调用计作一步，辅助输入与可访问消息长度按接口受多项式约束；真实执行时间还须计入运行证明者的成本。若 $P^*$ 为 PPT 且差距 $\varepsilon-\kappa$ 至少为逆多项式，提取的实际期望时间也是多项式。本页采用的是输出有效见证的 Las Vegas 约定，有限期望保证以概率一终止，不另含输出错误见证的概率。证明者私有的 $z$ 只绑定在 oracle 内，不作为提取器输入；真正公开的辅助信息可并入 $x$ ，但须两侧保持同一权限。

提取器可按模型黑盒运行、重置或 rewind $P^*(z)$ ，在分叉时保持其已选随机带与此前状态，并控制验证者随机挑战；它不直接读取私有状态。非黑盒定义还可能读取证明者代码，那是另一个访问模型。它不是现实协议参与者，不从单次线上 transcript 中凭空恢复 witness。并发会话、不可重置设备和非交互证明都会改变可用的访问方式，因而需要专门知识定义。

这里没有隐藏 bit 或 $1/2$ 猜测基线。关键量是接受概率 $\varepsilon$ 相对 $\kappa$ 的超额及其对应的提取成本。另一类定义允许输出失败符号 $\bot$ ，并同时规定成功概率与时间；不能把那种成功保证与这里的期望时间公式任意拼接。Bellare–Goldreich 原始 Definition 3.1 只在 $x\in L_R$ 上要求提取，普通 soundness 另列；本页明确采用所有 $x$ 的加强版本，因此 $x\notin L_R$ 时接受率不能超过 $\kappa$ 。这仍不自动给出交互式证明页固定的 $1/3$ 误差，除非 $\kappa\le1/3$ 或已另外放大。

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

直觉

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

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

例子与边界

Schnorr Sigma 协议取素数阶 $q$ 的循环群 $G=\langle g\rangle$ ，并检查公开值 $y$ 和承诺都属于 $G$ 。prover 证明知道 $x\in\mathbb Z_q$ 使 $y=g^x$ 。它发送承诺 $a=g^r$ ，收到随机挑战 $c\in\mathbb Z_q$ 后回复 $z=r+cx\bmod q$ ，验证者检查 $g^z=ay^c$ 。若能获得同一 $a$ 下两个不同挑战 $c\ne c'$ 的接受 transcript $(a,c,z)$ 与 $(a,c',z')$ ，则

x=(z-z')(c-c')^{-1}\bmod q

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

单个接受 transcript 通常不能提取 Schnorr witness。诚实验证者 transcript 甚至可以在不知道 $x$ 时通过先选 $c,z$ 、再令 $a=g^zy^{-c}$ 来模拟；若在所选群族上假设离散对数困难，那么一个从单份接受 transcript 高效提取见证的算法，与这个无见证模拟器复合，就会求出离散对数，违反该困难性假设。模拟性质本身并不排除见证容易求出的群。PoK 声称的是从可重复交互的成功策略中提取，不是从任意孤立证明记录中恢复秘密。

知识证明与零知识正交。PoK 限制 prover 的能力来源，ZK 限制 verifier 学到的内容；一个协议可以可提取却泄漏整个 witness，也可以零知识却没有所需的知识可靠性。称为 zero-knowledge proof of knowledge 时，两套定义及其对手模型都必须分别成立。

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

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

推论与应用

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

Sigma 协议的 special soundness、rewinding 和分叉引理是常见提取技术。实际系统还需报告 knowledge error、挑战长度、重复方式、提取器访问模型和具体成功损失；仅把挑战空间放大或把协议非交互化，不会自动保留原知识定理。

参考资料

Mihir Bellare and Oded Goldreich, On Defining Proofs of Knowledge, CRYPTO 1992，Definition 3.1、§§4.3–4.4 与 §6：原始真语句量词、私有辅助输入、soundness 与不同成功／时间约定。
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, CPT 2010, v.2，§3 Definition 2 与 Theorem 1：重绕 oracle 访问、期望步数及 Sigma 的知识误差。

形式陈述 ​

反向链接

形式陈述