2023年6月24日发(作者：)

ANewID-basedGroupSignatureSchemefromBilinearPairingsXiaofengChen1,FangguoZhang2andKwangjoKim11InternationalResearchcenterforInformationSecurity(IRIS)InformationandCommunicationsUniversity(ICU),58-4Hwaam-dongYusong-ku,Taejon,305-732KOREA{crazymount,kkj}@2SchoolofInformationTechnologyandComputerScienceUniversityofWollongong,NSW2522Australiafangguo@ethattraditionalID-basedsystemsfrompairingsseemunsuitapaperweproposenewewID-basedsystems,ifdishonestKGCimpersonatesanhonestusertocommunicatewithothers,theusercanprovideaproofoftreacheryoftheKGCafter-wards,rmore,weproposeagroupsignatureschemeunderthenewsystems,eofthegrouppublickeds:Groupsignature,Bilinearpairings,ID-basedcryptography.1IntroductionGroupsignature,introducedbyChaumandvanHeijst[11],canverifythesignaturewithagrouppublicr,itiscomputationalhardtodecidewhethertwodiffofgroupsignatureschemes[2,8,12,13,22]havebeenpresentedaftertheChaumandvanHeijst’r,mostofthemaremuchinefficientforlargegroupsbecausethegr,newmemberadditionandrevocationrequirere-issuingallmembers’sch[9]presentedthefirstefficientgroupsignatureschemesforlargegroupsinwhiseetal[1]proposedapr-basedgroupsignatureschemeisfirstlyproposedbyPark,KimandWon[21].Theschemeismuchinefficient:thelengthofthegrouppublickeyand2signatureareproportionaltothesizeofthegroup;moreprecisely,rmore,MaoandLim[20]ndJan[27]r,itisuniversallyforgeable[17]andnotcoalition-resistant[16].Recently,thebilinearpairings,namelytheWeilpairingandtheTatepairingofalgebraiccurves,haveinitiatedsomecompletelynewfieldsincryptography,makingitpossibletorealizecryptographicprimitivesthatwerepreviouslyun-knownorimpractical[6,7].Moreprecisely,theyareimportanttoolsforcon-structionofID-basedcryptographicschemes[4,6,15,24,28].However,Itisstillanopenprsonsareasfollows:Firstly,,thetrustedthirdparty,calledKGC,ly,thepublickeyIDofausershouldnotre-vealhis/herrealidentityinformr,ifweuseanarbitrarystringasthepublickey[3],aninherentproblemistrly,amembercandenyhissignaturebecauseKGnowswhoindeedgeneratesthecemple,givenapublickey“h80fef6je59”,whocanprovideaproofthatthepublickeyisgeneratedbyKGCorthemembers?So,ItseemsthatthetraditionalID-basedsystemsfrompaperwefirstlypstingwithpreviousschemes,weneverasystems,ifthedishonestKGCimpersonationanhonestusertosignadocument,theusercanprovideaproofthattheKGCisdishonest,proposeagrtofthepaperisorganizedasfollows:Tion5,urityandeffiy,concludingremarkswillbemadeinSection7.2GroupSignatureInthissectionweintroducethedefifisignatureschemeisadigitalsignatureschemeconsistedofthefollowingfourprocedures:3–Setup:Oninputasecurityk,theprobabilisticalgorithmoutputstheinitialgrouppublickeyYandthesecretkeySofthegroupmanager.–Join:Aprotocolbetweenther’soutputisamembershipcertificateandamembershipsecret.–Sign:Aprobabilisticalgorithmthatoninputagrouppublickey,amem-bershipcertificate,sisthegroupsignatureSigofm.–Verify:AnalgorithmtakesasinputthegrouppublickeymathcalY,thesignatureSig,themessagemtooutput1or0.–Open:Thedeterministicalgorithmtakesasinputthemessagem,thesigna-tureSig,thegroupmanager’ssecretkeyStoreturn“Identity”or“failure”.Asecuregroupsignaturemustsatisfythefollowingproperties:–Correctness:SignaturesproducedbyagroupmemberusingSignmustbeacceptedbyVerify.–Unfrogeability:Onlythegroupmemberscansignmessagesonbehalfofthegroup.–Anonymity:Givenavalidsignature,itiscomputationallyhardtoidentifythesignerforanyoneexceptthegroupmanager.–Unlinkability:Decidingwhethertwodifferentvalidsignatureswerecomputedbythesamegroupmemberiscomputationallyhardforanyoneexceptthegroupmanager.–Traceability:Thegroupmanagerisalwaysabletoopenavalidsignatureandidentifythesigner.–Exculpability:Neitherthegroupma,thegroupmanagerorcolludeswithsomegroupmem,themembershouldresponsibleforavalidsignaturethathedidnotproduce.–Coalition-resistance:Acolludingsubsetofgroupmembers(evenifcomprisedofthewholegroup)cannotproduceavalidsignaturethatthegroupmanagercannotopen.–Efficiency:Theefficiencyofgroupsignatureisbasedontheparameters:thesizeofthegrouppublickey,thelengthofthegroupsignaturesandtheefficiencyofthealgorithmsandprotocolsofthegroupsignatures.3PreliminaryWorksInthisSection,wewillbrieflydescribethebasicdefinitionandpropertiesofbilinearpairingsandGapDiffipresentID-basedpublickeysettingfrompairings.43.1BilinearPairingsLetG1beacyclicadditivegroupgeneratedbyP,whoseorderisaprimeq,,bbeelements∗methatthediscretelogarithmproblems(DLP)earpairingsisamape:G1×G1→G2withthefollowingproperties:ar:e(aP,bQ)=e(P,Q)ab;-degenerate:ThereexistsPandQ∈G1suchthate(P,Q)=1;able:Thereisanefficientalgorithmtocomputee(P,Q)forallP,Q∈G1.3.2GapDiffie-HellmanGroupLetG1beacyclicadditivegroupgeneratedbyP,whoseorderisaprimeq,assumethattheinversionandmultiplicationinG1canbecomputedeffifiteLogarithmProblem(DLP):GiventwoelementsPandQ,tofind∗,suchthatQ=gern∈ationDiffie-HellmanProblem(CDHP):GivenP,aP,bPfora,b∈∗,onDiffie-HellmanProblem(DDHP):GivenP,aP,bP,cPfora,b,c∈∗Zq,todecidewhetherc≡G1aGapDiffie-HellmanGroupifDDHPcanbesolvedinpolynomialtimebutthereisnopolynoupcanbefoundinsupersingularellipticcurveorhyperellipticcurveoverfinitefield,edetails,see[6,10,15].3.3ID-basedSettingfromBilinearPairingsTheID-basedpublickeysystems,introducedbyShamir[23],allowsomepublicinformationoftheusersuchasname,addressandemailetc.,vat-basedpublickeysettingfrombilinearpairingscanbeimplementedasfollows:LetG1beacyclicadditivegroupgeneratedbyP,whoseorderisaprimeq,earpairingsisamape:G1×G1→finetwocryptographichashfunctionsH1:{0,1}∗→ZqandH2:{0,1}∗→G1.∗–Setup:KGCchoosesarandomnumbers∈ZqandsetPpub=-terpublishessystemsparametersparams={G1,G2,e,q,P,Ppub,H1,H2},andkeepsasthemaster-key,whichisknownonlyhimself.5–Extract:Ausersubmitshis/putestheuser’spublickeyasQID=H2(ID),andreturnsSID=sQIDtotheuserashis/herprivatekey.4NewID-basedSystemswithoutTrise,r,itwillbedifficulttofictsasthegroupmanagerofagroup,ore,themostimportantthinsection,wepreseystems,KGCisassum1beaGapDiffie-Hellmangroupofprimeorderq,earpairingsisamape:G1×G1→finethreecryptographichashfunctionsH1:{0,1}∗×G1→ZqandH2:{0,1}∗×G1→G1.4.1NewID-basedPublickeySettingfromBilinearPairings[Setup]∗KGCchoosesarandoms∈ZqandsetsPpub=temspublicparametersareparams={G1,G2,e,q,P,Ppub,H1,H2,}.KGCkeepsssecretlyasthemaster-key.[Extract]Ausersubmitshis(orher)identityinformationIDandauthenticateshimself∗(orherself)rthenrandomlychoosesanintegerr∈putestheuser’spublickeyQID=H2(ID||T,rP)andsendsSID=sQIDtotheuserviaasecurechannel,r’plicity,wedonotdiscussthisproblemhere.4.2NewID-basedsignatureschemefromBilinearPairingsRecently,ChaandCheon[10]premeisnotonlyeffipaper,wepremecanberegardedastheextendedversionofChaandCheon’ethatthemessagetobesignedism.[SigningProtocol]–Supposethesigner’omlychoosesaninteger∗a∈ZqandcomputesU=aQID.–ThesignercomputesV=rH2(m,U).–Thesignercomputesh=H1(m,U+V).–ThesignercomputesW=(a+h)(U,V,W,T,rP)isthesignatureofthemessageofm.[Verification]TheverifierfirstlycomputesQ=H2(ID||T,rP),H2(m,U),h=H1(m,U+V).Heacceptsthesignatureifthefollowingequationshold:e(W,P)=e(U+hQ,Ppub)e(V,P)=e(H2(m,U),rP)ore,thesignerfirstlyprovedthatidentityIDindeedcorrespondstorP,whichisensuredbytheKGC’esignerprovedthatheknowsrwithoutrevealinganyinformationofr.[Tracingprotocol]ConsiderthefollowingimpersonationattackbythedishonestKGC:SupposeKGC(orcolludeswithadishonestuser)(orthey)candoasfollows:∗–KGCrandomlychoosesanintegerr′∈ZqandletQID′=H2(ID||T,r′P).–Hethenperformstheabovesigningprotocolforthemessagem.′′′′–Output(U,V,W,rP).Becausee(W,P)=e(U′+hQID,rP+Ppub),e(V,P)=e(H2(m,U),rP)andQID′=H2(ID||T,r′P),KGCforgeda“valid”r,theusercanprovideaprooftoconvincethatthesignatureisforgedbyKGC,whichissimilartoCA-basedsystems.1HefirstlysendsQID=H2(ID||T,rP)andrPtothearbiter,andthenheprovidesa“proof”that1′′′′′′IntheCA-basedsystems,CAalsocanforgeauser’scertifir,theusercanaccusethedishonestCAbecausethereexisthistwodifferent“valid”certifiore,CA-basedsystemsreachGirault’strustedlever3.7heknowssQIDbyusingthecommoncoefficientproofofknowledgeproto-col:e(sQID,P)=e(QID,Ppub).Iftheequationholds,identityIDcorrespondstotwodifferentr′natureschemeystems,Visthe“real”regardedasacertifiGCisnotatrustedparty,ersarycanknowthetargetuser’,ifhecancomputeVforamessagem,hecansuccessfullyforgeasignatureoftheuser’iderthefollowinggame:ethei-thinputofqueryis(mi,U)andhegetsthecorrespondingsignatureVi,here1≤i≤y,heoutputsanewpair(m,V).WesaythattheadversarywinsthegameifrPisnotqueriedande(V,P)=e(H2(m,U),rP).IfthereexistsanalgorithmA0foranadaptivelychosenmessageattacktoourschemewithanon-negligibleprobability,wecanconstructanalgorithmA1asfollows:–chooseanintegeru∈{1,2,···,k}.DefineSign(H2(mi,U))=Vi.–Fori=1,2,···,k,A1respondstoA0’squeriestoH2andSign,whilefori=u,A1replacesmuwithm.–A0outputs(mout,Vout).–Ifmout=mandthesignatureVisvalid,A1outputs(m,U,V).Otherwise,atuisrandomlychosen,,sinceH2isarandomoracle,theprobabilitythattheoutputofA0isvalidwithoutqueryofH2(m,U)2(m,U)=bP,weobtainV=,atthetargetuserisrandomlychosen,wecandeducethatoursigna-tureschemeissecureagainstonexistentialadaptivelychosenmessageandIDattacks.⊓⊔5ProposedID-basedGroupSignatureSchemeInthisSection,ethereexistsahierarchicalID-basedsystem[14].IfthegroupmanagerisnotaKGC,orewejustconsiderthecasethatthegroupmanagerisaKGC.8[Setup]serwithidentityIDwhogetshisprivatekeySIDfromtheKGCisa“potential”groupmember.2ThegrouppublickeyY={G1,G2,e,q,P,Ppub,H1,H2}.KGCcomputesauser’nlyusedforordinarysignature.[Join]Whenauserlaterwantstobea“real”memberofthegroup,heandKGCperformtheJoinProtocolasfollows:–Theuserrandomlychoosesxi∈Zqfori=1,2,···,sendsrxiP,xiP,rP,IDandSIDtoKGC.–IfSID=sH2(ID||T,rP)ande(rxiP,P)=e(xiP,rP),KGCsendstheuserSi=sH2(T,rxiP)fori=1,2,···,isetheprotocolisterminated.3–Theuser’smembercertificatesare(Si,rxiP)andhisprivatesigningkeysarerxi,herei=1,2,···,k.–KGCaddsrxiP,xiP,rP,IDtothememberlist.[Sign]Tosignamessagem,theuserrandomlychoosesacertainsigningkeyandcorrespondingmembercertificateandthencomputesthefollowingvalues:––––∗U=aH2(T,rxiP)forrandomlychosenintegera∈Zqandcertaini.V=rxiH2(m,U).h=H1(m,U+V).W=(a+h)(U,V,W,T,rxiP)validperiod,theverifiercomputesQ=H2(T,rxiP),H2(m,U),h=H1(m,U+V).Heacceptsthesignatureifthefollowingequationshold:e(W,P)=e(U+hQ,Ppub)e(V,P)=e(H2(m,U),rxiP)[Open],therearesomeuserswhogetstheprivatekeyfromtheKGCjustforordinarysignatureandtheywillnevertobethe“real”dsnottoverifySID=sH2(ID||T,rP)fortheuserswhobecomethegroupmembersimmediately.9Givenavalidgroupsignature,rcannotdenyhissignaturebecauseKGCcanprovideaproofthatitisindeedtheuser’ssignature:e(rxiP,P)=e(xiP,rP)e(SID,P)=e(H2(ID||T,rP),Ppub)Also,KGCcannotmisattributeasignaturetoframetheuserunlesshecancomputebPgivenp,aPandrPwhichsatisfies:a≡rbmodqWedefinethisproblemtheReversionofComputationDiffie-HellmanProblem(RCDHP),eisanadversaryA0(withoutcolludingwithKGC)canforgeamembercertificatewithtimetandanon-negligibleprobabilityǫ,thenwecansolveCDHPinG1atmostwithtimetandanon-negligibleprobabilityǫ.erthefollowinggame:ethei-thinputofqueryis(T,riP)andhegetsthecorrespondingcertificateSi,here1≤i≤y,heoutputsanewpair(rP,S).A0winsthegameifrPisnotqueriedande(S,P)=e(H2(T,rP),Ppub).IfA0outputsavalidpair(rP,S).LetH2(T,rP)=aP,Ppub=edCDHPinG1forS=-interactiveprotocolunderlyingthesignatureschemesisanhonest-verifierzero-knowledgeproofofknowledgeofamembercertifirictourattentiontheproofofknowledgepartandweusethetechniqueof[1].Weshowthattheknowledgeextractorcanrecoverthemembercertifi(U,V,W,T,rxiP)and(U,V′,W′,T,rxiP)-fineh=H1(m,U+V).Becausee(W,P)=e(U+hH2(T,rxiP),Ppub),wehaveW=s(U+hH2(T,rxiP))4Proof:GivenP,aP,bP,supposewecansolveRCDHPinG1,thenwecanobtainb−=(ab)b−1P,wecangetabPfromaPandb−,,aP,bP,letQ=bP,soP=b−ewecansolveCDHPinG1,sowithQandb−1Qwecangetb−,b−canobtainab−1PfromaPandb−,wesolveRCDHPinG1.10Similarly,wehaveW′=s(U+h′H2(T,rxiP)).So,weobtainsH2(T,rxiP))=(h−h′)−1(W−W′)Notethate(rxiP,P)=e(xiP,rP),i.e.,nercannotdenyhissignaturebecausehisSIDsatisfies(SID,P)=e(H2(ID||T,rP),Ppub)-basedgroupsignatureschemefrombilinearpthatourschemesatisfiesallthesecuritypropertieslistedinDefinition1.–Correctness:Itistrivial.–Unfrogeability:Eventhe“potential”ntheassumptionthatH1andH2arerandomoracles,itcanbeeasilydeducedbythetheorem3.–Anonymity:Sincexiisrandomlychosen,rxiPrevealsnoidentityinforma-tionoftheusertoanyoneexceptKGC.–Unlinkability:GivenrxiPandrxjP,itiscomputationallyhardtodecidetheycorrespondencethesamerPwithoutknowingxiPandxjP.–Traceability:KGCcanopenanyvalidgroupsignaturebecausehecanprovideazero-knowledgeproofthatthesignerindeedproducesthesignature.–Exculpability:Fromthetheorem1wecaneasilydeduceneitherthegroupm,thegroupmanagerorcolludeswithsomegroupmemberscannotmisattributeavalidgroupsignaturetoframeacertainmembersinceoneperiodTcorrespondencesonlyoneuniquerP.–Coalition-resistance:Fromthetheorem2and3wecandeducethatacollud-ingsubsetofgroupmembers(evenifcomprisedofthewholegroup)cannotproduceavalidsignaturethatthegroupmanagercannotopen.6.2EfficiencyThesizeofthegrouppublicorithmsandprotocolsofthegroupsigna-turesareeffir,theusercanonceapplymanymembershipcertificatescorrespondingtodifferentsigningkeys,whichissimilartotheideaof“trusteetokens”[18].Therefore,theueaisalsousedforsecrethandshakesagreements[3].6.3ComparisonwithTwoPreviousGrouollowingtables,“independent,linear”denotesthatthenumberisisindependentorlinearinthenumberofgroupmembers.11Scheme[8]Scheme[1]ProposedSchemeDoubleDLPStrongRSACDHPRootDLPDDHPAnonymityComputationallyComputationallyComputationallyIdentificationbyGMbyGMbyGM(KGC)InclusionofnewmembersYesYesYesSystemCA−basedCA−basedID−basedNumberofcertificateOneOneManyLengthofgrouppublickeyFixedFixedFixedLengthofsignatureFixedFixedFixedComisonwithtwopreviousgroupsignatureschemesPropertiesAssumption7ConcludingRemarksThesalientpropertiesofgroupsignaturemakeitattractiveforplentyofapplica-tionsinelectroniccommerce[19,25,26].InthispaperweproposenewID-proposeanID-beofthegrouppublickerawbackthatausopenproblemtodesignaly,Bel-lare,MicciancioandWarinschi[5]esignase,sch,,,Apracticalandprovablysecurecoalition-resistantgroupsignaturescheme,AdvancesinCryptology-Crypto2000,LNCS1880,pp.255-270,Springer-Verlag,se,,Someopenissuesandnewdirectionsingroupsignatures,FinancialCryptography1999,LNCS1648,pp.196-211,Springer-Verlag,z,,r,ers,n,,Secrethandshakesfrompairing-basedagreements,Proceedingofthe2003IEEESympo-siumonSecurityandPrivacy,pp.180–196,o,,,,Efficientalgorithmsforpairings-basedcryptosystems,AdvancesinCryptology-Crypto2002,LNCS2442,pp.354-368,Springer-Verlag,e,chi,Foundationsofgroupsignatures:formaldefinations,simplifiedrequirements,andaconstructionbasedongeneral12assumptions,AdvancesinCryptology-Eurocrypt2003,LNCS2656,pp.614-629,Springer-Verlag,in,Identity-basedencryptionfromtheWeilpairings,Ad-vancesinCryptology-Crypto2001,LNCS2139,pp.213-229,Springer-Verlag,,,m,ShortsignaturesfromtheWeilpairings,AdvancesinCryptology-Asiacrypt2001,LNCS2248,pp.514-532,Springer-Verlag,sch,Efficientandgeneralizedgroupsignatures,AdvancesinCryptology-Eurocrypt1997,LNCS1233,pp.465-479,Springer-Verlag,r,Efficientgroupsignaturesschemesforlargegroups,AdvancesinCryptology-Crypto1997,LNCS1294,pp.410-424,Springer-Verlag,,Anidentity-basedsignaturefromgapDiffie-Hellmangroups,PublicKeyCryptography-PKC2003,LNCS2567,pp.18-30,Springer-Verlag,jst,Groupsignatures,AdvancesinCryptology-Eurocrypt1991,LNCS547,pp.257-265,Springer-Verlag,en,Newgroupsignatureschemes,AdvancesinCryptology-Eurocrypt1994,LNCS950,pp.171-181,Springer-Verlag,en,Ontheefficiencyofgroupsignaturesprovidinginformation-theoreticanonymityenisch,AdvancesinCryptology-Eurocrypt1995,LNCS1233,pp.465-479,Springer-Verlag,erg,HierarchicalID-BasedCryptography,AdvancesinCryptology-Asiacrypt2002,LNCS2501,pp.548–566,Springer-Verlag,,Efficientidentitybasedsignatureschemesbasedonpairingss,Proc.9thWorkshoponSelectedAreasinCryptography–SAC2002,LNCS2595,Springer-Verlag,pp.310-324,,Onthedifficultycoalition-resistanceingroupsignatureschemes(II),TechniqueReport,LCIS-99-6B,,,Cryptanalysisoftwogroupsignatureschemes,Infor-mationSecurity1999,LNCS1729,pp.271-275,Springer-Verlag,,TrusteeTokens:simpleandpracticalanonymousdigitalcointracing,FinancialCryptography1999,LNCS1648,pp.33-43,Springer-Verlag,skays,,Groupblindsignatures:Ascalablesolutiontoelectroniccash,FinancialCryptography1998,LNCS1465,pp.184-197,Springer-Verlag,,CryptanalysisinprimeordersubgroupofZn,AdvancesinCryptology-Asiacrypt1998,LNCS1514,pp.214-226,Springer-Verlag,,,ID-basedgroupsignature,ElectronicsLetters,33(19),pp.16163-1617,en,Howtoconveranydigitalsignatureschemeintoagroupsignauresheme,InSecurityProtocolsWorkshop1997,pp.177-190,Springer-Verlag,,Identity-basedcryptosystemsandsignatureschemes,AdvancesinCryptology-Crypto1984,LNCS196,pp.47-53,Springer-Verlag,,AnidentitybasedauthenticatedkeyagreementprotocolbasedontheWeilpairings,.,Vol.38,No.13,pp.630-632,i,ki,AnAnonymousElectronicBiddingProtocolBasedonNewConvertibleGroupSignatureScheme,ACISP2000,LNCS1841,pp.10-12,Springer-Verlag,,Groupsignaturesandtheirrelevancetoprivacyprotectingofflineelec-troniccashsystems,ACISP1999,LNCS1587,pp.228-243,Springer-Verlag,,AnovelID-basedgroupsignature,Internationalcomputersymposium,workshoponcryptologyandinformationsecurity,pp.159-164,,ID-basedblindsignatureandringsignaturefrompairings,AdvancesinCryptology-Asiacrypt2002,LNCS2501,pp.533-547,Springer-Verlag,2002.