Hierarchical identity based encryption with consta

HierarchicalIdentityBasedEncryptionwithConstantSizeCiphertextDanBoneh∗[e-mail]†[e-mail]-JinGoh∗[e-mail]20,2005AnextendedabstractofthispaperappearsinR.Cramer,editor,AdvancesinCryptology—EURO-CRYPT2005,volume3493ofLectureNotesinComputerScience,pages440–456,Springer,2005.AbstractWepresentaHierarchicalIdentityBasedEncryption(HIBE)systemwheretheciphertextconsistsofjustthreegroupelementsanddecryptionrequiresonlytwobilinearmapcomputa-tions,regardlessofthehierarchydepth.EncryptionisasefficientasinotherHIBEsystems.Weprovethattheschemeisselective-IDsecureinthestandardmodelandfullysecureintherandomoraclemodel.Oursystemhasanumberofapplications:itgivesveryefficientforwardsecurepublickeyandidentitybasedcryptosystems(withshortciphertexts),itconvertstheNNLbroadcastencryptionsystemintoanefficientpublickeybroadcastsystem,anditprovidesanefficientmechanismforencryptingtothefuture.Thesystemalsosupportslimiteddelegationwhereuserscanbegivenrestrictedprivatekeysthatonlyallowdelegationtoboundeddepth.TheHIBEsystemcanbemodifiedtosupportsublinearsizeprivatekeysatthecostofsomeciphertextexpansion.1IntroductionAnIdentityBasedEncryption(IBE)system[24,5]isapublickeysystemwherethepublickeycanbeanarbitrarystringsuchasanemailaddress.Acentralauthorityusesamasterkeytoissueprivatekeystoidentitiesthatrequestthem.HierarchicalIBE(HIBE)[17,14]isageneralizationofIBEthatmirrorsanorganizationalhierarchy.Anidentityatlevelkofthehierarchytreecanissueprivatekeystoitsdescendantidentities,butcannotdecryptmessagesintendedforotheridentities(detailsaregiveninSection2.1).ThefirstconstructionforHIBEisduetoGentryandSilverberg[14]wheresecurityisbasedontheBilinearDiffie-Hellman(BDH)assumptionintherandomoraclemodel.AsubsequentconstructionduetoBonehandBoyen[1]givesanefficient(selective-IDsecure)HIBEbasedonBDHwithoutrandomoracles.Inbothconstructions,thelengthofciphertextsandprivatekeys,aswellasthetimeneededfordecryptionandencryption,growslinearlyinthedepthℓofthehierarchy.TherearecurrentlytwoprincipalapplicationsforHIBE.Thefirst,duetoCanetti,Halevi,andKatz[9],isforwardsecureencryption.Forwardsecureencryptionenablesuserstoperiodicallyupdatetheirprivatekeyssothatamessageencryptedatperiodncannotbereadusingaprivatekeyfromperiodn′n.ToprovideforT=2ttimeperiods,theCHKconstructionusesaHIBEofdepthtwhereidentitiesarebinaryvectorsoflengthatmostt.Attimen,theencryptorencryptsusingtheidentitycorrespondingtothen-thnodeofthisdepthtbinarytree.Consequently,using∗StanfordUniversity.SupportedbyNSF.†VoltageInc.,PaloAlto.1previousHIBEsystems[14,1],ciphertextsinthisforwardsecureconstructionareofsizeO(t);privatekeysareofsizeO(t2)butcanbereducedtosizeO(t)byusingupdateablepublicstorage.ThesecondapplicationforHIBE,duetoDodisandFazio[11],isusingHIBEtoconverttheNNLbroadcastencryptionsystem[22]intoapublic-keybroadcastsystem.Unfortunately,theresultingpublic-keybroadcastsystemisnobetterthansimplerconstructionsbecauseciphertextlengthinpreviousHIBEconstructionsislinearinthedepthofthehierarchy.OurContribution.WepresentaHIBEsystemwheretheciphertextsizeaswellasthedecryp-tioncostareindependentofthehierarchydepthℓ.CiphertextsinourHIBEsystemarealwaysjustthreegroupelementsanddecryptionrequiresonlytwobilinearmapcomputations.PrivatekeysinourbasicsystemcontainℓgroupelementsasinpreviousHIBEconstructions.Oursystemgivesaforwardsecureencryptionsystemwithshortciphertextsconsistingofonlythreegroupelements,foranynumberT=2toftimeperiods.WithourbasicHIBEsystem,theprivatekeysizeinthisforwardsecureencryptionsystemisO(t2).InSection4wedescribeahybridsystemthatborrowssomefeaturesfromtheBoneh-BoyenHIBE[1]andresultsinaforwardsecureencryptionschemewhereprivatekeysizeisreducedtoO(t3/2)andciphertextsizeisO(√t).ByusingupdateablepublicstorageasinCHK[9],privatekeysizeinthesesystemscanbefurtherreducedtosizeO(t)andO(√t)respectively.Inaddition,instantiatingtheDodis-Fazio[11]systemwithourHIBEsystemresultsinapublic-keybroadcastsystemthatisasefficientastheNNLsubsetdifferencemethod.Itisworthnotingthatprivatekeysinoursystemshrinkastheidentitydepthincreases;thisshrinkageistheoppositebehaviorfrompreviousHIBEsystemswhereprivatekeysbecomelargeraswedescenddeeperdownthehierarchytree.Thisbehaviorleadsto“limiteddelegation”whereanidentityatdepthkcanbegivenarestrictedprivatekeythatonlyletsitissueprivatekeystodescendantsoflimiteddepth(asopposedtoanydescendant).SecurityofoursystemisbasedontheBilinearDiffie-HellmanInversionassumptionpreviouslyusedin[1,12,19].WedescribetheassumptioninSection2.3.InSection3wedescribeourHIBEsystemandproveitssecurityintheselectiveidentitymodelwithoutusingrandomoracles.Wethenobservethataselective-IDsecureHIBEresultsinafullysecureHIBEintherandomoraclemodel.InSections4and5wediscussseveralextensionsandapplicationsofthesystem.Forexample,inadditiontotheapplicationsalreadymentioned,weshowhowprivatekeyscanbefurthercompressedtosublinearsizeandalsodescribeanefficientmechanismforencryptingtothefuture.2PreliminariesWebrieflyreviewthedefinitionofHIBEandbilineargroups,anddescribetheBilinearDiffie-HellmanInversionassumpti