一种可撤销匿名性的环签名方案黄大威;杨晓元;陈海滨【摘要】环签名提供了匿名发布信息的有效方法,现有环签名方案存在不可追踪签名者真实身份的问题.基于身份密码体制和双线性对技术,提出了一种环签名方案,方案除了满足无条件匿名性和不可伪造性,还满足可撤销匿名性,必要时由PKG(Private Key Generator)充当仲裁验证者,达到定位真实签名者的目的.【期刊名称】《计算机工程与应用》【年(卷),期】2010(046)024【总页数】3页(P88-89,200)【关键词】环签名;身份密码体制;可撤销匿名性;双线性对【作者】黄大威;杨晓元;陈海滨【作者单位】武警工程学院电子技术系网络与信息安全武警部队重点实验室,西安,710086;武警工程学院电子技术系网络与信息安全武警部队重点实验室,西安,710086;西安电子科技大学计算机网络与信息安全教育部重点实验室,西安,710071;武警工程学院电子技术系网络与信息安全武警部队重点实验室,西安,710086【正文语种】中文【中图分类】TP3091 概述1984年，Shamir提出了基于身份密码系统的概念[1]。
在此密码系统中，用户的公钥是与其身份紧密相关的字符串，如电子邮件地址、用户名等；由PKG （Private Key Generator）负责给每个用户发放与其身份相对应的私钥。
文献[1]中提出了基于身份的签名方案。
2001年，Boneh和Fraklin[2]利用双线性对给出了第一个可行的基于身份的加密系统。
环签名由Rivest、Shamir和Tauman[3]在2001年正式提出，以实现对消息的完全匿名签名。
接收方只能确认签名来自于某个群体，而不能确认具体签名者。
考虑到具体应用环境的需要，人们对基本的环签名做了适当扩展，如基于身份的环签名[4]、关联性环签名[5]等。
在电子拍卖中，一方面需要保护投标者的隐私权，另一方面又得保证投标者在中标以后不能抵赖。
现有许多环签名方案在提供匿名性的同时却不能定位真实签名者的身份，针对这个问题，基于身份密码体制和双线性对技术提出了一个环签名方案，在满足无条件匿名性和不可仿造性的同时，必要时可以由身份密码体制中的PKG 担当一个仲裁验证者，完成匿名性的撤销，达到定位真实签名者身份的目的。
2 预备知识2.1 双线性映射设G1和G2分别是阶为大素数q的循环加法群和乘法群，P是G1的生成元。
随机数a，b，c∈Zq，假设离散对数问题在G1和G2中都是难解的。
双线性对是这两个循环群之间的一个映射e：G1×G1→G2，满足如下性质：（1）双线性性：e（aP，bQ）=e（P，Q）ab，其中a，b ∈ Zq；（2）非退化性：存在P，Q ∈ G1，使e（P，Q）≠1；（3）可计算性：存在有效的算法计算e（P，Q），其中P，Q ∈ G1。
2.2 困难问题（1）离散对数问题（DLP）：任取P，Q ∈ G，找整数n ∈ ，使满足Q=nP；（2）计算性Diffie-Hellman问题（CDHP）：已知P、aP、bP，计算abP。
文中假定DLP、CDHP是计算困难的。
2.3 环签名分叉引理环签名分叉引理[6]：设一个环签名方案，安全参数为k，环成员数目为n。
A为一个输入仅仅是公开数据的概率多项式时间图灵机，A向随机预言机请求的数目为Q，向签名预言机请求的签名数目为W。
假设在时间T内，A以概率ε≥产生一个有效的环签名 (m，R，R，...，R，12n h1，h2，...，hn，σ)，其中VQ.n表示 Q 个元素的 n 置换数目，VQ.n=Q(Q-1)(Q-2)...(Q-n+1)，哈希值hi=H(m，Ri)。
假设环签名能够在时间Ts内，并且在不知道环的任何私钥的情况下以不可区分的概率被仿真，那么就存在另一个概率多项式时间图灵机，该图灵机产生两个有效的环签名(m，R1，R2，...，Rn，h1，h2，...，hn，σ)，(m，R1，R2，...，Rn，h′1，h′2，...，h′n，σ′)满足：3 基于身份的可撤销匿名性环签名在基于身份密码体制中，给定双线性对系统(G1，G2，e，q，P)，G1和G2分别是阶为大素数q的循环加法群和乘法群，P是G1的生成元。
映射e：G1×G1→G2是两个循环群之间的一个双线性映射。
Setup：PKG随机选择s∈Zq*作为其主私钥，计算Ppub=sP作为其主公钥，计算P′pub=sPpub。
给定哈希函数H1和H2，H1:{0，1}*→G1，而H2:{0，1}*→Zq，则系统的公开参数 params={G1，G2，e，q，P，Ppub，P′pubH1，H2}。
Keygen：用户将身份ID∈{0，1}*送PKG，PKG设定用户公钥为QID=H1(ID)，私钥为SID=sQID，PKG通过安全信道将私钥送给用户。
用户的身份集合为L={ID0，ID1，…，IDn-1}。
Sign：（1）签名者k随机选择n-1个成员作为环成员，随机选择t∈Zq*，计算P1=tP。
（2）对于i∈(k+1，...，n-1，0，...，k-1)，任选ai∈Zq*，计算Ri=aiP，ci=H2(L‖m‖Ri)，R′i=aiPpub。
（3）对于k，任选a∈Zq*，计算（4）生成签名，公开签名σ=(L，m，R0， R1， ...， Rn-1，U，S)。
Verfiy：（1）签名验证：对∀i∈{0，1，...，n-1}计算验证等式e(P，S)，若e(P，S)等于e(Ppub，V+U)，则签名成立。
（2）可撤销匿名性：当需要撤销匿名性时，验证者向PKG发送仲裁验证请求，对于任意环成员k1，PKG计算如果等式成立，则确认签名者的真实身份为k1。
4 安全性分析（1）正确性（2）无条件匿名性因为ai，i∈{0，1，...，n-1}\k是在Zq*上随机选择的，所以Ri、R′i是在G上均匀分布的，计算出的ci也是在G上均匀分布的。
签名者随机选择a、t也就是说Rk=aP，R′k=aP2- Σi\kciQIDi也是均匀分布的。
所以说Ri、R′i不会泄露任何有关签名者的信息。
接下来考虑签名S是否会泄露签名者的信息，从S=可以得到为了确认是否是签名者，唯一的方法是验证即验证假如IDk是真实的签名者，那么只需要验证然而对于环中任一成员 IDj，j∈{0，1，...，n-1}，等式都是成立的，也就是说签名S不会泄露任何有关签名者的信息，所以说方案满足无条件匿名性。
（3）不可伪造性设挑战者C拥有(P，aP，bP)，想求出abP，这是一个CDHP问题。
攻击者A向挑战者C请求预言机应答，C随机产生应答。
挑战者C给予攻击者A系统公钥Ppub=bP，b为系统私钥，b对于C是未知的。
挑战者C存储身份哈希值的请求-应答对，C抛硬币w∈{0，1}，当w=0时，随机选择di计算QIDi=diaP，由于a、b都是未知的，其私钥不能得到。
假设攻击者A能够以不可忽略的概率仿造一个有效的环签名σ=(L，m，R0，R1，...，Rn-1，U，S)，相应的随机预言为根据环签名分叉引理[6]，存在另一个概率多项式的挑战者C能够产生两个环签名σ=(L，m，R0，R1，...，Rn-1，U，S)，σ′=(L，m，R0，R1，...，Rn-1，U，S′) 满足① 对某一j∈{1，2，...，n}，cj≠ c′j；②任取i∈{1，2，...，j-1，j+1，...，n}，ci=c′i。
因此对上面两个式子计算得到SIDj=(S-S′)/(cj-c′j)。
由上面的结论挑战者C能够以不可忽略的概率计算私钥SIDj=(S-S′)/(cj-c′j)=abP，从而以不可忽略概率解决了CDHP问题，所以说方案在随机预言机模型下是不可仿造的。
（4）可撤销匿名性真实签名者选择的随机数a和t对于任何人都是不可知的，包括PKG。
又因为只有PKG拥有主私钥s，所以只有他可以计算P*=sP1=tPpub，对于用户身份集合中的任一成员k1，可以验证等式只有真实的签名者能够满足上述等式，进而完成了可撤销匿名性，定位了真实签名者的身份。
5 结束语对于满足特殊性质的环签名的研究是当前数字签名领域的研究热点之一。
基于身份密码体制提出了一个环签名方案，通过仲裁验证者PKG在必要时撤销环签名匿名性，解决了不能定位真实签名者的问题。
【相关文献】[1]Shamir A.Identity based cryptosystems and signature schemes[C]//Proceedings of Crypto’84 on Ad vances in Cryptology，1984.[S.l.]：Springer-Verlag，1985：47.[2]Boneh D，Franklin M.Identity-based encryption from the weil pairing[C]//LNCS 2139：Advances in Cryptology，2001：213-229.[3]Rivest R L，Shamir A，Tanman Y.How to leak a secret[C]//Boyd C.LNCS 2248：Proc of Asia Crypt01.[S.l.]：Springer-Vedag，2001：552-565.[4]Zhang Fang-guo，Kim Kwangjo.ID-based blind signature and ring signature from pairings[C]//LNCS 2501：Advances in Cryptology—AsiaCrypt 2002：533-547.[5]Mao H A，Chow S S M，Susilo W，et al.Short linkable ring signaturerevisited[C]//LNCS 4043：EuroPKI2006.Berlin：Springer-Verlag，2006：101-115.[6]Herranz J，Saez G.Forking lemmas for ring signature scheme[C]//Indocrypt.Berlin：Springer-Verlag，2003.。
