Fiat–Shamir 变换 | Codeboy's Blog

形式陈述

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

e=H(\mathsf{domain},\mathsf{parameters},\mathsf{statement},a,\mathsf{context}),

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

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

设 $G=\langle g\rangle$ 为素数阶 $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$ ，并计算

e=H(\mathsf{domain},G,q,g,Y,m,a),\qquad z=r+ex\pmod q.

验证者先检查公钥、承诺的群成员资格和响应 $z\in\mathbb Z_q$ ，再检查 $g^z=aY^e$ 。EUF-CMA 使用数字签名页的新消息标准：最终伪造的 $m$ 没有被请求签名。在经典随机预言机模型中，Pointcheval–Stern 的 forking-lemma 路线可把对该精确 Schnorr 签名接口的 EUF-CMA 伪造者转成离散对数求解器，但需要以下条件：

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

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

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

直觉

承诺和公开上下文经哈希得到挑战，再由响应组成非交互证明 — Fiat–Shamir 的哈希挑战链

Fiat–Shamir 把公币交互证明中的 verifier 随机挑战替换为对 transcript 与声明求得的哈希值。prover 先固定承诺，再查询所有人共享且响应一致的随机预言机，最后给出响应；它仍可更换承诺反复查询，故证明必须计入自适应查询和 grinding，而不能把挑战口头描述成绝对不可控制。验证者可独立重算挑战，因而省去在线验证者；ROM 安全并非对任意确定哈希函数的无条件定理。

例子与边界

三步 Sigma 协议的交互 transcript 为 $(a,e,z)$ ，非交互对象则只携带 $(a,z)$ ，挑战由验证者使用完整编码重新计算。在上面的 Schnorr 实例中，statement 是公钥 $Y$ ，context 包含待签消息 $m$ ，域标签与群参数把这次哈希和其他协议用途隔开；这说明“适当消息绑定”具体落在哪些字段上。

若直接把挑战写成 $H(a)$ ，哈希输入没有绑定声明、公共参数、协议域和必要上下文，证明便可能遭跨实例或跨协议重放，或出现可塑性问题。知识提取还要求明确 extractor 如何获得同一承诺下的不同挑战、knowledge error 与查询损失；交互协议的 special soundness 本身不足以证明非交互对象可提取。标准模型中并非所有 Sigma 协议的 Fiat–Shamir 变换都安全；量子随机预言机下的安全证明也需专门技术，不能直接沿用经典 rewinding。

同一承诺下的两次响应能算出什么

取玩具群 $G=\langle2\rangle\subset\mathbb Z_{23}^{\times}$ ，其阶为 $q=11$ 。设 $x=3$ ，公钥 $Y=8$ ，重复使用 $r=4$ 得到相同承诺 $a=16$ 。若两个完整哈希输入的挑战分别为 $e=2$ 和 $e'=7$ ，响应分别为 $z=10$ 、 $z'=3$ 。两次验证为

2^{10}\equiv16\cdot8^2\equiv12\pmod{23},\qquad 2^3\equiv16\cdot8^7\equiv8\pmod{23}.

相减后在 $\mathbb Z_{11}$ 中提取

x=(10-3)(2-7)^{-1}=7\cdot6^{-1}=7\cdot2=3\pmod{11}.

这同一个计算既是交互特殊可靠性的核心，也说明真实签名中复用 nonce 会泄漏私钥。安全归约用受控重放取得两个分支，现实攻击者并没有免费重置诚实签名者的权限。

读到这里可以完成一项检验：核算这两次验证与提取，再区分诚实验证者模拟、重绕提取及随机预言机编程各自获得了哪些权限。若签名挑战仅为 $H(a)$ 而未绑定消息，把一次合法签名复制到另一条未签消息就能通过同一验证；这已经违反新消息不可伪造。小群只演示等式，不能作为安全参数。

推论与应用

Fiat–Shamir 以 Sigma 协议的承诺—挑战—响应为输入，以密码哈希实例化理想挑战，支撑 Schnorr 类签名、非交互知识证明和大量区块链证明系统中的 transcript 压缩。零知识、签名不可伪造性与 knowledge extraction 必须逐构造、逐模型验证，不能由变换语法一并推出。

单元素VOPRF把这项变换用于同离散对数关系：由响应重建两个临时点，再按规定的长度前缀重算挑战，只有匹配才允许去盲输出。它单独证明错误关系在明确理想挑战模型中的逐查询界，并保留非零组合系数、规范编码和固定公钥条件；该关系证明不能替代整个OPRF的伪随机性或输入隐藏论证。

参考资料

Amos Fiat, Adi Shamir, How to Prove Yourself: Practical Solutions to Identification and Signature Problems (1986), original transform.
David Pointcheval and Jacques Stern, Security Proofs for Signature Schemes, EUROCRYPT 1996，§3 分叉引理与 §6 Theorem 13 的 Schnorr 结论。
Dan Boneh, Victor Shoup, A Graduate Course in Applied Cryptography (2023/2026 draft), Fiat–Shamir and signatures.

沿学习路线继续2

选择一条阅读路线；每条路线的前后站点分别列在下方。

随机挑战怎样变成不可伪造的证明第 4 / 4 站

上一站Sigma 协议

已到本路线终点

从字节映射到盲求值与公钥核验第 5 / 6 站

上一站不经意伪随机函数下一站可验证不经意伪随机函数

形式陈述 ​

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

同一承诺下的两次响应能算出什么 ​

反向链接

形式陈述

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

同一承诺下的两次响应能算出什么