Fiat-Shamir启发式签名

Fiat-Shamir启发式（Fiat Shamir heuristic）是一种能够将交互式证明（interactive proof of knowledge）转换成非交互证明（non-interactive proof knowledge）的启发式算法.

交互式证明

在交互式证明中，证明者（prover）$\mathcal{P}$$\mathcal{P}$想要向验证者（verifier）$\mathcal{V}$$\mathcal{V}$证明其拥有某个知识，而这个知识可能非常抽象，无法展示. 在这种情况下，$\mathcal{V}$$\mathcal{V}$可以通过向$\mathcal{P}$$\mathcal{P}$进行提问，并且通过对$\mathcal{P}$$\mathcal{P}$的回答进行验证来检验其是否具有相应的知识，每次成功检验都能够使$\mathcal{V}$$\mathcal{V}$更相信$\mathcal{P}$$\mathcal{P}$具有相应的知识. 交互式证明的具体思想可以总结如下：

$\mathcal{P}$$\mathcal{P}$想要向$\mathcal{V}$$\mathcal{V}$证明自己拥有某个知识. 于是$\mathcal{V}$$\mathcal{V}$采用提问的方式，若$\mathcal{P}$$\mathcal{P}$每次都能成功回答，那么$\mathcal{V}$$\mathcal{V}$就有很大的概率相信$\mathcal{P}$$\mathcal{P}$拥有相应的知识.

一个比较接近的例子就是面试. 其中面试官是$\mathcal{V}$$\mathcal{V}$而应聘者是$\mathcal{P}$$\mathcal{P}$，每次$\mathcal{P}$$\mathcal{P}$的成功回答都能够使$\mathcal{V}$$\mathcal{V}$相信其拥有相应的专业技能. 那么显然，$\mathcal{P}$$\mathcal{P}$不应该事先了解$\mathcal{V}$$\mathcal{V}$所选择的所有问题，否则$\mathcal{P}$$\mathcal{P}$可以直接记录所有答案然后直接选择相应问题的结果即可. 但是这种提问的环境要求$\mathcal{P}$$\mathcal{P}$和$\mathcal{V}$$\mathcal{V}$能够进行通信，而这在现实中由于带宽瓶颈等问题可能很难做到. 这个时候期望的一种证明形式可能如下：$\mathcal{P}$$\mathcal{P}$直接将证明发送给$\mathcal{V}$$\mathcal{V}$，然后$\mathcal{V}$$\mathcal{V}$直接验证该证明是否成立.

Fiat-Shamir启发式签名

使用Fiat-Shamir启发式签名可以将上述交互式证明过程转换成非交互时的直接验证过程. 其做法如下：

$\mathcal{P}$$\mathcal{P}$使用一个伪随机函数来产生随机问题，并且就这些问题产生相应的结果，并且以此作为其对相应知识的证明. 于此同时$\mathcal{V}$$\mathcal{V}$对每次问题的结果进行验证，并且$\mathcal{V}$$\mathcal{V}$需要能够验证这些答案与每个问题的对应性.

只要$\mathcal{P}$$\mathcal{P}$用来产生问题的输入具有随机性，那么从直觉上可以得到其效果与交互式方案是相同的，具体证明见超链接部分.

应用

目前Fiat-Shamir启发式签名经常用来将交互式证明转换成非交互式证明，例如在知识证明（proof of knowledge）等一系列工作中，一个常见的套路就是首先提供一个交互式版本，然后再使用Fiat-Shamir启发式签名将其转换成一个非交互证明方法从而减少通信轮数.