分叉引理Forking lemma

最近看到几篇ID-based的论文有利用forking lemma进行概率推导的，所以先写写这个。
why,what,how

• 为什么使用分叉引理？
  证明数字签名方案的安全性常用的一种模型是随机预言模型ROM。在随机预言模型中，数字签名方案使用的hash函数至少有一个需要被看做随机预言机。在这种模型下，证明数字签名方案安全性的一个重要技术就是随机预言机重放技术，也就是通过重放hash值来破解一个困难问题。该技术的理论依据就是著名的分叉引理(Forking Lemma)。
• 什么是分叉引理？
  2000年 , Pointcheval和 Stern提出了一般签名体制的概念 , 为了证明随机预言模型下数字签名方案的安全性而提出的。
  令 $Q_i$代表敌手 $\mathcal A$发送的第 $Q_i$次随机预言询问， $h_i$表示挑战者 $\mathcal C$对第 $i$次随机预言询问返回的结果。分叉引理的示意图如图。
  

在安全性证明中，挑战者 $C$为了能够利用敌手 $\mathcal A$破解一个困难的问题，它需要运行两次挑战过程，使得第二次挑战过程的输出结果和第一次的输出结果在开始一段时间内都是相同的，但是在某处之后就会发生改变，从而挑战者 $\mathcal C$据此能够破解一个困难的问题，如大数分解问题或者离散对数问题。

Pointcheval2000¹提出的分叉引理
假设 $(KeyGen,Sign,Ver)$是一个安全参数为 $k$的数字签名方案， $\mathcal A$是一个输入仅是公开数据的概率多项式时间算法。令 $\mathcal Q$是 $\mathcal A$询问随机预言机的最大可能次数。如果 $\mathcal A$在时间 $t$内能够以概率 $\varepsilon > 7Q/2^k$生成一个有效的签
名 $(\mu,\sigma _1,h,\sigma _2)$，则存在一个新的算法 $\mathcal B$，它通过控制算法 $\mathcal A$，能够在期望的时间 $t' \le 84480tQ/\varepsilon$内生成两个有效的签名 $(\mu,\sigma _1,h,\sigma _2)$和 $(\mu,\sigma _1,h',\sigma _2')$，使得 $h\ne h'$。
原式在该篇论文的通用forking lemma中。

Pointcheval和Stern提出的上述分叉引理仅仅适用于普通的数字签名方案，而对于其他具有某些特殊性质的数字签名算法来说，上述分叉引理是不适用的（除盲签名，Schnorr，El Gamal签名）。为了将Pointcheval-Stern分叉引理的基本思想扩展到更多其他类型的数字签名方案中，设计适用于所有签名方案的分叉引理，Bellare2006²给出了下面的一般分叉引理(General Forking Lemma)。

引理(一般分叉引理).设 $q$是一个正整数， $H$是一个具有 $h>2$个元素的集合。令 $\mathcal I\mathcal G$是参数生成算法， $\mathcal B$是一个随机算法，算法 $\mathcal B$的输入是 $\{x,h_1,…,h_q\}$,输出是 $(J, \sigma)$，其中 $x\in \{0,\cdots,q\},h_i\in H(i\in [q])$。
令算法 $\mathcal B$的接受概率 $acc$为试验 $EXP=[x\leftarrow \mathcal I\mathcal G;h_1,\cdots,h_q\leftarrow H;(J,\sigma)\leftarrow B(x,h_1,\cdots,h_q)]$中 $J\ge1$的概率。
令与 $\mathcal B$相关的分叉算法 $F_{\mathcal B}$表述如下。
1.算法 $F_{\mathcal B}$输入 $x$:
2‘随机选择 $\rho \in \{0,1\}$,
3.从集合 $H$中随机选择 $h_1,\cdots,h_q$，
4. $(I,\sigma)\leftarrow B(x,h_1,\cdots,h_q;\rho)$,
5.如果 $I=0$，则返回 $(0, \varepsilon ,\varepsilon)$,
6.从集合 $H$中随机选择 $h'_1,\cdots,h'_q$，
7: $(I',\sigma')\leftarrow B(x,h_1,\cdots,h_{I-1},h'_I,\cdots,h'_q;\rho)$,
8.如果 $I=I'$并且 $h\ne h'$，则输出 $(1,\sigma,\sigma ')$;否则输出 $(0, \varepsilon ,\varepsilon)$,
设 $frk=Pr[b=1:x\leftarrow {\mathcal I\mathcal G};(b,\sigma,\sigma ')\leftarrow F_{\mathcal B}(x)]$，则我们有
$frk \geqslant acc \cdot(\frac{{acc}}{q} - \frac{1}{h})$

这里我们简单地对上述一般分叉引理进行一些直观的解释。首先，我们可以将实验 $EXP=[x\leftarrow \mathcal I\mathcal G;h_1,\cdots,h_q\leftarrow H;(J,\sigma)\leftarrow B(x,h_1,\cdots,h_q)]$看做是敌手 $\mathcal A$伪造签名的过程，其中算法 $\mathcal B$就是敌手 $\mathcal A$用来伪造签名的算法。因此我们可以容易地知道，概率 $acc$实际上就是敌手 $\mathcal A$成功伪造签名的概率。其次，分叉算法实际上可以看做是利用算法 $\mathcal B$输出两个签名的过程，所以概率 $frk$是指分叉算法 $F_{\mathcal B}$能够输出两个有效且不同签名的概率(需要满足 $h_I=h_I'$)。
综合可得，一般分叉引理关于 $acc$和 $frk$的关系说明，如果存在一个敌手 $\mathcal A$能够以概率 $acc$伪造一个数字签名方案的有效签名，则存在一个算法 $F_{\mathcal B}$通过利用敌手 $\mathcal A$能够以概率 $frk \geqslant acc \cdot(\frac{{acc}}{q} - \frac{1}{h})$输出该签名方案两个有效且相关的不同签名。

• 分叉引理应用
  在很多数字签名方案的安全性证明过程都有使用。
• Todo，列举一些论文。