3 Secure Identity Based Encryption Without Random

SecureIdentityBasedEncryptionWithoutRandomOraclesDanBoneh1,
andXavierBoyen21ComputerScienceDepartment,StanfordUniversity,[e-mail]2VoltageSecurity,PaloAlto,[e-mail]ntityBasedEncryptionschemewhoseproofofsecuritydoesnotrelyontherandomoracleheuristic.SecurityisbasedontheDecisionBilinearDiffie-Hellmanassumption.ThissolvesanopenproblemposedbyBonehandFranklinin2001.1IntroductionIdentityBasedEncryption(IBE)providesapublickeyencryptionmechanismwhereapublickeyisanarbitrarystringsuchasanemailaddressoratelephonenumber.ThecorrespondingprivatekeycanonlybegeneratedbyaPrivateKeyGenerator(PKG)whohasknowledgeofamastersecret.InanIBEsystem,usersauthenticatethemselvestothePKGandobtainprivatekeyscorrespondingtotheiridentities.AlthoughIdentitybasedencryptionwasproposedtwodecadesago[Sha84],andafewearlyprecursorssuggestedovertheyears[Tan87,MY96],itisonlyrecentlythatthefirstworkingimplementationswereproposed.BonehandFranklin[BF01,BF03]definedasecuritymodelforIdentityBasedEncryp-tionandgaveaconstructionbasedonthebilinearDiffie-Hellmanproblem.Cocks[Coc01]describesanotherconstructionusingquadraticresiduesmoduloacomposite.Thesecurityofthesesystemsrequirescryptographichashfunc-tionsthataremodeledasrandomoracles,i.e.,thesesystemsareprovensecureintherandomoraclemodel[BR93].Thesameholdsforseveralotheridentitybasedsystemsfeaturingsignatures[CC03],keyexchange[SOK00],hierarchicalidentities[GS02],andsigncryption[Boy03].ItisnaturaltoaskwhethersecureIBEsystemscanexistinthestandardmodel,i.e.,withoutresortingtotherandomoracleheuristic.Thisquestionisespeciallyrelevantinlightofseveraluninstantiablerandomoraclecryptosys-tems[CGH98,BBP04],whicharesecureintherandomoraclemodel,butaretriviallyinsecureunderanyinstantiationoftheoracle.Towardsthisgoal,sev-eralrecentresults[CHK03,BB04,HK04]constructIBEsystemssecurewithoutrandomoraclesinweakerversionsoftheBoneh-Franklinmodel.However,untilnow,buildingafullysecureIBEremainedopen.
SupportedbyNSFandthePackardFoundation.M.Franklin(Ed.):CRYPTO2004,LNCS3152,pp.443–459,2004.c
InternationalAssociationforCryptologicResearch2004444DanBonehandXavierBoyenInthispaperweconstructanIBEsystemthatissecureintheBoneh-Franklinmodelwithoutusingrandomoracles.SecurityisbasedonthedecisionalversionofthebilinearDiffie-Hellmanassumption.OursystemdemonstratesthatfullysecureIBEsystemscanexistwithoutrandomoracles.Themainshortcomingoftheproposedsystemisthatitisinefficient;consequently,wemostlyviewourconstructionasanexistenceproof.2PreliminariesBeforepresentingourresultswebrieflyreviewadefinitionofsecurityforanIBEsystem.Wealsoreviewthedefinitionforgroupswithabilinearmap.First,weintroducesomenotation.2.1NotationForafinitesetSweusexR←StodefinearandomvariablexthatpicksanelementofSuniformlyatrandom.ForarandomizedalgorithmAweusexR←A(y)todefinearandomvariablexthatistheoutputofalgorithmAoninputy.WeletPr[b(x):x←A(y)]denotetheprobabilitythatthepredicateb(x)istruewherexistherandomvariabledefinedbyx←A(y).Foravectorz∈Σnweusez|itodenotethei’thcomponentofz.2.2SecureIBESystemsRecallthatanIdentityBasedEncryptionsystem(IBE)consistsoffouralgo-rithms[Sha84,BF01]:Setup,KeyGen,Encrypt,Decrypt.TheSetupalgorithmgeneratessystemparameters,denotedbyparams,andamasterkeymaster-key.TheKeyGenalgorithmusesthemasterkeytogeneratetheprivatekeycorre-spondingtoagivenidentity.Theencryptionalgorithmencryptsmessagesforagivenidentity(usingthesystemparameters)andthedecryptionalgorithmdecryptsciphertextsusingtheprivatekey.BonehandFranklin[BF01]definechosenciphertextsecurityforIBEsystemsunderachosenidentityattack.Intheirmodeltheadversaryisallowedtoadap-tivelychosethepublickeyitwishestoattack(thepublickeyonwhichitwillbechallenged).Moreprecisely,securityforanIBEsystemisdefinedusingthefollowingtwoprobabilisticexperimentsCCA-ExpA(0)andCCA-ExpA(1).ExperimentCCA-ExpA(b):foranalgorithmAandabitb∈{0,1}definethefollowinggamebetweenachallengerandA:Setup:AchallengerrunstheSetupalgorithm.ItgivesAtheresultingsystemparametersparams.Itkeepsthecorrespondingmaster-keytoitself.Phase1:AlgorithmAissuesqueriesq1,...,qmwhereeachqueryqiisoneof:–PrivatekeyqueryforanidentityIDi.ThechallengerrespondsbyrunningalgorithmKeyGentogeneratetheprivatekeydicorrespondingtothepublickeyIDi.ItsendsditoA.SecureIdentityBasedEncryptionWithoutRandomOracles445–DecryptionqueryforaciphertextCiandanidentityIDi.ThechallengerrespondsbyrunningalgorithmKeyGentogeneratetheprivatekeydicorrespondingtoIDi.ItthenrunsalgorithmDecrypttodecrypttheciphertextCiusingtheprivatekeydi.ItgivesAtheresultingplaintext.Thesequeriesmaybeaskedadaptively,thatis,eachqueryqimaydependontherepliestoq1,...,qi−1.Challenge:OnceAdecidesthatPhase1isoveritoutputsanidentityID∗andtwoequallengthplaintextsM0,M1∈Mthatitwishestobechal-lengedon,undertheconstraintthatithadnotpreviouslyaskedfortheprivatekeyofID∗.ThechallengersetsthechallengeciphertexttoC∗=Encrypt(params,ID∗,Mb).ItsendsC∗asthechallengetoA.Phase2:AlgorithmAissuesmorequeriesqm+1,...,qnwhereqiisoneof:–PrivatekeyqueryforanyidentityIDiwhereIDi=ID∗.Thechalle