BLS签名形式化安全证明（十四行诗版）

作者：Kurt Pan

定理：
如果哈希函数

$H$是随机预言
且如果CDH问题是困难的
则BLS签名方案是选择消息攻击下存在不可伪造（EU-CMA) 安全的
安全损失

$L=q_H$，

$q_H$是对随机预言哈希查询的次数

证明：

假设存在敌手

$\mathcal{A}$
可以

$(t,q_s,\epsilon )$攻破
BLS签名方案的EU-CMA安全

构造模拟器

$\mathcal{B}$以解决CDH问题

$\mathcal{B}$的输入是CDH实例

$(g,g^a,g^b)$
目标是输出CDH问题的解

$g^{ab}$
同时

$\mathcal{B}$控制着随机预言
且运行

$\mathcal{A}$的实例

$\mathcal{B}$的模拟过程如下：

• 初始化

$\mathcal{B}$ 将公钥

$pk$设置为
来自于CDH实例的

$g^a$
私钥

$sk=a$

• 哈希查询

在收到敌手的哈希查询前

$\mathcal{B}$ 随机选择整数

$i^{\ast }\in [1,q_H]$，
接着准备一个开始为空的哈希列表
记录所有的查询和应答

令第

$i$个哈希查询是

$m_i$
如果

$m_i$已在哈希列表中

$\mathcal{B}$ 依表来返回该查询

否则，

$\mathcal{B}$在

${\mathbb{Z}}_p$中随机选择

$w_i$
并设置

$H\left(m_i\right)$如下：

$H\left(m_i\right)=\{\begin{array}{ll}{g}^{b+w_i}& \text{当}i=i^{\ast }\\ g^{w_i}& \end{array}$

$\mathcal{B}$ 以

$H\left(m_i\right)$ 应答查询
并添加

$(i,m_i,w_i,H\left(m_i\right))$ 到哈希列表中

• 签名查询

对消息

$m_i$的签名查询
如果

$m_i$就是那哈希列表中的第

$i^{\ast }$次查询的消息，中止。
否则，有

$H\left(m_i\right)=g^{w_i}$

$\mathcal{B}$ 计算

${\sigma }_{m_i}$ 如下

${\sigma }_{m_i}={\left(g^a\right)}^{w_i}$

由于

${\sigma }_{m_i}=H{\left(m_i\right)}^a={\left(g^{w_i}\right)}^a={\left(g^a\right)}^{w_i}$
因此

${\sigma }_{m_i}$ 是

$m_i$的一个有效签名

• 伪造

敌手对某个没有查询过的消息

$m^{\ast }$
输出一个伪造的签名

${\sigma }_{m^{\ast }}$

如果

$m^{\ast }$并非是那哈希列表中的第

$i^{\ast }$个查询的消息，中止。
否则，有

$H\left(m^{\ast }\right)=g^{b+w_{i^{\ast }}}$

由于

${\sigma }_{m^{\ast }}=H{\left(m^{\ast }\right)}^a={\left(g^{b+w_{i^{\ast }}}\right)}^a=g^{ab+a{w}_{i^{\ast }}}$

$\mathcal{B}$ 计算

$\frac{{\sigma }_{m^{\ast }}}{{\left(g^a\right)}^{w_{i^{\ast }}}}=\frac{g^{ab+a{w}_{i^{\ast }}}}{{\left(g^a\right)}^{w_{i^{\ast }}}}=g^{ab}$
作为CDH问题实例的解

模拟器构造如是说

$◻$

如果模拟器成功猜出

$i^{\ast }$
所有的查询签名可模拟
成功模拟和有效攻击的概率为

$\frac{1}{q_H}$

解决CDH问题的概率为

$\frac{\epsilon }{q_H}$
模拟器运行时间为

$t+T_s$

$T_s=O(q_H+q_s)$

证毕

$◼$