Anonymous hierarchical identity-based encryption (

AnonymousHierarchicalIdentity-BasedEncryption(WithoutRandomOracles)XavierBoyen∗BrentWaters†March3,2006ThispaperisavailablefromtheIACRCryptologyePrintArchiveatfficientandpractical,withsmallciphertextsofsizelinearinthedepthofthehierarchy.Applicationsincludesearchonencrypteddata,fullyprivatecommunication,etc.Ourresultsresolvetwoopenproblemspertainingtoanonymousidentity-basedencryption,ourschemebeingthefirsttoofferprovableanonymityinthestandardmodel,inadditiontobeingthefirsttorealizefullyanonymousHIBEatalllevelsinthehierarchy.1IntroductionThecryptographicprimitiveofidentity-basedencryptionallowsasendertoencryptamessageforareceiverusingonlythereceiver’sidentityasapublickey.Recently,therehasbeeninterestin“anonymous”identity-basedencryptionsystems,wheretheciphertextdoesnotleaktheidentityoftherecipient.Inadditiontotheirobviousprivacybenefits,anonymousIBEsystemscanbeleveragedtoconstructPublickeyEncryptionwithKeywordSearch(PEKS)schemes,aswasfirstobservedbyBonehetal.[10]andlaterformalizedbyAbdallaetal.[1].Roughlyspeaking,PEKSisaformofpublickeyencryptionthatallowsanencryptortomakeadocumentserarchablebykeywords,andwherethecapabilitiestosearchonparticularkeywordsaredelegatedbyacentralauthority.AnonymousHIBEfurtherenablessophisticatedaccesspoliciesforPEKSandID-basedPEKS.Priortothispaper,theonlyIBEsystemknowntobeinherentlyanonymouswasthatofBonehandFranklin[11].Althoughtheydidnotstateitexplicitly,theanonymityoftheirschemefollowedreadilyfromtheirproofofsemanticsecurity.OnedrawbackoftheBoneh-FranklinIBEparadigmisthatitssecurityproofsaresetintherandomoraclemodel.Morerecently,efficientIBEschemesduetoBonehandBoyen[5]andWaters[29]havebeenprovensecureoutsideoftherandomoraclemodel,buttheseschemesarenotanonymouswhenimplementedusing“symmetric”bilinearpairingse:G×G→GT,becauseonecantestifagivenciphertextwasencryptedforacandidateidentity.Inretrospect,onenotesthatwithminormodificationsBonehandBoyen’stwoschemes∗VoltageInc.,PaloAlto—[e-mail]†SRIInternational—[e-mail]1“BB1”and“BB2”,andWaters’byextension,mayinfactbecomeanonymouswhenimplementedwithan“asymmetric”pairinge:G׈G→GTunderstrongadditionalassumptions(suchashardnessofDDHinG),butthisisnoteasytoprove.Furthermore,forafundamentalreasonthisobservationappliesonlytonon-hierarchicalIBE,anditwouldbenicenottorelyonsuch“risky”assumptionswhicharepatentlyfalseinthesymmetricsetting.Atanyrate,andevenifoneweretoconsidertheuseofrandomoracles,theresimplydoesnotexistanyknownhierarchicalidentity-basedencryptionschemewhichisalsoanonymous.(Inparticular,theGentry-Silverberg[19]HIBEschemeisnot.)IntheirrecentCRYPTO’05paper,Abdallaetal.[1]citethecreationofananonymousIBEsystemwithoutrandomoraclesandananonymousHIBEsystemwithorwithoutrandomoraclesasimportantopenproblems.1.1OurResultsWepresentanAnonymousIBEandHIBEschemewithoutrandomoracles,therbysolvingbothopenproblemsfromCRYPTO’05.OurschemeisveryefficientforpureIBE,andreasonablyefficientforHIBEwithshallowhierarchiesofpracticalinterest.WeproveitsecurebasedsolelyonBoneh’setal.[9]DecisionLinearassumption,whichisoneofthemildestusefulcomplexityassumptionsinbilineargroups.Atfirstsight,ourconstructionbearsasuperficialresemblancetoBonehandBoyen’s“BB1”HIBEscheme[5,§4]—butwithatleasttwobigdifferences.First,weperform“linearsplittings”onvariousportionsoftheciphertext,tothwartthetrial-and-erroridentityguessingtowhichotherschemesfellprey.Thisideagivesusprovableanonymity,evenundersymmetricpairings.Second,weusemultipleparallelHIBEsystemsandconstantlyre-randomizethekeysbetweenthem.Thisiswhatletsususethelinearsplittingtrickatalllevelsofthehierarchy,butalsoposesatechnicalchallengeinthesecurityreductionwhichmistnowsimulatemultipleinteractingHIBEsystemsatonce.Solvingthisproblemwasthecrucialstepthatgaveusahierarchywithoutdestroyinganonymity.Buildinga“flat”anonymousIBEsystemturnsouttobereasonablystraightforwardusingourlinearsplittingtechniquetohidetherecipientidentitybehindsomerandomization.Complicationsarisewhenonetriestosupporthierarchicalkeygeneration.Inanutshell,topreventcollusionattacksinHIBE,“parents”mustindependentlyre-randomizetheprivatekeystheygivetotheir“children”.InallknownHIBEschemes,re-randomizationisenabledbyanumberofsupplementalcomponentsinthepublicsystemparameters.Whythisbreaksanonymityisbecausethesamemechanismthatallowsprivatekeystobepubliclyre-randomized,alsoallowsciphertextstobepubliclytestedforrecipientidentities.Randomoraclesoffernoprotectionagainstthis.Tocircumventthisobstable,weneedtomakethere-randomizationelementsnon-public,andtiethemtoeachindividualprivatekey.Inpracticalterms,thismeansthatprivatekeysmustconveyextracomponents(althoughnottoomany).Therealdifficultyisthateachsetofre-randomizationcomponentsconstitutesafull-fledgedHIBEinitsownright,whichmustbesimulatedtogetherwithitspeersinthesecurityproof(theirnumbergrowslin