Space-efficient identity based encryption without

Space-EfficientIdentityBasedEncryptionWithoutPairings∗DanBoneh†CraigGentry‡MichaelHamburg{dabo,cgentry,mhamburg}@cs.stanford.eduStanfordUniversityAbstractIdentityBasedEncryption(IBE)systemsareoftenconstructedusingbilinearmaps(a.k.a.pairings)onellipticcurves.OneexceptionisanelegantsystemduetoCockswhichbuildsanIBEbasedonthequadraticresiduosityproblemmoduloanRSAcompositeN.TheCockssystem,however,produceslongciphertexts.SincetheintroductionoftheCockssystemin2001ithasbeenanopenproblemtoconstructaspaceefficientIBEsystemwithoutpairings.InthispaperwepresentanIBEsysteminwhichciphertextsizeisshort:anencryptionofan`-bitmessageconsistsofasingleelementinZ/NZplus`+1additionalbits.Security,asintheCockssystem,reliesonthequadraticresiduosityproblem.Thesystemisbasedonthetheoryofternaryquadraticformsandasaresult,encryptionanddecryptionareslowerthanintheCockssystem.1IntroductionInanIdentityBasedEncryption(IBE)systemanystringcanfunctionasapublickey[37].IBEsystemshavefoundnumerousapplicationsincryptography(see[13,14,7,23,42,8,11,5]tonameafew)andcomputersecurity[2,41,31,32,38].TherearecurrentlytwoapproachesforconstructingIBEsystems.ThefirstapproachbuildsIBEsystemsusingbilinearpairings[9,6,40,36].Theresultingsystemsareefficientbothinperformanceandciphertextsize.TherichstructureofbilinearmapsenablesvariousextensionssuchasHierarchicalIBE[29,26],anonymousIBE[8,1,12,25],andmanyothers.Thesecondapproach,duetoCocks[17],buildsanelegantIBEsystembasedonthestandardquadraticresiduosityproblem[33,p.99]moduloanRSAcompositeN(intherandomoraclemodel).CiphertextsinthissystemcontaintwoelementsinZ/NZforeverybitofplaintext.Hence,theencryptionofan`-bitmessagekeyisofsize2`·log2N.Forexample,whenencryptinga128-bitmessagekeyusing1024-bitmodulus,oneendsupwithaciphertextofsize32678bytes.Forcomparison,pairingbasedmethodsproducea36byteciphertextforcomparablesecurity.Alongstandingopenproblemsince[17]istheconstructionofaspaceefficientIBEsystemwithoutpairings,namelyasystemwithshortciphertexts.Weconstructsuchasystem—anencryptionofan`bitmessageconsistsofasingleelementinZ/NZplus(`+1)additionalbits.Hence,ciphertextsizeisabout`+log2N.Whenencryptinga128-bitmessagekeytheresultis∗Thispaperisthefullversionof[10].†SupportedbyNSFandthePackardFoundation.‡SupportedbytheHerbertKunzelStanfordGraduateFellowship.1aciphertextofsize1024+129=1153bitsor145bytes.Thesystemmakesextensiveuseofthetheoryofquadraticforms[15].Inparticular,encryptionanddecryptionarebasedonaneffectiveversionofLegendre’sfamousthreesquarestheorem.OurmainproposedIBEsystemispresentedinSection6.ThesystemisrelatedtotheCockssystemandsecurityissimilarlybasedonthequadraticresiduosity(QR)problem.AsintheCockssystem,ourIBEproofofsecuritymakesuseoftherandomoraclemodel.However,therandomoraclemodelisneededonlyforprovingthattheunderlyingRabinsignatureschemeisexistentiallyunforgeable.TomakethisprecisewefirstprovesecurityinthestandardmodelundertheInteractiveQRassumption(IQR),namelyundertheassumptionthattheQRproblemisdifficultinthepresenceofahashsquarerootoracle.WethennotethatIQRisequivalenttoQRintherandomoraclemodel.WeobservethatthesystemisananonymousIBEunderthequadraticresiduosityassumption.(theCockssystemisknowntonotbeanonymous,althoughavariantofitis[21]).InAppendixE,wedescribeageneralframeworkforusinghashproofsystems(asdefinedin[19])thathaveatrapdoortoconstructIBEsystemsthatareanonymousandsecureagainstchosen-ciphertextattacksinthestandardmodelundertheInteractiveSubsetMembership(ISM)assumption,ageneralizationoftheIQRassumption.Weprovidehashproofsystemsforquadraticresiduosity,whichinduceasystembasedonIQR(inthestandardmodel).WealsoprovideaPKEsystemsecureagainstchosen-ciphertextattacksundertheQRassumption,whichmaybeofindependentinterest.Encryptiontimeinoursystemisnotideal.RecallthatencryptiontimeinmostpracticalpublickeysystemssuchasRSAandexistingIBEsystems[9,17]iscubicinthesecurityparameter.Encryptiontimeinoursystemisquarticinthesecurityparameterpermessagebit.Decryptiontime,however,iscubicasinothersystems.ThebottleneckduringencryptionistheneedtogenerateprimesontheorderofN.InSection5.3weshowatimespacetradeoffwherethenumberofprimestogeneratecanbesignificantlyreducedatthecostofamodestincreaseintheciphertextsize.2DefinitionsRecallfrom[37,9]thatanIdentityBasedEncryptionsystem(IBE)consistsoffouralgorithms:Setup,KeyGen,Encrypt,Decrypt.TheSetupalgorithmgeneratessystemparameters,denotedbyPP,andamasterkeyMSK.TheKeyGenalgorithmusesthemasterkeytogeneratetheprivatekeydIDcorrespondingtoagivenidentityID.TheEncryptalgorithmencryptsmessagesforagivenidentity(usingthesystemparameters)andtheDecryptalgorithmdecryptsciphertextsusingtheprivatekey.AnIBEmustremainsecureagainstanattackerwhocanrequestprivatekeysforidentitiesofhischoice.ThisiscapturedinthestandardIBEsecuritygame[9],whichalsocaptureschosenciphertextattacks.BeyondthebasicsemanticsecurityrequirementsforIBEencryptiononecanalsorequirethattheIBEbeanonymous,namelythataciphertextrevealnoinformationabouttheidentityusedtocreatetheciphertext.AnonymousIBEisusefulforavarietyofapplicationssuchassearchingonencrypteddata[8