Sigma 协议 | Codeboy's Blog

形式陈述

设

R\subseteq\mathcal X\times\mathcal W, \qquad L_R=\{x:\exists w,\ (x,w)\in R\}

是可高效验证的见证关系。Sigma 协议是在公共输入 $x$ 上证明“知道 $w$ 使 $(x,w)\in R$ ”的三步公开币协议：证明者先发送首消息 $a$ （习惯称为 commitment，但它不必是密码学承诺方案），验证者从有限挑战空间 $\mathcal E$ 均匀抽取 $e$ ，证明者返回响应 $z$ 。验证者以谓词

V(x,a,e,z)\in\{0,1\}

决定是否接受，三元组 $(a,e,z)$ 称为 transcript。标准性质包括：

**完备性：**若 $(x,w)\in R$ 且双方诚实执行，则验证者接受；
**特殊可靠性：**存在高效提取器 $\operatorname{Ext}$ ，从两个具有相同首消息、不同挑战的接受 transcript

(a,e,z),\qquad(a,e',z'),\qquad e\ne e'

中输出见证 $w$ ，满足 $(x,w)\in R$ ；这是知识证明提取器的代数基础，但完整 PoK 结论还要写明 extractor 对作弊 prover 的访问、knowledge error 与期望运行时间； 3. **诚实验证者零知识：**存在不使用见证的高效模拟器，它生成的 transcript 分布与诚实验证者按协议随机选择挑战时的真实 transcript 完全相同、统计接近或计算不可区分；具体协议必须声明采用哪一种口径。

在标准均匀挑战和特殊可靠性条件下，证明者预先猜中唯一可回答挑战的概率为 $1/|\mathcal E|$ ，这给出典型知识误差。更一般的挑战分布、重复方式或提取定义需要单独给出相应误差界。

直觉

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

例子与边界

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

Schnorr 协议中 prover 知道 $x$ 使 $y=g^x$ ：发送 $a=g^r$ ，收到挑战 $e$ 后返回 $z=r+ex$ ，验证 $g^z=a y^e$ 。若有同一 $a$ 对不同 $e,e'$ 的两个有效响应，则

x=(z-z')/(e-e')

（在群阶域中），从而提取见证。

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

推论与应用

Sigma 协议构成身份认证、证明知识、AND/OR 组合以及 Fiat–Shamir 签名的模块化基础。零知识证明提供隐私目标，知识证明规定从成功 prover 提取见证的量词，交互式证明提供完备与可靠框架；Fiat–Shamir在 ROM 等附加模型中用哈希替换挑战，其 oracle programming 与非交互提取条件不能由交互 special soundness 自动推出。

参考资料

Dan Boneh, Victor Shoup, A Graduate Course in Applied Cryptography (2023/2026 draft), Sigma protocols.
Shafi Goldwasser, Silvio Micali, Charles Rackoff, The Knowledge Complexity of Interactive Proof Systems (1989), zero-knowledge foundations.

形式陈述 ​

反向链接

形式陈述