一种无证书聚合签名方案的改进

王启明，樊爱宛

（1.平顶山学院 计算机科学与技术学院，河南 平顶山 467002；2.平顶山学院 软件学院，河南 平顶山 467002）

0 引 言

为了降低公钥证书管理的复杂性和解决密码托管的安全性等问题，AlRiyami等人首次提出无证书的密码系统[1]。无证书密码系统利用密钥生成中心KGC（Key Generation Center）产生用户的部分私钥，与用户随机选择的秘密值共同组成用户公钥与私钥。为解决签名效率偏低的问题，Boneh等人提出聚合签名的思想[2]。聚合签名是多个用户对多个消息分别签署的签名，能够合成一个短的签名，而验证者只需对聚合后的短的签名进行验证，便可以确信多个用户分别进行了签名。

由于无证书与聚合签名在节约计算和通信成本方面的优势，第一个无证书聚合签名的安全模型和聚合签名方案在2007年由Gong等人提出[3]。此后，一些无证书聚合签名方案又被相继提出。文献[4]以文献[5]为基础，构建了一种无证书聚合签名方案，但是由于涉及到两个群的计算，效率偏低。文献[6]提出一种有效的无证书聚合签名方案，方案采用常量对运算，极大地提高了签名验证时的效率。但是文献[7]指出其不能抵抗无证书攻击模型中类型Ⅱ敌手的攻击。从目前无证书聚合签名研究状况分析，大部分方案存在不能抵抗两类攻击和计算效率偏低的问题。为此，侯红霞等人构造了一种改进的无证书聚合签名方案（以下简称HZD方案）[8]，由于采用常量对运算，能够在保证安全的基础上，提高签名验证时的效率。然而，本文针对HZD方案进行安全性分析，发现这种方案不能抵抗TypeⅡ攻击者A2的伪造攻击。因此，提出一种改进方案，在随机预言模型下，证明该改进方案在适应性选择消息攻击下是具有不可伪造性的。

1 预备知识

1.1 数学难解问题

定义1 计算Diffle⁃Hellman问题（CDHP）：已知G是阶为q的循环群，P是群G的生成元，给定P，aP，bP∈G，其中a，b∈未知，计算abP是困难的。

1.2 无证书聚合签名的定义与安全模型

一个无证书聚合签名系统由7个算法组成，分别是系统建立、部分密钥生成、设置秘密值、设置私钥与公钥、签名、签名聚合和聚合签名验证。

无证书聚合签名系统存在2种攻击者。

Type I：攻击者A1无法获取KGC的主密钥 s，但是可以任意替换公钥。此类型主要是模仿非法用户进行的攻击。

TypeⅡ：攻击者A2可以获取KGC的主密钥 s，但是不可以任意替换公钥。此类型主要是模仿能够为用户生成部分密钥的KGC进行的攻击。

如果无证书聚合签名方案在适应性选择消息攻击下是存在性不可伪造的，就需要通过与Type I和TypeⅡ攻击者进行博弈游戏。假设挑战者C是方案的防守方，攻击者A1和A2是方案的攻击方，则博弈游戏有2种：Game 1是攻击者A1与挑战者C关于伪造性攻击的游戏；Game 2是攻击者A2与挑战者C关于伪造性攻击的游戏。

2 HZD方案的安全性分析

HZD方案是一个标准的无证书聚合签名方案，主要的7个算法可见文献[8]。HZD方案针对2个攻击类型的适应性选择消息、选择身份以及公钥替换攻击下是存在不可伪造的[8]。本节采用TypeⅡ攻击者A2对HZD方案进行伪造攻击，以证明其方案具有可伪造的安全缺陷。攻击者A2通过以下步骤进行消息的伪造。

（1）随机选择ri∈，计算 Ui=riP。

（2）计算 hi=H2(mi，IDi，pki，Ui)，计算 Vi=di+riQ+shipki。

（3）返回 σi=(Ui，Vi)。

TypeⅡ攻击者A2可以采用以上方式伪造多个用户签名，并且经过聚合方验证聚合操作后，也能通过聚合签名验证。因为验证方依据以上参数能够通过等式e(P，Vi)=e(Ppub，Ui+hiQi)e(hipki′，h)判断。单用户签名验证通过证明如下。

由此可见Vi=di+riQ+shipki。故A2通过以上步骤可以伪造若干个合法的消息，HZD方案在TypeⅡ攻击者A2攻击下不具有不可伪造性。

3 改进方案的描述

本文的改进方案仍然是由7个算法构成：系统建立、部分密钥生成、设置秘密值、设置私钥与公钥、签名、聚合签名和聚合签名验证。其中，系统建立中添加一个哈希函数 H3：{0，1}*→G1，部分密钥生成、设置秘密值、设置私钥与公钥等3个算法与原方案相同。本文仅对签名、聚合签名和聚合签名验证算法进行描述。

（1）签名：假设发送方用户i的身份为IDi，私钥为(di，xi)，公钥为 pki，消息 mi∈，用户i根据以下步骤生成签密信息σ。

① 随机选择ri∈，计算Ui=riP。

②计算Qi=H1（IDi），hi=H2（mi，IDi，pki，Ui），h=H3（P，Ppub）。计算 Vi=di+hiriQ+xih。

③ 返回σi=（Ui，Vi）。

（2）聚合签名：假设聚合方收到来自n个用户的签名，其中用户 i的签名信息σi=（Ui，Vi），其中 1≤i≤n。聚合方根据以下步骤生成聚合签名信息σ。

①计算Qi=H1（IDi），hi=H3（mi，IDi，pki），h=H3（P，Ppub）。

② 判断 e（P，Vi）=e（Ppub，Qi）e（Ui，hiP）e（pki，h）。如果成立，则进行聚合操作，转入③，否则拒绝聚合操作，终止算法。

④ 输出 σ =(U，V)。

（3）聚合签名验证：假设n个用户进行签名，输入用户对应公钥 pki，对应消息 mi和聚合签名信息σ=(U，V)，其中1≤i≤n。验证方根据以下步骤验证聚合签名信息σ。

① 计算Qi=H1(IDi)，hi=H2(mi，IDi，pki，Ui)，h=H3(P，Ppub)。

4 改进方案的分析

4.1 改进方案正确性分析

本文改进方案正确性成立，证明如下：

4.2 改进方案安全性分析

在随机谕言模型环境下，改进方案具有存在性不可伪造的安全性。

定理1在计算CDHP困难和随机谕言模型的假设下，改进方案在适应性选择消息攻击下是存在性不可伪造的。

引理1假设一个Type I攻击者A1在t时间内以不可忽略的概率ε赢得了Game 1的胜利，则存在一个算法C，在t′时间内以一个不可忽略的概率ε′解决CDHP难题。其中，qH1，qE，qpk，qs分别表示对 H1询问的次数、对部分密钥生成询问、对公钥询问的次数和对签名询问的次数，tm和tinv分别为1个标量乘时间和1个逆运算时间。

证明：假定一个Type I攻击者A1以不可忽略的概率ε赢得了Game 1的胜利，需要构造一个算法C，利用A1解决CDHP难题。C收到一个CDHP难题实例（aP，bP），其中随机数a，b∈为未知数，目标是能够计算出abP。C随机选择一个身份IDj，并回答A1以下询问。

初始化：C计算 Ppub=aP，params=（q，G1，G2，e，P，Ppub，H1，H2，H3）。C将 params发送给 A1。

H1询问：C 构建 H1列表（IDi，Qi，di，xi，pki）。A1 向 C提出IDi询问，如果在H1列表中存在，C向A1返回Qi的值，否则C以下面步骤进行回答。

（1）如果 IDi≠IDj，C 随机选择 ti∈，计算 Qi=tiP，添加到H1列表，并向A1返回Qi的值。

（2）如果IDi=IDj，C计算 Qi=tibP，添加到H1列表，并向A1返回Qi的值。

H2询问：C构建 H2列表（m，IDi，pki，Ui，h2）。A1向 C提出（m，IDi，pki）的询问，如果在H2列表中存在，C向A1返回 h2的值，否则C随机选择h2∈，添加到H2列表中，并向A1返回h2的值。

部分秘钥提取：A1向C提出IDi的询问，C以下面方式进行回答。

（1）如果 IDi在私钥列表（IDi，di，xi）列表中存在，C向A1返回di的值。

（2）如果 IDi≠IDj，计算 di=tiaP，添加到列表，并向A1返回di的值。

（3）如果IDi=IDj，C返回“⊥”，并终止算法。

H3询问：C构建H3列表（P，Ppub，h）。A1向C提出（P，Ppub）的询问，如果在H3列表中存在，C向A1返回h的值，否则C随机选择z∈，计算 h=zP，将 h 添加到 H2列表中，并向A1返回h的值。

公钥询问：C构建公钥列表（m，xi，IDi，pki）。A1向C提出IDi的询问，如果记录列表中存在，C向A1返回pki的值，否则C随机选择xi∈，计算 pki=xiP，添加到列表中，并向A1返回pki的值。

公钥替换：A1用自己选取的pki替换IDi的公钥。A1向C提出（IDi，pki），C将（m，⊥，IDi，pki）添加到公钥列表中。

签名：A1向 C提出（m，IDi，pki）的询问，如果 IDi≠IDj，C依据方案的签名算法，计算σi=（Ui，Vi），将结果添加到签密列表，并将σ返回给A1，否则C返回“⊥”，并终止算法。

最后，A1 停止查询，输出σ=（U*，V*）。如果在查询过程中，C没有返回“⊥”终止算法，则得到以下等式。

由此可得：

求解abP：

为了分析C解决CDHP难题的不可忽略的概率ε′，首先定义 4个事件 E1，E2，E3，E4。

E1：在进行部分秘钥提取询问中，C不能返回“⊥”，并终止算法。

E2：A1签名询问没有失败，成功输出σi=（Ui，Vi）。

E3：A1成功伪造聚合签名σ=（U*，V*）。

E4：A1询问H1过程中，至少有一条记录为IDi=IDj。

从模拟攻击中，可知：

那么，C在t′时间内解决CDHP难题的不可忽略的概率为：

如果对方案攻击成功的概率ε是不可忽略的，则C能够以不可忽略的概率解决CDHP问题。所以，本方案在计算CDHP困难和随机谕言模型的假设下，改进方案在适应性选择消息攻击下是存在性不可伪造的。

引理2假设一个TypeⅡ攻击者A2在t时间内以不可忽略的概率ε赢得了Game 2的胜利，则存在一个算法C，在t′时间内以一个不可忽略的概率ε′解决CDHP难题。其中，qH1，qE，qpk，qs分别表示对 H1询问的次数、对部分密钥生成询问、对公钥询问的次数和对签名询问的次数，tm和tinv分别为1个标量乘时间和1个逆运算时间。

引理2的证明方式与引理1相似。A2向C提出IDi询问，如果IDi=IDj，C计算pki=tiaP，添加到公钥列表，并向A2返回pki的值。在H3询问中，h=bP。如果在查询过程中，C没有返回“⊥”终止算法，则得到以下等式求解abP方程式：

分析C解决CDHP难题的不可忽略的概率ε′，与引理1相同。C在t′时间内解决CDHP难题的不可忽略的概率为：

如果对方案攻击成功的概率ε是不可忽略的，则C能够以不可忽略的概率解决CDHP问题。所以，在计算CDHP困难和随机谕言模型的假设下，改进方案在适应性选择消息攻击下是存在性不可伪造的。

4.3 改进方案效率分析

假设m表示群G1上1次标量乘计算，e表示l个双线性对的计算，l表示G1群元素的长度。本文签名长度仅为2l，签名与验证总计算量为6nm+4e。

（1）文献[5]中方案的签名长度2l，总计算量7nm+5e。本文改进方案的运算效率比此方案少了1个标量乘和双线对运算。

（2）文献[9]方案的签名长度2l，总计算量6nm+5e。虽然与本文改进方案的聚合签名长度相同，但是比改进方案多了1个双线性对运算。

（3）文献[10]的签名与改进方案相同，总计算量也比改进方案小。但是，存在与HZD方案相同的可伪造性攻击。由此可见，本文方案在聚合签名的长度和计算量方面，其效率明显高于现有方案。

5 结 语

本文分析了文献[8]的无证书聚合签名方案，指出此方案存在TypeⅡ攻击者A2的伪造攻击。本文在此基础上，提出了一个改进方案。在计算CDHP困难和随机谕言模型的假设下，证明改进方案在适应性选择消息攻击下具有不可伪造性。改进方案在签名与验证过程中，只需要6个标量乘和4个双线性对运算，与同类安全的无证书聚合签名方案相比，效率较高。

[1]AL RIYAMI S S，PATERSON K G.Certificateless public key cryptography[C]//Advances in CryptologyASIACRYPT 2003.Taibei，China：Springer Berlin Heidelberg，2003：452⁃473.

[2]BONEH D，GENTRY C，LYNN B，et al.Aggregate and veri⁃fiably encrypted signatures from bilinear maps[C]//Advances in CryptologyEUROCRYPT 2003.Warsaw：Springer Berlin Heidelberg，2003：416⁃432.

[3]ZHANG Lei，ZHANG Fu ⁃tai.A new certificateless aggregate signature scheme[J].Computer Communications， 2009， 32（6）：1079⁃1085.

[4]ZHANG Lei， QIN Bo， WU Qian ⁃hong， et al.Efficient many⁃to⁃one authentication with certificateless aggregate signa⁃tures[J].Computer Networks，2010，54（14）：2482⁃2491.

[5]XIONG Hu，GUAN Zhi，CHEN Zhong，et al.An efficient cer⁃tificateless aggregate signature with constant pairing computa⁃tions[J].Information Science，2013，219（10）：225⁃235.

[6]SHEN Li⁃min，SUN Yin⁃xia.On the security of a certificate⁃less aggregate signature scheme[J].International Journal of Ad⁃vancements in Computing Technology，2013，5（3）：358⁃367.

[7]杜红珍，黄梅娟，温巧燕，等.高效的可证明安全的无证书聚合签名方案[J].电子学报，2013，41（1）：73⁃76.

[8]侯红霞，张雪锋，董晓丽，等.改进的无证书聚合签名方案[J].山东大学学报：理学版，2013，48（9）：29⁃34.

[9]喻琇瑛，何大可.一个新的无证书聚合签名[J].计算机应用研究，2014，31（8）：2485⁃2487.

[10]孙华，郭磊，郑雪峰，等.一种有效可证安全的基于身份代理聚合签名方案[J].计算机科学，2012，39（1）：44⁃47.