# BLS签名形式化安全证明（十四行诗版）
:::info
作者：[Kurt Pan](https://twitter.com/kurtpan666)
:::

> **定理**：
> 如果哈希函数$H$是随机预言
> 且如果CDH问题是困难的
> 则BLS签名方案是选择消息攻击下存在不可伪造（EU-CMA) 安全的
> 安全损失$L=q_H$，$q_H$是对随机预言哈希查询的次数

证明：

假设存在敌手$\mathscr{A}$
可以 $\left(t, q_s, \varepsilon\right)$攻破
BLS签名方案的EU-CMA安全

构造模拟器$\mathscr{B}$以解决CDH问题
$\mathscr{B}$的输入是CDH实例$\left(g, g^a, g^b\right)$
目标是输出CDH问题的解$g^{ab}$
同时$\mathscr{B}$控制着随机预言
且运行$\mathscr{A}$的实例

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

- 初始化

$\mathscr{B}$ 将公钥$pk$设置为
来自于CDH实例的$g^a$
私钥$sk=a$

- 哈希查询

在收到敌手的哈希查询前
$\mathscr{B}$ 随机选择整数 $i^* \in\left[1, q_H\right]$，
接着准备一个开始为空的哈希列表
记录所有的查询和应答

令第$i$个哈希查询是$m_i$
如果$m_i$已在哈希列表中
$\mathscr{B}$ 依表来返回该查询

否则，$\mathscr{B}$在$\mathbb{Z}_p$中随机选择$w_i$
并设置$H\left(m_i\right)$如下：
$H\left(m_i\right)=\left\{\begin{array}{ll}
g^{b+w_i} & \text {当} i=i^* \\
g^{w_i} &
\end{array} \right.$

$\mathscr{B}$ 以$H\left(m_i\right)$ 应答查询
并添加 $\left(i, m_i, w_i, H\left(m_i\right)\right)$ 到哈希列表中
- 签名查询

对消息$m_i$的签名查询
如果$m_i$就是那哈希列表中的第$i^*$次查询的消息，中止。
否则，有 $H\left(m_i\right)=g^{w_i}$
$\mathscr{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^*$
输出一个伪造的签名$\sigma_{m^*}$

如果$m^*$并非是那哈希列表中的第$i^*$个查询的消息，中止。
否则，有$H\left(m^*\right)=g^{b+w_{i^*}}$

由于
$\sigma_{m^*}=H\left(m^*\right)^a=\left(g^{b+w_{i^*}}\right)^a=g^{a b+a w_{i^*}}$

$\mathscr{B}$ 计算
$\frac{\sigma_{m^*}}{\left(g^a\right)^{w_{i^*}}}=\frac{g^{a b+a w_{i^*}}}{\left(g^a\right)^{w_{i^*}}}=g^{a b}$
作为CDH问题实例的解

模拟器构造如是说
$\square$

如果模拟器成功猜出$i^*$
所有的查询签名可模拟
成功模拟和有效攻击的概率为$\frac{1}{q_H}$

解决CDH问题的概率为$\frac{\varepsilon}{q_H}$
模拟器运行时间为$t+T_s$
$T_s=O\left(q_H+q_s\right)$

证毕
$\blacksquare$