Fiat-Shamir启发式签名
Fiat-Shamir启发式签名 Fiat-Shamir启发式（Fiat Shamir heuristic）是一种能够将 交互式证明 （interactive proof of knowledge）转换成 非交互证明 （non-interactive proof knowledge）的启发式算法. 交互式证明 在交互式证明中， 证明者 （prover） P 想要向 验证者 （verifier） V 证明其拥有某个知识，而这个知识可能非常抽象，无法展示. 在这种情况下， V 可以通过向 P 进行提问，并且通过对 P 的回答进行验证来检验其是否具有相应的知识，每次成功检验都能够使 V 更相信 P 具有相应的知识. 交互式证明的具体思想可以总结如下： P 想要向 V 证明自己拥有某个知识. 于是 V 采用提问的方式，若 P 每次都能成功回答，那么 V 就有很大的概率相信 P 拥有相应的知识. 一个比较接近的例子就是面试. 其中面试官是 V 而应聘者是 P ，每次 P 的成功回答都能够使 V 相信其拥有相应的专业技能. 那么显然， P 不应该事先了解 V 所选择的所有问题，否则 P 可以直接记录所有答案然后直接选择相应问题的结果即可. 但是这种提问的环境要求 P 和 V 能够进行通信，而这在现实中由于带宽瓶颈等问题可能很难做到. 这个时候期望的一种证明形式可能如下： P 直接将证明发送给 V ，然后 V 直接验证该证明是否成立. Fiat-Shamir启发式签名 使用 Fiat-Shamir启发式签名 可以将上述交互式证明过程转换成非交互时的直接验证过程. 其做法如下： P 使用一个 伪随机函数 来产生随机问题，并且就这些问题产生相应的结果，并且以此作为其对相应知识的证明. 于此同时 V 对每次问题的结果进行验证，并且 V 需要能够验证这些答案与每个问题的对应性. 只要 P 用来产生问题的输入 具有随机性 ，那么从直觉上可以得到其效果与交互式方案是相同的，具体证明见超链接部分. 应用 目前Fiat-Shamir启发式签名经常用来将交互式证明转换成非交互式证明，例如在 知识证明 （proof of knowledge）等一系列工作中，一个常见的套路就是首先提供一个交互式版本，然后再使用Fiat-Shamir启发式签名将其转换成一个非交互证明方法从而减少通信轮数