一个可证安全的基于证书聚合签名方案

陈建能，岳昊，黄振杰

闽南师范大学计算机科学与工程系，福建漳州 363000

◎网络、通信、安全◎

一个可证安全的基于证书聚合签名方案

陈建能，岳昊，黄振杰

闽南师范大学计算机科学与工程系，福建漳州 363000

1 引言

以公钥基础设施为核心的传统公钥密码体制采用公开验证证书的方式来保证用户公钥的真实性，可是，对于证书的管理是传统公钥密码体制比较难克服的弱点之一。1984年，在Shamir提出的基于身份的公钥密码体制中，用户的公钥直接从用户身份信息中生成，每一个用户私钥的生成都依靠一个可信的第三方，称为私钥生成器（Private Key Generater，PKG），基于身份的公钥密码体制虽然避免了使用证书带来的问题，实现了用户公钥和身份的绑定，但无法彻底解决用户密钥托管问题，而且需要一个安全信道来传输密钥。

在2003年Eurocrypt会议上，Gentry[1]首先提出基于证书的公钥密码体制，在该公钥密码体制中每一个签名者都拥有自己的公私钥对和一个由权威认证机构颁发的证书。在对消息加密或者签名时，签名者必须使用自己证书和私钥。因为签名私钥是签名者自己挑选的，所以不存在密钥托管问题。不久，Kang[2]等人提出基于证书数字签名的安全性定义和两个具体的签名方案。2007年，Li[3]等人提出了基于证书的安全模型和一种新的攻击称为替换公钥攻击。在2008年，Liu[4]等人提出了两个基于证书的数字签名方案，其中一个方案没有用到双线性对，另外一个方案是在标准模型下证明其安全性的。不久，Zhang[5]证明了方案的不安全性并提出改进方案。2009年，Wu[6]等人提出了基于证书数字签名的一种新的安全模型。2011年，Li[7]等人提出了高效的基于证书短签名方案。

聚合签名这个概念最早是由Boneh，Gentry，Lynn和Shacham[8]在2003年的Eurocrypt国际会议上提出来的。随后，Lysyanskaya[9]等人用认证陷门排列（certified trapdoorpermutations）构造了一个聚合签名方案，但他们的方法只能构造有序的聚合方案，即第n个签名者必须等第n-1个签名者签名完成之后才能继续自己的签名。2004年，Cheon[10]等人首次用基于身份的思想构造了一个聚合签名方案，随后，Cheng[11]，Xu[12]、Gentry与Ramzan[13]等人分别提出了各自的基于身份的聚合签名方案，其中，以Gentry与Ramzan所提出的方案效率最高，只用到3个双线性对运算。2006年，Steve Lu[14]提出了一个无预言机的聚合签名方案。2007年，Liu等人[15]提出了一个在标准模型下可证明安全的无证书聚合签名方案。同年，Huang等人[16]重新构造无证书的聚合签名安全模型，并介绍了两个具体的构造方案。2009年，Zhang[17]等人提出了一个安全高效的无证书聚合签名方案。2010年，一个韩国的学者Kyung-Ah Shim[18]提出了一个基于身份的聚合签名方案，该方案在聚合签名验证过程中只用到两次双线性对运算，具有较高的效率。

在聚合签名中，消息被分成n个部分，由n个签名者分别对其签名，再把n个签名合成为一个聚合签名，验证者只要验证聚合签名即可，大大提高了签名的验证效率。具有附加性质的聚合签名在现实生活中已经得到广泛应用，例如代理聚合签名在电子商务和电子政务中用于签名的授权，盲聚合签名具有不可追踪性，应用于电子货币，顺序聚合签名应用于网络传输中等。

可是，国内外文献中基于证书的聚合签名方案据作者所知目前还没有，本文利用基于证书数字签名的思想和双线性对的特殊性质，提出了一个可证明安全的基于证书聚合签名方案。

2 预备知识

2.1 双线性对

设G1，G2是阶为素数q的加法循环群，P是G1的生成元，e：G1×G1→G2是双线性映射，并且满足：

（1）双线性：给定元素P、Q、a、b∈G1，有：e（aP，bQ）= e（abP，Q）=e（P，abQ）。

（2）非退化性：存在元素Q、P∈G1，使得e（Q，P）≠1G2，其中1G2是群G2的单位元。

（3）可计算性：对于所有元素Q、P∈G1，存在一个有效的算法可计算e（Q，P）。

2.2 数学问题

CDH问题（Computational Diffie-Hellman Problem，CDHP）。

定义1设G是阶为素数q的群，对任意a、b∈Z*q、P∈G，给定（P，aP，bP），计算abP称为CDH问题。在本文中假定CDHP是难解的。

3 基于证书聚合签名安全模型

基于证书聚合签名方案中一般包含系统参数建立（setup），询问（Queries）和结果输出（Output）等算法，其中Queries还包含公私钥询问UserKeyGen Query，哈希值询问Hash Query，证书询问CertGen Query，替换公钥询问ReplacePublicKey Query，和签名询问Sign Query等过程。

下面定义基于证书聚合签名方案的不可伪造性：

基于证书聚合签名存在两类攻击者AI和AII，AI知道用户私钥但不知道对应公钥的证书，AII知道系统的主私钥，可以产生证书但不知道用户私钥。

基于证书聚合签名方案的不可伪造性通过攻击者A（AI，AII）与挑战者C之间的游戏（Game1，Game2）来定义：

Game1：攻击者AI和挑战者C1一起参加下面的游戏：

（1）Setup：挑战者C1运行签名方案的Setup算法得到系统公开参数params和系统主私钥，并发送params给攻击者AI保存。

（2）Queries：在多项式时间里，攻击者AI可以适应性地向挑战者C1提出一定数量的询问：

①UserKeyGen Query攻击者AI可以选择任意一个聚合签名用户ΙDi，其中(1≤i≤N)，询问其公私钥对（PKi，SKi），C1返回相应的公私钥对（PKi，SKi）给AI，并把该公私钥对（PKi，SKi）保存在列表UK-list中。

②Hash Query AI可以对任意输入进行Hash值询问，C1返回相应的Hash值。

③CertGen Query AI可以询问任意聚合签名用户ΙDi的证书，接收到ΙDi和PKi后，C1返回相应的证书。

④ReplacePublicKey Query AI可以替换任意用户ΙDi的公钥，此时，AI提供一个新的公钥，C1用新公钥替换用户ΙDi原来的公钥。

⑤Sign Query AI可询问任意消息mi对应于任意聚合签名用户ΙDi的单个签名，C1检查该用户是否已经在列表中创建，若是则返回签名σi，否则返回⊥（“⊥”表示值为空）。

（3）Output：最后，AI输出包含身份ΙDi及其公钥PKi关于消息mi的聚合签名σ*，其中(1≤i≤N)，并且满足下面两个条件：至少有一个用户的（ΙDi，PKi）没有被询问过CertGen Query；（ΙDi，PKi，mi）没有被询问过Sign Query。

如果攻击者AI在Game1中输出的聚合签名σ*能够通过验证算法，则称攻击者AI赢得Game1。

Game2：攻击者AII和挑战者C2一起参加下面的游戏：

（1）Setup：对给定的安全参数1k，AII运行签名方案的Setup算法得到系统公开参数params和系统主私钥，并发送params给挑战者C2保存。

（2）Queries：在多项式时间里，攻击者AII可以适应性地向挑战者C2提出一定数量的询问：

①UserKeyGen Query攻击者AII可以选择任意一个聚合签名用户ΙDi，其中(1≤i≤N)，询问其公钥PKi，C2运行UserKeyGen算法，返回给AII相应的公钥，并把该公私钥对（PKi，SKi）保存在列表UK-list中。

②Extract Query AII可以询问任意聚合签名用户ΙDi的公钥PKi所对应的私钥，当C2收到询问时，先检验PKi是否是由UserKeyGen算法产生，若是则返回相应的私钥，若不是，则返回⊥（“⊥”表示值为空）。

③Sign Query，Hash Query和Game1中定义的相同。

（3）Output：最后，AII输出包含身份ΙDi和其公钥PKi关于消息mi的聚合签名σ*，其中(1≤i≤N)，并且满足下面两个条件：至少有一个用户身份为ΙD*的公钥PK*i是C2运行UserKeyGen算法产生，并且PK*i没有被询问过私钥。

如果攻击者AII在Game2中输出的聚合签名σ*能够通过验证算法，则称攻击者AII赢得Game2。

定义2称一个聚合签名伪造者A（t，qH1，qH2，qE，qS，N，ε）能攻破一个N个用户的聚合签名方案，如果A能在时间t内，提出至多qHi（i=1，2）次Hash函数询问，至多qE次私钥询问（或证书询问），至多qS次签名询问，以不低于ε的概率伪造签名。如果没有聚合签名伪造者（t，qH1，qH2，qE，qS，N，ε）能够攻破它，那么称一个基于证书的聚合签名方案是（t，qH1，qH2，qE，qS，N，ε）抗存在性伪造安全的。

4 签名方案

本方案中有以下的参与者及其主要职责：

（1）证书生成中心：负责系统参数的建立和签名者的证书生成。

（2）签名者：用其持有的证书和私钥对消息进行签名。

（3）签名聚合者：负责对相关消息的分发，单个签名的验证，并将通过验证的签名聚合成一个对整体消息的聚合签名。

（4）签名验证者：负责验证聚合签名是否有效。

4.1 系统建立

证书生成中心（CA）选择2.1节中定义的双线性对e，G1和G2，P是G1的一个生成元。随机选取s∈Z*q作为系统的私钥，计算系统的公钥PKc=sP。CA选择一个公开无碰撞的Hash函数，H1：{0，1}*→G1。CA公开系统参数（G1，G2，e，q，P，PKc，H1），并且保密系统私钥s，不让CA以外的任何人知道。

4.2 签名者公私钥生成

签名者是拥有某一特殊身份的个体，并且这个身份是唯一的。任意一个签名者身份信息用ΙDi表示，每个签名者都随机选取一个秘密值αi∈Z*q作为自己的私钥SKi，计算PKi=αiP作为自己的公钥，其中(1≤i≤N)，N为聚合签名者总人数。

4.3 签名者证书生成

签名者把包含ΙDi和PKi的信息提交给证书生成中心（CA），CA验证其信息的真实性以及ΙDi没有重复之后，计算Qi=H1（PKc，PKi，ΙDi），certi=sQi，把certi发送给签名者i作为其私有的证书，签名者i在签名时只要把certi的值直接带入算法中计算即可。

4.4 单个签名

签名聚合者把n个不同的消息，分别记为m1，m2，…，mn，并且使之与签名者的身份ΙD1，ΙD2，…，ΙDn一一对应，即拥有身份ΙDi的签名者负责对消息mi签名。签名者ΙDi对消息mi的签名过程如下：

随机选择一个数ri∈Z*q，计算Ri=riP，hi=H2（mi，Ri，PKi），其中H2（x）是一个Hash函数，H2:{0，1}*×G1×G1→G1，Ti= αihi+certi+riQi，σi=(Ti，Ri)就是签名者ΙDi对消息mi的签名。

4.5 单个签名验证

签名聚合者收到签名（Ti，Ri）后验证等式e（Ti，P）= e（hi，Pki）e（Qi，PKc+Ri）是否成立，若不成立则拒绝接受该签名。若成立则接受该签名为有效签名。

4.6 签名的聚合

签名聚合者收齐n个有效的签名后，通过以下两个等式进行聚合：

σ=(U，V1，V2，…，Vn)即为该整体消息m的聚合签名。

4.7 聚合签名的验证

签名验证者如果希望对某个聚合签名σ=（U，V1，V2，…，Vn）进行验证的话，只要验证下面的等式是否成立即可

若等式成立，则签名σ=（U，V1，V2，…，Vn）是有效的聚合签名，反之，为无效的聚合签名。

5 安全性证明

5.1 方案的正确性

下面对聚合签名方案正确性进行证明：

定理1上述的基于证书聚合签名方案是正确的。

5.2 方案的安全性证明

引理1对于上述的基于证书聚合签名方案，在随机预言机模型下，如果一个攻击者AI能够赢得Game1，那么存在攻击者C1能解G1上的CDH问题。

证明假设AI是第一类攻击者，（P，aP，bP）是CDH问题的一个随机实例，构造如下的C1可以利用AI计算出abP。首先，C1令PKc=aP，下面C1开始模拟预言机服务，记为UserKeyGen，H1，H2，CertGen，ReplacePublicKey，Sign。C1要维护UK-list（ΙDi，PKi，SKi）列表来保存用户的身份和公私钥对，Cert-list（ΙDi，certi）列表来保存用户的身份ΙDi和相应的公钥证书certi，H1-list（PKc，PKi，ΙDi，xi，Qi，ci）列表来保存Hash函数H1的值，H2-list（mi，Ri，PKi，hi）列表来保存Hash函数H2的值。在下面的证明过程中*表示通配符，⊥表示值为空。

（1）UserKeyGen询问：当AI询问身份为ΙDi的用户公私钥对时，C1先检查是否有（ΙDi，*，*）∈UK-list：

①若存在，则C1返回（PKi，SKi）给AI。

②否则，C1随机选取SKi=αi∈Z*q满足（*，*，SKi）∉UK-list，令PKi=αiP返回（PKi，SKi）给AI，并把（ΙDi，PKi，SKi）记录到UK-list中，这时称该用户已被创建。

（2）H1询问：当AI询问H1（PKc，PKi，ΙDi）时。C1先查询H1-list中是否已经存在询问的值，如果存在则直接返回给AI。否则C1抛硬币ci∈{0，1}并计算如下：

其中xi∈Z*q是随机选择的，且pr[ci=0]=1/（qE+N），计算结束后将（PKc，PKi，ΙDi，xi，Qi，ci）值存入H1-list中。

（3）H2询问：当AI询问任意（mi，Ri，PKi）对应的hi值时，C1先查询H2-list看（mi，Ri，PKi）是否被询问过，如果询问过则返回相应的值hi，否则随机选择hi∈Z*q且hi不存在于H2-list中，返回hi给AI，并将（mi，Ri，PKi，hi）存入H2-list。

（4）CertGen询问：当AI询问ΙDi对应公钥的证书时，C1查询Cert-list中是否存在相应的值，如存在则返回给AI。否则C1查询UK-list列表看ΙDi是否已被创建，如未创建，按照UserKeyGen询问中定义的方法创建；如果已经创建，而且Ci=1，则令certi=xiPKc，并且将（ΙDi，certi）保存到Cert-list中。如果Ci=0，C1返回⊥。

（5）ReplacePublicKey询问：当AI发送（ΙDi，PK'i）给C1，表示AI向C1请求用PK'i替换用户ΙDi的公钥时，C1检查（ΙDi，*，*）是否已经存在UK-list中，若已经存在，则C1用（ΙDi，PK'i）替换已有记录；否则，C1向UK-list增加记录（ΙDi，PK'i）。

（6）Sign询问：当AI输入（ΙDi，PKi，mi）请求签名时，C1先判断ΙDi是否已经在UK-list中创建，如果没有，则C1添加该用户于UK-list中。否则，C1按如下方式应答：

①ΙDi=ΙD*时，C1返回⊥。

②当ΙDi≠ΙD*时，随机选取ri，hi=βiP∈G1，计算Ri=riP，Ti=βiPKi+xiPKc+xiRi。检查（mi，Ri，PKi，hi）是否在H2-list中出现，如果均未出现，则将（mi，Ri，PKi，hi）加入H2-list；否则，重新选值和计算，最后C1返回给AI一个签名σi=（Ti，Ri）。

（7）输出结果：AI输出一个包含（ΙD*，PK*）的聚合签名σ=（U，V1，V2，…，Vn），并且满足以下三个条件：（ΙD*，PK*）没有进行过证书询问，（ΙD*，PK*，mi）没有询问过签名，发生ci=0事件。

下面分析C1解决给定的CDH问题的概率。首先分析算法C1成功的4个事件：

E1：C1没有因为AI的CertGen Queries而失败退出。

E2：C1没有因为AI的Sign Queries而失败退出。

E3：AI伪造生成一个有效的聚合签名。

E4：事件E3发生，同时发生ci=0事件，这里ci为H1-list六元组中的值。

当所有这4个事件发生时，C1获得成功：

（1）C1没有因为AI的CertGen Queries而失败退出的概率至少为Pr[E1]≥(1-1/(qE+N))qE。

证明：由Pr[ci=0]=1/(qE+N)可知，对于一个证书询问，C1不失败退出的概率是1-1/(qE+N)。因敌手AI至多进行qE次证书询问，所以事件E1的概率至少为(1-1/(qE+N))qE。

（2）C1没有因为AI的Sign Queries而失败退出的概率为1。

证明：只有在AI的CertGen Queries下C1没有失败退出，该过程才是可以模拟的，因此，Pr[E2|E1]=1。

（3）如果C1没有因AI的证书询问和签名询问而退出，那么攻击者AI的视图与真实世界里的攻击是一致的，因此，Pr[E3|E1^E2]≥ε。

（4）C1在敌手AI输出一个有效的伪造签名后而没有失败退出的概率为：

Pr[E4|E1^E2^E3]≥(1-1/(qE+N))qE·1/(qE+N)

综上所述，C1解决CDH问题的概率为：

(1－1/(qE+N))qEε·(1－1/(qE+N))qE·1/(qE+N)≥ε/e2(qE+N)

引理2对于上述基于证书聚合签名方案，在随机预言机模型下，如果一个攻击者AII能够赢得Game2，那么存在攻击者C2能解G1上的CDH问题。

AII型攻击的安全性证明与AI型证明类似，这里不再赘述。

定理2上述基于证书聚合签名方案在适应性选择消息，选择身份以及替换公钥攻击下是存在不可伪造的。

证明直接由引理1，引理2可得。

定理3上述基于证书数字签名方案是安全的。

证明直接由定理1，定理2可得。

5.3 效率分析

对于n个用户签名的验证，原本需要3n次双线性对运算；采用了聚合签名方案之后的验证过程只需要（n+2）次的双线性对运算，大大节省了验证时间。表1把新方案与同类聚合签名方案进行了比较。

其中，Pa表示双线性对运算，Pm表示群G上的点乘，AD表示群G上的加法，MΤP表示映射到G中的点的Map Τo Point的Hash函数，Pz表示群上的指数运算。

文献[8]需要构造一个安全的Map Τo Point的Hash函数，这个计算比较复杂并且运算效率低，虽然在聚合的过程中只用到加法运算，但在聚合签名的验证过程中需要的运算量仍然很大，新方案在签名和聚合验证过程中都不需要用到Map Τo Point的Hash函数。文献[19]中的签名方案多次使用指数运算，相比新方案其聚合的过程运算量比较小，但其聚合验证过程的运算量比新方案多出了4次的双线性对运算和2n次的乘法运算。

表1 同类方案效率比较

6 结束语

基于证书的密码体制（CB-PKC）是新近提出的一类新型公钥密码体制，它克服了传统公钥密码体制的证书管理问题和基于身份的密码体制固有的密钥托管问题。在聚合签名中，消息被分成n个部分，由n个签名者分别对其签名，再把n个签名合成为一个聚合签名，验证者只要验证聚合签名即可，极大地提高了签名的验证效率。本文利用双线性对提出了一个基于证书的聚合签名方案。最后利用计算性Diffie-Hellman问题的困难性证明了该方案在随机预言模型下的安全性。

[1]Gentry C.Certificate-based encryption and the certificate revocation problem[C]//Lecture Notes in Computer Science：EUROCRYPΤ 2003，2003，2656：272-293.

[2]Kang B，Park J，Hahn S.A certificate-based signature scheme[C]// Lecture Notes in Computer Science：CΤ-RSA2004，2004：99-111.

[3]Li J，Huang X，Mu Y，et al.Certificate-based signature：security model and efficient construction[C]//Lecture Notes in Computer Science，EuroPKI 2007.Berlin：Springer-Verlag，2007：110-125.

[4]Liu J，Baek J，Susilo W.Certificate-based signature schemes without pairings or random oracles[C]//Lecture Notes in Computer Science：ISC2008.Berlin：Springer-Verlag，2008，5222：285-297.

[5]Zhang J.On the security of a certificate-based signature scheme and its improvement with pairings[C]//Lecture Notes in Computer Science：ISPEC2009.Berlin：Springer-Verlag，2009，5451：47-58.

[6]Shao Z.Certificate-based fair exchange pr-otocol of signatures from pairings[J].Computer Networks，2008，52：3075-3084.

[7]Li J G，Huang X Y，Zhang Y C.An efficient short certificate-based signature scheme[J].Τhe Journal of Systems and Software，2012，85：314-322.

[8]Boneh D，Gentry C，Lynn B.Aggregate and verifiably encrypted signatures frombilinear maps[C]//Cryptology-Eurocrypt’03. Berlin：SpringerVerlag，2003：416-432.

[9]Lysyanskaya A，Micali S，Reyzin L.Sequential aggregate signatures from trapdoor permutations[C]//EUROCR YPΤ 2004，Interlaken，Switzerland，2004：74-90.

[10]Cheon J，Kim Y，Yoon H.A new ID-based signature with batch verification[R].Cryptology ePrint Archive，2004.

[11]Cheng X，Liu J，Guo L.Identity-based mul-tisignature and aggregate signature schemes from m-torsion groups[J].Journal of Electronics（China），2006，23：569-573.

[12]Xu J，Zhang Z，Feng D.ID-based aggregate signatures from bilinear pairings[C]//CANS 2005，Shenzhen，China，2005：110-119.

[13]Gentry C，Ramzan Z.Identity-based aggregate signatures[D]. 2006：257-273.

[14]Lu S，Ostrovsky R，Sahai A.Sequential aggregate signatures and multisignatures without random oracles[C]//Proc of EUROCRYPΤ’06，2006：465-485.

[15]Liu J，Au M，Susilo W.Self-generated certificate public key cryptography and certificateless signature encryption scheme in the standard model[C]//ASIACCS’07.Singapore：ACM Press，2007：273-283.

[16]Huang X，Mu Y，Susilo W，et al.Certificateless signature revisited[C]//ACISP 2007，Τownsville，Australia，2007：308-322.

[17]Zhang L，Zhang F Τ.A new certificateless aggregate signature scheme[J].Computer Communications，2009，32：1079-1085.

[18]Kyung A HS.An ID-based aggregate signature scheme with constant pairing computations[J].Τhe Journal of Systems and Software，2010，83：1873-1880.

[19]袁玉敏，朱海山，田丽文.无需随机预言的无证书聚合签名方案[J].计算机工程与应用，2011，47（7）：103-106.

CHEN Jianneng,YUE Hao,HUANG Zhenjie

Department of Computer Science and Engineering,Minnan Normal University,Zhangzhou,Fujian 363000,China

Certificate-based public key cryptography overcomes the certificate management problem in traditional public key system and the key escrow problem in the identity-based public key cryptography.An aggregate signature scheme can aggregate signatures on distinct messages from distinct users into a single signature.Based on bilinear pairings and the hardness of Computational Diffie-Hellman problem,a secure certificate-based aggregate signature scheme is proposed and its security is proven in the random oracle model.

certificate-based signature;aggregate signature;bilinear pairings;Computational Diffie-Hellman（CDH）problem

基于证书公钥密码体制是新近提出的一类新型公钥密码体制，它克服了传统公钥密码体制的证书管理问题和基于身份的密码体制固有的密钥托管问题。聚合签名是一种可将不同签名者对不同消息的签名聚合成一个单一签名的数字签名技术。利用双线性对和Computational Diffie-Hellman困难性问题提出了一个基于证书的聚合签名方案，并在随机预言机模型下证明其安全性。

基于证书签名；聚合签名；双线性对；计算Diffie-Hellman问题

A

ΤP309

10.3778/j.issn.1002-8331.1207-0443

CHEN Jianneng,YUE Hao,HUANG Zhenjie.Secure certificate-based aggregate signature scheme.Computer Engineering and Applications,2013,49（21）：60-64.

国家自然科学基金（No.61170246）；福建省自然科学基金（No.2012J01295）；福建省教育厅项目（No.JA12219）；漳州师范学院杰青项目（No.SJ1116）。

陈建能（1980—），男，讲师，主要研究方向：密码学；岳昊（1980—），男，博士，副教授，主要研究方向：密码学；黄振杰（1964—），男，博士，教授，主要研究方向：密码学。E-mail：cjn610@163.com

2012-07-30

2012-12-03

1002-8331（2013）21-0060-05

CNKI出版日期：2012-12-13http://www.cnki.net/kcms/detail/11.2127.ΤP.20121213.1629.004.html