《基于rsa公钥密码体制的可选择可转换关联环签名-张文芳.pdf》由会员分享，可在线阅读，更多相关《基于rsa公钥密码体制的可选择可转换关联环签名-张文芳.pdf（13页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第40卷第5期 计 算 机 学 报 V0140 No52017年5月 CHINESE JOURNAL OF COMPUTERS May 2017基于RSA公钥密码体制的可选择可转换关联环签名张文芳”3 熊 丹2 王小 敏” 陈 桢”3 刘旭东”3”(西南交通大学信息科学与技术学院成都610031)(中国电子科技网络信息安全有限公司成都200233)3(西南交通大学信息安全与国家计算网格四川省重点实验室 成都610031)摘要环签名因其无条件匿名性、自发性和灵活的群结构被广泛应用于电子现金、电子投票等强匿名认证领域其中，关联环签名可以在不泄露真实签名者身份的前提下证明两个签名是否由同一人签发，因
2、此可以在保障匿名性的前提下避免签名权滥用，如重复投票、电子现金重复花费等问题然而，已有关联环签名的安全性大多数建立在离散对数困难问题基础上，且绝大多数方案因强关联性导致匿名性退化为了克服上述问题，该文提出一个基于大整数分解难题和RSA公钥密码体制的可选择关联可转换环签名方案，并给出该类环签名的形式化安全模型通过选择随机参数生成关联标签的方式，使得所提方案不仅具备强匿名性，而且环签名的关联性可由签名者自主决定此外，签名者可以在不公开秘密随机参数的前提下将环签名转换为普通数字签名，能够抵抗可转换性攻击在随机预言机模型下可证明该方案在适应性选择消息和选择公钥攻击下是存在性不可伪造的此外，性能分析表明
3、，该文方案与同类方案相比具有较高的运行效率关键词RSA公钥密码体制；环签名；选择关联性；强匿名性；可转换性中图法分类号TP309 DOI号1011897SPJ1016201701168Selectively Linkable and Convertible Ring SignatureBased on RSA Public Key CryptosystemZHANG Wen-Fan913 XIoNG Danl2 WANG XiaoMinl CHEN ZhenlLIU XuDon913”(School of Information Science and Technology，Southwest
4、 Jiaotong University。Chengdu 610031)”(China Electronic Technology Cyber Security Limited Company，Chengdu 200233)”(Key Laboratory of Information Science and National Computing Grid，Southwest Jiaotong University，Chengdu 610031)Abstract Ring signatures are widely used in strong anonymous athentication
5、environments suchas electronic cash and electronic voting，because of their unconditional anonymity，spontaneityand flexible group structuresHowever，for some special purpose，we should discriminate if twosignatures are signed by the same signerFor example，we should distinguish if a voter has castmutipl
6、e ballots and the same ecash has been repeatedly consumedTo solve the above mentiondproblems，linkable ring signatures were proposed，by which any two signatures generated by thesame person can be detected，with the premise of not disclosing the indentity of the real signerHowever，most of the existing
7、linkable ring signature schemes are based on discrete logarithmpublic key cryptosystems，and the vast maj ority of schemes only have the characteristics of weakanonymi。ty and strong linkabilityIn this paper，a selectively linkable and convertible ringsignature based on RSA public key cryptosystem was
8、proposed，and a formal security model of收稿日期：20151229在线出版日期：201610 29本课题得到国家自然科学基金(61003245，61371098)、四川省科技厅应用基础研究基-余(2015JY0182)、中央高校基本科研业务费专项基金(swJTullcx041)资助张文芳，女，1978年生，博士，副教授，主要研究方向为密码学、信息安全E-mail：wfzhangswjtueducn熊丹，女，1989年生，硕士研究生，主要研究方向为信息安全、环签名王小敏(通信作者)，男，1974年生，博士，教授，主要研究领域为信息安全、轨道交通安全工程Ema
9、il：xmwangswjtueduCD陈桢，男，1990年生，硕士研究生，主要研究方向为信息安全、基于属性的密码体制刘旭东，男，1990年生，硕士研究生，主要研究方向为环签名、基于属性的密码体制万方数据5期 张文芳等：基于RSA公钥密码体制的可选择可转换关联环签名this kind of ring signature was presentedThe scheme is proven to be unconditionally anonymous，and the linkability of the signature can be decided by the signer through
10、selecting randomparameters to generate the linkable tagBesides，in necessary occasions，the signer can convertthe ring signature into an ordinary digital signature on the premise of not revealing secret parameters，SO that he can prove himself as the real signerIt is proven that the proposed scheme can
11、 resistthe convertable attack and is existentially unforgeable against the adaptive chosen plaintext attackand the chosen public_key attack under the random oracle modelFinally，the performance analysisshows that the proposed scheme has high operating efficiencyKeywords RSA public key cryptosystem；ri
12、ng signature；selective linkability；strong anonymity；convertibility引 言2001年，Rivest，Shamir和TaumanLlo首次提出了环签名的概念，因其按照一定规则首尾相连可组成一个环状结构而得名，签名验证者可以确定签名者来自环中的某一个成员，但无法确定真实签名者的身份不同于群签名的是，环签名可以任意选择一组成员作为可能的签名者，没有群的建立过程，也不需要群管理员，并且能够保证签名者身份的无条件匿名性，这些性质使环签名在电子现金、电子选举、Ad hoe等匿名身份认证领域有着广泛应用随着环签名的提出，各种实现方案被先后提出，
13、如Dodis等人23在Eurocrypt2004上利用FiatShamir变换给出一个随机预言机模型下可证安全的环签名方案，Shacham和Waters3在PKC2007首次基于双线性映射提出一个高效环签名，2009年Bender等人L41给出第一个标准模型下可证安全的环签名随后，环签名的研究进入一个非常活跃的时期2015年Bose等人51给出一个无需随机预言机假设的定长环签名方案，Shim6提出一个具有固定数量Pairing运算的高效环签名方案，Wang等人71给出一个可引用(quotable)的环签名方案；2016年Gritti等人嘲给出一个签名长度为0(109：N)的环签名方案除了上述利
14、用大整数分解和离散对数等平均困难问题构造的环签名之外，为了抵抗量子计算攻击并降低计算复杂度，基于格、编码和多变量二次方程组(Multivariate Quadratic，MQ)难解问题的环签名也被先后提出2010年Brakerski和Kalaio提出第一个基于格中最坏问题(worst-case problem in lattice)的环签名方案，随后多个基于格中困难问题的环签名及门限环签名方案被提出10。5|文献1617基于MQ问题先后提出多变量公钥密码体制下(Multivariate Public Key Cryptosystem，MPKC)的环签名方案2007年Zheng等人181基于综合
15、解码问题给出一个环签名方案，Melchor等人口朗和Dallot等人2叩则先后给出基于编码的门限环签名方案；2016年，文献21给出一个基于LDGM(LowDensityGeneratorMatrix)码的环签名上述方案可以被看作后量子环签名方案此外，一系列具备不同特性的环签名方案也被先后提出，如门限环签名、可撤销匿名性的环签名、代理环签名和不可否认环签名等zz-26某些环境中，在保证匿名性的前提下，需要知道两个签名是否由同一签名者签发，如在电子投票中，既需要保护选民的隐私，又要避免重复投票为解决上述问题，Liu等人273提出了关联环签名(LinkableRing Signature)的概念：
16、存在有效算法可以在不泄露真实签名者身份的前提下证明两个签名由同一签名者签发通过在环签名中添加关联标签，该文给出了第一个关联环签名方案LSAG(LinkableSpontaneous Anonymous Group)，并用改造后的分叉引理证明了方案的安全性同时，作者指出关联环签名框架不具有无条件匿名性，如何设计一个具有强匿名性的关联环签名是一个尚待解决的问题2 7|此后，不同的关联环签名框架被先后提出28-35如文献28利用双线性对构造了一种GDH(Gap DiffieHellman)群上的关联环签名，签名之间的关联性由零知识协议保证；2005年，Tsang等人2鲴将可分性和关联性同时应用于门限
17、环签名，提出了可分关联门限环签名，并引入了指责关联性、“群体一指向”关联性和“事件一指向”关联性；文献30-32针对电子投票和电子现金中重复投票、重复花费等问题提出了简短关联环签名的形式化安全模型及实现方案万方数据计 算 机 学 报然而，这些关联环签名框架均引入强关联标签实现同源签名间的相互关联，若环中其他成员合作，真实签名者的身份即会暴露，因此都不具备强匿名性特点此外，如果签名者拒绝加入正确的关联标签，则整个签名无效，即签名的关联性不能由签名者自行决定针对上述问题，Liu等人361提出了一种指定验证者的关联环签名，保证所有人都能验证签名的正确性，但只有指定的验证者才能验证签名的关联性随后，C
18、how等人373提出一个第三方托管的关联环签名方案，只有关联认证机构才能关联两个环签名2008年，Jeong等人381提出了可选择关联环签名(Selective Linkable Ring Signature)，签名者可以自行决定是否使其生成的不同环签名之间具备关联性，同时通过使用随机参数生成关联标签的方式实现了签名的强匿名性和弱关联性虽然可选择关联环签名在一定程度上解决了普通关联环签名匿名性退化的问题，但现有方案大多借助离散对数困难问题进行构造，仅存在少部分基于其他NP困难问题的可选择关联环签名方案3 9|除可选择关联性外，在某些应用中(如需要为揭发者颁奖等场合)，环签名还需要具备可转换性(
19、Convertibility)，即签名者在必要时能够将环签名转化为普通的数字签名，从而证明自己为签名者本人基于不同体制的可转换环签名虽被先后提出394“，但多数方案无法抵抗可转换性攻击，即环中其他成员能够代替实际签名者进行签名转换m本文针对现有可选择关联环签名大多建立在离散对数难题基础上，大部分方案由于引入强关联标签导致匿名性退化，以及可转换环签名无法抵抗可转换攻击等问题，提出一个基于大整数分解困难问题的可选择关联可转换环签名方案与现有关联环签名大多依赖于单一困难问题不同，本文所提方案基于RSA公钥密码体制原型构建，其数学基础为大整数分解本方案通过选择随机参数生成关联标签的方法，具备可选择关联
20、性和强匿名性，同时签名者可以在不公开秘密随机参数的前提下将环签名转换为普通数字签名，能够抵抗可转换性攻击本文给出该类可选择关联可转换环签名的形式化安全模型，并在随机预言机模型下证明所提方案在适应性选择消息和选择公钥攻击下是存在性不可伪造的最后，将所提方案的性能与同类方案进行对比分析，仿真结果表明本文方案在保证匿名性的前提下具有很高的运算效率本文第2节介绍关联环签名的相关研究工作；第3节给出可选择关联可转换环签名方案的安全模型及其安全性的形式化定义；第4节提出一个基于RSA公钥密码体制的可选择关联可转换环签名方案；第5节对所提方案的正确性和安全性进行证明；第6节给出方案的性能分析和效率比较；第7
21、节利用WinNTL和OpenSSL函数库给出方案的算法实现；最后对全文进行总结2 相关工作环签名具备的匿名性(anonymity)主要分为两类：计算匿名性(computational anonymity)和无条件匿名性(unconditional anonymity)(1)计算匿名性是指方案的匿名性是基于某一数学困难问题(如离散对数问题、RSA问题、大整数分解问题、DiiHellman问题等)如果存在一个敌手能够有效地求解这一困难问题，则匿名性将会被攻破(2)无条件匿名性是指即便某一敌手拥有无限的计算能力和时间，依然无法获得签名者的真实身份，即匿名性仍然能够得到保证大多数传统的环签名都具备无条
22、件匿名性，也有一些环签名方案提供计算匿名性然而关联环签名自提出以来一直只能提供计算匿名性直到2008年，Jeong等人38才提出了一个具备强匿名性的弱关联环签名，并将关联环签名的匿名性分为两类：强匿名性(strong anonymity)和弱匿名性(weak anonymity)(1)弱匿名性已知环签名中所有环成员的公钥，只要环中所有成员不揭露自己的身份，任何人都不可能获知此环签名的真实签名者身份(2)强匿名性已知环签名中所有环成员的公钥，即便环中所有成员的私钥均被知晓，任何人依然无法得知此环签名的真实签名者身份目前绝大多数关联环签名只具备弱匿名性，仅有少数方案提供了强匿名性下面对关联环签名的
23、相关研究工作进行详细的分析和介绍关联环签名的概念由Liu等人273于2004年首次提出，主要用于一些既要保障签名者的匿名性又要避免签名者滥用签名权的场所，即关联环签名需要满足匿名性、自发性(spontaneity)和关联性(1inkability)这3个基本性质目前的研究主要通过在环签名中添加关联标签、指定关联验证者、引入第万方数据5期 张文芳等：基于RSA公钥密码体制的可选择可转换关联环签名三方权威机构等方式实现环签名的可关联性在第一类关联环签名方案中，签名者的私钥信息被嵌入关联标签中，验证者可以通过关联标签判断两个签名是否由同一个签名者产生，由于该类方案的关联标签包含了签名者私钥且签名的关
24、联性可被任何人验证，因此具有强关联性和弱匿名性LSAG方案273即为此类关联环签名，在随机预言机模型下，该方案利用改造后的分叉引理证明其在抗适应性选择明文攻击和适应性选择密钥攻击下是不可伪造的Liu等人在文献-27中还利用LSAG方案实现了可检测重复投票的电子投票协议，并进一步给出基于LSAG的(，咒)门限关联环签名方案，其时间复杂度和空间复杂度均为O(tn)2006年，Zheng等人28指出LSAG方案271的安全性仅基于DDH(Decisional Diffie-Hellman)假设，而DDH问题在GDH群上是可解的，因此将LSAG进一步扩展为GDH群上的关联环签名方案此外，Tsang等人
25、2妇于2005年提出可分(Separable)门限关联环签名及其安全模型，即使成员使用不同的密码元语和系统参数，仍能够自发组群产生有效的关联环签名，该方案的时间和空间复杂度均为O(咒)，同时文献E29还对关联性进行了细化分类，引入了指责和非指责关联性、“群体一指向”关联性和“事件一指向”关联性具备“非指责”关联性是指方案只能检测两个环签名是否由同一人生成，但如果具备“指责”关联性则可以进一步输出两个同源环签名的签名者身份“群体一指向”关联性指同一签名者利用同一群体对不同消息产生的签名之间具备关联性，“事件一指向”关联性则指签名者不论选取什么群体对事件进行签名，只要事件相同，其签名之间就具备关联
26、性随后，Fujisaki在文献34中首次提出了标准模型下可证明安全的关联环签名方案然而，上述方案均存在签名长度与群成员数量相关这一缺陷，当所选群成员数量较多时，必然导致签名长度过长，因此并不实用为了克服签名长度过长这一缺陷，Tsang等人E303利用文献E2中的短环签名构造了签名长度固定的可关联环签名方案，其安全性基于LDRSA(Link Decisional RSA)假设，同时探讨了该短关联环签名在电子投票和电子现金中的应用但Au等人E3阳通过研究指出文献30-1中关联环签名方案的安全模型存在缺陷并提出一个基于强RSA假设和强DDH假设的改进模型，给出了在新安全模型下可证明安全的签名长度固定
27、的关联环签名方案随后，其又在文献32中首次给出可撤销关联(Revokeiff_Linkability)环签名的定义和安全模型，提出一个基于身份(ID-Based)的签名长度固定的可撤销关联环签名方案，并在新安全模型下证明了该方案的安全性上述关联环签名由于加入强关联标签导致不具备强匿名性随后，研究者围绕弱关联性和强匿名性展开广泛的研究在指定验证者关联环签名中，只有指定的验证者才能将两个同源环签名进行关联，因此能够更好地保护签名者的匿名性，如文献E36-1利用零知识证明和可验证秘密共享(Verifiable SecretSharing，VSS)保证所有人都能验证签名的正确性，但只有指定群体中多于门
28、限值的验证者合作才能重构出关联标签并验证签名的关联性，因此可有效约束普通签证者的关联权限，但这种方案需要较高的计算代价且签名长度较长Chow等人口73于2006年提出“托管关联性”的概念，并利用基于身份的密码体制给出一个身份托管关联环签名方案，避免了PKI体制中复杂的公钥证书维护和管理问题所谓托管关联性，是指环签名的关联性只能被第三方托管机构验证，因此可进一步约束验证者的关联权限然而，该方案仍存在密钥托管问题并引入了计算量较大的双线性对运算随后，Tsang等人给出一个无双线性对的基于身份关联门限环签名方案3朝及其相应的短签名方案3，其安全性基于随机预言机模型下的DDH假设上述方案虽然通过约束关
29、联性的方式来增强匿名性，但仍然达不到强匿名性要求2008年，Jeong等人381首次提出“可选择”(Selective)关联环签名的概念，签名者可根据实际情况自主选择是否生成具有关联性的环签名，既可以直接生成关联环签名，也可以生成不具有关联性的普通环签名，且在不泄露身份的前提下签名者可以在事后将其生成的普通环签名进行关联该方案通过使用随机参数生成关联标签的方式实现了环签名的强匿名性和弱关联性可选择关联环签名对于保护举报者身份具有重要的应用价值例如，举报者利用可选择关联环签名先后揭发了两个秘密，且前一个秘密已被证实是可靠的，则举报者可在不泄露自己身份的前提下证明两个秘密之间的关联性，进而提高人们
30、对后一个秘密的信任程度由于可选择关联环签名具备强匿名性，因此举报者的身份即使在权威机构的合作下也不会被暴露随后，文献E393给出一个基于双线性映射的可选择关联环签名然而，已有的可选择关联环签名方案大多借助离散对数困难问题进行构造，如何构造基万方数据计 算 机 学 报于其他NP困难问题的可选择关联环签名是一个亟待研究的方向3 可选择关联可转换环签名方案安全模型31算法组成定义1 可选择关联可转换环签名由以下5个多项式时间算法(G，S，V，LV，CV)组成(1)公私钥生成算法(G)G(1)是一个概率多项式时间算法(PPT)，输入安全参数愚后，输出私钥s愚及其对应公钥p忌(2)签名算法(S)S(16
31、，m，L，sk)是一个概率多项式时间算法(PPT)，输入安全参数志，消息m，公钥集合L以及与L中某一公钥对应的私钥s愚后，输出签名仉(3)验证算法(V)V(16，m，L，盯)是一个概率多项式时间算法(PPT)，输入安全参数愚，消息Tt，公钥集合L和签名口后，输出1或者0，分别代表接受或者拒绝签名对于任意消息m和任意公钥集合L，若想验证算法V(1，m，L，s(1，n，L，sk)一1成立，要求公私钥对(sk，pk)必须是由G(1)产生的，且L是由声是组成的公钥集合(4)关联性验证算法(LV)LV(16，(L 7，m 7，叮7)，(L”，)是一个概率多项式时间算法(PPT)，当输入安全参数忌，两个公
32、钥集合L 7，L，和两对消息签名对(m7，盯7)和(仇，)后，输出1或者0，分别代表满足关联性和不满足关联性对于任意两个公钥集合L 7，L，和任意两对消息签名对(m 7，盯7)和(优”，)，若想验证算法LV(1 6，(L 7，优7，d7)，(L，)一1成立，要求L7，L，是由p忌组成的公钥集合，且(L7，m7，口7)和(L，扩，)分别满足V(1，m7，L7，口7)一1和V(1，L，)一1(5)转换性验证算法(CCV(16，m，L，盯)是一个概率多项式时间算法(PPT)，当输入安全参数忌，消息m，公钥集合L和签名盯后，输出1或者0，代表能够或不能确认签名口为环中某一确定成员的合法签名对于任意消息
33、m和任意公钥集合L，若想验证算法CV(1，m，L，盯)一1成立，要求L是由p忌组成的公钥集合，且(m，口)满足V(1，m，L，盯)一1为简洁起见，在后续算法描述中省略了安全参数愚32安全定义定义2 若可选择关联可转换环签名满足以下性质，则称此方案是安全的(1)正确性若签名者按照正确的签名算法生成签名盯，则仃通过验证算法V(1，m，L，盯)的概率为1(2)在适应性选择消息和选择公钥攻击下是存在性不可伪造设(sk。，pki)(i一1，2，7z)是由G(1kr)生成的公私钥对，kmin(k1，是2，乜)，L一p是。，础。，p尼。)，SO(m7，L7)为签名预言机当输入任意消息m7和任意公钥集合L 7
34、L，签名预言机输出一个签名口7满足V(m7，L7，盯7)一1如果对于任意一概率多项式时间算法A与签名预言机SO进行交互产生(优，L，d)一A50(L)满足(m，L，仃)没有在之前的询问一应答对中出现过，且V(m，L，口)一1概率在安全参数尼下是可忽略的，其中LL，则称可选择关联可转换环签名在抗适应性选择消息和选择公钥攻击下是存在性不可伪造的(3)强匿名性设(ski，pki)(i一1，2，72)是由G(16t)生成的公私钥对，L=户足。，夕志z，户惫。)如果对于任意L，任意消息仇以及由S(1，m，L，sk)生成的任意签名盯，对于任意算法A，输出i满足skski(i一1，2，咒)的概率仅为1n，则
35、称方案具备强匿名性(4)关联性设(ski，户志i)(i一1，2，咒)是由G(1k一)生成的公私钥对，忌一min(k。，忌2，志。)，L=声愚。，p忌。，p走。)，L7，L，任意两个消息m7，舻的对应签名为仃7一S(1，m7，L7，sk一)，一S(1，L，sk，)(其中，丌7，1，2，竹)当签名仃7，为同一用户所签时，则存在一个概率多项式时间(PPT)算法F，能以不可忽略的概率得出盯7，为同人所签；而如果签名盯7，不是由同一用户所签，则对任意概率多项式时间算法F，得出签名为同一人所签的概率是可忽略的，则称此环签名方案是关联的(5)对非签名者的不可转换性对于非签名者，如其能成功将某一合法环签名口转
36、换为一个有效的普通数字签名的概率是可忽略的，则称方案对非签名者具备不可转换性，也即非签名者无法证明自己为真实签名者4基于RSA公钥密码体制的可选择关联可转换环签名方案41初始化对于i一1，2，孢，每个用户U，任意选择两个万方数据5期 张文芳等：基于RSA公钥密码体制的可选择可转换关联环签名 1173大素数P。和qi，计算N：一Ptg r和9(Nr)一(夕i一1)(qi一1)随机选择整数8，(11Q(忌)，在时间r内伪造一个有效的签名盯，满足V(m，L，d)一1(其中，Q为一个多项式函数，k为足够大的安全参数)，即1Pr(A(L)一(m，口)：V(m，L，仃)一1)石南万则存在一个PPT算法，在
37、时间刀r内，以不可忽略的概率卢永五再知求解RsA困难问题证明 设L一夕忌。，夕忌：，夕忌。)一(N，e1)，(N。，e：)，(N。，e。)(见31节中的定义)，NrainN，N。，N。)A为一PPT敌手，能对随机预言机Hi(i一1，2，咒)最多进行qH次询问，对签名预言机SO最多进行q。次询问假设A能以不可忽略的概率e1Q(南)，在时间r内伪造一个有效的签名口，即1Pr(A(L)一(优，d)：V(m，L，盯)一1)百i豸，其中：Q为一多项式函数；qH和q。在安全参数k下仅能进行多项式次增长除了重复询问外，独立随机预言Hi输出随机结果，SO也能询问预言机Hi，并且与A的询问输出保持一致通过调用黑
38、盒子A，PPT仿真器sim能够仿真随机预言机，从而得到与每个hash函数Hi和签名预言机So一致的回答对于任一消息m，任一公钥集合LL，sire通过模拟SO，不用任何私钥，仅仅通过控制H，便能按如下步骤生成一个有效的签名口(1)首先，sire随机选择i。1，2，咒，CiRNi(2)然后，随机选择b。E。N2，rE。N2，并计算李一玎1rmodN2(3)接下来，对于i=k，忌+1，尼+2，咒一1，咒，1，2，k一1，随机选择S；ERZ，丑ERZN，计算2iCf+s?rood N：，牙：一ci+j；rood Ni，然后计算C：+lHi+1(L，辱，n，zi，牙。modNi)(i=；6k一1)(4)
39、然后，设置H(L，百，m，敬1，磊一1)一靠(5)最后，输出(f1，S1，5。，j1，矗，每，r)注意：当i一咒时，H一Hl，C一C1SO像实际签名者为U。一样返回签名A返回一个伪造签名，且同时对所有用于验证方程的规个随机预言询问均已询问过的概率不小于Q(忌) qqH-nqs ，其中，q表示所有预言机应答的可能结果的个数，因为q-q二n-一nqs值很小可忽略，所以A返回一个伪造签名，且同时对所有用于验证方程的佗个随机预言询问均已询问过的概率不小于1Q(尼)因此，当A伪造一个有效签名时，必定询问过与验证方程一致的咒个对Hi的询问，记这，z个询问为X。X，xi，1i。i。i。当S0对A的询问生成签
40、名时，S0对H；的询问可忽略对于一个由A成功伪造的签名盯，考虑被A询问过的所有用于验证的询问集合假设XX，X为第一次出现满足验证的咒个询问，其中1i，i：，i。设k满足：Xi。Ht(L，百，m，c女一1+se6k一-modN一1，C女一1+5k一1roodN一1)即Xi，对应于验证中对H。的询问称k为环签名盯的缺口如果i，一z，则记A伪造的签名口为(z，愚)一伪造签名，也即第一次出现与所有的验证相关的询问是第z次询问，且缺口等于k在仿真开始时sim选择一对(z，尼)，其中lzqH，1k咒，则sire能以不小于1(咒(qH+nq。)Q(是)的概率确保自己的猜测是正确的，并且接收X：。一H。(L，
41、百，m，一，魏一。)，XiH+l(L，亭，m，z，氖)当询问x礓发生时(询问Xt+，一H+1(L，李，m，C女+sroodN，C+s-eroodN)一H+l(L，每，m，戤，氟)也已经发生，因为与验证相关的询问已经全部发生)，sire返回C作为H(L，百，m，一1，氟一1)的值此时，由于C。，砟，磊均为已知，如果A能成功伪造环签名，则将输出满足关系式z。一C+se；k rood N。和君；一C；+ji modN。的S和j，即A能够在不知道(靠，百，N；)对应私钥cp(N。)的前提下从s e；kroodN和jiroodNt中求解出S。和；。，这与RSA问题求解是困难的相矛盾因此，不可伪造性得证
42、证毕定理3(强匿名性) 本文方案具备强匿名性证明 假设签名GL(m)一(c1，Sl”，5。，jl，一，元，百)是由签名者仉生成的一个合法签名由签名过程可知，“+。一H女+1(L，百，m，u，口)亭随机分布于万方数据5期 张文芳等：基于RSA公钥密码体制的可选择可转换关联环签名(1，9(NK)中，“和秽随机分布于ZN。中，且H；：0，1)+一ZNL，所以C。+，在ZI中具有随机性对于i一是+1，尼+2，咒一1，咒，1，2，是一1，C：+1一Hi+1(L，百，m，ci+se，rood N：，C。+j；roodN。)，且SiRZN，最RZN，Hi：0，1)+一Z，因此C川也均匀随机分布于Z中由上可知
43、，对于所有的i一1，2，以，Ci均随机分布于zN中所以签名盯中的C。随机分布于Zk中另外，对于签名盯L(m)一(c1，S1，S。，i1，L，e，r)中的Si和i：，除了S。和i。是由计算所得外，其余Si和ji都是从Z中随机选取的而S。一(甜一C。)噍roodN，氕一(口一靠)V女1 rood N，又因为“，口也是从ZM中随机选择的，且上面已证得C。RZ；，所以S。和i。也随机分布于ZN，中因此，对于任一固定的n(L，m)，(s1，s2，岛)和(j1，j2，j。)分别有|N。i一1种可能的解，且这些解具有等概性关联标签百一a；-1 rmod p(N)，其中(1a妒(M)，1r妒(N；)，且a。和
44、r均由签名者随机选取，所以(百，r)随机分布于(1，够(NK)中综上可知，乱(m)一(cl，S1，S。，j1，瓦，百)中的每一参数都具有随机性，所以对于任意算法A，由签名信息口输出某一i，满足skski(i一1，2，咒)的概率仅为1In，因此本方案具备强匿名性证毕定理4(关联性) 对于某一签名乱(m)一(f，S。，S。，j。，j。，每)，若伪造者A能以不可忽略的概率产生与盯。(m)关联的环签名乱(m7)一(c：，s：，s：，S：，j：，百)，则存在一个PPT算法能以不可忽略的概率求解RSA困难问题证明 定理2已证明，非环成员者不可能伪造合法环签名所以只需考虑环成员伪造与已知签名关联的环签名而环
45、成员只拥有一个自己的私钥，而无法知道群中其他成员的私钥假设已知签名为OL(m)一(c1，S1，S。，j1，瓦，季，r)，A伪造的与盯。(m)关联的环签名为OL(m 7)一(C：，S：，S：，；，j：，百，r)因为A为环成员，所以其只知晓自己的私钥与定理2证明方法相同，假设A能成功伪造一个与盯。(仇)关联的环签名OL，(m7)，则将输出j：满足2。一“+j：8roodN女，其中，磊，靠均为已知，即A能够在不知道(李，N。)对应私钥9(N。)的情况下从或roodN。中求解出i；，这与RSA问题求解是困难的相矛盾因此，关联性得证 证毕定理5(对非签名者的不可转换性) 在随机预言模型下，若大数分解是困
46、难的，则本方案对非签名者具备不可转换性证明 假设某一合法签名为d。(m)一(c，S。，s。，；。，j。，百，r)，其中茸一“f1 r只有签名者可知口f1的值，且nfl随机分布于(1，9(N。)中当签名者给出验证AProofE(巩，口f1)：e女一订1 rood9(Nt)八弓一口flrmod9(N女)证明其拥有知识(巩，院f1)后，验证者验证成立后，便能确认签名确实为阢所签另外，在大整数分解难题下，由百和r求解口f1是困难的，所以对非签名者来说，证明其拥有知识(巩，乜f1)是困难的，即将签名转换成普通签名的概率是可忽略的，因此本方案对非签名者具备不可转换性 证毕6性能及效率对比本节通过与现有典型
47、关联环签名方案的性能比较给出所提方案的运行效率评估表1对算法中用到的变量及运算符进行了定义表1 相关变量及运算符定义符号 定义竹MJEECMECp环成员总数模乘运算的时间复杂度模逆运算的时间复杂度模指数运算的时间复杂度椭圆曲线上倍点运算的时间复杂度椭圆曲线上双线性映射运算的时间复杂度表2给出本文方案与现有的典型关联环签名方案272 93133q43 638。3 94胡的匿名性及效率比较结果为了更直观地对各个方案的计算量进行对比，此处根据文献46推算出的不同运算之间的等价换算关系对表2中的签名、验证以及总计算量进行换算根据文献46，假设163比特的椭圆曲线密码算法与1024比特的RSA、DL或DiffiHellman密码体制算法具有相同的安全强度则有E240M，E824ECM，E32ECP，J12M可以推出E240M，ECM2913M，ECP75M，I12 M对数据进行换算后的结果详见表3中的T(S)估计值、T(V)估计值和T(S，V)估计值为了更清晰地说明表中各方案的效率，取M一15ts，以720，并将表3中的总时间复杂度显示于图1中从表3和图1可以看出，在签名及验证的总时问复杂度上，当环成员总数孢较小时(咒8)，本文方案效率仅次于文献43方案的效率，当竹较大时万方数据