Efficient identity based ring signature

EfficientIdentityBasedRingSignature⋆ShermanS.M.Chow⋆⋆,S.M.Yiu,andLucasC.K.HuiDepartmentofComputerScienceTheUniversityofHongKongPokfulam,HongKong{smchow,smyiu,hui}@cs.hku.hkAbstract.Identity-based(ID-based)cryptosystemseliminatetheneedforvaliditycheckingofthecertificatesandtheneedforregisteringforacertificatebeforegettingthepublickey.Thesetwofeaturesaredesirableespeciallyfortheefficiencyandtherealspontaneityofringsignature,whereausercananonymouslysignamessageonbehalfofagroupofspontaneouslyconscriptedusersincludingtheactualsigner.Inthispaper,weproposeanovelconstructionofID-basedringsignaturewhichonlyneedstwopairingcomputationsforanygroupsize.Theproposedschemeisproventobeexistentialunforgeableagainstadaptivechosenmessage-and-identityattackundertherandomoraclemodel,usingtheforkinglemmaforgenericringsignatureschemes.Wealsoconsideritsextensiontosupportthegeneralaccessstructure.Keywords:Identity-basedsignature,ringsignature,bilinearpairings,efficiency,realspontaneity,generalaccessstructure,anonymity1IntroductionRingsignatureisagroup-orientedsignaturewithprivacyconcerns:ausercananonymouslysignsamessageonbehalfofagroupofspontaneouslyconscriptedusersincludingtheactualsigner.Anyverifiercanbeconvincedthatthemessagehasbeensignedbyoneofthemembersinthisgroup,buttheactualsignerremainsunknown.However,thetheoryofringsignaturefacestwoproblemswhenitcomestoreality.Intraditionalpublickeyinfrastructure(PKI),thepublickeyisusuallya“random”stringthatisunrelatedtotheidentityoftheuser,sothereisaneedforatrusted-by-allcertificateauthority(CA)toassurethe⋆ThisresearchissupportedinpartbytheAreasofExcellenceSchemeestablishedundertheUniversityGrantsCommitteeoftheHongKongSpecialAdministrativeRegion(HKSAR),China(ProjectNo.AoE/E-01/99),twograntsfromtheResearchGrantsCounciloftheHKSAR,China(ProjectNo.HKU/7144/03EandHKU/7136/04E),andtwograntsfromtheInnovationandTechnologyCommissionoftheHKSAR,China(ProjectNo.ITS/170/01andUIM/145).⋆⋆correspondingauthor2ShermanS.M.Chow,S.M.Yiu,LucasC.K.Huirelationshipbetweenthecryptographickeysandtheuser.Asaresult,anyverifierofasignaturemustobtainacopyoftheuser’scertificateandcheckthevalidityofthecertificatebeforecheckingthevalidityofthesignature.Inringsignature,notonlytheverifiermustverifyallthepublickeysofthegroup.Thesignermustdosoaswellorhis/heranonymityisjeopardized(considertheextremecasethatallcertificatesusedareindeedinvalidexceptthesigner’sone).Thecommunicationandthevalidationofalargenumberofpublickeysgreatlyaffecttheefficiencyofthescheme.Moreover,realspontaneityisnotalwayspossibleforringsignatureundertraditionalPKI.Thesignercannotspontaneouslyconscriptuserswhohavenotregisteredforacertificate.Identity-based(ID-based)ringsignaturesolvedtheseproblems:thepublickeyofeachuseriseasilycomputablefromastringcorrespondingtothisuser’sidentity(forexample,anemailaddress).Thispropertyavoidsthenecessityofcertificates,andassociatesanimplicitpublickeytoeachpersonovertheworld.Unfortunately,thetheoryofID-basedringsignaturestillfacessomeobstaclesinrealapplication:ID-basedringsignatureschemesareusuallyderivedfrombilinearpairings,apowerfulbutcomputationallyexpensiveprimitive.TheimportantpropertiesofbilinearpairingsandassociatedintractableproblemsarerecalledinSection3.Fromthereviewinthenextsection,weknowthatthenumberofpairingcomputationsofallexistingID-basedringsignaturefrombilinearpairingsgrowslinearlywiththegroupsize,whichmakestheefficiencyofID-basedschemesovertraditionalschemesquestionable.ItisfairtosaydevisinganID-basedringsignatureusingsublinearnumbersofpairingcomputationremainsanopenquestion.Weclosethisopenprobleminthispaper.AnefficientID-basedringsignatureisproposedinSection5,whichonlytakestwopairingoperationsforanygroupsize,andthegenerationofthesignatureinvolvesnopairingcomputationsatall.Theproposedschemeisproventobeexistentialunforgeableagainstadaptivechosenmessage-and-identityattackundertherandomoraclemodel.TheframeworkandthesecuritynotionofID-basedringsignaturearediscussedinSection4.Intheliterature,1-out-of-n-groupsringsignaturewasalsoconsidered,whichsupportsanad-hocaccessstructureconsistingofgroupsofdifferentsizes.Theverifiercanbeconvincedthatthesignatureisgeneratedfromallmembersofacertaingroup,butcannotknowwhichgrouphasindeedparticipatedinthesigning.WenoticethatanID-basedringsignatureforthegeneralaccessstructurecanbeimplementedbyan1-out-of-n-groupsEfficientIdentityBasedRingSignature3ringsignature.ExtensionoftheproposedschemetosupportthisgeneralaccessstructureisshowninSection6.2RelatedWorkThefirstworkonID-basedringsignatureisin[13].Afterthat,[8]gaveamoreefficientconstruction,while[1]pointedoutandfixedsomesmallinconsistenciesin[13]and[8].AnotherID-basedringsignatureschemewasproposedin[6].AnID-basedringsignatureschemeforanonymoussubsets(i.e.1-out-of-n-groupsinsteadof1-out-of-n-individuals)wasalsoconsideredinthiswork.Thepairingoperationsin[6]canbeexecutedinparallel,whichisnotpossibleinschemeslike[1,8,13].Thresholdringsignatureisthet-out-of-nthresholdversionofringsignature,wheretormoreentitiescanjointlygenerateavalidsignaturebutt−1orfewerentitiescannot.The