Fiat–Shamir 1986：把验证者的硬币换成哈希

破除误解：不是一条已证明的定理，也不是 RSA 的变体#

第一种误读，把 1986 年这篇当成“非交互化定理”。原文对识别协议给出了基于分解难度的论证；对签名版本，作者把那个函数假定为行为像随机函数，在这个假定下论证伪造需要大约 $2^{kt}$ 次尝试。七年后贝拉雷与罗加韦才把“把哈希当成公开随机函数”写成一套设计方法，1996 年普安特舍瓦尔（David Pointcheval）与斯特恩（Jacques Stern）才用分叉引理在随机预言机模型里给出这类签名的证明。在任何具体哈希下签名是否安全，九页没有回答，后来的戈德瓦塞尔与卡莱 2003给出了否定的反例。

第二种误读，把它当成 RSA 的一个快速版本。两者共用合数模 $n=pq$，但难题不同：RSA 依赖求 $e$ 次根，这里依赖在不知道分解的情况下求模 $n$ 平方根，而求平方根与分解 $n$ 在多项式时间意义下等价。签名者也不做大指数模幂，只做少量模乘。作者明确把这一点当成卖点：识别与签名可以在当时计算能力很弱的智能卡上完成。

第三种误读，把它当成零知识定义本身。零知识与交互式证明的定义来自戈德瓦塞尔、米卡利与拉科夫。菲亚特与沙米尔借用这套语言来说明识别协议不泄露秘密，他们的贡献是一个高效的具体实例和一次把交互去掉的改写。更严格的“身份的零知识证明”表述，见 1988 年费吉（Uriel Feige）、菲亚特与沙米尔在《Journal of Cryptology》第 1 卷上的后续论文。

第四种误读，把它和沙米尔 1984 年的身份型密码混为一篇。那一年沙米尔在 CRYPTO '84 上提出“用身份信息直接当公钥”的设想，并给出一个身份型签名方案，但没有给出身份型加密的实现，后者要等到 2001 年博内（Dan Boneh）与富兰克林（Matthew Franklin）的配对方案。1986 年这九页是身份型思路的一个识别实例：用户的 $v_j$ 由身份信息算出，用不着公钥证书。两篇共享作者和思路，对象不同。

装置：可信中心、平方根与 $k \times t$ 个挑战位#

方案有一个可信中心。中心选两个大素数，公开乘积 $n$，自己保留分解。每个用户有一串身份信息 $I$，例如姓名和卡号。中心用一个公开函数从 $I$ 算出若干个值 $v_j$，挑出其中是模 $n$ 二次剩余的 $k$ 个，再利用手里的分解，求出 $s_j$，使 $s_j^2 v_j \equiv 1 \pmod n$。$s_j$ 写进用户的智能卡。公钥不需要另建目录：任何人都能从身份信息重新算出 $v_j$。

识别是三步对话，重复 $t$ 轮。证明者随机取 $r$，送出承诺 $x = r^2 \bmod n$。验证者送回 $k$ 个随机位 $e_1,\dots,e_k$。证明者回应 $y = r\prod_{e_j=1} s_j \bmod n$。验证者检查 $y^2\prod_{e_j=1} v_j \equiv x$。不知道 $s_j$ 的冒充者，只能在送出承诺之前猜中挑战位，每轮猜中的概率是 $2^{-k}$，$t$ 轮合计 $2^{-kt}$。原文用 $k$ 与 $t$ 的不同取法，在通信量、存储量与安全水平之间做权衡。

反过来看，同一个承诺若能对两种不同的挑战都给出正确回应，两份回应相除就得到若干 $s_j$ 的乘积。这正是可靠性论证的核心：能通过验证的人，一定“知道”秘密，因为从他那里可以把秘密抽出来。它也说明随机数 $r$ 每轮都必须新取，绝不能对两个挑战重复使用同一承诺。

签名版本把验证者拿掉。签名者先取 $t$ 个随机数，算出 $t$ 个承诺 $x_i$；再把消息 $m$ 与全部承诺送进公开函数 $f$，取函数值的前 $kt$ 位，排成 $t$ 行 $k$ 列的挑战矩阵 $e_{ij}$；最后按识别协议的规则算出 $t$ 个回应 $y_i$。签名由身份信息、挑战矩阵与回应组成。验证者用回应和公开的 $v_j$ 重算出承诺 $z_i$，再检查 $f(m, z_1,\dots,z_t)$ 的前 $kt$ 位是否就是签名里的那个矩阵。

这一步要成立，挑战位必须在承诺确定之后才“出现”，并且签名者无法操纵。在交互版本里，这由验证者的硬币保证。在签名版本里，只能由 $f$ 保证：签名者如果能先选挑战、再倒推出与之吻合的承诺，就能不知秘密而伪造。$f$ 必须同时吃进消息与承诺，签名才与这条消息绑定。后来的文献把只哈希承诺、不哈希公开陈述的做法称为“弱”变换；2012 年对赫利俄斯（Helios）投票系统的分析表明，漏掉陈述会让本应可靠的证明失守。九页里的签名把消息和承诺都送进了 $f$。

这套设计的工程含义很直接。签名与验证只用到模 $n$ 的乘法与平方，乘法次数随 $k$ 与 $t$ 线性增长，没有大指数模幂，适合当时的智能卡芯片。代价是签名比 RSA 签名长，因为它带着 $t$ 个回应和整个挑战矩阵。$k$ 大意味着卡里要存更多 $s_j$，$t$ 大意味着要算、要传更多回应；原文把两者的乘积 $kt$ 当作安全参数，再按存储与带宽分配。

秘密为什么不泄露，可以从单轮看清。验证者看到的是 $x$ 与 $y$。对任何一种挑战位，只要知道答案，就能先随机取 $y$，再倒推出与之吻合的 $x = y^2\prod v_j^{e_j}$，得到一份与真实对话分布相同的记录。验证者因此学不到 $s_j$。同一个“先取回应、再倒推承诺”的技巧，正是签名版本必须用 $f$ 堵住的口子：在交互里它只能被模拟器使用，因为模拟器可以事先知道挑战；在签名里，若签名者能事先知道挑战，伪造就成了。

九页之后：专利保密令与一串后继方案#

这篇论文还有一段专利插曲。两位作者 1986 年 7 月就这套方案提交了美国专利申请。1987 年 1 月，美国专利商标局应陆军的要求对申请下达保密令，理由是公开会危害国家安全。方案此前已在会上公开报告，作者又不是美国公民，保密令引起学界抗议，不久即被撤销，《纽约时报》1987 年 2 月 17 日报道了这件事。专利 1988 年授权，编号 US 4,748,668。

方案本身很快有了后继。1988 年费吉、菲亚特与沙米尔把识别协议改写成严格的身份零知识证明，并加入符号位，使验证者连 $v_j$ 的二次剩余性也学不到。同年吉尤（Louis Guillou）与基斯卡特（Jean-Jacques Quisquater）给出一种基于 RSA 型 $e$ 次根的变体，减少了卡上需要存的秘密个数。1989 年施诺尔（Claus-Peter Schnorr）在 CRYPTO '89 上提出基于离散对数的识别协议，并用同一步改写成签名，这就是后来的施诺尔签名。这些方案的骨架相同：承诺、挑战、回应三步，再用哈希代替挑战。

它证明了什么，没有覆盖什么#

对识别协议，九页给出的论证是：若存在冒充者能以明显高于 $2^{-kt}$ 的概率通过验证，就能把它变成求模 $n$ 平方根的算法，从而分解 $n$；协议本身不泄露 $s_j$ 的信息。对签名，论证建立在 $f$ 像随机函数的假定上，属于启发式。它没有给出标准模型下的签名安全证明，也没有使用戈德瓦塞尔、米卡利与里维斯特 1984 年提出的选择消息攻击定义（期刊版 1988 年）来分析签名。

安全参数在两种用法里的含义不同。识别是在线的：冒充者每次只能对一位真实的验证者尝试一次，失败就会被发现，$2^{-kt}$ 可以取得比较宽松。签名是离线的：伪造者可以在自己的机器上反复换承诺、反复计算 $f$，直到碰上一组能用的挑战位，尝试次数只受算力限制。原文因此对签名建议了比识别大得多的 $kt$。这一区别后来成了所有非交互证明的常识：交互协议的可靠性误差，不能原样当作变换后的安全水平。

它没有覆盖把这一步推广成一般变换之后的问题：对哪些三步协议、在哪种模型下、用什么样的哈希，变换才保持可靠。随机预言机模型下的正面答案出自 1996 年的分叉引理；对具体哈希的反面答案出自卡内蒂、戈德赖希与哈勒维的方法论反例，以及戈德瓦塞尔与卡莱 2003 年针对这一变换本身的构造。今天零知识证明系统里的非交互版本，绝大多数仍靠这一步把交互去掉，它们的安全论证也因此大多停在随机预言机模型里。

即使在随机预言机模型里，后来的证明也不紧。分叉引理的做法是让伪造者用同一套随机带运行两次，在关键的哈希询问处换一个答案，指望它两次都在同一个承诺上交出签名，从而得到两份回应、抽出秘密。为了让两次撞在同一处，归约要付出与哈希询问次数相当的损失。九页的启发式没有计算这类损失，签名参数的选取也就没有照顾到它。

它也没有处理可信中心本身的风险。中心知道 $n$ 的分解，因而能为任何身份算出秘密；这是身份型方案的结构性代价，不是实现缺陷。

跨域连接#

• 戈德瓦塞尔、米卡利与拉科夫 1985：交互式证明与零知识的定义在那里。本页拿那套语言来说明识别协议不泄露 $s_j$，再走出一步定义里没有的事：把验证者删掉。两篇的关系是定义与应用，不是同一个结果。
• 贝拉雷–罗加韦 1993：本页的签名论证已经把 $f$ 当成随机函数，只是没有给这个假定起名字，也没有把它写成方法。1993 年把“先在公开随机函数里设计和证明，再换成真实哈希”正式写成范式，并标出最后一跳是启发式。
• 戈德瓦塞尔–卡莱 2003：针对本页这一步的直接反例。存在一个本身安全的三步公开硬币识别协议，经过变换后，无论用哪个具体函数族代替 $f$，得到的签名都能被伪造。它说明本页的启发式不能升级成一般定理。
• 卡内蒂–戈德赖希–哈勒维：对随机预言机方法论整体的反例，针对的是“随机预言机里安全，换成任何哈希就不安全”的人造方案，不专门针对三步协议。读本页的签名部分，需要同时记住这两条反例的范围不同。
• 零知识证明前沿：区块链与可验证计算里的简洁证明，多数先设计成公开硬币的交互协议，再用这一步变成一串可以离线检查的字节。哈希该吃进哪些内容，是这些系统里反复出事的地方。
• 哈希：算法页里的哈希服务于查找与分桶，要的是分布均匀。本页对 $f$ 的要求更强：签名者不能先选输出再找输入。两种用途共享名字，安全要求不同。
• 交互式证明与零知识：总览把非交互化放在零知识一章的末尾，作为把理论带进工程的一步。本页是那一步的出处。总览里讲的模拟器与本页单轮里的“先取回应、再倒推承诺”是同一个技巧，在交互里证明不泄露，在签名里则必须被哈希挡住。
• 密码学基础：总览把签名放在公钥密码之下。本页提供另一条来路：签名不一定来自“可逆的陷门置换”，也可以来自一个可以去掉交互的识别协议。施诺尔签名与今天常见的 EdDSA 都走这条路。
• 沙菲·戈德瓦塞尔：她既是零知识定义的作者之一，又是 2003 年反例的作者之一。人物页里这两件事相隔十八年，本页正好夹在中间。
• 数论：本页的难题是模合数求平方根。1979 年拉宾（Michael Rabin）已经证明，能对随机二次剩余求出模 $n$ 平方根的算法可以用来分解 $n$；本页的可靠性论证正是落在这一等价上。数论页里的二次剩余与中国剩余定理，是读懂中心为什么能算出 $s_j$、别人为什么算不出的前提。
• TLS 证书生态：证书体系用签发机构的签名把公钥绑到名字上，机构本身不知道用户私钥。本页的可信中心省掉了证书，但它知道分解，因而能算出任何人的秘密。两种设计把信任放在不同的地方，代价也不同。
• RSA 公钥密码：同样用合数模，难题是求 $e$ 次根；本页的难题是求平方根，并且把计算量压到少量模乘。

参考文献#

• Amos Fiat & Adi Shamir, "How to Prove Yourself: Practical Solutions to Identification and Signature Problems", Advances in Cryptology — CRYPTO '86, LNCS 263, Springer, 1987, pp. 186–194. DOI: 10.1007/3-540-47721-7_12. —— 本文对象。
• Shafi Goldwasser, Silvio Micali & Charles Rackoff, "The Knowledge Complexity of Interactive Proof-Systems", Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985, pp. 291–304. DOI: 10.1145/22145.22178. —— 零知识的定义来源。
• Uriel Feige, Amos Fiat & Adi Shamir, "Zero-Knowledge Proofs of Identity", Journal of Cryptology 1(2), 1988, pp. 77–94. —— 同一识别思路的后续严格表述。
• Mihir Bellare & Phillip Rogaway, "Random Oracles are Practical: A Paradigm for Designing Efficient Protocols", Proceedings of the 1st ACM Conference on Computer and Communications Security, 1993, pp. 62–73. DOI: 10.1145/168588.168596. —— 随机预言机方法论。
• David Pointcheval & Jacques Stern, "Security Proofs for Signature Schemes", Advances in Cryptology — EUROCRYPT '96, LNCS 1070, Springer, 1996, pp. 387–398. DOI: 10.1007/3-540-68339-9_33. —— 分叉引理，随机预言机模型下的签名证明。
• Shafi Goldwasser & Yael Tauman Kalai, "On the (In)security of the Fiat-Shamir Paradigm", Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, 2003, pp. 102–115. DOI: 10.1109/SFCS.2003.1238185. —— 针对本变换的反例。

延伸阅读#

• 与 戈德瓦塞尔–卡莱 2003 对读：同一个变换，一边是 1986 年的启发式，一边是 2003 年的反例。
• 与 交互式证明与零知识 对读：总览里的非交互化一节，就是本页这一步。
• 与 贝拉雷–罗加韦 1993 对读：本页已经把函数当成随机函数来用却没有给这个假定命名，1993 年把它写成设计方法，并标出换成真实哈希时的代价。
• 与 卡内蒂–戈德赖希–哈勒维 对读：那篇说明随机预言机里的证明不能一般地搬到具体哈希上，本页的签名版本正处在这条缝上。