> **定理**： > 如果哈希函数$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$