王 硕，程相国，陈亚萌，王 越

WANG Shuo1,CHENG Xiangguo1,CHEN Yameng2,WANG Yue1

1.青岛大学 计算机科学技术学院，山东 青岛 266071

2.青岛大学 数据科学与软件工程学院，山东 青岛 266071

1.College of Computer Science and Technology,Qingdao University,Qingdao,Shandong 266071,China

2.College of Data Science and Software Engineering,Qingdao University,Qingdao,Shandong 266071,China

1 引言

1984年，Shamir首次提出了基于身份的签名方案[1]，给出了传统公钥密码体制中对数字证书过度依赖的解决方法。2011年，谷科等[2]提出了一个基于CDHP假设的高效安全的基于身份的签名方案，使得签名的长度更短且安全性更高。1991年，Chaum和Heyst[3]提出了群签名体制，该签名对签名者给予保护，即验证者不知道签名者的身份，但在对签名存在争议时，群管理员可以打开签名，进而识别出真正的签名者。将基于身份的签名技术和群签名方案相结合，先后构造出了众多的基于身份的群签名方案[4-5]。群签名在军事、政治和经济方面有着广泛的应用，如电子现金[6]、身份托管[7]、竞标[8]等。

密钥是密码体制的安全保障，密钥的泄露会对密码体制造成毁灭性的打击。在公钥密码体制中，在保持公钥不变的前提下，密钥自保护技术主要有3种，包括前向安全技术[9]、入侵容忍技术[10]和密钥隔离技术。2002年，Dodis等[11]首次给出了密钥隔离的概念，签名者的临时签名密钥在协助器的协助下完成密钥演化，若没有协助器提供更新消息，签名者的密钥无法从当前时间段更新到下一时间段，在协助器密钥安全的情况下，敌手只能伪造当前时间段的签名方案。2006年，Zhou等[12]为解决基于身份的签名方案中的密钥泄露问题，将密钥隔离技术同基于身份的签名方案相结合，提出了基于身份的密钥隔离签名方案。Song[13]首次提出了具有前向安全性质的群签名方案，但方案基于RSA问题，签名长度较长，构造较为复杂，实用性不强。2015年，Zhang等[14]在双线性对上构造了基于身份的前向安全群签名方案。2007年，Li等[15]提出了能够选择性撤销的密钥隔离群签名方案，方案是基于DDH假设和RSA构造的，而在双线性对上，DDH假设能够得到验证，因此不满足安全性。2015年，Zhao等[16]在随机预言模型下提出了并行密钥隔离聚合签名方案。Reddy等[17]在随机预言模型下提出了基于身份的密钥隔离聚合签名。这些群体性签名方案都是基于CDH困难问题构造的，在选择消息攻击下具有不可伪造性。本文以Cheng等[18]提出的基于身份的群签名方案为基础，提出了基于身份的密钥隔离群签名方案。在构造群签名的过程中不需要执行零知识证明协议，简化了构造过程。方案是基于CDH问题构造的，采用的密钥隔离技术不但能解决密钥泄露和安全密钥更新的问题，而且在同等的安全条件下，具有较短的签名长度，对于群成员的跟踪只需要搜索存储列表即可，大大提高了方案的实用性。

2 相关知识

2.1 双线性配对

设(G1,+)和(G2,⋅)是阶为素数q的循环群，P为G1的一个生成元。如果映射e:G1×G1→G2能够满足下面的性质，则称该映射为双线性对。

（1）双线性：对于任意的a,b∈ℤ和P,Q∈G1，满足e(aP,bQ)=e(P,Q)ab。

（2）非退化性：存在P∈G1，满足e(P,P)≠1。

（3）可计算性：对于任意的P,Q∈G1，存在一个计算e(P,Q)的有效算法。

2.2 困难问题

（1）离散对数问题（DL）：对于任意的Q∈G1，求a∈使得Q=aP∈G1在计算上是不可行的。

（2）计算Diffie-Hellman问题（CDH）：对于给定的aP,bP∈G1，a,b∈是未知的，计算Q=abP∈G1是困难的。

（3）判断Diffie-Hellman问题（DDH）：对于给定的aP,bP,cP∈G1,a,b,c∈是未知的，判断c≡ab(modq)是否成立是困难的。

上述的CDH和DDH问题在群G1上求解是困难的，但借助双线性对，通过计算e(aP,bP)=e(P,abP)可以判定c≡ab(modq)等式是否成立，因而DDH问题就可解。

3 基于身份的密钥隔离群签名方案

本文提出的基于身份的密钥隔离群签名方案包括一个可信的第三方（PKG）、管理员IA、管理员OA、协助器和用户。PKG负责进行初始设置，IA负责群成员的加入，OA负责为签名者提供签名帮助，协助器负责提供密钥更新消息。方案由以下11个多项式时间算法构成。

（1）系统建立算法（Setup）：对于给定的安全参数λ，由PKG运行Setup算法生成主密钥、协助器密钥和必须的系统参数。

①(G1,+)和(G2,)是素数阶为q的循环群，P为G1的一个生成元，构造安全的双线性对e。

②随机选择s∈作为群的主密钥，并计算Ppub=sP；随机选择sH∈作为协助器密钥，并计算PH=sHP。

③选择两个安全的哈希函数H1:{0,1}*→G1，H2:{0,1}*→。

④公开系统参数：

SP={G1,G2,q,P,Ppub,PH,e,H1,H2}

（2）管理员密钥生成算法（Gkg）：输入管理员IA的身份信息IDM,由PKG计算QM=H1(IDM),DM=sQM，则IA的私钥为DM。

（3）用户密钥生成算法（Ukg）：输入用户Ui的身份信息IDi，由PKG计算Qi=H1(IDi)，Di=sQi，则Ui的私钥为Di。

（4）群成员加入算法（Join）：用户Ui申请加入群，Ui和IA、OA完成以下的交互协议。

①用户Ui将身份信息IDi发送给IA，申请加入群。

②IA随机选择Xi∈G1，计算Yi=DM-Xi，将Xi保存并发送给Ui，IA将(IDi,Yi)发送给OA，OA将(IDi,Yi)保存到存储列表L1。执行完上述协议后，Ui成为合法的群成员。

（5）密钥提取算法（Extract）：给定用户Ui的身份信息IDi和IA的身份信息IDM，系统主密钥s和协助器的密钥sH。由PKG进行以下运算：

①计算Qi,t=H1(IDM,t)，其中t为时间段。

②计算USi,0=sQM+sHQi,0。

算法输出用户Ui的初始密钥USi,0。然后用户根据PKG产生初始密钥USi,0和签名密钥Xi计算得出USXi,0=USi,0+Xi=sQM+sHQi,0+Xi作为群成员的初始的临时密钥。

（6）协助器更新消息生成算法（UpdateM）：该算法输入(sH,IDi,IDM,t)。协助器计算t时间段的更新消息UKi,t=sH(Qi,t-Qi,t-1)，并将更新消息UKi,t发送给指定的签名者Ui。

（7）用户临时私钥更新算法（UpdateU）：给定t时间段协助器的更新消息UKi,t和t-1时间段的临时密钥USXi,t-1，计算t时间段的临时签名密钥：

USXi,t=USXi,t-1+UKi,t=sQM+sHQi,t+Xi之后删除UKi,t、USXi,t-1。

（8）签名算法（Sign）：在t时间段，对于给定的消息m∈{0,1}*，用户Ui在OA的协助下对其进行签名。

①Ui计算wi,t=hi,t(USXi,t+Di)，这里hi,t=H2(m)，并将(IDi,hi,t,wi,t)发送给OA。

②OA接收到(IDi,hi,t,wi,t)，首先根据Ui的身份信息IDi判断其是否为合法的群成员，若不合法，则拒绝提供签名帮助，若合法，则OA随机选择zi,t∈Z*q，计算Zi,t=zi,tP,δi,t=hi,tzi,tPpub，ηi,t=hi,tYi，σi,t=wi,t+δi,t+ηi,t，Vi,t=Qi+Zi,t。OA将(IDi,zi,t,hi,t,t)保存到存储列表L2，并将对消息m的签名设置为(σi,t,Vi,t)。

（9）验证算法（Verify）：验证者可以通过等式e(P,σi,t)=e(Ppub,hi,t(2QM+Vi,t))e(PH,hi,tQi,t)验证签名是否正确。

（10）打开算法（Open）：OA可以打开群签名，通过查询存储列表(L1,L2)来确定该签名是否由合法的群成员所签。

（11）示证算法（Judge）：证明在t时间段，签名(σi,t,Vi,t)是用户Ui对消息m的一个签名。OA通过计算δi,t=hi,tzi,tPpub和εi,t=σi,t-δi,t，可知εi,t是由OA和Ui合作产生的多签名，只有OA和Ui联合才能产生，因此可以判定，签名(σi,t,Vi,t)确实是Ui在t时间段对消息m的群签名。

4 安全性和性能分析

4.1 安全性分析

通过对签名方案进行分析，给出了方案九方面的安全性。下面给出具体分析。

（1）正确性

方案的正确性由两部分组成：一是验证算法的正确性，即Ui对消息m产生的群签名一定能够被验证；二是示证算法的正确性，即验证者对签名提出异议时，管理员OA运行Judge算法，验证签名是由合法的群成员所签，并确定签名者的身份。

①验证算法的正确性

由上面的验证过程可知，签名能够被正确验证。

②示证算法的正确性

验证签名(σi,t,Vi,t)确实是群成员Ui在t时间段对消息m的群签名。则OA计算δi,t=hi,tzi,tPpub和εi,t=σi,t-δi,t，并通过下面的等式证明：

由上面的验证过程可知，εi,t是IA和Ui在t时间段对消息m产生的多签名，该多签名只有OA和Ui合作才能完成，因此可得知示证算法的正确性。

（2）不可伪造性

不可伪造性指的是只有合法的群成员才能代表群体对消息进行签名。对于给定Ui在t时间段对消息m的群签名(σi,t,Vi,t)，可得知其构造过程如下：

由签名的构造过程可知，(σi,t,Vi,t)是由OA和Ui共同合作完成的多签名。由分析可知，π1是由OA和Ui共同合作完成的具有（2，2）门限性质的签名，该签名是不可伪造的；π2是Ui产生的基于身份的签名方案，该签名可证是不可伪造的；π3是OA为了保证Ui签名的匿名性随机产生的一个离散对数问题，而CDH问题在群G1上是难解的[19]，因此也是不可伪造的。即使敌手获得了管理员IA的私钥DM且能代表OA随机生成一个关于消息m的离散对数问题，也就是说，敌手能够伪造π1和π3，在敌手不能获得签名者身份私钥的情况下，由于不能伪造π2而不能伪造群签名。因此，本文提出的密钥隔离的群签名方案满足不可伪造性。

（3）匿名性

匿名性是指签名者不能从签名中识别出具体的签名者的身份。签名(σi,t,Vi,t)是Ui在t时间段对消息m产生的群签名。由（1）和（2）中签名的构造过程可知，本文提出的方案在验证过程中会涉及Ui的身份信息，但在产生签名的过程中，OA随机选择zi,t∈，计算Zi,t=zi,tP，Vi,t=Qi+Zi,t，将Ui的身份信息Qi进行掩盖，而hi,t是上的随机元素，其他元素都是群G1上的随机元素，因此满足匿名的基本要求。

在敌手具有一定的攻击能力的前提下，该签名方案仍然能够满足匿名性的要求。假设敌手攻击群成员Ui和管理员IA的私钥，同时敌手能够执行Join算法添加群成员并能撤销群成员使得管理员OA不对其提供签名帮助，敌手能够在OA的帮助下打开除目标群签名外的其他任何的群签名。对于给定的消息m，敌手随机选择两个诚实的群成员i0和i1。敌手可以得到群成员ib(b∈{0,1})在t时间段对消息m产生的群签名(σib,t,Vib,t)。敌手若能够判别出签名(σib,t,Vib,t)来自于i0或i1，则称其赢得了游戏，即解决了G1上的一例CDH问题。

假设敌手获得了Ui在t时间段临时群签名密钥USXib,t、私钥Dib和IA的私钥DMb,计算v=hib,t(USXib,t+Dib)，u=hib,tYib，ε=σib,t-v-u，Zib,t=Vib,t-Qib，因为Ppub,Zib,t∈G1，所以一定存在m,n∈，使得Ppub=mP，hib,tZib,t=nP，则：

由双向性对的非退化性可知ε=mnP，即敌手解决了G1上的一例CDH问题，而CDH问题在群G1上的是难解的，因此方案满足匿名性。

（4）可跟踪性

可跟踪性是指群管理员通过打开算法可识别出签名者的具体身份。对于Ui在t时间段对消息m产生的群签名(σi,t,Vi,t)，在群签名产生的过程中，需要向OA寻求签名帮助，而OA在为Ui提供签名帮助的时候，首先验证Ui的合法身份，若不合法则拒绝提供帮助；若合法，则提供帮助。OA在为Ui提供签名帮助的时候会将Ui的身份信息保存到存储列表中。因此，OA能够对合法群成员产生的签名进行跟踪。

可跟踪性的含义还包括在OA不提供签名帮助的情况下，敌手不能产生有效的群签名。假设敌手获得Ui在t时间段的临时签名密钥USXi,t和私钥Di，保证IA是安全可信的，根据（2）中群签名的构造过程，在Yi未知的前提下，敌手不能伪造一个被OA跟踪的群签名。这是因为Ui通过执行Join算法成为群成员，IA随机选择Xi发送给用户Ui，计算Yi=DM-Xi，将Yi发送给OA。若Ui只知道Xi，在IA可信且OA不提供签名帮助的情况下，因为CDH问题在G1上是难解的，所以Ui不能产生被OA跟踪的合法的群签名。此部分签名是Ui和OA合作完成的（2，2）门限签名[20]，即使敌手获得Ui的私钥，在OA的私钥未知的情况下，仍然不能够伪造该部分签名。

综上可知，在G1上的CDH问题难解的前提下，方案满足可跟踪性。

（5）无关联性

无关联性是指对于任意给定的一些有效的群签名，只有群管理员能够区分其中的某两个签名是否来自同一个签名者。对于群成员Ui在两个不同的时间段k和j产生的群签名 (σi,k,Vi,k)和 (σi,j,Vi,j)，假设敌手能够对两个群签名进行区分，即敌手得知了(σi,k,Vi,k)是Ui在k时间段对消息m的签名。假设敌手知道了Ui的临时签名密钥USXi,k、私钥Di和管理员IA的私钥DM，但OA必须是可信的。计算v=hi,k(USXi,k+Di),u=hi,kYi，ε=σi,k-v-u,Zi,k=Vi,k-Qi。可以证明求解(Ppub,Zi,k,hi,k,ε)是计算群G1上的一例CDH问题，而CDH问题在群G1上的是难解的。因此在群签名不被打开的情况下，判断两个不同的群签名是否是同一个签名者是困难的。

（6）不可陷害性

方案满足不可伪造性，在协助器密钥安全的情况下，只有合法的群成员才能在管理员OA的协助下产生群签名，因此满足不可陷害性。

（7）抗联合攻击

抗联合攻击是指部分群成员合谋在一起也不能产生被管理员跟踪不到的有效签名。签名者只有在群管理员OA的帮助下才能完成群签名，在为签名者提供签名帮助时，只有在确定签名者的合法身份之后才为其提供帮助。因此，部分群成员联合在一起在没有OA提供签名帮助的情况下仍然不能产生被OA跟踪到的群签名。

（8）密钥隔离安全性

假设在t时间段，敌手获得了Ui的私钥Di和临时群签名密钥USXi,t，他只能对当前时间阶段的签名造成危害。在协助器密钥安全的情况下，敌手不能从协助器获得密钥的更新消息，因而不能危害其他时间段的群签名。因此，本文提出的方案能够满足密钥隔离安全性。

（9）安全密钥更新

假设敌手已经获得了用户Ui的私钥Di。在t时间段，Ui正将其临时群签名密钥从USXi,t-1更新到USXi,t，此时敌手对Ui进行攻击，那么敌手只能获得USXi,t-1、USXi,t和更新消息UKi,t，然而敌手只能对t-1、t时间段内的签名造成危害，不能对其他时间段的签名造成威胁，因此方案满足安全密钥更新。

4.2 性能分析

本文方案首次将密钥隔离技术运用到基于身份的群签名方案中，提高了签名的安全性，减轻了密钥泄露以后带来的损失。将本文提出的基于身份的密钥隔离群签名方案与方案[15]提出的密钥隔离群签名方案和方案[18]提出的基于身份的群签名方案相比较。假设方案在有限域Zq（q是长度为170 bit的素数）的椭圆曲线上运行，(G1,+)是该椭圆曲线上一个q阶子群。G1中的元素长度为170 bit的字符串，(G2,⋅)是大小约为21020有限域Zq某个有限扩域的子群。从签名长度和算法复杂度两方面在签名长度、数乘运算、加法运算、模乘运算和双线性对次数方面对方案进行比较，见表1。

表1 签名长度和复杂度比较

通过与方案[15]比较可知，本文方案签名长度较短，且不需要模指数运算，计算较为简便。而方案[15]基于RSA和DDH假设，DDH假设在双线性对下是可验证的，不具备安全性。相对于基于RSA构造的方案，本文方案只需要进行简单的数乘和加法运算，群成员的跟踪也较为方便，不需要繁杂的零知识证明，构造相对简单。而与方案[18]比较，本文方案构造更为简单，签名长度更短，且满足密钥隔离安全性。

5 结束语

本文在基于身份的群签名的基础上提出了基于身份的密钥隔离群签名方案，解决了群签名中的密钥泄露问题，降低了密钥泄露带来的损失。方案具有较短的签名长度，对群成员的跟踪只需要搜索存储列表，满足密钥隔离安全性，提高了群签名的实用性。本文方案的不足是，OA在为签名者提供签名帮助时，必须时刻在线；任意的群成员和OA串通就可以获得IA的私钥；群成员的跟踪由OA来完成，一些存储列表也由OA完成，因此OA必须是可信的。