概述

Fiat-Shamir变换由Fiat和Shamir在1986年提出，一个非常有用的方式以将公共掷币的交互式协议中的交互量减少到最小

在正式介绍之前，先讲一下交互式论据的相关知识

Interactive Arguent

最早由$[BCC80]$提出，其概念和之前提到的交互式证明很类似，同样是Prover尝试让Verifier接受某个陈述为真，大概如下图所示

和交互时证明一样，其具有两个特性

  • 完备性：P让V接受$x\in L$的概率为$1-negl$
  • 计算合理性：任何计算有界的恶意的P都只能以$negl$的概率使V接受$x\notin L$

但与交互式证明唯一的区别在于，交互式证明中不对Prover做任何要求，也即IP中的Prover是计算无界的（Computation Unbounded），但在交互式论证中Prvoer和Verifier都是计算有界的（Computation Bounded）

Fiat-Shamir Transform

Fiat-Shamir变换可以将任意的公共掷币的交互式论据转换为非交互式论据，从而Prover只需要想Verifier发送一条消息即可

大概长这样，左侧是公共掷币的交互式论据，V发送的消息$\beta_i$取决于V的掷币结果，然后P和V有来有回的互相发消息，直到协议执行完毕

而右侧是非交互式论据，因为我们不希望Verifier发送任何消息，因此需要一个方式来生成一些随机性，因此需要引入一个极其复杂的哈希函数$H$，要求其是不可预测的，此时$P_{FS}$先发送第一条消息$\alpha_1$，然后利用$H$计算$\beta_1=H(x,\alpha_1)$（这里$x$和之前一样，是公共输入），之后再发送$\alpha_2$，计算$\beta_2=H(x,\alpha_1,\alpha_2)$，以此类推发送消息和计算对应的$\beta$，直到$r$条消息全部发送完毕

FS变换一个非常重要的作用在于，对于交互式证明系统而言，交互确实会起到一些作用，但是FS变换可以让交互从证明中完全解放出来

根据上面所说的，非交互式论据看起来很复杂，但是因为Hash函数的特性，实际使用时其开销会非常小，又由于其非常强大的证明力，应用场景也是非常的广泛，比如CS证明，(zk-)SNARGs，STARKs

FS变换安全吗

是否存在这样的Hash函数，使得FS变换是安全的呢？答案是目前仍不晓得（甚至知之甚少），因此和之前提到的一样，讨论安全性时仍然讨论的是理想化的模型，也即假设有这样理想的哈希函数使得FS变换是安全的

Random Oracle Model

这个概念最早由$[BR93]$提出，另一个非常cooooooool的模型

Random Oracle表示一个黑盒，其内部是一个完全随机的函数$R:\{0,1\}^\lambda\rightarrow\{0,1\}^\lambda$，所有的参与方（无论是否诚实）都可以访问这个黑盒，对于任何的请求$x$和$y$，若有$x=y$，则黑盒会返回完全相同的串，若有$x\neq y$，则黑盒会返回两个完全独立的串
在接下来的内容中，若讨论的模型是基于RO的，则其安全性很大程度上依赖于RO中函数R

FS in ROM

看起来是这样

将原来那个Hash函数替换为了Random Oracle $R$，根据RO的定义，$P_{FS}$和$V_{FS}$（包括尝试作弊的$P_{FS}$和$V_{FS}$）都可以访问R，然后$P_{FS}$利用$R$来计算$\beta_i$

  • 定理：对于任何具有可忽略的合理性的基于$R$的常数轮交互式论证$\Pi_R$，其安全性很大程度上依赖于$R$
  • 断言：存在一个多轮协议$\Pi$，其合理性错误为$negl$，对其应用FS变换后其合理性不再成立（即便是在ROM下）

证明：选择一个具有常数合理性的常数轮协议，并顺序重复多次，在交互式的情况下，其合理性会以指数级下降，只要重复足够多的次数，其合理性可达到$negl$，但是作用FS变换之后（无论使用的是Hash函数还是ROM），由于原来的合理性为常数，这意味着假设有一个作弊的$P_{FS}$，根据协议计算$\beta_1$后，$\beta_1$对其有利概率为常数，因此只要$\beta_1$对作弊$P_{FS}$的不利，则其重新选择一个$\alpha_1$并再次计算$\beta_1$，直到对其有利为止（不难证明这重复计算$\beta_1$的次数期望为常数次），然后以此类推计算$\beta_2$直至协议执行完毕，从而这个作弊的可以成功欺骗$V_{FS}$

换句话说，因为原本协议的合理性为常数，因此作弊的$P_{FS}$找到一个对其有利的$\beta_1$需要尝试常数次，如果原本协议的合理性为$negl$，则其找到一个有利的$\beta_1$需要超多项式的尝试次数

Three Msg Protocol

如果安全性有问题的话，那么来看一个只有三条消息的协议，，像下面这个图一样

左侧的交互式协议中，P先给V发送一条消息$\alpha$，V抛币后向P返回$\beta$，之后根据$\beta$，P再发送$\gamma$给V，利用FS变换（基于ROM）后得到右侧的这个非交互的版本，这个变换在ROM下是安全的

为什么？在分析三个性质之前，先介绍一下其他的知识点

分叉引理

一个事实：假设$(X,Y)$为联合随机变量，满足$Pr[A(X,Y)]\geq\epsilon$，则至少有$\frac{\epsilon}{2}$的$x\in X$，满足$Pr_{Y|x}[A(x,Y)]\geq\frac{\epsilon}{2}$

基于这个事实，来分析一下合理性，之前提到了$P_{FS}^*$运行时间为$T$，因此在$T$内它可以向RO发起至多$T$次查询，标记为$Q_1,...,Q_T$，不失一般性，这些$Q_i$都是不同的，且记$P_{FS}^*$发送的第一条消息
$\alpha \in \{Q_1,...,Q_T\}$，从而有$∃ i^*\in [T]$，在条件$Q_{i^*}=\alpha$时，使得$P_{FS}^*$取得优势的概率为$\frac{\epsilon}{T}$（反证法证明）

分叉引理：对于$\frac{\epsilon}{2T}$个$\{q_1,...,q_{i^*}\}$，对于所有的$i\leq i^*$，在条件$Q_{i^*}=\alpha$且$Q_i=q_i$时，使得$P_{FS}^*$取得优势的概率为$\frac{\epsilon}{2T}$，意思是，若第一部分$P_{FS}^*$使得V接受的概率为$\frac{\epsilon}{2T}$，则第二部分$P_{FS}^*$使得V接受的概率仍然为$\frac{\epsilon}{2T}$（用上面的事实证明）

分叉引理讲的是这么个事情：如果对手可以以不可忽略的概率伪造签名，那么具有相同随机磁带的同一对手可以在使用不同随机预言机的攻击中创建第二次伪造的概率也不可忽略

攻破V的合理性

对于三条消息的协议，若$P^*$希望攻破这个协议，根据上面分析的结果，$P^*$会这么做

  1. $P^*$在交互时本地运行一个$P_{FS}^*$，在这个$P_{FS}^*$中，其对于第$i^*$个查询之前的查询，其都将一个随机的串作为查询请求（得到的回答不重要）
  2. 当到第$i^*$个查询时，$P^*$将$\alpha=Q_{i^*}$作为第$i^*$个查询的请求，同时将$\alpha$发送给V（并从V那里得到$\beta$）
  3. 继续用随机的串运行$P_{FS}^*$剩下的请求，直至结束
  4. 最终$P_{FS}^*$输出$(\alpha',\beta',\gamma')$
  5. 如果有$\alpha=\alpha',\beta=\beta'$，则$P^*$向V发送$\gamma=\gamma'$

分析：（没看懂）此时$P^*$欺骗V的概率为$(\frac{\epsilon}{2T})^2$，不为$negl$

回到ROM下的FS

接下来分析三个性质

  • 完备性：显然成立
  • 合理性：利用反证法，对于$\forall x\notin L$，假设$P_{FS}^*$运行时间为一个多项式时间$T$且以一个比较显著的概率（比如$\geq \epsilon,\epsilon \neq negl$）使得$V_{FS}$接受$x$，则结合上述的分析与分叉定理，在交互式协议中恶意的$P^*$可以通过这样的$P_{FS}^*$来以概率$(\frac{\epsilon}{2T})^2$欺骗V，因为$\epsilon \neq negl$且$T$为一多项式，因此$(\frac{\epsilon}{2T})^2$也是一个不可忽略的量，又由于交互式协议中的合理性成立的，恶意的$P^*$无法欺骗V，从而原假设不成立，也即不存在这样的$P_{FS}^*$以一个比较显著的概率$\geq \epsilon$使得$V_{FS}$接受$x$，故基于ROM的FS中，$P_{FS}^*$欺骗$V_{FS}$接受$x$的概率为$negl$
  • 零知识性：因为ROM下的FS有多种零知识的定义（及一些问题），因此并没有在此之上定义零知识性，对于Verifier而言，其除了看到$(\alpha,\beta,\gamma)$以外，他还获得了一个访问随机函数R的权限，满足$R(x,\alpha)=\beta$，那么问题来了，是否V可以自己获得这个函数？（是否可以取决于对ZK的定义，接下来解释）

因此，基于ROM的FS是具有合理性的，但是零知识性是否成立取决于一些合适的定义

但是现实生活中并不存在这种理想的模型，因为这样的Hash函数需要$2^\lambda \ bit$来表示，现有的PRF不足以满足这个性质，那么问题来了，是否可以用现有的Hash函数来使得FS变换变得安全呢？坏消息是不能，甚至更糟，$[CHG98]$证明了存在一些协议，使得在ROM下是安全的，但是对于实例化后（比如说用AES或者任何你觉得合适的Hash函数来替代RO）会被完全攻破

那基于这样的坏消息，如何将基于ROM的证明变安全呢？积极来看，这些反例都是人为设计的，且对于ROM的分析可知，FS变换在现实生活中确实是安全的，且其是一个很好的启发式，有利于提高协议的可行性和效率，消极来看，因为这样的安全性基于我们仍未知的假设，且这些反例不知道什么时候会变为现实（万一变了就寄了）

Instantiating Fiat Shamir with Explicit Hash Function

  • 问题：是否可以用某个Hash函数族来安全的应用FS启发式？
  • 定义：称一个Hash族$H$是FS可兼容的（FS-compatible），表明对一个具体的协议$\Pi$而言，$FS_H(\Pi)$是安全的

上述定义的意思是，对于特定的协议，对其应用基于Hash函数族$H$，得到的协议仍然满足合理性和零知识性，因此考察一个函数族$H$是否是FS可兼容的，主要是考察其合理性和零知识性（完备性根据之前的分析显然成立）

此时上面的三条消息的协议变成下面这样

  • $V_{FS}$从函数族里面选择一个Hash函数$h\in H$，将其发送给$P_{FS}$
  • $P_{FS}$用收到的h，计算$\beta=h(x,\alpha)$，然后根据得到的$\beta$，设置合适的$\gamma$，并将$(\alpha,\beta,\gamma)$发送给$V_{FS}$

如果这样变换后协议仍然安全（满足合理性和零知识性），则称这个函数族$H$是FS可兼容的

  • 定义：称一个函数族$H$是可编程的，表明有$h\in H$，满足$h(x,\alpha)=\beta$
  • 断言：若$H$是可编程的且$\Pi$是一个HVZK协议，则$\Pi_{FS}(h)$是一个ZK协议（HVZK：Honest Verifier ZK，意思是要求协议中的Verifier一定是诚实的，不存在试图欺骗Prover的行为）
  • 定理：$[B01,GK03]$存在一些协议，其对于任意函数族H都是FS不可兼容的

后记

本系列文章撰写于研一，受笔者知识面与理解能力的局限，部分概念与定理的表述难免有不准确与不严谨的地方，烦请各位专业人士斧正

参考文章

$[1]$ 云中「秘密」：构建非交互式零知识证明——探索零知识证明系列（五）

$[2]$（以）Odeb Gol­dre­ich 著；温巧燕，杨义先译。密码学基础 $[M]$. 北京：人民邮电出版社.2003.

$[3]$ Zero-Knowledge Proof-Wiki

$[4]$ The 9th BIU Winter School on Cryptography | BIU Cyber Center