基于群签名的公平电子拍卖方案

基于群签名的公平电子拍卖方案∗孟键马传贵（信息工程大学信息工程学院，河南郑州，450002）摘要:本文基于一个群签名方案及可验证秘密共享，设计了一个新的密封投标的电子拍卖系统，利用群签名的性质，系统具有可保护投标人的投标价和防止中标人抵赖的特点；由于我们利用了高效的群签名方案使得协议具有步骤简略，计算量小等特点，使得本协议具有很高的效率。关键词：电子拍卖;投标；群签名中图分类号：TP393.08文献标识码：AAfairelectronicauctionbaseongroupsignatureMENGjian,MAchuan-gui(InstituteofInformationEngineering,InformationEngineeringUniversity,ZhengZhou450002,China)Abstract:Afairelectronicauctionsystemisproposed,whichisbasedonanefficientandprovablegroupsignature.Thenewprotocolprotectstheprivacyofthebidders,andthewinnercannotrepudiatehisbid.Itismoreefficientthanothersbyusingaefficientgroupsignatureschemes.Keywords:electronicauction;bid；groupsignature引言电子拍卖是电子商务的重要组成部分，也是电子商务中极为活跃的一个方面。常见的拍卖方式大概有四种类型：价格递增式拍卖或英式拍卖，价格递减式拍卖或荷兰式拍卖，密封式拍卖及第二价位拍卖。电子拍卖的安全要求[3]主要包括：（1）公平。应由出价昀高的投标者中标，中标者必须支付规定的价格；（2）保密。除中标信息外，所有的其他投标信息应当保密；（3）匿名。除中标者的信息外，所有其他的投标者信息应当保密。文献[4]基于群签名技术和shamir门限方案，设计了一个适于分布式松耦合广播,预约系统使用的安全电子拍卖协议,协议不仅保证了投标者对所投价位的不可否认性和匿名性，而且保证了拍卖代理对接收标书的不可否认性.文献[5]利用群签名与可验证的秘密共享方案设计了一个密封投标的电子拍卖协议。本文基于新的更安全高效的群签名在文献[5]的基础上给出一些改进，具有步骤简略，计算量小，安全性更高等特点，使得本协议具有很高的效率。本文所提出的新的电子拍卖方案是:我们选取T为注册中心，m个人为拍卖代理，其中我们保证不诚实的代理个数不超过t-1个，n个投标者通过向T申请成员证书，m个投标代理通过分布式密钥生成方案生成共享密钥，投标时，投标人将标价进行加密和签名并发送给投标代理，代理共同将标价解密并发送给T；由于群签名的匿名性及不可伪造性，我们可以保证通过投标人对加密的标价的签名，任何人都不可能知道投标价所对应的人；而且通过公钥加密，我们能够保证在不诚实的代理不超过t－1的条件下，其他任何人不可能知道投标人的投标价，昀后我们利用群签名的不可抵赖性，我们可以看到中标的投标人不能抵赖自己的身份，从而达到满足电子投标的特点，在协议中，我们利用了[1]中的知识签名方案，在达到完全安全的前提下,使得在协议的运行中步骤更加简略，效率也更加高。新的电子拍卖系统是基于Ateniese等的群签名方案，其中有关基于离散对数的知识签名和强RSA假设等问题请参照[1].基本工具：参数：取1ε，安全参数k,21,,λλpl满足2)(21++kλελ，pl42λ。定义区间∗基金项目：国家自然科学基金重大项目（No.90104035）、河南省自然科学基金（No.0211011300）[]212122,22λλλλ+−=Γ，Gl为群G的阶的bit长度，满足GGllG2||21≤−。我们取H为防联合碰撞的hash函数H：k*{0,1}{0,1}→。定义1取Ggy∈,，(){}{}()11,01,0,++±×∈klkGscε，我们假设有消息m，签名者选取{}()klGr+±∈ε1,0，计算c和s，有()mggyHcr||||||=，cxrs−=。其中()myggyHccs||||||=为对离散对数yxglog=的知识签名，我们把它设为：spk{}()mgyαα=:定义2取Ghgyy∈,,,21，(){}{}()11,01,0,++±×∈klkGscε，签名者选取{}()klGr+±∈ε1,0，计算()mhghgyyHcrr||||||||||||21=，s=r-cx.其中()myhyghgyyHccscs||||||||||||2121=为对21loglogyyxhg==的知识签名。我们把它记为spk{}()mgygyααα=∧=21:定义3取Ghgyyz∈,,,,21，(){}{}(){}()121211,01,01,0,,2++++±×±×∈klkkpsscελε，选取{}()kr+±∈21,01λε，{}()klpr+±∈221,0ε，计算()mhhghhgyzHcrrr||||||||||||||2212121=，)2(1111λ−−=xcrs，222cxrs−=。其中()myhzhghhgyzHccscscs||||||||||||||221111221λ−=为对yxh2log2=及211xxhgz=的指数的知识签名。我们把它记为spk(){}()mhyhgzββαβα21:,=∧=系统建立我们取T为可信的注册中心，负责投标人的注册，公布投标价位，并在昀后确定中标人的身份；取m个拍卖代理，分别为mppp,,,21Λ，他们负责接受投标人的标书，并确定每一轮的昀高投标价；有n个投标人，分别为nBBB,,,21Λ，我们假设不诚实的拍卖代理不超过t个。系统公开参数取1ε，安全参数k,21,,λλpl满足2)(21++kλελ，pl42λ。定义区间[]212122,22λλλλ+−=Γ，我们取H为防联合碰撞的hash函数H：k*{0,1}{0,1}→。T：生成参数n’=pq,p=2p’+1,q=2q’+1,p’,q’,p,q都是大素数，a,h,0a,m,g是QR（n）中的素元，且保证他们为底的离散对数是不可求的，并选取∗∈''qpRzx，把xgy=modn’作为其公钥，此时我们看到群公钥为（n’,a,0a,y,g,h）.相对应的私钥为（p’,q’,x）.注册：每一个投标人都要向T注册，每一个iB选取Γ∈ix，计算ixiaC=modn’U=SPK[ixiaC=:,βα]iB将iC和U发送给T，T通过签名知识验证，如果错误则停止，如果正确T计算()()exeiiaaaCAi1010==modn’并将iA发送给iB。iB接受到iA后，通过eixAaai=0验证iA的正确性，如果不正确，就向T报错。如果正确，就接受iA，ix为其私钥。共享密钥生成：各个投标代理利用分布式密钥生成方案[6]生成各自的密钥is及公钥y’，类似iB，iP也向T发送iC和U，T通过验证后将证书iA发送给iP。投标：iB选取pl2}1,0{∈ω，得ωyATi=1modn’，ωgT=2modn’,iB将标价w通过T的公钥加密E（w）,然后运用群签名对E（w）进行签名()()()()(){}())(2222/:,112012121wEgTyaaTSPKVkkee+++++−∧=∧==λελλελββααβα将其和1T，2T发送给jP，其中我们为了达到容错的目的，使得每一个iB向每一个jP发送。jP可通过签名的知识证明验证其身份及其密文的正确性，然后t个代理可在一起恢复秘密S，可解得w，通过比较可得到昀大投标值，将1T，2T，w一同发送给T，T计算xiTTA21/=modn’.可得出昀终中标者，再将iA和1T，2T，V，w公布即可，所有人都可验证。安全性分析:在此方案中，我们应用了群签名及公钥加密，使得投标人的标书既具有保密性又具有认证性，以及我们运用的秘密共享的安全性保证了在投标过程中不会被泄漏，也不会发生一个投标人的标书被攻击者伪造或替换的情况。其次，在投标过程中我们通过一个安全的秘密共享方案把投标人的标书在m个投标代理中分享，在相互勾结的拍卖代理不超过t－1的前提下，任何拍卖代理不可能知道投标人的标价，保证了标书对投标代理的保密性。在诚实的拍卖代理不少于t个的前提下，即使t－1个代理相互勾结，在不知道投标人的投标价的前提下，他们也不能操纵拍卖过程；在中标人的身份及中标价公布后，任何投标人都可验证其正确性；在中标人的身份及其中标价公开后，由于还公开了有关的参数，这些参数导致中标人无法抵赖自己是真正的投标者。效率分析：我们把本协议和[5]相对比可以看到，在[5]中其利用的是[2]的群签名的方法，是对离散对数，双重离散对数，及e次根的离散对数的知识签名，通过分析我们可以看到在注册及共享密钥生成时，其时间复杂度时一样的；可是在投标时，由于其利用的是对双重离散对数，及e次根的离散对数的知识签名，我们假设n，m为同一数量级时，可以看到其时间复杂度为O（3t），而在本协议中复杂度为O（2t），所以说基于[1]的签名方案，我们的效率更高。总结:本文主要是在现有电子拍卖方案的基础上，结合了可验证的群签名，达到了保持签名者的匿名性，保护了投标者的投标价，防止了拍卖代理之间相互结合作弊，在公布投标人及投标价后，具有不可抵赖性，使得中标人无法抵赖。在方案中，利用了[1]中的较好的群签名技术，使得本协议效率远远高于其他方案。文献:[1]GiuseppeAteniese,JanCamenisch,MarcJoye,andGeneTsudik,APracticalandProvablySecureCoalition-ResistantGroupSignatureSchemecrypt’2000[c],vol1880,Springer-Verlag,2000,255-270.[2]CAMENISCHJ,STADERM.EfficientGroupSignatureSchemesforLargeGroups[A].AdvancesinCryptology-Crypto’97[C].SpringerVerlog,1997.[3]BOYDC,MAOW.SecurityIssuesforElectronicAuctions[R].HPLabsTechnicalReport,2000.[4]姬东耀，王育民一个基于群签名的安全电子拍卖协议ACTAELECTRONICASINICA,VoL.30No.1Jan.2002[5]苏云学，祝跃飞，闫丽萍一个利用群签名的电子拍卖协议ComputerApplicationsVol.25No.1Jan.2005[6]GennaroR,JareckiS,KrawczykH,RabinT.Securedistributedkeygenerationfordiscrete-logbasedcryptosystems[A].InEUROCRYPT’99[C],J.Stern(Ed.),Springer-Verlag,Berlin,1999作者简介：孟键（1981－）男，北京市，信息工程学院，硕士研究生，研究方向：信息安全。通讯地址：河南省郑州市1001信箱7410分箱；邮编：450002邮箱：[e-mail]马传贵，男，1962.4，山东菏泽，教授，研究方向：代数组合、群论、密码学及信息安全。