标准模型下的新的基于身份的短签名方案New identity-based short signatu

ProcediaEngineering15(2011)3445–34491877-7058©2011PublishedbyElsevierLtd.doi:10.1016/j.proeng.2011.08.645Availableonlineat(2011)000–000*,YupuHubandQingWucaDepartmentofMathematicalScience,XidianUniversity,Xi’an,710071,ChinabKeyLaboratoryofComputerNetworksandInformationSecurity,MinistryofEducation,XidianUniversity,Xi'an,710071,ChinacSchoolofAutomation,Xi’anInstituteofPostsandTelecommunications,Xi’an,710121,ChinaAbstractAnewidentity-basedshortsignature(IBS)isproposedinthispaper.Thenewschemeisconstructedinthestandardmodelandhasshortpublicparametersandprivatekeys.Inaddition,thesizeofthesignatureachieves320bits,whichismuchmoreefficientthantheexistingIBSschemes.Underthen-ComputationalDiffie-HellmanExponentProblem(n-CDH),thenewschemeisprovablesecurity.©2011PublishedbyElsevierLtd.Selectionand/orpeer-reviewunderresponsibilityof[CEIS2011]Keywords:identity-basedsignature,shortsignature,provablesecurity,standardmodel1.IntroductionShortsignatureschemesareneededinenvironmentswithspaceandbandwidthconstraints.Therearegoingtobealotofdevicesexchangingmessageswitheachotherintheseenvironments,e.g.,PDAs,cellphones,RFIDchips,sensornetworksandvehicle-2-vehiclecommunications[1,2].Shortsignatureisanactiveresearcharea.In[3,4],oneencodesapartofthemessageintothesignaturethusshorteningthetotallengthofthemessage-signaturepair.Forlongmessages,onecanthenachieveaDSAsignatureoverheadoflengthof160bits.Boneh,LynnandShacham[5]usedatotallynewapproachtodesignsuchshortdigitalsignaturesin2001.Anumberofdesirableschemeswereproposedatpresent.Inthesesystems,thebindingbetweenthepublickeyandtheidentityofthesignerisobtainedviaadigitalcertificate.Shamirshowed*Correspondingauthor.Tel.:[phone];fax:[phone].E-mailaddress:[e-mail]-NC-NDlicense.3446LeyouZhangetal./ProcediaEngineering15(2011)3445–34492LeyouZhangetal/ProcediaEngineering00(2011)000–000thatitwouldbemoreefficientiftherewasnoneedforsuchabinding[6].Itiscalledidentity-basedcryptography.Identity-basedencryption(IBE)wasintroducedfirstlyin[6].Thefirstidentity-basedsignature(IBS)schemewasproposedbyShamir[6],butthesizeofgeneratedsignatureisquitelarge,whichhas2048bitswhenoneutilizesa1024-bitRSAmodulus.GuillouandQuisquater[7]improvedShamir’sschemeandshortenedthesignaturesizeto1184bitswhenoneuses1024-bitRSAmodulusand160-bithashfunction.BonehandFranklin[8]foundedthatbilinearpairingsonellipticcurvescouldbeusedtomakeID-basedencryptionschemepossibleandpractical.Now,manyIBSschemes[10-16]areproposedbasedonbilinearpairings.Thesesignaturesgeneratedby[10-16]aremuchshorterandsimplerthansignaturesfromschemesin[7,9],whichachieveapproximately320-bitsize.However,theseschemesareprovablesecureintherandomoraclesmodel.Manyresultshaveshownthatsecurityintherandomoraclemodeldoesnotimplythesecurityintherealworld.Securityinthestandardmodelusuallyprovidesahighersecuritylevelthansecurityintherandomoraclemodel.ThewellknownconstructionofIBSinthestandardmodelwasproposedin[17].ItisbasedontheWaters’sscheme[18].Sothepublickeyssizeismuchlargerthanthepreviousschemes.Inaddition,thesizeoftheproposedschemeachieves480bits.OurContributionsAnaturalextensionoftheeffortsistoprovideamoreefficientscheme.Weproposeanewschemeinthispaper.Ourschemecontainssomedesirablefeaturesoverthepreviousworks,suchasconstructedinstandardmodelandshortpublickeysandprivatekeys.Inaddition,Thesizeofsignatureachieves320bits,whichismoreefficientthantheexistingschemes.Underthen-CDHassumption,ourschemeisprovablysecureagainstselective-identityandmessageattack.2.Preliminaries2.1.HardnessAssumptionDefinition1(n-ExponentComputationalDiffie-HellmanProblem)GivenagroupGofprimeorderpwithgeneratorgandelementsgα,2gα,L,ngαG∈,whereisselecteduniformlyatrandomfromαpZandn≥1,then-CDHprobleminGistocompute1ngα+.Definition2Wesaythatthe(t,)n-CDHassumptionholdsinagroupG,ifnoadversaryrunningintimeatmosttcansolvethen-CDHprobleminGwithprobabilityatleast.εε2.2.SecurityDefinitionAnIBSschemeissecureifitsatisfiestworequirements,CorrectnessandExistentialUnforgeability.Thestandardnotionofsecurityforasignatureschemeiscalledexistentialunforgeabilityunderachosenmessageattack[12-17],whichisdefinedusingthefollowinggamebetweenachallengerandanadversaryA:Inti:Theadversaryfirstoutputsthechallengeidentity.***1(,,)nIDvv=SetupThechallengerrunsalgorithmKeyGentoobtainapublickeyPKandaprivatekeySK.TheadversaryAisgivenPK.QueriesProceedingadaptively,Arequestssignaturesonatmostsqmessagesofhischoice1M,L,sqM∈{0,1},underPK.Thechallengerrespondstoeachquerywithasignature.(,SignMσ=)SKiiForgeryAoutputsapair(M,)andwinsthegameif(1)Misnotanyof(σ1M,,sqM);(2)Verify(PK,M,)=Valid.σDefinition3Asignatureschemeis(t,)existentiallyunforgeableunderaweakadaptivechosenmessageattackifnoprobabilisticpolynomialtime(runningintimeatm