DOI: 10.11817/j.issn.1672-7207.2015.12.021

基于双线性对的聚合代理签名

喻琇瑛，何大可

(西南交通大学 信息科学与技术学院，四川 成都，610031)

摘要：结合聚合签名和代理签名的特点，基于证书签名思想，提出基于证书的聚合代理签名定义和安全模型，在双线性对下，构造一个新的基于证书聚合代理签名方案。在计算Diffie-Hellman困难问题(CDH)假设和随机预言机模型下，对方案的安全性和效率进行分析。研究结果表明：与n个独立代理签名相比，本文方案有效压缩了签名长度，提高了签名和验证效率。

关键词：基于证书的签名；聚合代理签名；CDH问题；双线性对

中图分类号：TP309             文献标志码：A         文章编号：1672-7207(2015)12-4535-07

A certificate-based aggregate proxy signature scheme

YU Xiuying, HE Dake

(School of Information Science and Technology, South West Jiao Tong University, Chengdu 610031, China)

Abstract: The definition of certificate-based aggregate proxy signature was introduced based on Boneh’s aggregate signature model and Mambo’s proxy signature model, the security model for such signatures was presented and a certificate-based aggregate proxy signature scheme from bilinear pairing was constructed. The security and the efficiency of scheme were analyzed. The results show that the scheme is existentially unforgeable against adaptively chosen message attacks from two types of adversaries in random oracle model. In terms of computation, it is also useful for reducing the size of certificate chains and thus it has higher efficiency in signature and verification algorithm than n proxy signatures.

Key words: certificate-based signature; aggregate proxy signature; computational Diffie-Hellman problem; bilinear pairing

2003年的欧密会上，Gentry^[1]提出了基于证书的密码体制，证书由权威认证机构CA颁发，只作为用户公钥的真实性以及与身份唯一对应关系的证明，无须保密，而私钥由用户自行生成；用户采用证书和私钥进行消息加密或者签名。与无证书公钥密码体制相比，该体制避免了无证书和基于身份公钥密码体制存在的容易遭受公钥替换攻击问题或密钥传递需要安全信道的问题。近年来，若干基于证书公钥密码体制下的研究和签名方案相继被提出^[2-3]。在实际应用中，常常面临同时对多个消息进行签名和验证问题。为了实现n(n＞1)个用户对于n个不同消息的签名以及多个签名验证过程的简化， Boneh等^[4]提出了聚合签名的概念，使得多个用户的签名可以聚合为1个签名后一次性通过验证。基于聚合签名的压缩性、简捷性等特殊性质和广阔的应用前景，许多学者相继提出了相关的研究成果^[5-10]。1996 年，Mambo 等^[11]提出代理签名的概念。原始签名者(delegator)可以授权自己的签名权限给1个或者多个代理者(proxy signer)，这一技术可以广泛应用于电子现金系统的构造。在电子商务应用中，常常要求在短时间内对多个签名进行验证。假设1个用户同时拥有n个银行账号，某次交易需要将多笔电子现金累加进行电子产品的支付，这就需要用户分别到n个银行取款，完成支付后商家再分别到n个银行进行验证，浪费大量时间和存储空间。为提高交易的效率，对于取款和支付环节，可以利用基于代理签名的多银行电子现金系统，而在验证环节，聚合签名的引入则可以提高有效效率。将聚合签名与代理签名结合，能够使由多个用户生成的代理签名通过聚合得到1个签名，用户只需要对生成的聚合代理签名进行验证，因此 在签名和验证环节的效率都显著高于n个独立的代理签名，从而有效利用聚合签名和代理签名两者的特点。针对此类电子商务领域的具体需求，结合代理签名和聚合签名特性，Li等^[12]提出聚合代理签名概念，对n个不同消息，n个代理签名者能代表同一原始签名人生成相应代理签名，由任意聚合签名者将其聚合为1个代理签名，只需要对聚合的代理签名进行验证。如王勇兵等^[13]构造了1个基于身份的代理聚合签名，但陈群山等^[14]指出该方案不具有代理签名者的不可否认性，且无法抵抗身份替换攻击。孙华等^[15]提出了1个可证安全的基于身份的代理聚合签名方案，若干不同的代理聚合签名方案相继被提出，经过分析，目前现有方案都基于聚合代理签名定义，仅实现n个代理签名者对于1个原始签名人的签名代理和聚合。在此基础上，本文作者提出了针对多个原始签名人的聚合代理签名，n个代理签名者可以代表n个不同的原始签名人，实现对于n个不同消息的代理签名生成以及签名的聚合。结合基于证书公钥密码体制，利用双线性对构造1个基于证书的聚合代理签名，并对其一般模型和安全性进行研究和分析。

1  基于证书聚合代理签名模型

1.1  基于证书聚合代理签名一般模型

在基于证书的聚合代理签名方案中，参与者分别为认证中心CA、原始签名人、代理签名人、签名聚合者和签名验证者。其一般模型包含如下7个算法  阶段：

1) Setup(系统参数设置)。该算法由CA执行。CA输入安全参数k，输出系统参数和主密钥。CA公开系统参数，保密系统主密钥。

2) UserKeyGen(用户密钥生成算法)。输入用户ID_i相关参数、身份标识ID_i和自己选定的秘密值x_i，输出其秘密值/公钥对。

3) CertGen (证书生成)。该算法由CA执行。输入系统公开参数params、系统主密钥masterkey，用户ID_i和用户公钥，输出用户的证书。

4) Proxy-Key-Extract(代理密钥生成算法)。输入用户公钥p_i以及相关参数，输出1个代理密钥(或)。

5) CBP-Sign(基于证书代理签名算法)。输入用户相关参数，输出签名。

6) Aggregate(签名聚合算法)。输入n个有效的身份-公钥-消息-签名对(1≤i≤n)，输出对n个的聚合签名σ。

7) Verify(签名验证算法)。输入相关参数、n个有效的身份-公钥-消息-签名对(1≤i≤n)以及聚合签名σ，签名有效则输出为“1”，签名无效则输出为“0”。

1.2  基于证书聚合代理签名安全模型

Boldyreva等^[16]对代理签名安全模型相关工作进行了总结与分析，结合相关模型，本文给出基于证书聚合代理签名安全模型，描述如下2类攻击者。

第1类攻击者A_I不知道系统主密钥，但可以对用户公钥进行任意替换，同时能得到除目标签名者以外的用户的证书以及替换公钥后的证书，一般为外部攻击者；在聚合代理签名中，这类攻击者分2种情况。情况1)，在没有获得用户u*授权下，攻击者A_I作为代理签名人伪造1个假装u*授权的代理签名；情况2)，攻击者A_I伪造1个被敌手控制的用户(bad user)授权给用户u*的代理签名。

第2类攻击者A_II通常代表恶意的证书发放机构，这类攻击者拥有系统主密钥，可以生成任意用户的证书，但不能对用户公钥进行替换。

下面通过2个敌手与挑战者间的安全游戏来描述基于证书的聚合签名安全模型。游戏开始前，由挑战者C完成初始化：输入安全参数k，运行系统生成算法，得到系统主密钥s和系统参数。

游戏1  (第1类攻击者A_I)：

挑战者C保密s，并将参数发送给攻击者A_I。

攻击：攻击者可以适应性地进行询问，包括以下询问。

1) Hash 询问：攻击者A_I可以对任何Hash预言机进行Hash值询问。

2) Private-Key询问：A_I输入用户身份信息ID_i，C运行秘密值生成算法，得到ID_i的公私钥对并返回x_i给A_I。

3) Public-Key 询问：A_I输入ID_i，C运行公钥生成算法，计算得到ID_i的公钥并返回给A_I。若ID_i公钥已替换，则终止询问。

4) CerGen询问：A_I输入ID_i和P_i，C运行证书生成算法，计算得到ID_i的证书并返回给A_I。

5) Replace-Public-Key询问：A_I可以用自选的任意值替换用户ID_i的公钥，而无须提供对应的x_i。

6) CBP-Sign询问：A_I输入用户身份ID_i，对应公钥P_i、消息m_i，C运行代理签名算法，计算得到签名并返回给A_I。

签名伪造：A_I输出1个包含n个身份、公钥、消息的三元组(1≤i≤n)的有效聚合代理签名，若至少存在1个用户，A_I没有对其进行私钥询问，也没有询问过身份为、公钥为的用户对消息m_i的签名，并且输出签名使得验证式Verify[]=1成立，则A_I赢得游戏。

游戏2  (第2类攻击者A_II)：

挑战者C将参数和主密钥s发送给攻击者A_II。

攻击：攻击者A_II可以适应性地对预言机进行前面游戏1中所列举的Hash询问、Private-Key询问、Public-Key 询问以及CBP-Sign询问，预言机的应答与游戏1中的相同。

签名伪造：攻击者A_II输出1个包含n个身份、公钥、消息三元组(1≤i≤n)的有效聚合代理签名。如果至少存在1个用户和A_II没有对其进行私钥询问以及其对消息m_i的签名；且输出的签名使得验证式Verify[]=1成立，则A_II赢得游戏。

定义1  对于所有多项式时间攻击者，如果其赢得游戏1和游戏2的概率可以忽略，那么该聚合代理签名方案在适应性选择消息攻击下是存在不可伪造的；即对所有多项式时间攻击者而言，在若干次询问后攻击者的优势是关于参数1^k可以忽略的。

2  双线性对下基于证书的聚合代理签名

根据聚合代理签名的一般模型，在双线性对下构造了1个基于证书的聚合代理签名，方案包含9个算法步骤，具体描述如下。

1) 系统建立。由认证中心CA执行并生成以下参数：

① 2个群G₁和G₂，其中大素数q为群的阶，P为G₁生成元，1个Weil对映射；

②  作为系统主密钥，令系统公钥P₀=sP；

③ ，H₃：{0,1}^*为3个安全Hash函数。

公开系统参数。

2) 用户密钥生成。用户ID_i选择随机数，计算作为公钥，密钥对为。

3) 证书生成。CA按照以下步骤生成用户证书：

① 用户ID_i发送包含其身份信息和公钥的数据data={}给CA；

② CA对用户信息有效性和重复性进行验证，如果公钥P_i有效，则CA计算，，发送给用户ID_i作为其证书。

4) 部分代理私钥生成。原始签名人生成委托证书m_w，并执行以下步骤为代理签名人B_i生成部分代理私钥：

① 计算

② 计算部分代理私钥

③ 发送给B_i。

5) 部分代理私钥验证。B_i验证以下等式：

若等式成立，接受，否则拒绝。

6) 设置代理私钥。代理签名人B_i设置其代理私钥为：

7) 代理签名。代理签名者，用其公私钥对。对消息进行签名步骤如下。

① 计算，，。

② 选择 ，B_i计算 ，。

③ 户对于消息m_i的签名即为。

8) 签名聚合。收到n个用户发送来的签名对(1≤i≤n)后，任意聚合人进行以下计算：

， ， 。验证以下等式：

若等式成立，则接受为合法签名。若n个签名全部有效，则聚合者计算，，就是n个身份公钥对为  的签名者对于n个消息m_i的聚合代理签名。

9) 聚合签名验证。任何人可以作为验证者对签名进行验证。对于给定的 (1≤i≤n)，及聚合签名，验证人执行以下操作：

① 计算，，(1≤i≤n)，  ，。

② 接受签名 当且仅当等式成立。

3  签名方案分析

3.1  正确性分析

对新方案中使用的2个验证式进行推导分析。

1) 代理签名者收到原始签名者发出的代理签名授权信息后，需要对授权信息进行验证，其验证式的正确性推导如下：

2) 当签名接收者收到代理者对消息m 的聚合代理签名，需要进行验证，其验证式的正确性推导结果为

通过以上推导结果，本方案正确性得证。

3.2  方案的安全性分析

在本文所提出的安全模型下，通过两类攻击者启动算法C_I和C_II所进行的挑战者的模拟，通过2个定理的证明对所提出的新方案进行安全性证明，并将方案的安全性规约到CDH困难问题。

CDH问题(computational diffie-hellman problem问题)：给定aP，bP(是未知的随机数)，计算abP。

定理1  基于随机预言机模型和CDH困难假设，本文方案在第1类攻击者A_I的适应性选择消息攻击下，针对情况1)和情况2)，都是存在不可伪造的。设q_H，q_X，q_P和q_S分别代表A_I访问随机预言机CerGen，Public-Key，Reveal-Private-Key， CBP-Sign的次数，若攻击者A_I能够在时间t之内，以不可忽略的概率ε成功伪造签名，则存在一个算法多项式C_I，在时间t′≤内解决CDH困难问题，其概率ε′≥ε (其中，t₁为标量乘的运算时间)。 即若CDH假设成立，则本文方案在第1类攻击下是安全的。

证明  C运行系统建立算法并获得系统参数，设系统公钥为。C初始化L_H1，L_H2和L_H3(分别对应hash询问H₁，H₂，H₃)，L_C，L_pk等列表为空，并负责列表的维护和更新。A_I 执行询问并获得相应的应答如下。

1) H₁询问。当A_I输入的用户，C查找L_H1，进行以下操作：

若记录存在，则将返回给A_I；若记录  不存在，任选，计算 记录到L_H1，返回给A_I。

当A_I输入用户，C查询L_H1时，进行以下操作：

若记录 存在，则将返回给A_I；若记录 不存在，则任选，掷硬币得到；若c=0，则计算，记录到L_H1，否则，计算并返回给A_I，记录到表L_H1。

2) H₂询问。A_I输入P₀，C查找列表L_H2，若记录存在，则输出W和T，否则选择任意 ，令W=dP，T=kP，。添加记录到L_H2，并返回W，T和U′给A_I。

3) H₃询问。对A_I给定的， C查找L_H3，若存在记录，则返回h_i给A_I，否则，任选，返回h_i，并将记录 到添加列表L_H3。

4) Reveal-CerGen询问。对于给定ID_i，C查找列表L_D, 若找到记录，则返回给A_I，否则，计算并返回，添加记录到列表L_C。

5) Public-Key询问。对于给定ID_i，C查找列表L_pk，若存在记录，则返回，否则，任选，计算返回给A_I，添加记录 到表L_pk中。

6) Replace-Public-Key询问。对于给定ID_i，允许A_I自己选取的公钥代替，A_I将发送给C，C 令 ，=，并添加到L_pk列表中。

7) CBP-Sign询问。A_I输入， C在各相应列表中查找记录，若c=0，则在列表中获取相关参数，计算得到，任选，并将签名对返回给A_I，否则拒绝。

最后，A_I停止模拟，输出1个有效的聚合代理签名(U*,V*)。挑战者C查找相关记录(1≤i≤n)，若所有c均为0，则失败退出，否则，只要有1个c=1，假设其对应，则可以在列表中找出其对应的参数，得到等式如下：

因此C可计算得到

C求解CDH问题的概率如下，定义3个事件分别如下。

E₁：C成功回应A_I的Reveal-Partial-Private-Key询问和CLAS-Sign询问，没有返回失败；

E₂：A_I成功伪造了包含有的聚合签名；

E₃：在n条记录中，至少存在1条记录中的c=1。

则挑战者C能够以如下概率求解CDH问题：

1) 分解 为 ；

2) 由≥ ，≥，≥得到：

≥

在事件E₁，E₂，E₃全部发生的前提下，C成功解决CDH问题从而获胜的概率为

≥

由上述推导可知：若方案中签名可伪造，则存在算法C_I可以在时间t′内以概率ε′解决CDH问题，而  这与CDH困难问题假设矛盾。因此，本签名方案在CDH假设成立的前提下是安全的。

定理2  基于随机预言机模型和CDH困难假设，本文方案在第2类攻击者A_II的攻击下存在不可伪造。

设q_P，q_X，q_S分别表示A_II访问随机预言机Public-Key，Reveal-Secret-Value，CBP-Sign的次数，若攻击者A_II能够在时间t之内，以不可忽略的概率e成功伪造签名，则存在1个算法多项式C_II，在时间t′≥内解决CDH问题，其概率≥(t₁的定义同定理1)。即，如果CDH假设成立，那么本文方案在第2类攻击下是安全的。

CDH问题实例：给定(其中，未知)，计算 。

证明  C运行系统建立算法并获得系统参数，设系统公钥为，已知s，C初始化L_H1，L_H2，L_H3，L_pk等列表为空，并负责列表的维护和更新。A_II执行询问并获得相应的应答如下。

1) H₁询问：输入用户ID_i，C在L_H1中查找记录  ，若存在，则返回Q_i给A_II；否则掷硬币得到，任选，计算 ，记录到L_H1，返回Q_i给A_II。

2) H₂询问：对A_II给定的，C查询列表L_H2，若记录存在，则输出W，否则随机选择 ，令T=kP，，W=aP。返回W，T和U′给A_II，将添加到L_H2。

3) H₃询问：同定理1。

4) Public-Key询问：A_II输入ID_i，C查询列表L_pk，若记录存在，则返回 给A_II；否则选择任意，计算，返回 给A_II，并将记录到表L_pk中。

5) Reveal-Secret-Value询问：对于给定ID_i，C查找列表L_H1，找到记录，如果c=1则拒绝。若c=0，则在列表L_pk中查找记录，若存在则返回x_i，否则，任意选，计算，返回x_i，将记录添加到表L_pk中。

6) CBP-Sign 询问：A_II输入 询问签名， C在各相应列表中查找记录，若c=0，则计算得到 ，任选，并将签名对返回给A_II，否则拒绝。

最后，A_II停止模拟，输出1个有效聚合代理签名(U*,V*)。攻击者C查找相关记录(1≤i≤n)，若所有c均为0，则失败退出，否则，只要有1个c=1，假设其对应，则可以在列表中找出其对应的参数，得到等式如下：

。

因此，

在事件E₁，E₂和E₃全部发生的前提下，C求出，解决了CDH困难问题从而获胜的概率为

≤

由上述推导可知：若本方案中签名可伪造，则存在算法C_II可以在时间t′内以概率ε′解决CDH问题，而这与CDH困难问题假设矛盾。因此，本签名方案在CDH假设成立的前提下是安全的。

综上，若A_I或A_II可以成功伪造签名，则挑战者可以利用其攻击能力解决CDH困难问题。本方案安全性得证。

3.3  方案的效率分析

由于聚合代理签名实现了对n个代理签名的聚合，验证时只需要对1个聚合签名进行验证，由等式可知：方案中，聚合者只需要计算和 ，便可以得到聚合签名，签名的压缩率为1/n，相比较n个独立代理签名的分别验证，聚合代理签名在计算效率上有显著提高。而在本文所提出的新方案中，签名验证仅需要5个双线性对运算，具有较高的计算效率。目前，还没有基于证书的聚合代理签名方案被提出，而对比其他现有聚合代理签名方案，本方案实现了对不同原始签名人代理签名的生成和聚合，在实际应用中更具优势。

4  结论

1) 基于Boneh的聚合签名模型和现有聚合代理签名的概念，利用双线性对构造了1个基于证书的聚合代理签名。

2) 对基于证书聚合代理签名的安全模型进行了定义，证明方案在自适应选择消息攻击下存在不可伪造，其安全性可归约于CDH 问题。由于聚合代理签名的特殊性质，其在电子商务等领域具有广泛的应用前景，构造效率更高的聚合代理签名以及标准模型下的聚合代理签名将有待下一步研究。

参考文献 ：

[1] Gentry C. Certificate-based encryption and the certificate revocation problem[C]//Proceedings of the Eurocrypt 2003. Warsaw, Poland, 2003: 272-293.

[2] 周萍, 何大可, 张文芳. 具有强安全性不含双线性对的基于证书盲签名[J]. 四川大学学报, 2013, 45(4): 111-116.

ZHOU Ping, HE Dake, ZHANG Wenfang. Strongly secure certificate-based blind signature scheme without pairings[J]. Journal of Sichuan University, 2013, 45(4): 111-116.

[3] 李继国, 钱娜, 黄欣沂, 等. 基于证书强指定验证者签名方案[J]. 计算机学报, 2012, 35(8): 1579-1587.

LI Jiguo, QIAN Na, HUANG Xinyi, et al. Certificate-based strong designated verifier signature scheme[J]. Chinese Journal of Computers, 2012, 35(8): 1579-1587.

[4] Boneh D, Gentry C, Lynn B, et al. Aggregate and verifiably encrypted signatures from bilinear maps[C]//Proceedings of Cryptology-Eurocrypt 2003. Berlin: Springer, 2003: 416-432.

[5] Shim K A. On the security of a certificateless aggregate signature scheme[J]. IEEE Communications Letters, 2011, 15(10): 1136-1138.

[6] XIONG Hu, GUAN Zhi, CHEN Zhong, et al. An efficient certificateless aggregate signature with constant pairing computations[J]. Information Science, 2013, 219(1): 225-235.

[7] SHEN Limin,SUN Yinxia. On the security of a certificateless aggregate signature scheme[J]. International Journal of Advancements in Computing Technology, 2013,5(3):358-367.

[8] 杜红珍, 黄梅娟, 温巧燕. 高效的可证明安全的无证书聚合签名方案[J]. 电子学报, 2013, 41 (1): 73-76.

DU Hongzhen, HUANG Meijuan, WEN Qiaoyan. Efficient and provably-secure certificateless aggregate signature scheme[J]. Acta Electronica Sinica, 2013, 41(1): 73-76.

[9] 喻琇瑛, 何大可. 一种新的无证书聚合签名[J]. 计算机应用研究, 2014, 31(8): 2485-2487.

YU Xiuying, HE Dake. New certificateless aggregate signature scheme[J]. Application Research of Computers, 2014, 31(8): 2485-2487.

[10] 明洋, 赵祥模, 王育民. 无证书聚合签名方案[J]. 电子科技大学学报, 2014, 43(2): 188-193.

MING Yang, ZHAO Xiangmo, WANG Yumin. Certificateless aggregate signature scheme[J]. Journal of University of Electronic Science and Technology of China, 2014, 43(2): 188-193.

[11] Mambo M, Usuda K, Okamoto E. Proxy signature for delegating signing operation[C]//Proceedings of the 3rd ACM Conference on Computer and Communications Security. New York: ACM Press, 1996: 48-57.

[12] Li J, Kim K, Zhang F, et al. Aggregate proxy signature and verifiably encrypted proxy signature[M]. Berlin: Springer-Verlag, 2007: 208-217.

[13] 王勇兵, 卢晓杰, 张建中. 一种基于身份的代理聚合签名方案[J]. 济南大学学报(自然科学版), 2011, 25(3): 301-304.

WANG Yongbing, LU Xiaojie, ZHANG Jianzhong. An identity-based proxy aggregate signature scheme[J]. Journal of University of Jinan (Science and Technology), 2011, 25(3): 301-304.

[14] 陈群山, 黄振杰, 郝艳华, 等. 基于身份的代理聚合签名方案的分析与改进[J]. 济南大学学报(自然科学版), 2014, 28(3): 204-208.

CHEN Qunshan, HUANG Zhenjie, HAO Yanhua, et al. Analysis and improvement of identity-based proxy aggregate signature scheme[J]. Journal of University of Jinan (Science and Technology), 2014, 28(3): 204-208.

[15] 孙华, 郭磊, 郑雪峰, 等. 一种有效可证安全的基于身份代理聚合签名方案[J]. 计算机科学, 2012, 39(1): 44-47, 52.

SUN Hua, GUO Lei, ZHENG Xuefeng, et al. Efficient and provably secure identity-based proxy aggregate signature scheme[J]. Computer Science, 2012, 39(1): 44-47, 52.

[16] Boldyreva A, Palacio A, Warinschi B. Secure proxy signature schemes for delegation of signing rights[J]. Journal of Cryptology, 2012, 25(1): 57-115.

(编辑  赵俊)

收稿日期：2014-12-13；修回日期：2015-03-20

基金项目(Foundation item)：国家自然科学基金资助项目(61401377)(Project (61401377) supported by the National Natural Sciences Foundation of China)

通信作者：喻琇瑛，博士研究生，从事密码学和信息安全研究；E-mail：xyyu@swjtu.edu.cn