Sigma 协议

Sigma 协议的关键不是首消息是否具有密码学承诺的隐藏性和绑定性，而是挑战必须在首消息固定后才产生。若同一个 $a$ 能对两个不同挑战都给出有效响应，特殊可靠性就把这两份相容答案“相减”出一个见证；若只有一个挑战能回答，作弊者只能事先猜测。另一方面，诚实验证者零知识说明随机挑战下看到的完整对话可以脱离见证重造，因此对话没有向诚实验证者泄露额外可利用信息。

Schnorr 身份协议是标准实例。特殊可靠性不是完整的并发安全定义，HVZK 也弱于对恶意验证者的零知识；协议组合时必须说明模型。

Schnorr 协议取素数阶 $q$ 的循环群 $G=⟨g⟩$，公开值 $y\in G$，见证 $x\in {\mathbb{Z}}_q$ 满足 $y=g^x$。取 $r\leftarrow U({\mathbb{Z}}_q)$，发送 $a=g^r$，收到独立均匀挑战 $e\in {\mathbb{Z}}_q$ 后返回 $z=r+exmodq$，验证群成员资格、$z\in {\mathbb{Z}}_q$ 及 $g^z=a{y}^e$。这里均匀有限集抽样作为随机原语；精确公平比特实现可用期望多项式拒绝抽样，严格有界实现需另计截断误差。若有同一 $a$ 对不同 $e,e^{\prime }$ 的两个有效响应，则

在 ${\mathbb{Z}}_q$ 中成立：因为 $q$ 为素数且 $e\ne e^{\prime }(\mathrm{mod}q)$，分母可逆，从而提取见证。对给定挑战 $e$，模拟器均匀选 $z\in {\mathbb{Z}}_q$，置 $a=g^z{y}^{-e}$；映射 $r\mapsto z=r+ex$ 是双射，所以这与真实条件 transcript 完全同分布。

承诺随机数 $r$ 复用会像签名 nonce 复用一样泄露 $x$。诚实验证者零知识不自动等于对任意恶意 verifier 零知识；挑战空间太小还会使冒充概率过高，需重复或扩大。

Sigma 协议构成身份认证、证明知识、AND/OR 组合以及 Fiat–Shamir 签名的模块化基础。零知识证明理路零知识证明Zero-knowledge proof证明者使验证者相信陈述为真而不泄露额外知识的交互证明。提供隐私目标，知识证明理路知识证明Proof of knowledge · PoK要求任何以超过知识误差的概率说服验证者的证明者，都对应一个能提取有效见证的算法。规定从成功 prover 提取见证的量词，交互式证明理路交互式证明系统Interactive proof system · IP由计算受限的概率验证者与计算无界证明者多轮交互定义的证明模型。提供完备与可靠框架；Fiat–Shamir理路Fiat–Shamir 变换Fiat–Shamir transform · Fiat–Shamir heuristic用哈希输入与承诺生成挑战，把公开币交互证明转化为非交互证明或签名。在 ROM 等附加模型中用哈希替换挑战，其 oracle programming 与非交互提取条件不能由交互 special soundness 自动推出。