Fiat–Shamir 变换

形式陈述 ​

Fiat–Shamir 是一种变换语法，不是对任意三步协议成立的通用安全定理。对三步公开币协议 $(a,e,z)$，把验证者随机挑战替换为

这里 $H$ 的输出须落在原协议的挑战空间 $\mathcal{E}$，全部字段先作无歧义编码。若用固定长度摘要实例化，还须明确摘要到 $\mathcal{E}$ 的映射；直接模 $q$ 约化一般不是精确均匀抽样。证明者输出 $(a,z)$，验证者重算 $e$ 并检查原协议验证式。 这一段只定义非交互 transcript；零知识、知识可靠性或签名不可伪造性都必须另给协议、模型与归约。

一个具体结论：Schnorr 签名的经典 ROM 版本 ​

设 $G=⟨g⟩$ 为素数阶 $q$ 的有效编码群，群与参数由安全参数 $\lambda$ 索引，$1/q$ 可忽略。密钥生成取 $x\leftarrow U({\mathbb{Z}}_q)$，公钥为 $Y=g^x$，并假设相应群族上的离散对数困难。这里 $H$ 是输出均匀 ${\mathbb{Z}}_q$ 元素的随机预言机。签名者取均匀 nonce $r\leftarrow {\mathbb{Z}}_q$，令 $a=g^r$，并计算

验证者先检查公钥、承诺的群成员资格和响应 $z\in {\mathbb{Z}}_q$，再检查 $g^z=a{Y}^e$。EUF-CMA 使用数字签名理路数字签名Digital signature由私钥签名、公开验证并提供不可伪造性的认证机制。页的新消息标准：最终伪造的 $m$ 没有被请求签名。在经典随机预言机模型理路随机预言机模型Random oracle model · ROM把所有参与者共享的哈希接口理想化为可自适应查询且响应一致的真随机函数。中，Pointcheval–Stern 的 forking-lemma 路线可把对该精确 Schnorr 签名接口的 EUF-CMA 伪造者转成离散对数求解器，但需要以下条件：

1. 原 Schnorr 协议具有 special soundness；同一 $a$ 下两个不同挑战 $e\ne e^{\prime }$ 的有效响应可提取 $x=(z-z^{\prime })/(e-e^{\prime })modq$。
2. 诚实验证者零知识模拟允许签名 oracle 先选 $(e,z)$、令 $a=g^z{Y}^{-e}$，再对完整哈希输入编程响应。
3. 对手的随机预言机与签名查询数均为多项式。证明先界定签名模拟在已查询点编程的冲突概率，再处理最终伪造从未查询其完整哈希输入的情形；不能把“已经查询”额外假定成攻击者义务。当 $Y\ne 1$ 时，固定 $(m,a,z)$ 至多匹配一个挑战，未查询成功概率至多 $1/q$；均匀密钥的 $Y=1$ 事件也只有 $1/q$，所以这两类例外合计至多 $2/q$。余下的非忽略成功质量才进入分叉论证。
4. 哈希输入无歧义绑定域、群参数、公钥、消息和承诺；删去其中一项会改变被证明的签名方案。

例如每次模拟签名先独立均匀选 $e,z$，其 $a=g^z{Y}^{-e}$ 条件于过去仍均匀。若至多有 $Q_H$ 次对手查询及 $Q_S$ 次签名查询，对此前表项冲突作保守并集界理路并集界Union bound · Boole 不等式多个坏事件中至少一个发生的概率，不超过各事件概率之和。，概率至多为 $Q_S(Q_H+Q_S)/q$；证明在冲突时中止并计入这项损失。forking 再重放对手并改变某次随机预言机回答，完整归约还会损失查询次数和原伪造概率的因子。本页只陈述这一经典 ROM 实例，不把它外推到任意 Sigma 协议、标准模型或量子随机预言机。

在这个 Schnorr 实例中，按显示的公式直接执行，签名需要一次群幂、一次哈希查询，以及模 $q$ 的一次标量乘法和一次加法；验证需要两次群幂、一次群乘法和一次哈希查询。这里计数的是原语调用，不把群幂或哈希视为常数时间：消息与参数编码、群成员及标量范围检查、精确均匀抽样，以及各原语的位运算时间和工作空间都须另计。