标准模型下可证明安全的基于身份多代理签名

陈　明　　　袁少良

(宜春学院数学与计算机科学学院　江西宜春　336000)



标准模型下可证明安全的基于身份多代理签名

陈明袁少良

(宜春学院数学与计算机科学学院江西宜春336000)

(chenming9824@aliyun.com)

基于身份多代理签名的2类主要形式化安全模型分别存在敌手攻击目标不准确和敌手分类不完备的问题，而且，目前仍缺乏真正可证明安全的有效方案.融合现有安全模型，重新定义了基于身份多代理签名的标准安全模型.新模型立足于改进现有模型存在的问题，采用更加完备的敌手分类标准，形式化定义各类敌手的行为和攻击目标，采用简单清晰的证明结构.在新安全模型框架下，提出一种基于身份的多代理签名方案，其安全性被规约为多项式时间敌手求解CDH问题.此外，着重分析了最近提出的一种基于身份多代理签名方案及其安全模型，指出其中的3个主要缺陷.对比分析表明，新的安全模型更加完备，新提出的多代理签名是一种真正的、在标准模型下可证明安全的基于身份密码方案.

多代理签名；基于身份密码学；双线性映射；计算Diffie-Hellman问题；标准模型

代理签名(proxysignature)是指原始签名者将自身的签名权限授予代理签名者，然后由代理签名者代表原始签名者实施签名的一种签名算法.自1996年Mambo等人[1]提出代理签名概念以来，其他研究者相继提出代理签名的多个变种，包括：多代理签名(multi-proxysignature)、代理多签名(proxymulti-signature)、多代理多签名(multi-proxymulti-signature)、代理盲签名(proxyblindsignature)和代理环签名(proxyringsignature)等[2-8].代理签名及其变形在电子商务和电子政务等领域有重要的研究和应用价值.

从授权方式来看，代理签名主要分为：完全代理、部分代理和基于授权书的代理.代理授权书由原始签名者和代理签名者共同协商，并由原始签名者实施代理授权签名.授权书内容主要包含：原始签名者和代理签名者身份、代理权适用范围描述和有效期限等信息.基于授权书的代理签名能够实现原始签名者和代理签名者身份的可鉴别性、(原始签名者)授权和(代理签名者)代理行为的不可否认、以及防止代理权被滥用等安全属性[9-11].比较而言，不采用授权书的代理签名方案存在一些固有的局限性[9-11]，目前的研究重点都集中在基于授权书的代理签名方案.

基于身份密码学(identity-basedcryptography，IBC)[12-13]是一种将用户身份标识(ID)作为用户公钥的非对称密码体制.在IBC中，可信的密钥生成中心(privatekeygeneration，PKG)根据用户ID使用其主密钥为用户生成长期私钥，但不产生公钥证书，无需公钥基础设施支持，从而减轻了用户密钥管理负担.Zhang等人[14]将IBC与代理签名相结合提出基于身份的代理签名方案.基于身份的代理签名方案继承了IBC算法的优点，不需要构建公钥基础设施，易于实现，已成为本领域研究的一个新热点.

针对电子商务的特殊应用需求，Hwang等人[2]提出多代理签名概念，由1个原始签名者将他的签名权授予n(>1)个代理签名者，然后由n个代理签名者共同代表原始签名者实施签名.考虑如下场景：当公司首席执行官正在长途飞行，但有一份紧急文件需要立即签署，此时，公司各部门经理可以行使事先被授予的代理签名权共同代表首席执行官签署该文件.可见，多代理签名方案具有实际的应用价值.

一些研究者相继提出多个IBMPS(identity-basedmulti-proxysignature)方案[15-21].Chen等人[15]、Li等人[16]、Mishra等人[19]提出的IBMPS方案没有定义有效的形式化安全模型.Cao等人[17]、Sahu等人[20]分别提出一种IBMPS方案，并在随机预言模型下证明了方案的安全性.但是，Xiong等人[18]、Asaar等人[22]分别指出Cao等人[17]的方案和Sahu等人[20]的方案存在安全缺陷.最近，谷科等人[21]提出一种标准模型下的IBMPS方案(记为Gu-IBMPS).标准模型不依赖于现实世界无法实现的随机预言假设[23]，比随机预言模型具有更强的安全规约.但是，Gu-IBMPS方案及其安全模型存在几个缺陷(详细分析见本文2.2节)，不具有可证明安全性.就目前掌握的文献来看，还没有一种IBMPS方案真正实现了可证明安全性.

在代理签名的安全模型方面，Boldyreva等人[24]首先提出一个可证安全模型，并将几种代理签名机制的安全性规约为基本的计算复杂性假设.随后，Wang等人[25]、Cao等人[17]沿用了Boldyreva模型，并将该模型扩展到(基于身份的)多代理签名方案.但是Boldyreva模型证明结构复杂，且不完备，正如Schuldt等人[26]所指出的那样，该模型没有将代理授权签名作为安全游戏模拟的对象.最近，在早期工作的基础上，Boldyreva等人[11]进一步归纳总结了相关研究[26-27]，改进了其安全模型，包括：明确地定义了代理签名的各项安全属性；引入自我代理(self-delegation)[27]扩展了敌手类型，并对敌手行为进行了形式化定义；明确区分一般代理和基于授权书的代理签名及其安全模型.此外，Huang等人[28]也提出一种代理签名安全模型.Yu等人[29]，Liu等人[30]、Sun等人[31]分别将Huang模型扩展到多代理签名和代理多签名领域.与Boldyreva模型不同，Huang等人的模型及其扩展[28-31]强调代理授权签名在多代理签名安全模型中的重要作用，定义了代理授权签名询问，定义了3种类型的敌手，明确指出其定义的第2类敌手[30-31]的主要攻击目标是伪造代理授权签名.但是，该模型没有涵盖原始签名者的自我代理情形.谷科等人[21]引用了Boldyreva模型[11]，并基于Paterson等人[32]的标准签名模型，定义了多代理签名的标准模型.但是，该模型[21]显然没有注意到代理授权签名在多代理签名安全模型中的作用，存在缺陷，不能有效模拟针对代理授权签名的攻击行为.因此，尽管Gu-IBMPS方案在其安全模型下可证明安全，仍然受到其定义的第4类敌手的伪造攻击.详细分析见本文2.2节.

可见，可证明安全的基于身份多代理签名及其安全模型还有待进一步研究，这是本文研究的动机.

本文研究了基于身份的多代理签名及其安全模型，主要在2方面做出一定贡献：

1) 在总结、融合现有安全模型的基础上，定义了基于身份多代理签名的标准安全模型.本文安全模型基本沿用了Huang模型的证明结构，定义了代理授权签名询问，能有效模拟针对代理授权签名的攻击行为，同时引用了Boldyreva模型的敌手类型(增加了自我代理情形的形式化模拟)，形式化定义了各类敌手的行为.与现有2类主要安全模型比较，本文安全模型证明结构更清晰，各类敌手攻击目标更明确，敌手类型涵盖更全面.并且，本文标准安全模型只需稍加扩展，可用于基于身份的(多)代理(多)签名方案形式化分析.

2) 本文提出一种真正在标准模型下可证明安全的基于身份多代理签名方案.相较现有方案，本文方案不仅安全性更强，而且计算开销更低.此外，本文还详细分析了Gu-IBMPS方案及其安全模型存在的主要缺陷.

1　背景知识

1.1双线性映射与困难数学问题

这里简要阐述与本文相关的基本数学理论：双线性映射理论及存在的困难数学问题和假设.详细内容请参考文献[13,32].

双线性映射.给定大素数p，阶为p的循环群G1和G2，g是G1的1个生成元，如果e：G1×G1→G2是从G1到G2的1个有效的双线性映射，那么满足以下条件.

1)双线性：给定u，v∈G1和任意的a，b∈p，满足e(ua，vb)=e(u，v)a b；

2)非退化性：e(g，g)≠1；

3)可计算性：给定任意的u，v∈G1，存在多项式时间算法能成功计算e(u，v).

CDH(computationalDiffie-Hellman)问题.对于任意未知的a，b∈p，给定g，ga，gb∈G1，求解ga b.

CDH假设.如果不存在多项式时间算法在时间t内以至少ε的概率求解CDH问题，那么称(ε，t)-CDH假设在G1上成立.

1.2基于身份多代理签名模型

IBMPS方案由系统建立(Setup)、用户私钥产生(KeyGen)、基于身份签名(IB-Sign)及验证(IBS-Verify)、代理授权签名(DelegateGen)及验证(DelegateVer)、多代理签名(MProxySign)及验证(MProxyVerify)八个算法组成.

Setup算法由PKG执行，输入安全参数k，输出系统公开参数params和PKG主密钥msk.

KeyGen算法由PKG执行，输入params，IDu，msk，输出用户私钥sku.

IB-Sign算法作为DelegateGen和MProxySign算法基础，输入params，签名者身份IDu及其私钥sku，签名消息m，输出签名σIBS.

IBS-Verify算法作为DelegateVer和MProxyVerify算法基础，输入params，IDu，m，σIBS，输出T表示接受签名或⊥表示签名无效.

DelegateVer算法由每位代理者分别执行，输入params，IDo，w，δ，输出T表示代理授权签名有效或⊥表示代理授权签名无效.

1.3基于身份多代理签名安全模型

本文在Paterson等人[32]的标准签名模型基础上，融合Boldyreva模型[11]和Huang模型及其扩展[28-31]，定义了基于身份多代理签名的标准安全模型.

(多)代理签名方案应满足的主要安全属性包括[2,10-11]：不可伪造性(unforgeability)、不可否认性(undeniability)、身份可鉴别性(identifiability)、可验证性(verifiability)和防止滥用性(preventionofmisuse).

文献[11，26，28-30]的分析表明，采用代理授权书的(多)代理签名方案若能实现不可伪造性，那么必然满足身份的可鉴别性、不可否认性和防止滥用性.基于此，本文重点讨论IBMPS方案的可验证性和自适应选择消息攻击下的不可伪造性(existentialunforgeabilityunderadaptivechosenmessageattack，EUF-CMA).

下面回顾现有模型定义的敌手类型.

谷科等人[21]将Boldyreva等人[11]定义的4种类型敌手扩展到多代理签名集合，描述如下：

第1种类型敌手(无代理情况，本文用A1表示)用于模拟标准签名方案的安全性，被允许询问用户私钥(除了不被敌手所控制的用户ID*)和签名预言机，以及创建新用户.

第2种类型敌手(自我代理情况，本文用A2表示)不控制原始签名者和代理签名者，此一情形下，原始签名者和所有代理签名者均是同一用户ID*.

第3种类型敌手(授权代理情况，本文用A3表示)控制了原始签名者和至多n-1个代理签名者.

第4种类型敌手(被代理情况，本文用A4表示)控制了所有n个代理签名者，但不控制原始签名者.

可见，4种类型的敌手都实现了能力最大化，他们控制了除挑战用户ID*以外的所有用户，并且还被赋予创建新用户的能力.我们将在下面的安全模型中形式化定义每一类敌手的行为.

Gu-IBMPS模型允许敌手(主要指A2A3A4)提交“代理签名私钥询问”和(多代理)“签名询问”，没有定义“用户私钥询问”和“代理授权签名询问”.该安全模型并不完备，不能有效模拟A4的攻击能力(详细分析见本文2.2节).A4控制了所有代理签名者，不控制原始签名者，从A4的视角来看，如果能伪造原始签名者的有效代理授权签名，那么利用他所控制的代理签名者可以产生合法的多代理签名.由此推论：A4的主要攻击目标是伪造(不被控制的)原始签名者ID*对特定授权书w*的有效代理授权签名.

此外，Huang等人[28]模型也定义了3种类型的敌手，Yu等人[29]、Liu等人[30]将其扩展到多代理签名集合.其中，第1类敌手不控制任何的合法用户，仅能取得系统公开参数和用户身份(公钥)；第2类敌手等同于本文的A4；第3类敌手则等同于本文的A3.可以看出，该模型定义的第23类敌手蕴含了第1类敌手，因而在其证明过程中通常省略了第1类敌手[29-30].然而，Huang等人及其扩展模型[28-31]并不考虑标准签名(A1)和自我代理情况(A2).

本文整合上述研究，定义敌手A∈{A2，A3，A4}与挑战者B之间的游戏(IBMPS-EUF-CMAgame)模拟IBMPS方案的不可伪造性.由于A1敌手用于模拟标准签名方案的安全性，本文的标准签名直接采用Paterson签名机制[32]，并且该签名机制在标准模型下被证明满足IBS-EUF-CMA安全，因此本文安全模型省略了A1敌手.此外，文献[11]描述了一种可能的攻击行为：敌手通过询问标准签名预言机(而非“代理授权签名”预言机)取得代理授权签名.同时，该文也给出一种相应的解决方案，即：为不同的预言机询问分配标签.为了简化证明过程，本文模型忽略这一可能的攻击行为.

关于IBMPS-EUF-CMAgame的描述如下：

1) 系统建立：B执行系统建立算法，输出系统公共参数params，并发送给A.

2) 询问：A自适应地执行多项式时间的询问.

①KeyGen询问：A提交1个用户身份u，B返回签名者私钥sku；

下面对3种敌手的行为进行说明.

定义1. 如果不存在概率多项式时间敌手A，在时间t内以至少ε的概率赢得IBMPS-EUF-CMAgame，则IBMPS方案满足(ε，t，qe，qd，qs)-IBMPS-EUF-CMA安全.这里，A最多执行了qe次KeyGen询问、qd次DelegateGen询问和qs次MProxySign询问.

2　多代理签名方案的密码学分析

2.1基于身份多代理签名方案描述

最近，谷科等人[21]提出一种基于身份的多(群)代理签名方案Gu-IBMPS，简要描述如下.

1)Setup：PKG执行Setup算法，产生并发布公共参数params={G1，G2，e，g，g1，τ′，I，m′，M}.其中，e：G1×G1→G2是满足定义的双线性映射；g是G1的生成元；g1，τ′，m′∈G1由PKG随机选择；I=(τi)，M=(mi)是由PKG选择的长度分别为nu，nm的向量，并且向量I，M的元素τi和mi也是群G1上的元素.此外，PKG选择3个抗碰撞的Hash函数H：{0，1}*→p，Hu：{0，1}*→{0，1}nu和Hm：{0，1}*→{0，1}nm，生成用户公共参数列表UPK_List用于发布注册用户生成的公共参数，初始值为空.

2)KeyGen：提交用户身份ui，ui为长度是nu的二进制串，PKG随机选择xi，ri∈p，产生用户私钥为).其中，Vi⊆{1，2,…，nu}表示ui中比特值等于1的位置d的集合.同时产生用户公钥参数pki=gxi.

3)UPK_List：PKG通过安全信道发送私钥ski给用户ui，并将公钥参数pki发布到UPK_List.ui按照下列等式验证私钥ski的正确性：

4)MDelegate：u1为原始签名者，对于每个代理者uj，j∈{2，3,…，n，n+1}，u1随机选择sj∈p，计算.其中，w1为授权书.令δ1,j,3=sk1,2=gr1，δ1,j,4=w1，则uj的代理授权签名δj=(δ1,j,1，δ1,j,2，δ1,j,3，δ1,j,4).

6)MProxySign：n个代理签名者代表u1按如下步骤对消息m进行签名.

① 每个代理者uj随机选择λj∈p，计算:，令σ1,j,3=psk1,j,2，σ1,j,4=psk1,j,4，输出部分代理签名pσ1,j=(σ1,j,1，σ1,j,2，σ1,j,3，σ1,j,4).

② 存在1个代理者up(p∈{2，3,…，n，n+1})收集所有代理者的部分代理签名，并按照下列等式验证每个部分代理签名的正确性:

如果存在某个部分代理签名无效则拒绝代理签名，否则计算：

令σ1,1,3=psk1,p,3=gr1，生成长度为n+1的元组σ1,3=(σ1,j,3)，j∈{1，2,…，n，n+1}.最后，输出多代理签名(w1，pσ1=(σ1,1，σ1,2，σ1,3，σ1,4)).

7)MProxyVerify：收到对消息m的多代理签名(w1，pσ1=(σ1,1，σ1,2，σ1,3，σ1,4))，按如下计算进行验证

如果相等则接受多代理签名，否则拒绝.

2.2Gu-IBMPS方案分析

基于Boldyreva模型[11]，文献[21]定义了多代理签名的敌手类型及形式化安全模型，并以此模型分析了Gu-IBMPS方案的安全性，认为该方案满足选择消息攻击下的不可伪造性.但是，本文分析发现，Gu-IBMPS方案及其安全模型存在3个缺陷.

1)Gu-IBMPS方案被称为基于身份的多代理签名，并不恰当.基于身份的签名方案需要在用户私钥产生阶段(即KeyGen算法)，将PKG的主密钥和用户身份嵌入到用户的私钥中，然后在签名验证阶段使用PKG的公钥和用户身份进行验证(具体算法过程可参考文献[13，32]).也就是说，基于身份的签名机制是将签名结果与PKG的主密钥和用户身份产生密码学关联，不使用公钥证书.反观Gu-IBMPS方案，PKG没有主密钥，用户私钥虽由PKG产生，但与PKG公钥不存在可验证的密码学关联关系，仅通过公告板UPK_List发布用户公开密钥参数.同时，Gu-IBMPS方案也没有使用公钥证书保障用户密钥的可信性.在现实世界中，这样的密码系统不完备，需要额外的密钥保障机制保护用户的公钥参数不被篡改.可见，Gu-IBMPS方案不是真正意义上的基于身份密码方案.

2)Gu-IBMPS方案不满足不可伪造性.我们首先回顾第4类攻击者A4(见文献[21]第2节情况4)：“敌手控制n+1个用户中的至多n个用户；该n个用户伪造1个在没有获得用户u*的授权下假装用户u*授权的多代理签名”.根据描述，敌手控制了除原始签名者u*以外的所有n个代理签名者(A4可以访问所有代理签名者的私钥)，那么A4需要获得u*的可验证正确的代理授权签名，就能成功伪造多代理签名.因此，A4的目标是伪造u*的代理授权签名.下面给出攻击实例演示A4如何伪造u*的授权签名.

A4可以收集n份不同的由u*签署的代理授权签名，为每个代理签名者伪造1份各不相同的代理授权签名(n个不同的sj，但A4不需要知道sj).在真实的攻击环境下，由于代理授权签名在公开信道上发送，攻击者收集代理授权签名是容易实现的.由于A4控制了所有n个代理签名者，A4能够按照Gu-IBMPS方案的MProxyKeyGen和MProxySign算法为每个代理签名者产生代理签名密钥并进行多代理签名.

因此，在第4类攻击者A4存在的情况下，Gu-IBMPS方案不满足不可伪造性.

形成上述攻击的原因是：Gu-IBMPS方案没有注意到MDelegate算法的本质是原始签名者对代理授权书w的签名，因而没有采用标准的Paterson签名[32]机制进行代理授权签名，而且在其后的安全性证明过程中缺乏对“攻击者伪造代理授权签名”这一攻击场景的形式化分析.

3)Gu-IBMPS方案的安全模型存在缺陷，不能完全模拟真实的攻击场景.正如前一点指出的，Gu-IBMPS模型忽略了“攻击者伪造代理授权签名”这一攻击场景，敌手不能询问代理授权签名.在真实环境下，代理授权签名通常在公开信道上发送，敌手能比较容易地窃取该授权签名.Schuldt等人[26]就曾指出，Boldyreva模型没有将代理授权签名作为安全游戏模拟要素.同样地，衍生自Boldyreva模型的Gu-IBMPS模型也没有定义代理授权签名询问，敌手不能询问(不被敌手控制的)用户u*对非特定授权书w(≠w*)的代理授权签名(上述攻击证明这一询问是必要的)，削弱了敌手的能力.通过以上分析可以看出，Gu-IBMPS模型沿袭了Boldyreva模型的固有缺陷，不能完备地模拟真实的攻击场景.

3　改进的基于身份多代理签名方案

本文提出一种标准模型下可证明安全的基于身份多代理签名方案，改进了Gu-IBMPS方案的2个缺陷：1)本文方案扩展于Paterson[32]签名机制，采用Paterson签名及验证算法作为其标准签名及验证算法，是一种真正意义上的标准模型下的IBMPS机制；2)本文方案的DelegateGen和DelegateVer算法将代理授权书w作为被签名消息，采用Paterson签名机制进行代理授权签名和验证，防止了代理授权签名伪造攻击.本文方案描述如下：

1)Setup：输入安全参数k，PKG执行Setup算法，产生满足定义的双线性映射e：G1×G1→G2，g是G1的生成元；PKG随机选择α∈p和g2∈G1，计算g1=gα，Q=e(g1，g2)，将(g1，g2，Q)作为PKG公钥，然后计算作为其主密钥；PKG随机选择u′，w′，m′∈G1，选择长度分别为nu，nw和nm的向量U=(ui)，W=(wi)，M=(mi)，向量中的元素满足ui，wi，mi∈G1；选择抗碰撞的Hash函数H1：{0，1}*→{0，1}nw，H2：{0，1}*→{0，1}nm分别用于将授权书和待签名消息映射到大小为nw位和nm位的消息空间.PKG发布公共参数params={G1，G2，e，g，g1，g2，Q，u′，U，w′，W，m′，M，H1，H2}.本文方案要求用户的身份ID统一为nu位二进制串.

2)KeyGen：提交用户身份ui.用μi⊆{1，2,…，nu}表示ui中位值为1的位置d的集合.PKG随机选择ri∈p，计算用户私钥).PKG通过安全信道将ski发送给ui.收到ski后，ui计算等式是否成立来验证私钥的正确性.如果验证等式成立，则接受ski作为自己的私钥；否则，重新申请私钥.

3)IB-SignIBS-Verify：本文方案采用Paterson签名机制作为标准签名及验证算法，具体请参考文献[32].

6)MProxySign：多代理签名算法分为2步.第1步由每个代理者产生部分代理签名；第2步由1个代理者up(p∈{2，3,…，n，n+1})收集所有部分代理签名生成最终的多代理签名.输入代理授权签名δ、原始代理签名者身份ui(i∈{1，2,…，n+1})、代理授权书w、消息m，按如下步骤执行：

① 每个uj(j∈{2，3,…，n+1})选择tj∈p，计算，令σj,3=skj,2，输出部分代理签名pσj=(σj,1，σj,2，σj,3).其中，θ⊆{1，2,…，nm}表示H2(m)中位值为1的位置i的集合.

注意，为了降低多代理签名聚合者up的计算开销，本文方案取消了up分别去验证其他代理者的部分代理签名pσj，up只需按照下面的MProxyVerify算法验证最终多代理签名的有效性.我们将在4.3节讨论这样的改进是否会影响算法的安全性.

7)MProxyVerify：收到对消息m的多代理签名(w，σ1，σ2，σ3，σ4)，验证者计算下列等式进行验证：

如果上式成立则接受多代理签名，否则拒绝.

4　改进方案分析

4.1正确性分析

本文方案的正确性由下列等式证明：

(1)

式(1)表明用户私钥验证有效.

(2)

式(2)表明代理授权签名及其验证有效.

(3)

式(3)表明多代理签名及其验证有效.

由式(1)～(3)可验证本文提出的多代理签名算法满足正确性和可验证性.

4.2安全性分析

根据本文1.3节定义的安全模型，IBMPS方案存在4种类型敌手.对于敌手A1，Paterson签名[32]机制已被证明满足IBS-EUF-CMA安全，本文不再赘述.下面讨论本文IBMPS方案在敌手A∈{A2，A3，A4}攻击下的安全性.

定理1. 令ρ，τ分别表示G1上的乘法运算和指数运算时间，假设A最多执行了qe次KeyGen询问、qd次DelegateGen询问和qs次MProxySign询问，如果(ε′，t′)-CDH假设成立，则本文提出的IBMPS机制满足(ε，t，qe，qd，qs)-IBMPS-EUF-CMA安全.这里，ε′≥ε[64qs(qd+qs)(qe+qd+qs)(nu+1)(nw+1)(nm+1)]，t′>t+O((qenu+qd(nu+nw)+qs(nu+nw+nm))ρ+(qe+qd+qs)τ).

与文献[32]的定理1类似，以下证明过程将本文IBMPS机制的不可伪造性规约为求解CDH问题.

证明. 假设存在(ε，t，qe，qd，qs)-forger敌手A，我们将构建1个算法B,利用A在时间t′内以至少ε′的概率解决CDH问题.下面模拟B与A的游戏.

1) 系统建立：B设置lu=2qe，lw=2(qe+qd)，lm=2(qe+qd+qs)，随机选择整数ku，km，kw，满足条件0≤ku≤nu，0≤km≤nm，0≤kw≤nw.对于给定的(qe，qd，qs，nu，nm，nw)，我们假设有：lu(nu+1)

这里，μ ，θ，ϖ 含义与第3节相同.然后，B构建公共参数：g1=ga，g2=gb，Q=e(g1,g2)；

B选择安全的Hash函数H1，H2，将公共参数{G1，G2，e，g，g1，g2，Q，u′，U，m′，M，w′，W，H1，H2}发给A.这里，U=(ui)，M=(mj)，W=(wt).与文献[32]相同，存在等式：

2) 询问：A自适应地执行多项式时间的询问.

①KeyGen询问.收到该询问，如果F(u)=0modlu，那么B终止游戏；否则F(u)≠0modlu，B随机选择ru∈p，计算用户私钥：sku=(sku,1，sku,2)=，返回给A.

根据文献[32]定理1的论述，存在等式：

与文献[32]保持一致，为了便于分析，本文模型也规定：当F(u)=0modlu时，B强制终止A的询问.根据文献[32]定理1的推论，由F(u)=0modp可推导F(u)=0modlu；由F(u)≠0modlu可推导F(u)≠0modp.也就是说，挑战用户u*的身份必然满足条件：F(u*)=0modlu.该条件确保敌手A不能询问u*的私钥.我们将(F(u)=0modlu∧F(u)≠0modp)定义为小概率事件.与文献[32]保持一致，同时也为了便于分析，本文也忽略这一小概率事件.

注意，为了保持用户身份与密钥的一致性，B需要存储已创建的用户私钥，以备查询，并且在以下各询问中，除挑战用户u*外，其他用户必须先创建私钥.

最后，B输出(δ1，δ2，δ3)作为代理授权签名.

可以验证，从A的视角来看，输出结果是1个有效的代理授权签名.

lm(ξ=H2(m))，B终止游戏，否则选择rk，tk∈p，计算：

下面分3种情况讨论B对CDH问题的回答.

作为对CDH问题的回答.

2) 对于第3类敌手A3，如果({∃终止游戏；否则，B计算：

作为对CDH问题的回答.

作为对CDH问题的回答.

游戏模拟到此结束.如果游戏没有终止，我们分析B利用A求解CDH问题的概率.DelegateGen询问分为：F(u1)≠0modlu，(F(u1)=0modlu)∧(T(ω)≠0modlw)2个部分.MProxySign询问分为：∀F(uk)≠0modlu，(∃F(uk)=0modlu)∧(K(ξ)≠0modlm)2个部分.

令qu是询问中出现的身份数量，qw是询问中出现的授权书的数量，qm是询问中出现的签名消息的数量.显然，存在不等式：qu≤qe+qd+qs，qw≤qd+qs，qm≤qs.与文献[32]类似的，本文定义6类事件Bi，B*，Cj，C*，Dk，D*如下.

Bi：F(ui)≠0modlu.

B*：F(u*)=0modp.

Cj：T(wj)≠0modlw.

C*：T(w*)=0modp.

Dk：K(mk)≠0modlm.

D*：K(m*)=0modp.

根据文献[32]定理1的推论，由F(u)≠0modlu可推导F(u)≠0modp；由T(w)≠0modlw可推导T(w)≠0modp；由K(m)≠0modlm可推导K(m)≠0modp.

因此，B没有终止游戏的概率为

Pr[

因此，有：

Pr[

如果游戏没有被终止，且A以不低于ε的概率赢得游戏，那么B以不低于ε[64qs(qd+qs)(qe+qd+qs)(nu+1)(nw+1)(nm+1)]的概率成功求解CDH问题.

从算法的时间复杂度来看，在KeyGen询问、DelegateGen询问和MProxySign询问中分别执行了O(nu)，O(nu+nw)，O(nu+nw+nm)次乘法运算以及O(1)次指数运算.令ρ和τ分别表示乘法运算和指数运算时间，那么算法B的时间复杂度为：t′≥t+O((qenu+qd(nu+nw)+qs(nu+nw+nm))ρ+(qe+qd+qs)τ).

证毕.

4.3对比与分析

就目前掌握的文献资料来看，仅有Gu-IBMPS[21]方案是标准模型下的IBMPS方案.表1从计算开销方面对比了本文提出的多代理签名与Gu-IBMPS方案.列举了5种主要运算:P表示双线性对运算，M1表示G1上的乘运算，E1表示G1上的指数运算，M2表示G2上的乘运算，E2表示G2上的指数运算.n表示代理签名者数量，uo表示原始签名者,up代表单个(非聚合)代理签名者,up k代表多代理签名聚合者,uv代表多代理签名验证者.

Table1　Comparison of Computing Costs表1　计算性能比较

从表1可以看出，由于本文方案取消了分别验证每个部分代理签名，而只验证1次多代理签名，大大地降低了up k的计算开销(每一种运算约减少了n的倍数次).此外，在多代理签名验证阶段，验证者约减少了(n+1)次M2运算和P运算.从总的计算性能来说，本文方案具有明显的优势，特别是避免了up k的高计算载荷(超过6nP).

安全性方面，现有IBMPS方案要么缺乏有效的形式化安全证明，要么存在已知安全缺陷.本文2.2节也指出了Gu-IBMPS方案存在安全缺陷，特别是该方案不符合基于身份密码方案的基本要求.本文提出了真正的标准模型下的基于身份多代理签名方案，PKG拥有主密钥，并且利用主密钥和用户身份为用户产生私钥，私钥验证、代理授权签名验证和多代理签名验证都需要输入PKG公钥和相应用户的身份，符合基于身份密码技术规范[12-13,32].其次，本文方案采用标准的Paterson签名机制进行代理授权签名，有效防止了攻击者伪造授权书.安全性证明表明，本文IBMPS方案真正实现了可证明安全性.

这里简要讨论在MProxySign算法中用多代理签名验证替换每个部分代理签名验证是否会影响算法整体安全性.根据4.2节的安全性证明，多代理签名的整体安全性能够被规约到任意单个用户ui(i∈(1，2，…，n，n+1))的行为.具体来说，(极端情况下，只有1个用户u*是诚实的，不被A所控制)如果敌手A能成功伪造有效的多代理签名，那么，A要么能伪造有效的代理授权签名(此时，u*=u1为原始签名者)，要么能伪造u*的部分代理签名(此时，u*=uj，j∈{2，3，…，n，n+1}为某个代理签名者).根据4.2节定理1的结论，针对本文提出的多代理签名方案，这样的敌手是不存在的.因此，本文“多代理签名有效”这一命题蕴含了“不存在敌手能成功伪造任一未被控制用户的部分代理签名”这一事实.也就是说，安全性证明表明“只要有1个诚实用户没有参与代理签名，多代理签名结果都无效”.根据逆否命题，可得：“所有诚实的用户都必须参与签名，多代理签名结果才有效”.因此，签名聚合者up可以使用多代理签名验证替代所有部分代理签名验证，不会降低算法安全性.

5　结束语

本文研究了基于身份多代理签名及其安全模型.目前，本领域主要存在2类形式化安全模型：Boldyreva模型及其衍生模型、Huang模型及其扩展模型.我们注意到，Huang模型的证明结构更简洁明晰，对敌手行为的刻画更准确，而Boldyreva模型定义了更加完整的敌手类型.在总结、融合这2类安全模型的基础上，本文定义了更加完备的多代理签名标准模型，采用了Huang模型的证明结构和Boldyreva模型的敌手类型，对各类敌手的行为进行了更加明确的形式化定义.本文定义的标准模型具有可扩展性，只需稍加扩展，可形式化分析各类(多)代理(多)签名方案.在本文安全模型框架下，我们提出一种基于身份的多代理签名方案.与现有方案相比，本文方案真正实现了可证明安全性，其安全性被规约为多项式时间敌手求解CDH问题.此外，本文还详细分析了最近提出的一种基于身份多代理签名方案及其安全模型，指出其存在的3点主要缺陷.对该文的研究，奠定了本研究的基础.

目前，标准安全模型已成为本领域的一类重要形式化方法，由于不依赖随机预言假设，标准模型具有比随机预言模型更强的安全规约.但是，标准模型需要构造特殊的安全函数，算法的计算开销通常高于随机预言模型下的同类型算法，并且模型的适应范围更窄.就目前掌握的文献资料来看，Paterson签名机制是唯一一种被广泛引用的标准模型下可证安全的IBS方案.构建标准模型下更加安全高效的IBS方案，以及将其扩展到其他密码技术领域(如：无证书密码学)仍然是一项开放性的工作.

[1]MamboM,UsudaK,OkamotoE.Proxysignaturefordelegatingsigningoperation[C] //Procofthe3rdACMConfonComputerandCommunicationsSecurity.NewYork:ACM, 1996: 48-57

[2]HwangSJ,ShiCH.Asimplemulti-proxysignatureschemeforelectroniccommerce[C] //Procofthe10thNationalConfonInformationSecurity. [S.1]:ROC, 2000: 134-138

[3]YiLijiang,BaiGuoqiang,XiaoGuozhen.Proxymulti-signaturescheme：Anewtypeofproxysignaturescheme[J].ElectronicsLetters, 2000, 36(6): 527-528

[4]HwangSJ,ChenCC.Newmulti-proxymulti-signatureschemes[J].AppliedMathematicsandComputation, 2004, 147(1): 57-67

[5]JiJiahui,LiDaxing,WangMingqiang.Newproxymulti-signature,multi-proxysignatureandmulti-proxymulti-signatureschemesfrombilinearpairings[J].ChineseJournalofComputers, 2004, 27(10): 1429-1435 (inChinese)(纪家慧, 李大兴, 王明强. 来自双线性配对的新的代理多签名、多代理签名和多代理多签名体制[J]. 计算机学报, 2004, 27(10): 1429-1435)

[6]LuRongxing,CaoZhenfu,ZhouYuan.Proxyblindmulti-signatureschemewithoutasecurechannel[J].AppliedMathematicsandComputation, 2005, 164(1): 179-187

[7]ZhangFangguo,Safavi-NainiR,LinCY.Newproxysignature,proxyblindsignatureandproxyringsignatureschemesfrombilinearpairing[EB//OL].IACRCryptologyePrintArchive, 2003 [2015-02-17].http://eprint.iacr.org//2003//104.pdf

[8]GuKe,JiaWeijia,JiangChunlin.Agroupproxysignatureschemebasedonsub-secretevolution[J].JournalofComputerResearchandDevelopment, 2012, 49(5): 962-973 (inChinese)

(谷科, 贾维嘉, 姜春林. 一种子秘密演化的群体代理签名方案[J]. 计算机研究与发展, 2012, 49(5): 962-973)

[9]KimS,ParkS,WonD.Proxysignatures,revisited[G] //LNCS1334:ProcofICICS’97.Berlin:Springer, 1997: 223-232

[10]LeeB,KimH,KimK.Strongproxysignatureanditsapplications[C//OL] //ProcoftheSymponCryptographyandInformationSecurity. 2001 [2014-12-30].http://cris.joongbu.ac.kr//publication//sps-SCIS2001.pdf

[11]BoldyrevaA,PalacioA,WarinschiB.Secureproxysignatureschemesfordelegationofsigningrights[J].JournalofCryptology, 2012, 25(1): 57-115

[12]ShamirA.Identity-basedcryptosystemsandsignatureschemes[G] //LNCS196:ProcofCRYPTO1984.Berlin:Springer, 1985: 47-53

[13]BonehD,FranklinM.Identity-basedencryptionfromtheweilpairing[G] //LNCS2139:ProcoftheCRYPTO2001.Berlin:Springer, 2001: 213-229

[14]ZhangFangguo,KimK.EfficientID-basedblindsignatureandproxysignaturefrombilinearpairings[C] //Procofthe8thConfonInformationSecurityandPrivacy.Berlin:Springer, 2003: 312-323

[15]ChenXiaofeng,ZhangFangguo,KimK.ID-basedmulti-proxysignatureandblindmulti-signaturefrombilinearpairings[C//OL] //ProcofKIISC, 2003[2014-12-30].http://caislab.kaist.ac.kr//publication//paper_files//2003//CISC2003//ID-based-proxymultisignature%20and%20multiblindsig.pdf

[16]LiXiangxue,ChenKefei.ID-basedmulti-proxysignature,proxymulti-signatureandmulti-proxymulti-signatureschemesfrombilinearpairings[J].AppliedMathematicsandComputation, 2005, 169(1): 437-450

[17]CaoFeng,CaoZhenfu.Asecureidentity-basedmulti-proxysignaturescheme[J].Computers&ElectricalEngineering, 2009, 35(1): 86-95

[18]XiongHu,HuJianbin,ChenZhong,etal.Onthesecurityofanidentitybasedmulti-proxysignaturescheme[J].Computers&ElectricalEngineering, 2011, 37(2): 129-135

[19]MishraS,SahuRA,PadhyeS,etal.EfficientID-basedmulti-proxysignatureschemefrombilinearpairingbasedonk-plusproblem[G] //CCIS165:ProcofINTECH2011.Berlin:Springer, 2011: 113-122

[20]SahuRA,PadhyeS.Provablesecureidentity-basedmulti-proxysignaturescheme[J].InternationalJournalofCommunicationSystems, 2015, 28(3): 497-512

[21]GuKe,JiaWeijia,LiChaoliang,etal.Identity-basedgroupproxysignatureschemeinthestandardmodel[J].JournalofComputerResearchandDevelopment, 2013, 50(7): 1370-1386 (inChinese)

(谷科, 贾维嘉, 李超良, 等. 标准模型下基于身份的群代理签名方案[J].计算机研究与发展, 2013, 50(7): 1370-1386)

[22]AsaarMR,SalmasizadehM,SusiloW.Securitypitfallsofaprovablysecureidentity-basedmulti-proxysignaturescheme[EB//OL].IACRCryptologyePrintArchive, 2014[2015-02-17].https://eprint.iacr.org//2014//496.pdf

[23]BellareM,RogawayP.Randomoraclesarepractical:Aparadigmfordesigningefficientprotocols[C] //Procofthe1stACMConfonComputerandCommunicationsSecurity.NewYork:ACM, 1993: 62-73

[24]BoldyrevaA,PalacioA,WarinschiB.Secureproxysignatureschemesfordelegationofsigningrights[EB//OL].IACRCryptologyePrintArchive, 2003 [2014-12-17].https://eprint.iacr.org//2003//096.pdf

[25]WangQin,CaoZhenfu,WangShengbao.Formalizedsecuritymodelofmulti-proxysignatureschemes[C] //ProcCIT’05.LosAlamitos,CA:IEEEComputerSociety, 2005: 668-672

[26]SchdultJC,MatsuuraK,PatersonKG.Proxysignaturessecureagainstproxykeyexposure[G] //LNCS4939:ProcofPKC2008.Berlin:Springer, 2008: 344-359

[27]MalkinT,ObanaS,YungM.Thehierarchyofkeyevolvingsignaturesandacharacterizationofproxysignatures[C] //ProcofCryptology-EUROCRYPT2004.Berlin:Springer, 2004: 306-322

[28]HuangXY,SusiloW,MuY,etal.Proxysignaturewithoutrandomoracles[G] //LNCS4325:Procofthe2ndIntConfonMobileAd-hocandSensorNetworks(MSN2006).Berlin:Springer, 2006: 473-484

[29]YuY,SunY,YangB,etal.Multi-proxysignaturewithoutrandomoracles[J].ChineseJournalofElectronics, 2008, 17(3): 475-480

[30]LiuZhenhua,HuYupu,ZhangXiangsong,etal.Provablysecuremulti-proxysignatureschemewithrevocationinthestandardmodel[J].ComputerCommunications, 2011, 34(3): 494-501

[31]SunYing,XuChunxiang,YuYong,etal.Improvementofaproxymulti-signatureschemewithoutrandomoracles[J].ComputerCommunications, 2011, 34(3): 257-263

[32]PatersonKG,SchuldtJCN.Efficientidentity-basedsignaturessecureinthestandardmodel[G] //LNCS4058:ProcofACISP2006.Berlin:Springer, 2006: 207-222

ChenMing,bornin1978.ReceivedhisPhDdegreefromChongqingUniversity,Chongqing,China,in2011.NowheislecturerofYichunUniversity.Hismainresearchinterestsincludeinformationsecurity,securityprotocolandformalmethods.

YuanShaoliang,bornin1976.ReceivedhisPhDdegreefromHunanNormalUniversity,Changsha,Hunan,China,in2012.NowheislecturerofYichunUniversity.Hismainresearchinterestsincludebifurcationtheory,chaostheoryandcryptography.

ProvablySecureIdentity-BasedMulti-ProxySignatureSchemeinStandardModel

ChenMingandYuanShaoliang

(College of Mathematics and Computer Science, Yichun University, Yichun, Jiangxi 336000)

Multi-proxysignatureschemesarequiteusefultoolswhileasignerrequiresdelegatinghissigningrighttoagroupofproxysigners.Therearetwomaintypesofformalsecuritymodelsofmulti-proxysignatures.However,theyhavedeficiencies,respectively.Oneofthemiscomplicated,anddoesnotmodelthechosenwarrantattacks;theothermodeldoeshavetheincompletedefinitionofadversary.Meanwhile,thereissofarnoprovablysecureidentity-basedmulti-proxysignaturescheme.Inthispaper,wegiveaformalsecuritymodeloftheidentity-basedmulti-proxysignatureschemes,andproposeanidentity-basedmulti-proxysignaturescheme.Oursecuritymodelcompensatesfordeficienciesinexistingmodels.Itdefinesmorepowerfuladversarycapacity,formalizesthebehaviorsoftheadversaries,andadoptssimpleandclearproofstructure.Theproposedidentity-basedmulti-proxysignatureschemeisbasedonthewell-studiedCDH(computationalDiffie-Hellman)assumption,andisprovenexistentiallyunforgeableagainstchosenmessagewarrantattacksinoursecuritymodel.Inaddition,wepresentthattherearethreesecurityflawsinarecentproposedidentity-basedmulti-proxysignatureschemeandinitssecuritymodel.Comparativeanalysisshowsthatthenewsecuritymodelismorecomplete,andthenewmulti-proxysignatureschemeisarealandprovablysecureidentity-basedcryptosysteminthestandardmodel.

multi-proxysignature;identity-basedcryptography;bilinearpairing;computationalDiffieHellman(DH)problem;standardmodel

2015-03-09；

2015-08-11

国家自然科学基金项目(11361067);江西省自然科学基金项目(2014ZBAB207022)

TP309

ThisworkwassupportedbytheNationalNaturalScienceFoundationofChina(11361067)andtheNaturalScienceFoundationofJiangxiProvinceofChina(2014ZBAB207022).