Constant-Size Hierarchical Identity-Based Signatur

Constant-SizeHierarchicalIdentity-BasedSignature/SigncryptionwithoutRandomOraclesAbstract.Weproposeahierarchicalidentity-basedsignature(HIBS)schemewhichisprovablewithoutrandomoraclemodel.Thesignaturesizeisindependenttothelevelofthehierarchy.Combiningwithexistinghierarchicalidentity-basedencryption(HIBE)schemes,weobtainahi-erarchicalidentitybasedsigncryption(HIBSC)schemewhichisprovablewithoutrandomoraclemodelandwhosesizeisindependentofthelevelofthehierarchy.Keywords:Hierarchicalidentity-basedsignature,signcryption,bilinearpairings1IntroductionIdentitybasedcryptosystem[28]isapublickeycryptosystemwherethepublickeycanbeanarbitrarystringsuchasanemailaddress.Atrustedauthority(TA)usesamastersecretkeytoissueprivatekeystoidentitiesthatrequestthem.ForanIdentityBasedEncryption(IBE)scheme,AlicecansecurelyencryptamessagetoBobusingBob’sidentity,suchasemailaddress,asthepublickey.ForanIdentityBasedSignature(IBS)scheme,Alicecansignamessageusingherprivatekeythatcorrespondstoanunambiguousnameofhers,suchasemailaddress.Thenanybodycanverifytheauthenticityofthesignaturefromthename.AnIdentityBasedSignCryption(IBSC)schemeisthecombinationofIBEandIBSwithacommonsetofparametersandkeys.Withsuchinfrastructure,itcanachieveanincreaseinefficiencyandanimprovementinsecurity.HierarchicalIBE(HIBE)[22,26]isageneralizationofIBEthatmirrorsthehierarchyoforganizations.Anidentityatlevelℓofthehierarchytreecanissueprivatekeystoitsdescendantidentities,butcannotdecryptmessagesintendedforotheridentities.Inparticular,anIBEisan1-levelHIBE.CombiningwithHierarchicalIBS(HIBS)originatedfromthesameidea,[17]proposedtheconceptofHierarchicalIBSC(HIBSC).Manyreductionistsecurityproofsconcerningidentitybasedcryptosystemsandothercryp-tosystemsusedtherandomoraclemodel[3].Severalpapersprovedthatsomepopularcryp-tosystemspreviouslyprovedsecureintherandomoracleareactuallyprovablyinsecurewhentherandomoracleisinstantiatedbyanyreal-worldhashingfunctions[14,2].Thereforeiden-titybasedcryptosystemsprovablysecureinthestandardmodelattractagreatinterest.SeveralIBEschemes[15,4,25]areproposedwhichissecurewithoutrandomoraclesunderaweaker“selective-ID”model[15].Recently,BonehandBoyen[5]andWaters[29]proposedIBEschemeswhichareprovablysecurewithoutrandomoraclesunderthestrongmodelof[9].SeveralrecentIBEschemes[4,5,29]achievechosenciphertextsecuritywithoutrandomoraclesfromtheirHIBEcounterparts.Theyusedtheresultof[16,10,8]thatanychosenplaintextsecure(ℓ+1)-levelHIBEschemecanbeusedtoconstructachosenciphertextsecureℓ-levelHIBEscheme.Itisnaturaltoaskwhetherotherefficienthierarchicalidentitybasedcryptosystemsaresecurewithoutrandomoracles.Inthispaper,weprovideanaffirmativeanswerbyconstructinganHIBSandHIBSCschemeswhichcanbeprovablysecurewithoutrandomoracles.Ourapproachismotivatedbytheabove-mentionedresultsconcerningHIBE.Weconstructaℓ-levelHIBSschemefromaweaker(ℓ+1)-levelHIBSscheme.21.1OurContributionWemakethefollowingcontributions:–Thefirstconstant-sizehierarchicalidentitybasedsignature(HIBS)scheme.Itisexisten-tiallyunforgeableprovidingtheDiffie-HellmanInversion(DHI)AssumptioninthesaIDmodelwithoutrandomoracles.ThesaID(sample-ID)modelisaslightlyweakermodelrelatedtothesID(select-ID)modelof[15].–Atransformationtheoreminthestyleoftransformationtheoremsin[24,16,10,8],thatlinksthesecurityofan(ℓ+1)-levelHIBSandthesecurityofanℓ-levelHIBS.ApersistenttechnicaldifficultyregardingtheuseofsIDmodelinthetransformationtheoremwasovercomebyusingoursaIDmodel.–Thefirstconstant-sizeidentitybasedsigncryption(IBSC)andhierarchicalidentitybasedsigncryption(HIBSC)schemewhichareprovablysecurewithoutrandomoracles.1.2RelatedResultsMostexistingpracticalsignatureschemesareprovablysecureintherandomoraclemodel.[21]proposedavariantofhash-and-signRSAsignaturescheme,whichisprovablysecurewithoutrandomoracles,bythestrongRSAassumption.Adifferentapproachisproposedin[18],andfurtherimprovementsareproposedin[20].[11]proposedasignatureschemeprovablysecureunderdiscrete-logtypeassumptioninthestandardmodel,butthesignaturesizeislong.[6]proposedashortsignatureschemesecurewithoutrandomoracles,underthenewq-SDHassumption.Shamir[28]suggestedanidentity-basedsignaturescheme.BonehandFranklin[9]pro-posedthefirstpracticalidentity-basedencryptionscheme,whichisprovablysecureintherandomoraclemodel.SeveralIBEschemes[15,4,25]areproposedwhichissecurewithoutrandomoraclesunderaweaker“selective-ID”model[15].Recently,BonehandBoyen[5]andWaters[29]proposedidentitybasedencryptionschemewhichisprovablysecurewithoutrandomoraclesunderthemodelof[9].Recently[13]proposedanidentitybasedsignaturewithoutrandomoracles,buttheirreductionistightonlyiftheyusethe“selective-ID”model.Zheng[32]proposedthatencryptionandsignaturecanbecombinedas“signcryption”whichcanbemoreefficientincomputationthanrunningencryptionandsignatureseparately.Therearesomepapers(e.g.[27,12,30])concerningthecombinationofidentity-basedsigna-tureandencryptiontoformidentitybasedsigncryptionschemes.Thesepapersareprovablysecureonlyintherandomoraclemodel.Hierarchicalidentitybasedcryptographywasproposedin[22]and[26]proposedanotherhierarch