1986年推出的Fiat-Shamir启发式算法允许将多轮交互式证明系统转换为由哈希函数保护的非交互式协议。它成为了广泛采用数字签名、加密货币、身份验证和零知识协议的重要组成部分。
交互式证明涉及拥有秘密数据的证明者和验证者之间的来回通信，后者想要检查数据是否符合某些陈述。Prover 对数据执行计算并发送初始证明消息。验证者回复一个 “质疑” ——一个随机生成的值。收到挑战后，Prover 会根据秘密数据和刚刚收到的挑战计算响应。Prover 和 Verifier 之间的这种互动循环持续了几轮，之后验证者将最终决定证据是否通过。
Fiat-Shamir背后的主要思想是将需要多轮实时挑战-响应互动的交互式协议转换为不需要验证者直接参与的非交互式版本。这是通过使用加密哈希函数来实现的，该函数生成以验证者挑战为模型的伪随机输出。Prover 在本地计算先前消息数据的哈希值，而不是等待实际的质询。
Fiat-Shamir 转换的安全性依赖于具有随机性属性的哈希函数来生成不可预测的挑战值。这可以防止不诚实的 Prover 预先计算响应或操纵结果。诸如 SHA2 或 SHA3 等具有抗碰撞性和单向性的加密哈希函数提供了所需的安全特性。他们的输出以验证者的挑战为模型，在计算上是无法预测或控制的。
如果应用正确选择的哈希函数，Fiat-Shamir 变换将保留原始交互式证明系统的安全特性。具体而言，如果转换后的证明方案存在作弊策略，那么使用计算验证器的原始方案也将存在作弊策略。这种被称为 “随机预言机模型” 的安全模型正式确定了在分析协议属性时可以合理地将哈希函数建模为随机预言机。
基于 Fiat-Shamir 的协议提供更快的验证速度，并允许将交互式方案传输到去中心化环境中：
身份验证 — Fiat-Shamir 允许将交互式质询响应身份验证流程转换为由哈希保护的非交互式签名方案。转换后的签名可以在本地进行自我验证。
加密货币 — Fiat-Shamir 启发式允许通过哈希而不是依赖中央权威来生成比特币和许多其他区块链平台所需的密钥对、公钥、地址和数字签名。
零知识 — 广泛用于区块链隐私解决方案的非交互式零知识证明通常依赖 Fiat-Shamir 来生成可扩展但安全的证明，而无需进行多轮互动。
革命性的 Fiat-Shamir 转型通过将交互式验证替换为高效的哈希算法，使数字签名、加密货币和零知识协议得以大规模采用。启发式是塑造数字时代基础安全技术不可或缺的工具。
