一种基于群签名的安全电子拍卖方案

书书书收稿日期：２００７１０１７基金项目：国家自然科学基金资助（６０４７３０２７，６０７７２７３６）；国家“８６３”高技术研究发展计划项目基金资助（２００７ＡＡ０１Ｚ４３５）作者简介：张跃宇（１９７８），男，讲师，西安电子科技大学博士研究生，Ｅｍａｉｌ：[e-mail]．一种基于群签名的安全电子拍卖方案张跃宇，李　晖，王育民（西安电子科技大学计算机网络与信息安全教育部重点实验室，陕西西安　７１００７１）摘要：基于线性ＣｒａｍｅｒＳｈｏｕｐ加密方案提出了一种新的短群签名方案，该方案的完全匿名性抗适应性选择密文攻击，允许攻击者在攻击匿名性时打开签名．以该群签名为构造模块设计了一种安全的电子拍卖方案，在相同的安全性要求下，签名长度、群公钥长度、签名密钥长度、注册密钥长度和追踪密钥长度指标与基于ＲＳＡ问题的同类拍卖方案相比，分别约是它的１／１４，１／７，１／１７，１／４０和１／４．与投标者是抗选择明文攻击完全匿名的基于双线性对的拍卖方案相比，新方案投标者具有抗选择密文攻击完全匿名，而通信量和计算量与前者相当．关键词：电子拍卖；群签名；线性ＣｒａｍｅｒＳｈｏｕｐ加密；完全匿名性中图分类号：ＴＮ９１８．１　　文献标识码：Ａ　　文章编号：１００１２４００（２００８）０４０６１４０６犛犲犮狌狉犲犲犾犲犮狋狉狅狀犻犮犪狌犮狋犻狅狀狊犮犺犲犿犲犫犪狊犲犱狅狀狋犺犲犵狉狅狌狆狊犻犵狀犪狋狌狉犲犣犎犃犖犌犢狌犲狔狌，犔犐犎狌犻，犠犃犖犌犢狌犿犻狀（ＭｉｎｉｓｔｒｙｏｆＥｄｕｃａｔｉｏｎＫｅｙＬａｂ．ｏｆＣｏｍｐｕｔｅｒＮｅｔｗｏｒｋａｎｄＩｎｆｏｒｍａｔｉｏｎＳｅｃｕｒｉｔｙ，ＸｉｄｉａｎＵｎｉｖ．，Ｘｉａｎ　７１００７１，Ｃｈｉｎａ）犃犫狊狋狉犪犮狋：　ＢａｓｅｄｏｎＬｉｎｅａｒＣｒａｍｅｒＳｈｏｕｐｅｎｃｒｙｐｔｉｏｎ，ａｎｅｗｓｈｏｒｔｇｒｏｕｐｓｉｇｎａｔｕｒｅｉｓｐｒｏｐｏｓｅｄ．Ｔｈｅａｎｏｎｙｍｉｔｙｐｒｏｐｅｒｔｙｏｆｔｈｉｓｓｃｈｅｍｅｉｓｓｅｃｕｒｅａｇａｉｎｓｔａｄａｐｔｉｖｅｃｈｏｓｅｎｃｉｐｈｅｒｔｅｘｔａｔｔａｃｋｓ（ＣＣＡ２），ｗｈｉｃｈａｌｌｏｗｓｔｈｅａｄｖｅｒｓａｒｙｔｏｏｐｅｎｔｈｅｓｉｇｎａｔｕｒｅｗｈｅｎｔｒｙｉｎｇｔｏｂｒｅａｋｔｈｅａｎｏｎｙｍｉｔｙｎｏｔｉｏｎ．Ｕｓｉｎｇｔｈｉｓｇｒｏｕｐｓｉｇｎａｔｕｒｅａｓａｂｕｉｌｄｉｎｇｂｌｏｃｋ，ａｓｅｃｕｒｅｅｌｅｃｔｒｏｎｉｃａｕｃｔｉｏｎｓｃｈｅｍｅｉｓｄｅｓｉｇｎｅｄ．Ｕｎｄｅｒｔｈｅｓａｍｅｓｅｃｕｒｉｔｙｃｏｎｄｉｔｉｏｎｓ，ｔｈｅｓｃｈｅｍｅｈａｓｓｉｚｅｓｏｆｓｉｇｎａｔｕｒｅ，ｇｒｏｕｐｐｕｂｌｉｃｋｅｙ，ｓｉｇｎｉｎｇｋｅｙ，ｒｅｇｉｓｔｅｒｋｅｙａｎｄｔｒａｃｉｎｇｋｅｙ１／１４，１／７，１／１７，１／４０ａｎｄ１／４ｔｈｏｓｅｏｆｔｈｅｓｃｈｅｍｅｂａｓｅｄｏｎｔｈｅＲＳＡｐｒｏｂｌｅｍ．Ｃｏｍｐａｒｅｄｗｉｔｈｔｈｅｐａｉｒｉｎｇｂａｓｅｄｓｃｈｅｍｅｉｎｗｈｉｃｈｔｈｅｂｉｄｄｅｒ’ｓａｎｏｎｙｍｉｔｙｉｓＣＰＡｓｅｃｕｒｅ，ｔｈｅｃｏｍｐｌｅｘｉｔｉｅｓｏｆｃｏｍｍｕｎｉｃａｔｉｏｎａｎｄｃｏｍｐｕｔａｔｉｏｎｉｎｔｈｉｓｐａｐｅｒａｒｅａｐｐｒｏｘｉｍａｔｅｔｏｔｈｏｓｅｉｎｔｈｅｆｏｒｍｅｒ，ｂｕｔｔｈｅＣＣＡ２ｆｕｌｌａｎｏｎｙｍｉｔｙｏｆｂｉｄｄｅｒｓｉｓａｃｈｉｅｖｅｄｉｎｔｈｉｓｎｅｗｓｃｈｅｍｅ．犓犲狔犠狅狉犱狊：　ｅｌｅｃｔｒｏｎｉｃａｕｃｔｉｏｎ；ｇｒｏｕｐｓｉｇｎａｔｕｒｅ；ｌｉｎｅａｒＣｒａｍｅｒＳｈｏｕｐｅｎｃｒｙｐｔｉｏｎ；ｆｕｌｌａｎｏｎｙｍｉｔｙ随着科技的发展和保密系统的完善，尤其是网络技术的发展，拍卖这种交易正逐渐从传统模式转向基于Ｉｎｔｅｒｎｅｔ的电子模式———电子拍卖．电子拍卖是一种特殊的现货交易方式，一个由拍卖群体决定价格及分配的过程，投标者的身份在拍卖期间不能泄漏，在拍卖结束后，只有中标者的身份泄漏．群签名的概念是由Ｃｈａｕｍ和Ｈｅｙｓｔ提出的［１］，在群签名方案中，群成员可以匿名签名，并且其成员身份可以被验证，在发生争执时，可以通过打开签名揭示签名者的真实身份．群签名具有一些特殊的性质，例如匿名性、无关联性、可追踪性、抗合谋攻击以及不可伪造性等，因此一些文献［２～８］认为群签名技术是设计电子拍卖方案的一个有效工具．其中，文献［６］利用的是可转换群签名方案；文献［３～５］中的电子拍卖方案基于ＣＳ９７群签名［９］，签名的长度约７ｋＢｙｔｅ，计算量大约１４００００次模乘，拍卖方案效率很低；文献［２］利用的是ＡＣＪＴ群签名方案［１０］，该签名方案是可证明安全的，抗联合攻击，但签名长度依然很长，并且存在密钥管理问题，在拍卖效率上也不是很高．上述５个方案都是基于ＲＳＡ问题．２００４年，Ｂｏｎｅｈ等人基于双线性对和判２００８年８月第３５卷　第４期　西安电子科技大学学报（自然科学版）犑犗犝犚犖犃犔　犗犉　犡犐犇犐犃犖　犝犖犐犞犈犚犛犐犜犢　Ａｕｇ．２００８Ｖｏｌ．３５　Ｎｏ．４定线性假设提出短群签名方案［１１］（简称ＢＢＳ方案），签名长度为１５３３ｂｉｔ，计算量与前面的方案相比较小．文献［７］利用ＢＢＳ方案提出一个新的拍卖方案，虽然拍卖效率大大提高，但依然存在问题，即ＢＢＳ方案是抗选择明文攻击（ＣＰＡ）完全匿名的，对Ｂｅｌｌａｒｅ等人于２００３年给出的完全匿名性定义［１２］进行了弱化，在试图攻破匿名性定义时对攻击者作了限制，不允许提问打开预言机，即不能打开签名．笔者首先对ＢＢＳ方案进行了改进，使用线性ＣｒａｍｅｒＳｈｏｕｐ加密［１３］替换线性加密方案［１１］，实现了一种抗选择密文攻击（ＣＣＡ２）完全匿名的群签名方案，允许攻击者在攻击匿名性时打开签名．１　电子拍卖１．１　电子拍卖模型　　一般来说，拍卖主体由若干投标者、拍卖行、注册中心以及卖方组成．拍卖过程分为以下４个步骤：（１）拍卖登记：拍卖开始之前每个投标者首先向注册中心提交拍卖申请，注册中心验证申请的合法性后，分配给每个合法的投标者一个秘密的序列号．（２）提交标价：拍卖行宣布拍卖开始后，每个合法的投标者提交他们的标价（公开竞价或者秘密投标）给拍卖行．一般情况下，卖方要给出一个最低价位，投标者的标价不能低于最低价位．（３）结束投标：经过一段时间后，拍卖行宣布投标结束（即不再接收标价）．（４）宣布结果：拍卖行宣布最高价位者获胜并且公开获胜标价．最后，中标者支付等量的货币，卖者将货物给中标者．１．２　电子拍卖应具有的安全性质一个电子拍卖方案通常应具有如下安全性质：（１）投标者的匿名性：不能从投标的签名上获得投标者的身份；（２）可追踪性：在宣布中标结果后中标者不能否认他／她所投的标；（３）不可伪造性：不能以一个有效的签名伪造标书；（４）可验证性：任何人都可以验证投标的签名，以确认投标人是否有效；（５）不同拍卖间的无关联性：同一投标者在不同拍卖中的投标不可以联系；（６）标价保密性：只有中标价公开，其他标价保密．２　复杂度假设与犆犆犃２完全匿名的群签名２．１　双线性群　　设犌１＝＜犵１＞，犌２＝＜犵２＞和犌３是阶为素数狆的循环群；ψ是犌２到犌１的可计算同构，ψ（犵２）＝犵１；犲为可计算的映射犲：犌１×犌２→犌３．犲具有两个性质，一是双线性，即对所有的狌∈犌１，狏∈犌２及犪，犫∈犣，有犲（狌犪，狏犫）＝犲（狌，狏）犪犫；二是非退化性，即犲（犵１，犵２）≠１，则称群（犌１，犌２）是一对双线性群［１４］．２．２　ＳｔｒｏｎｇＤｉｆｆｉｅＨｅｌｌｍａｎ（ＳＤＨ）假设设犌＝＜犵＞是阶为素数狆的循环群，对所有的概率多项式时间算法犃，概率犘［狉犃（犵，犵γ，…，犵（γ狇））（＝犵１／（γ＋狓），）狓∧狓∈犣］狆是可忽略的，其中γ∈犣狆［１５］．２．３　判定线性假设设犌＝＜犵＞是阶为素数狆的循环群，狌，狏，犺，η∈犚犌且犪，犫∈犚犣狆，对所有的概率多项式时间算法犃，概率犘狉［犃（狌，狏，犺，狌犪，狏犫，犺犪＋犫）］－犘狉［犃（狌，狏，犺，狌犪，狏犫，η］是可忽略的［１１］．２．４　ＣＣＡ２完全匿名的群签名笔者提出一种ＣＣＡ２完全匿名的群签名方案，它是以下所述电子拍卖协议的重要构造模块．设双线性群犌的生成元为犵，ＳＤＨ假设在（犌，犌）上成立，且线性假设在群犌上成立，Ｈａｓｈ函数犎：｛０，１｝→犣狆，ＣＣＡ２完全匿名的群签名方案由以下算法组成：（１）密钥生成算法ＫｅｙＧｅｎ（狀）　算法中的输入参数狀表示群成员的个数．选择狕１，狕２，狕３∈犚犣狆，令犵１，５１６第４期　　　　　　　　　　　　　　张跃宇等：一种基于群签名的安全电子拍卖方案犵２，犵３∈犌，使犺１←犵狕１１犵狕３３，犺２←犵狕２２犵狕３３，并令ω＝犵γ，其中γ∈犚犣狆，γ仅有密钥分发者知道．对１≤犻≤狀，选择狓犻∈犚犣狆，令犃犻←犵１／（γ＋狓犻），得到关于用户犻的ＳＤＨ对（犃犻，狓犻）．群公钥犽ｇｐ为（犵，犵１，犵２，犵３，犺１，犺２，ω），用户犻的私钥犽ｇｓ［犻］为（犃犻，狓犻），群管理员用于追踪签名的私钥犽ｇｍ为（狕１，狕２，狕３）．（２）签名算法Ｓｉｇｎ（犽ｇｐ，犽ｇｓ［犻］，犕）　该算法的参数为群公钥犽ｇｐ，用户犻的私钥犽ｇｓ［犻］和待签消息犕∈｛０，１｝．用户犻首先选择指数α，β∈犚犣狆，计算犃犻的线性ＣｒａｍｅｒＳｈｏｕｐ加密犜１＝犵α１，犜２＝犵β２，犜３＝犵α＋β３，犜４＝犃犻犺α１犺β２，然后计算两个辅助值δ１＝狓犻α，δ２＝狓犻β．接着随机选择盲化值狉α，狉β，狉狓犻，狉δ１，狉δ２∈犚犣狆，计算犚１←犵狉α１，犚２←犵狉β２，犚３←犵狉α＋狉β３，犚５←犜狉狓犻１·犵－狉δ１１，犚６←犜狉狓犻２·犵－狉δ２２，犚７←犜狉狓犻３·犵－狉δ１－狉δ２３，犚４←犲（犜４，犵）狉狓犻·犲（犜４，犵）狉狓犻·犲（犺１，犵）－狉δ１·犲（犺１，ω）－狉α·犲（犺２，犵）－狉δ２·犲（犺２，ω）－狉β，将上述值与消息犕进行Ｈａｓｈ后得犮←犎（犜１，犜２，犜３，犜４，犚１，犚２，犚３，犚４，犚５，犚６，犚７，犕），然后计算狊α＝狉α＋犮α，狊β＝狉β＋犮β，狊狓犻＝狉狓犻＋犮狓犻，狊δ１＝狉δ１＋犮δ１，狊δ２＝狉δ２＋犮δ２∈犣狆，最后，输出签名σ←（犜１，犜２，犜３，犜４，犮，狊α，狊β，狊狓，狊δ１，狊δ２）．（３）验证算法Ｖｅｒｉｆｙ（犽ｇｐ，犕，σ）　在此算法中，给定群公钥犽ｇｐ、消息犕和群签名σ，验证该签名是否为知识（犃犻，狓犻，α，β）的有效签名．验证者重推犚１～犚７：珟犚１←犵狊α１／犜犮１，珟犚２←犵狊β２／犜犮２，珟犚３←犵狊α＋狊β３／犜犮３，珟犚５←犜狊狓犻１／犵狊δ１１，珟犚６←犜狊狓犻２／犵狊δ２２，珟犚７←犜狊狓犻３／犵狊δ１＋狊δ２３，珟犚４←（犜４，犵）狊狓犻·犲（犺１，犵）－狊δ１·犲（犺１，ω）－狊α·犲（犺２，犵）－狊δ２·犲（犺２，ω）－狊β（·犲（犵，犵）／犲（犜４，ω））－犮．然后验证犮＝犎（犜１，犜２，犜３，犜４，珟犚１，珟犚２，珟犚３，珟犚４，珟犚５，珟犚６，珟犚７，犕），如果验证成功则验证者接受．（４）签名打开算法Ｏｐｅｎ（犽ｇｐ，犽ｇｍ，犕，σ）　群管理员在签名打开算法中输入群公钥犽ｇｐ＝（犵，犵１，犵２，犵３，犺１，犺２，ω）、消息犕、群签名σ＝（犜１，犜２，犜３，犜４，犮，狊α，狊β，狊狓，狊δ１，狊δ２）和群管理员私钥犽ｇｍ＝（狕１，狕２，狕３），执行该算法揭示此签名的签名者．在验证σ是有效签名后，对线性ＣｒａｍｅｒＳｈｏｕｐ加密犜１，犜２，犜３，犜４计算犃←犜４／（犜狕１１犜狕２２犜狕３３）．群管理员根据用户列表查找犃所对应的用户犃犻即可确定签名者身份．由于在上述群签名方案中所使用的加密方案，即线性ＣｒａｍｅｒＳｈｏｕｐ加密是ＣＣＡ２安全的，因此群签名方案是ＣＣＡ２完全匿名的，与ＢＢＳ方案一样，本节的群签名也具有完全可追踪性．上述两个性质的证明方法与ＢＢＳ方案类似，具体的证明过程可参见文献［１１］．在利用群签名构造的电子拍卖方案中，群管理员对应于拍卖管