Identity-based encryption secure against Selective

Identity-BasedEncryptionSecureAgainstSelectiveOpeningAttackMihirBellare1,BrentWaters2,[e-mail][e-mail]@stthomas.eduAbstract.WepresenttherstIdentity-BasedEncryption(IBE)schemesthatareprovensecureagainstselectiveopeningattack(SOA).Thismeansthatifanadversary,givenavectorofciphertexts,adaptivelycorruptssomefractionofthesenders,exposingnotonlytheirmessagesbutalsotheircoins,theprivacyoftheunopenedmessagesisguaranteed.Achievingsecurityagainstsuchattacksiswell-knowntobechallengingandwasonlyrecentlysolvedinthePKEcase,butthetechniquesusedtheredonotsolvetheIBEcase.OursolutionsillustratetwotechniquestoachievingSOA-secureIBE,onebasedontheBoyen-WatersanonymousIBEandtheotherbasedonWaters'dual-systemapproach.Keywords:Identity-basedencryption,pairings.1IntroductionSecurityagainstselective-openingattack(SOA)isarguablythemostparadoxicalandvexingopenquestioninthetheoryofencryption.Recently(and10yearsaftertheproblemwasidentied),wehaveseensolutions[2].Theseandfollowups[24,22],however,havebeenforthecaseofPublic-KeyEncryption(PKE).Anotherdomainwheretheproblemarises,andisimportantforapplications,isIdentity-BasedEncryption(IBE).ThetechniquesusedforPKEdonotyieldsolutionshere.(ThatSOA-secureIBEremainsopenandchallengingevenwithSOA-securePKEachievedisnotsurprisingsinceevenbasicIBErequirednewapproachescomparedtoPKEandtookmuchlongertoachieve[9,19,5,6,34].)ThispaperinitiatesatreatmentofIBEsecureunderSOA,providingdenitionsofsecurityandtherstsolutions.Oursolutionsdonotuserandomoracles.Background.Aselective-openingattackonaPKEschemeimaginesnsendersandreceivers.Senderiencryptsamessagem[i]underfresh,randomcoinsr[i]andthepublickeypk[i]ofthei-threceivertogetaciphertextc[i].Anadversarygiventhevectorccorruptssomesubsetofthesendersandlearnsnotonlytheirmessagesbutalsotheircoins.SOA-securityrequiresthattheremaining,unopenedmessagesretaintheirprivacy.SOA-securityisrequiredwhenimplementingtheassumedsecurechannelsinanadaptively-securemulti-partycomputationprotocol.Morepragmatically,itwouldberequiredtodistributesharesinadistributedle-systemthatisusingsecret-sharingforprivacy.IND-CPAandIND-CCA,widely-acceptedasthe\rightnotionsofencryptionprivacy,arenotknowntoimplysecurityunderSOA.ThedicultyofestablishingSOA-securitystemsfromthefactthattheadversarygetsthecoinsandalsothatthemessagesm[1];:::;m[n]mayberelated.Construc-tionsofSOAsecureschemesalsoremainedelusive,theareacoloredbynegativeresultsforcommitmentschemes[21,2,29].Finally,Bellare,Hofheinz,andYilek(BHY)[2]showedalargeclassofencryptionschemes,whichtheycalllossy[2,26,31],areSOAsecure.SchemestheyshowtobelossyincludevariantsofElGamal[28],theIND-CPAschemebuiltfromlossytrapdoorfunctionsbyPeikertandWaters[32],andeventheoriginalGoldwasser-Micaliencryptionscheme[23].Hemenway,Libert,Os-trovskyandVergnaud[24]showedthatre-randomizableencryptionandstatisticallyhiding,two-roundoblivioustransferimplylossyencryption,yieldingstillmoreexamplesofSOAsecurePKEschemesviathelossy-implies-SOA-secureconnectionofBHY.Fehr,Hofheinz,Kiltz,andWee(FHKW)[22]useadeniableencryption[13]approachtoachieveCC-SOA(Chosen-CiphertextSOA)securePKE.SOAforIBE.WecanadapttheSOAframeworktoIBEinanaturalway.Avectoridofadversarially-chosentargetreceiveridentitiesreplacesthevectorpkofpublicreceiverkeys.Senderiencryptsmessagem[i]undercoinsr[i]foridentityid[i]togetaciphertextc[i].Asbeforetheadversary,givenc,corruptsasubsetofthesendersandlearnstheirmessagesandcoins,andSOA-securityrequiresthattheunopenedmessagesaresecure.Atanytime,theadversarycanqueryExtractwithanyidentitynotinthevectoridandobtainitsdecryptionkey.Therearetwoelementshere,newcomparedtoPKE,thatwillbecentraltothetechnicalchallengesinachievingthegoal.TherstistheExtractoracle,afeatureofIBEsecurityformalizationssincethepioneeringworkofBonehandFranklin[9],thatallowstheadversarytoobtainthedecryptionkeyofany(non-target)receiverofitschoice.Thesecondisthatthetargetidentitiesarechosenbytheadversary.(Wewillachievefull,ratherthanselective-idsecurity[15].)IBEcanconvenientlyreplacePKEinapplicationssuchasthosementionedabove,makingitsSOA-securityimportant.Beyondthis,wefeelthatdeterminingwhetherSOA-secureIBEispossibleisaquestionofbothfoundationalandtechnicalinterest.Contributionsinbrief.Weprovideasimulation-based,semanticsecurityformalizationofSOA-secureIBE.(Thismeansourresultsdonotneedtoassumeconditionalre-sampleabilityofmessagespaces,incontrasttosomeoftheresultsof[2]forIND-stylenotions.)WeprovideageneralparadigmtoachieveSOA-secureIBEbasedonIBEschemesthatareIND-CPAandhaveapropertywecall1-Sided1SchemeParsCtxtKeysEncDecF/SAssumptionLoRn+6555exp5prFDLINBBoR4222exp2prFGSDFig.1.Our1SPOIND-CPAIBEschemes.Theseencrypt1-bitmessages.Bit-by-bitencryptionyieldsSOA-secureIBEschemesencryptingfullmessages.\Parsisthesizeofthepublicparameters,\Ctxtoftheciphertextand\Keysofthedecryptionkeys,allingroupelements,withnthelengthofidentities.(Inpracticen=160byhashingidentities.)\Encand\Decaretheencryptionand