A forward-secure public-key encryption scheme

AForward-SecurePublic-KeyEncryptionSchemeRanCanetti∗ShaiHalevi∗JonathanKatz†December23,2003AbstractCryptographiccomputationsareoftencarriedoutoninsecuredevicesforwhichthethreatofkeyexposurerepresentsaseriousandrealisticconcern.Inanefforttomitigatethedamagecausedbyexposureofsecretkeysstoredonsuchdevices,theparadigmofforwardsecuritywasintroduced.Inaforward-securescheme,secretkeysareupdatedatregularperiodsoftime;exposureofthesecretkeycorrespondingtoagiventimeperioddoesnotenableanadversaryto“break”thescheme(intheappropriatesense)foranypriortimeperiod.Anumberofconstructionsofforward-securedigitalsignatureschemes,key-exchangeprotocols,andsymmetric-keyschemesareknown.Wepresentthefirstnon-trivialconstructionsof(non-interactive)forward-securepublic-keyencryptionschemes.Ourmainconstructionachievessecurityagainstchosen-plaintextattacksunderthedecisionalbilinearDiffie-Hellmanassumptioninthestandardmodel.Thisschemeispractical,andallparametersgrowatmostlogarithmicallywiththetotalnumberoftimeperiods.Wealsogiveaslightlymoreefficientschemeintherandomoraclemodel.Bothourschemescanbeextendedtoachievesecurityagainstchosen-ciphertextattacksandtosupportanunboundednumberoftimeperiods.Towardourgoal,weintroducethenotionofbinarytreeencryptionandshowhowtocon-structabinarytreeencryptionschemeinthestandardmodel.Thisnewprimitivemaybeofindependentinterest.Inparticular,weuseittoconstructthefirstknownexampleofa(hierar-chical)identity-basedencryptionschemethatissecureinthestandardmodel.(Here,however,thenotionofsecurityweachieveisslightlyweakerthanwhatisachievedinsomepreviousconstructionsintherandomoraclemodel.)Keywords:BilinearDiffie-Hellman,Encryption,Binary-treeencryption,Identity-basedencryp-tion,Forwardsecurity,Keyexposure.∗IBMT.J.WatsonResearchCenter,NY,USA.{canetti,shaih}@watson.ibm.com.†Dept.ofComputerScience,UniversityofMaryland,CollegePark,[e-mail].1Contents1Introduction21.1OurContributions.....................................21.2Organization........................................42BinaryTreeEncryption42.1TheBilinearDiffie-HellmanAssumption.........................62.2ABTESchemeBasedontheBDHAssumption.....................73Forward-SecurePublic-KeyEncryption123.1Definitions..........................................123.2Forward-SecurePKESchemeswithLinearComplexity.................143.3AConstructionwithLogarithmicComplexity......................14ABasingHIBEonBTE18A.1Definitions..........................................19A.2FromBTEtoHIBE....................................20BBasingNIZKonPublicly-VerifiableTrapdoorPredicates2111IntroductionExposureofsecretkeyscanbeadevastatingattackonacryptosystemsincesuchanattacktypicallyimpliesthatallsecurityguaranteesarelost.Indeed,standardnotionsofsecurityoffernoprotectionwhatsoeveroncethesecretkeyofthesystemhasbeencompromised.Withthethreatofkeyexposurebecomingmoreacuteascryptographiccomputationsareperformedmorefrequentlyonpoorlyprotecteddevices(smart-cards,mobilephones,evenPCs),newtechniquesareneededtodealwiththisconcern.Avarietyofmethodshavebeenintroducedinanattempttodealwiththisthreat(includingsecretsharing[36],thresholdcryptography[14],andproactivecryptography[33]).Onepromisingapproach—whichwefocusonhere—istoconstructforwardsecurecryptosystems.Thisnotionwasfirstproposedinthecontextofkey-exchangeprotocolsbyG¨unther[22]andDiffie,etal.[15]:aforward-securekey-exchangeprotocolguaranteesthatexposureoflong-termsecretinformationdoesnotcompromisethesecurityofpreviously-generatedsessionkeys.Weremarkthataforward-securekey-exchangeprotocolnaturallygivesrisetoaforward-secureinteractiveencryptionschemeinwhichthesenderandreceivergenerateasharedkeywhichisusedtoencryptasinglemessageandisthenpromptlyerased.Subsequently,Anderson[3]suggestedforwardsecurityforthemorechallengingnon-interactivesetting.ThelifetimeofthesystemisdividedintoNintervals(ortimeperiods)labeled0,...,N−1.ThereceiverinitiallystoressecretkeySK0andthissecretkey“evolves”withtime.Namely,atthebeginningoftimeperiodi,thereceiverappliessomefunctiontothe“previous”keySKi−1toderivethe“current”keySKi;keySKi−1isthenerasedandSKiisusedforallsecretcryptographicoperationsduringperiodi.Thepublic(encryption)keyremainsfixedthroughoutthelifetimeofthescheme;thisiscrucialformakingsuchaschemeviable.Aforward-secureencryptionschemeguaranteesthatevenifanadversarylearnsSKi(forsomei),messagesencryptedduringalltimeperiodspriortoiremainsecret(aformaldefinitionisgiveninSection3).Notethatsincetheadversaryobtainsallsecretsexistingattimei,themodelinherentlycannotprotectthesecrecyofmessagesencryptedattimeiandatallsubsequenttimeperiods.Anumberofconstructionsofforward-securesignature/identificationschemesareknown[6,29,1,25,31,28],andforwardsecurityfornon-interactive,symmetric-keyencryptionhasalsobeenstudied[7].Theexistenceofnon-trivial,forward-securepublic-keyencryption(PKE)schemes,however,hasbeenopensincethequestionwasfirstposedbyAnderson[3].Forward-securePKEhastheobviouspracticaladvantagethatacompromiseofthesystemdoesnotcompromisethesecrecy