Fiat–Shamir 变换 | Codeboy's Blog

形式陈述

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

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

证明者输出 $(a,z)$ ，验证者重算 $e$ 并检查原协议验证式。这一段只定义非交互 transcript；零知识、知识可靠性或签名不可伪造性都必须另给协议、模型与归约。

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

设 $G=\langle g\rangle$ 为素数阶 $q$ 的群，公钥 $Y=g^x$ ，离散对数在该群族上困难。签名者取均匀 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.

验证者检查 $g^z=aY^e$ 。在经典随机预言机模型中，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}$ ，再对完整哈希输入编程响应。
挑战空间 $\mathbb Z_q$ 具有足够熵，对手的随机预言机与签名查询数均为多项式，且成功伪造对应一个已查询的新鲜哈希输入。
哈希输入无歧义绑定域、群参数、公钥、消息和承诺；删去其中一项会改变被证明的签名方案。

forking 会重放对手并改变某次随机预言机回答，所以归约损失依赖查询次数和原伪造概率。本页只陈述这一经典 ROM 实例，不把它外推到任意 Sigma 协议、标准模型或量子随机预言机。

直觉

承诺和公开上下文经哈希得到挑战，再由响应组成非交互证明 — 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。

推论与应用

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

参考资料

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，forking lemma 与经典 ROM 签名归约。
Dan Boneh, Victor Shoup, A Graduate Course in Applied Cryptography (2023/2026 draft), Fiat–Shamir and signatures.

形式陈述 ​

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

反向链接

形式陈述

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