hashhenhenlu.com

WeakadaptivechosenciphertextsecurehybridencryptionschemeXianhuiLu1,XuejiaLai2,DakeHe1,GuominLi1Email:luxianhui@gmail.
com1:SchoolofInformationScience&Technology,SWJTU,Chengdu,China2:Dept.
ofComputerScienceandEngineering,SJTU,Shanghai,ChinaAbstract.
Weproposeasecuritynotionnamedasweakadaptivechosenciphertextsecurity(IND-WCCA)forhybridencryptionschemes.
Althoughitisweakerthanadaptivechosenciphertextsecurity(IND-CCA),aIND-WCCAsecurehybridencryptionschemecanbeusedinanysituationsthataIND-CCAsecurehybridencryptionschemeusedin.
WeshowthatIND-WCCAsecurehybridencryptionschemecanbeconstructedfromIND-CCAsecureKEMandIND-PAsecureDEM.
SinceIND-PAistheba-sicrequirementofsymmetrickeyencryptionschemes,IND-WCCAhybridencryptionschemeisveryexibleandcanusemostofthestreamciphersandblockciphersastheDEMpartofthescheme.
UsethenewsecurenotionwecanrenecurrentIND-CCAsecurehybridencryptionschemesandgetmoreecientIND-WCCAsecurehybridencryptionschemes.
Keywords:hybridencryption,KEM,DEM,IND-WCCA1IntroductionPublickeyencryptionschemes(alsocalledasymmetricencryptionschemes)oftenlimitthemessagespacetoaparticulargroup,whichcanberestrictivewhenonewantstoencryptarbitrarymessages.
Forthispurposehybridschemesaredevised.
Inthesecryptosystemsasymmetricencryptionschemeisusedtoovercometheproblemstypicallyassociatedwithencryptinglongmessagesusing"pure"asymmetrictechniques.
Thisistypicallyachievedbyencryptingthemessagewithasymmetricencryptionschemeandarandomlygeneratedsymmetrickey.
Thisrandomsymmetrickeyisthensomehowencryptedusinganasymmetricencryptionscheme.
Thisapproachhasbeensuccessfullyusedformanyyears[2–9].
OneimportantadvanceinhybridcryptographyisthedevelopmentoftheKEM/DEMmodelforhybridencryptionalgorithms[10].
Thismodelsplitsahybridencryptionschemeintotwodistinctcomponents:anasymmetrickeyencapsulationmechanism(KEM)andasymmetricdataencapsulationmechanisms(DEM).
WhilsttheKEM/DEMmodeldoesnotmodelallpossiblehybridencryptionschemes,andthereareseveralexamplesofhybridencryptionschemesthatdonottintotheKEM/DEMmodel[3,4,17],itdoeshavetheadvantageofallowingthesecurityrequirementsoftheasymmetricandsymmetricpartsoftheschemetobecompletelyseparatedandstudiedindependently.
Thisapproachhasproventobeverypopularandseveralemergingstandardsarestronglysupportingitsuse,includingtheISO/IECstandardonasymmetricencryption[11].
Securityagainstadaptivechosenciphertextattacks(IND-CCAsecurity)[19–21]isastrongandusefulnotionofsecurityforpublickeyencryptionschemes,anditiscommonlyacceptedasthesecuritynotionofchoiceforencryptionschemesthataretobepluggedintoaprotocolrunninginanarbitrarysetting[22].
Asakindofpublickeyencryptionscheme,hybridencryptionschemesaredesignedtobeIND-CCAsecure.
CramerandShoup'swork[10]showsthatinordertoobtainaIND-CCAsecurehybridencryptionscheme,itissucientthatbothKEMandDEMareIND-CCAsecure.
KurosawaandDesmedtproposedanecienthybridschemenamedasKD04[17].
AlthoughthekeyencapsulationpartofKD04(KD04-KEM)isnotIND-CCAsecure[25],thewholeschemecanbeprovedtobeIND-CCAsecure.
ThusKurosawa-Desmedt'sschemepointsoutthattoobtainIND-CCAsecurehybridencryption,requiringbothKEM/DEMtobeIND-CCAsecure,whilebeingasucientcondition,maynotbeanecessaryone,andmightindeedbeanoverkill.
1.
1OurcontributionsWeproposeasecuritynotionnamedasweakadaptivechosenciphertextsecurity(IND-WCCA)forhybridencryptionschemes.
Inanadaptivechosenciphertextattackgametheadversaryisforbiddentoquerythedecryptionoraclewiththechallengeciphertext.
WenoticethatifonecanrefusetodecryptthechallengeciphertexthecanalsorefusetodecryptaciphertextwhoseKEMpartisthesameasthatofthechallengeciphertext.
Sowedenetheweakadaptivechosenciphertextattackgame,inwhichtheadversaryisnotallowedtoquerythedecryptionoraclewithaciphertextwhoseKEMpartisthesameasthatofthethechallengeciphertext.
WeseethatifwerefusetodecryptanyciphertextwhoseKEMpartisthesameasthatofthechallengeciphertext,thenaIND-WCCAsecurehybridencryptionschemecanbeusedinanysituationsthataIND-CCAsecurehybridencryptionschemeusedin,althoughitisweakerthanadaptivechosenciphertextsecurity.
WeshowthataIND-WCCAsecurehybridencryptionschemecanbeconstructedfromaIND-CCAsecureKEMandaIND-PAsecureDEM.
SinceIND-PAisthebasicrequirementofsymmetrickeyencryptionschemes,IND-WCCAhybridencryptionschemeisveryexibleandcanusemostofthestreamciphersandblockciphersastheDEMpartofthescheme.
UsethenewsecuritynotionwecanrenecurrentIND-CCAsecurehybridencryptionschemesandgetmoreecientIND-WCCAsecurehybridencryptionschemes.
1.
2Relatedworktag-KEM:Abeetalpresentedanewframework[23],whichmakesuseofanewobjectcalled"tag-KEM".
Theydenedanindependentsecuritycriteriaforthetag-KEM.
Thesecuritycriteriathattheyproposeforthetag-KEMisstricterthanforaKEM(asecureKEMwillnotbeasecuretag-KEM)butallowsfortheuseofaDEMthatisonlysecureagainstpassiveattacks.
UsingthisnewframeworktheycanreneseveralhybridschemesincludingFujisaki-Okamotoconversion[3],BallareandRogaway'sscheme[2]andREACT-RSA[9].
RemoveMACfromDHIES:M.
Abdalla,M.
BellareandP.
RogawayproposedanecientDie-HellmanIntegratedEncryptionScheme(DHIES)[7].
DHIESisnowembodiedinthree(draft)standards[13–15].
ItisanaturalextensionoftheElGamalscheme[1],andenhancedElGamalinacoupleofwaysimportanttocryptographicpractice.
First,itprovidesthecapabilityofencryptingarbitrarybitstringswhileElGamalrequiresthatmessagebeagroupelement.
Second,itissecureagainstchosenciphertextattack,whileElGamalissecureagainstchosenplaintextattack.
MostimportantlyDHIESrealizedtheabovetwogoalswithoutincreasingthenumberofgroupoperationsforencryptionanddecryption,andwithoutincreasingkeysizesrelativetoElGamal.
TheCCAsecurityofDHIESreliesontheOracleDie-Hellmanassumption(ODH).
KurosawaandMatsuo[18]showedthatMACcanbeeliminatedfromDHIESiftheunderlyingsymmetric-keyencryption(SKE)schemeissecureinthesenseofIND-CCA(secureagainstadaptivechosenciphertextattacks).
Theirschemeoerstherstsecurepublic-keyencryptionschemewithnoredundancyinthestandardmodel.
SecurehybridencryptionfromweakenedKEM:HofheinzandKiltz[26]putforwardanewparadigmforbuildinghybridencryptionschemesfromconstrainedchosenciphertextsecure(CCCA)KEMsplusauthenticatedsymmetricencryptionscheme.
CCCAhaslessdemandingse-curityrequirementsthanstandardadaptivechosenciphertextsecurity,itrequirestheadversarytohaveacertainplaintextknowledgewhenmakingadecapsulationquery.
CCCAcanbeusedtoexpressthekurosawa-Desmedthybridencryptionschemeitsgeneralizationstohash-proofsystemsinanabstractKEM/DEMsecurityframework.
Tightsecuritywithoutredundancy:Boyen[27]presentsaminimalistpublickeyencryptionscheme,ascompactasElGamal,butwithadaptivechosen-ciphertextsecurityunderthegapDie-Hellmanassumptionintherandomoraclemodel.
Boyenusesadual-hashdevicethatprovidestightredundancy-freeimplicitvalidation.
Thesystemisverysimpleandcompact:onellipticcurveswith80-bitsecurity,a160-bitplaintextbecomesa320-bitciphertext.
1.
3OutlineInsection2wereviewthebasicdenitionsofKEM,DEM,hybridencryptionscheme,OracleDie-HelmmanassumptionanddecisionalDie-Hellmanassumption.
Insection3weproposethenewsecuritynotionforhybridencryptionscheme:weakadaptivechosenciphertextsecurity(IND-WCCAsecurity)andshowedthatIND-WCCAsecurehybridencryptionschemecanbeconstructfromIND-CCAsecureKEMandIND-PA(secureagainstpassiveattack)secureDEM.
Insection4weshowthatusingthenewsecuritynotiontheexistinghybridencryptionschemecanberenedandyieldmoreecientscheme.
Finallywegivetheconclusioninsection5.
2PreliminariesInthissectionwereviewthedenitionsofKEM,DEM,hybridencryptionscheme,OracleDie-Hellmanassumption.
Indescribingprobabilisticprocesses,wewritexR←XtodenotetheactionofassigningtothevariablexavaluesampledaccordingtothedistributionX.
IfSisaniteset,wesimplywritesR←StodenoteassignmenttosofanelementsampledfromuniformdistributiononS.
IfAisaprobabilisticalgorithmandxaninput,thenA(x)denotestheoutputdistributionofAoninputx.
Thus,wewriteyR←A(x)todenoteofrunningalgorithmAoninputxandassigningtheoutputtothevariabley.
2.
1KeyEncapsulationMechanismAkeyencapsulationmechanismconsiststhefollowingalgorithms:–KEM.
KeyGen(1k):Aprobabilisticpolynomial-timekeygenerationalgorithmtakesasinputasecurityparameter(1k)andoutputsapublickeyPKandsecretkeySK.
Wewrite(PK,SK)←KEM.
KeyGen(1k)–KEM.
Encrypt(PK):Aprobabilisticpolynomial-timeencryptionalgorithmtakesasinputthepublickeyPK,andoutputsapair(K,ψ),whereK∈KD(KDisthekeyspace)isakeyandψisaciphertext.
Wewrite(K,ψ)←KEM.
Encrypt(PK)–KEM.
Decrypt(SK,ψ):AdecryptionalgorithmtakesasinputaciphertextψandthesecretkeySK.
ItreturnsakeyK.
WewriteK←KEM.
Decrypt(SK,ψ).
Werequirethatforall(PK,SK)outputbyKEM.
KeyGen(1k),all(K,ψ)∈[KEM.
Encrypt(PK)],wehaveKEM.
Decrypt(SK,ψ)=K.
AKEMschemeissecureagainstadaptivechosenciphertextattacksiftheadvantageofanyadversaryinthefollowinggameisnegligibleinthesecurityparameterk:1.
Theadversaryqueriesakeygenerationoracle.
Thekeygenerationoraclecomputes(PK,SK)←KEM.
KeyGen(1k)andrespondswithPK.
2.
Theadversarymakesasequenceofcallstothedecryptionoracle.
Foreachdecryptionor-aclequerytheadversarysubmitsaciphertextψ,andthedecryptionoraclerespondswithKEM.
Decrypt(SK,ψ).
3.
Theadversaryqueriesanencryptionoracle.
Theencryptionoraclecomputes:bR←{0,1};(K0,ψ)←PKE.
Encrypt(PK,mb);K1R←KD;andrespondswith(Kb,ψ).
4.
Theadversarycontinuestomakecallstothedecryptionoracleexceptthatitmaynotrequestthedecryptionofψ.
5.
Finally,theadversaryoutputsaguessb.
Theadversary'sadvantageintheabovegameisAdvCCAKEM,A(k)=|Pr[b=b]1/2|.
IfaKEMissecureagainstadpativechosenciphertextattackdenedintheabovegamewesayitisIND-CCAsecure.
2.
2DataEncapsulationMechanismAdataencapsulationmechanismDEMconsistsoftwoalgorithms:–DEM.
Encrypt(k,m):Thedeterministic,polynomial-timeencryptionalgorithmtakesasinputakeyk,andamessagem,andoutputsaciphertextχ.
Wewriteχ←DEM.
Encrypt(k,m)–DEM.
Decrypt(k,χ):Thedeterministic,polynomial-timedecryptionalgorithmtakesasinputakeyk,andaciphertextχ,andoutputsamessagemorthespecialsymbolreject.
Wewritem←DEM.
Decrypt(k,χ)WerequirethatforallkLen∈N,forallk∈{0,1}kLen,kLendenotesthelengthofthekeyofDEM,andforallm∈{0,1},wehave:DEM.
Decrypt(k,DEM.
Encrypt(k,m))=m.
ADEMissecureagainstpassiveattacksiftheadvantageofanyprobabilistic,polynomial-timeadversaryAinthefollowinggameisnegligibleinthesecurityparameterkLen:1.
Thechallengerrandomlygeneratesanappropriatelysizedkeyk∈{0,1}kLen.
2.
Aqueriesanencryptionoraclewithtwomessagesm0,m1,|m0|=|m1|.
Abitbisrandomlychosenandtheadversaryisgivena"challengeciphertext"χ←DEM.
Encrypt(k,mb).
3.
Finally,Aoutputsaguessb.
Theadversary'sadvantageintheabovegameisdenedasAdvPADEM,A(kLen)=|Pr[b=b]1/2|.
IfaDEMissecureagainstpassiveattackdenedintheabovegamewesayitisIND-PAsecure.
2.
3HybridEncryptionSchemeAhybridencryptionschemeisacombinationofKEMandDEMconsiststhefollowingalgorithms:–HE.
KeyGen(1k):HybridencryptionschemeusethekeygenerationalgorithmofKEMasit'skeygenerationalgorithmwhichisaprobabilisticpolynomial-timealgorithmtakesasinputasecurityparameter(1k)andoutputsapublickey/secretkeypair(PK,SK).
Wewrite(PK,SK)←HE.
KeyGen(1k).
–HE.
Encrypt(PK,m):GivenplaintextmandthepublickeyPK,theencryptionalgorithmofhybridencryptionschemeworksasfollow:(k,ψ)←KEM.
Encrypt(PK);χ←DEM.
Encrypt(k,m);C←(ψ,χ)First,theencryptionalgorithmusetheencryptionalgorithmofKEMproduceakeykandit'sciphertextψ,usingkeyasthekeyitusetheencryptionalgorithmofDEMtoencrypttheplaintextmandgettheciphertextχ.
Finallyitgettheciphertextofthehybridencryptionschemeincludingψandχ.
–HE.
Decrypt(SK,C):GivenciphertextC=(ψ,χ)andprivatekeySK,thedecryptionalgorithmofhybridencryptionworksasfollow.
k←KEM.
Decrypt(SK,ψ);m←DEM.
Decrypt(k,χ)First,thedecryptionalgorithmusethedecryptionalgorithmofKEMtodecryptψandgetthekeyk,thenusingkasthekeyitusethedecryptionalgorithmofDEMtodecryptχandgettheplaintextm.
Ahybridencryptionschemeissecureagainstadaptivechosenciphertextattacksiftheadvantageofanyadversaryinthefollowinggameisnegligibleinthesecurityparameterk:1.
Theadversaryqueriesakeygenerationoracle.
Thekeygenerationoraclecomputes(PK,SK)←HE.
KeyGen(1k)andrespondswithPK.
2.
Theadversarymakesasequenceofcallstothedecryptionoracle.
Foreachdecryptionor-aclequerytheadversarysubmitsaciphertextC,andthedecryptionoraclerespondswithHE.
Decrypt(SK,C).
3.
Theadversarysubmitstwomessagesm0,m1with|m0|=|m1|.
Oninputm0,m1theencryptionoraclecomputes:bR←{0,1};C←HE.
Encrypt(PK,mb)andrespondswithC.
4.
TheadversarycontinuestomakecallstothedecryptionoracleexceptthatitmaynotrequestthedecryptionofC.
5.
Finally,theadversaryoutputsaguessb.
Wesaytheadversarysucceedsifb=b,anddenotetheprobabilityofthiseventbyPrA[Succ].
Theadversary'sadvantageisdenedasAdvCCAHE,A=|PrA[Succ]1/2|.
IfahybridencryptionschemeissecureagainstadaptivechosenciphertextattackdenedintheabovegamewesayitisIND-CCAsecure.
2.
4OracleDie-HellmanAssumptionNowwereviewthedenitionoforacleDie-Hellmanassumption[7].
LetGbeagroupoflargeprimeorderq,H:{0,1}→{0,1}hLenbeacryptographichashfunctionandconsiderthefollowingtwoexperiments:experimentsExpodhrealG,H,A:uR←Zq;U←gu;vR←Zq;V←gv;W←H(guv)Hv(X)def=H(Xv);b←AHv(·)(U,V,W);returnbexperimentsExpodhrandG,H,A:uR←Zq;U←gu;vR←Zq;V←gv;W←{0,1}hLenHv(X)def=H(Xv);b←AHv(·)(U,V,W);returnbNowdenetheadvantageoftheAinviolatingtheoracleDie-HellmanassumptionasAdvodhG,H,A=Pr[ExpodhrealG,H,A=1]Pr[ExpodhrandG,H,A=1]HereAisallowedtomakeoraclequeriesthatdependontheguwiththesolerestrictionofnotbeingallowedtoqueryguitself.
WhenitistheExpodhrandG,H,Aexperimentwesay(g,U,V,W)comesfromtherandomdistributionR,otherwisewesay(g,U,V,W)comesfromtheODHdistributionO.
3WeakchosenciphertextsecurityInthissectionwedescribethenewsecuritynotionnamedasweakadaptivechosenciphertextsecurity(IND-WCCA)forhybridencryptionschemes.
Inanadaptivechosenciphertextattackgametheadversaryisforbiddentoquerythedecryptionoraclewiththechallengeciphertext.
Dierentwithpureasymmetricencryptionschemetherearetwoindependentpartintheciphertextofahybridencryptionscheme,ciphertextoftheKEMpartandciphertextoftheDEMpart.
WenoticethatifonecanrefusetodecryptthechallengeciphertexthecanalsorefusetodecryptaciphertextwhoseKEMpartisthesameasthatofthechallengeciphertext.
InfactcheckingonlytheKEMciphertextpartismoreecientthancheckingthewholeciphertext.
Sowedenetheweakadaptivechosenciphertextattackgame,inwhichtheadversaryisnotallowedtoquerythedecryptionoraclewithanyciphertextwhoseKEMpartisthesameasthatofthechallengeciphertext.
ItisclearthatifwerejectalltheciphertextwhoseKEMpartisthesameasthatofthechallengeciphertextthentherewillbenodierencebetweenIND-WCCAandIND-CCA.
WeseethatalthoughIND-WCCAisweakerthanIND-CCA,aIND-WCCAsecurehybridencryptionschemecanbeusedinanysituationsthataIND-CCAsecurehybridencryptionschemeusedin.
NowwegivethedetaildescriptionofIND-WCCAsecurity.
AhybridencryptionschemeissecureagainstweakadaptivechosenciphertextattacksiftheadvantageofanyadversaryintheIND-WCCAgamedenedinthefollowingisnegligibleinthesecurityparameterk:1.
Theadversaryqueriesakeygenerationoracle.
Thekeygenerationoraclecomputes(PK,SK)←HE.
KeyGen(1k)andrespondswithPK.
2.
Theadversarymakesasequenceofcallstothedecryptionoracle.
ForeachdecryptionoraclequerytheadversarysubmitsaciphertextCi=(ψi,χi),andthedecryptionoraclerespondswithHE.
Decrypt(SK,Ci).
3.
Theadversarysubmitstwomessagesm0,m1with|m0|=|m1|.
Oninputm0,m1theencryptionoraclecomputes:bR←{0,1};(ψ,χ)←HE.
Encrypt(PK,mb)andrespondswithC=(ψ,χ).
4.
TheadversarycontinuestomakecallstothedecryptionoracleexceptthatitmaynotrequestthedecryptionofciphertextCi=(ψi,χi)thatψi=ψ.
5.
Finally,theadversaryoutputsaguessb.
Wesaytheadversarysucceedsifb=b,anddenotetheprobabilityofthiseventbyPrA[Succ].
Theadversary'sadvantageisdenedasAdvWCCAHE,A=|PrA[Succ]1/2|.
Ifahybridencryp-tionschemeissecureagainstweakadaptivechosenciphertextattackdenedintheabovegamewesayitisIND-WCCAsecure.
WewillshowthataIND-WCCAsecurehybridencryptionschemecanbeconstructedfromaIND-CCAsecureKEMandaIND-PAsecureDEM.
Theorem1.
TheKEM/DEMhybridencryptionschemeissecureagainstweakadaptivechosenciphertextattacksassumingthat(1)KEMissecureagainstadaptivechosenciphertextattack,(2)DEMissecureagainstpassiveattack.
SupposethereisanadversarycanbreaktheKEM/DEMhybridencryptionschemeintheIND-WCCAattackgame.
FromthedenitionweseethattheIND-WCCAgamecanbeseenastheIND-CCAgameofKEM.
IfKEMisIND-CCAsecure,thenthekeythatDEMusestoencryptthechallengeplaintextisindependentfromtheadversary'sviewexceptanegligibleprobabilityAdvCCAKEM,A.
SotheIND-WCCAgamecanbeseenastheIND-PAattackgameofDEM.
SinceDEMisIND-PAsecure,bisindependentfromtheadversary'sviewexceptanegligibleprobabilityAdvPADEM,A.
Finallywegetthat:AdvWCCAHE,A≤AdvPADEM,A+AdvCCAKEM,ASinceAdvPADEM,AandAdvCCAKEM,AarenegligiblevalueswehavethatAdvPADEM,A+AdvCCAKEM,Aisalsoanegligiblevalue.
SoAdvWCCAHE,Aisnegligibleandthehybridencryp-tionschemeisIND-WCCAsecure.
Thatcompletestheproofoftheorem1.
4IND-WCCAsecurehybridencryptionschemeInsection3weshowedthatIND-WCCAsecurehybridencryptionschemescanbeconstructedfromIND-CCAsecureKEMandIND-PAsecureDEM.
SousethenewsecuritynotionwecanrenecurrentIND-CCAsecurehybridencryptionschemesandgetmoreecientIND-WCCAsecurehybridencryptionschemes.
InthissectionwegiveanecienthybridschemefromDHIES[7]asanexample.
Finallywecomparethenewschemewiththemostecientexistingschemesandshowthatthenewschemeismoreecient.
4.
1IND-WCCAsecurehybridencryptionschemefromDHIESRemovetheMACfromDHIES[7]wecangetaIND-WCCAsecurehybridschemeWDHIESasfollow:–HE.
KeyGen(1k):AssumethatGisgroupoforderqwhereqisalargeprime.
gR←G;xR←Zq;h←gxPK=(g,h,H,DEM);SK=(x)HereH:{0,1}→{0,1}kLenisacryptographichashfunctionusedinODHoracle,DEMissecureagainstpassiveattack.
–HE.
Encrypt(PK,m):Givenamessagem,theencryptionalgorithmrunsasfollows.
rR←Zq;ψ←gr;k←H(hr);χ←DEM.
Encrypt(k,m);C←(ψ,χ)–HE.
Decrypt(SK,C):GivenaciphertextC=(ψ,χ),thedecryptionalgorithmrunsasfollows.
k←H(ψx);m←DEM.
Decrypt(k,χ);Beforetheformalsecurityproofwegivesomeintuitiontoshowthatthenewschemeissecureagainstweakactiveattacks.
TheODH(OracleDie-Hellman)[7]assumptionguaranteesthatdif-ferentKEMciphertexts(c1)willyielddierentkeysindependenttoeachother.
Sotheadversarycannotgettheinformationofbfromthedecryptionoracle.
TheODHassumptionalsoassuresthattheadversarycannotgettheinformationofbfromthechallengeciphertext(theoutputoftheencryptionoracle).
FinallywehavethatthenewschemeisIND-WCCAsecurebasedontheODHassumption.
Nowwegivetheformalproofofthenewscheme.
Theorem2.
WDHIESissecureagainstweakadaptivechosenciphertextattackassumingthat(1)theoracleDie-HellmanproblemishardingroupG,(2)DEMisIND-PAsecure.
Toprovethetheorem,wewillassumethatthereisanadversarythatcanbreakthecryptosystem,andDEMisIND-PAsecureandshowhowtousethisadversarytoconstructastatisticaltestfortheODHproblem.
Forthestatisticaltest,wearegiven(g,U,V,W)comingfromeithertherandomdistributionRortheODHdistributionO.
Atahighlevel,ourconstructionworksasfollows.
Webuildasimulatorthatsimulatesthejointdistributionconsistingofadversary'sviewinitsattackonthecryptosystem,andthehiddenbitbgeneratedbythegeneratedoracle(whichisnotapartoftheadversary'sview).
WewillshowthatiftheinputcomesfromO,thesimulationwillbenearlyperfect,andsotheadversarywillhaveanon-negligibleadvantageinguessingthehiddenbitb.
WewillalsoshowthatiftheinputcomesfromR,thentheadversary'sviewisessentiallyindependentofb,andthereforetheadversary'sadvantageisnegligible.
ThisimmediatelyimpliesastatisticaltestdistinguishingRfromO:runthesimulatorandadversarytogether,andifthesimulatoroutputsbandtheadversaryoutputsb,thedistinguisheroutputs1ifb=b,and0otherwise.
Wenowgivethedetailsofthesimulator.
Theinputtothesimulatoris(g,U,V,W).
Thesimu-latorsetsh←V.
Thepublickeythattheadversaryseesis(g,h,H,DEM),whereH:{0,1}→{0,1}kLenisacryptographichashfunctionusedinODHoracle,DEMissecureagainstpassiveattack.
Firstwedescribethesimulationoftheencryptionoracle.
Givenm0,m1,thesimulatorchoosesb∈{0,1}atrandom,andcomputesk←W;ψ←U;χ←DEM.
Encrypt(k,mb);andoutputs(ψ,χ)Wenowdescribethesimulationofthedecryptionoracle.
Given(ψi,χi),thesimulatorrunsasfollow:ki←Hv(ψi)mi←DEM.
Decrypt(ki,χi)hereHv(X)=H(Xv)istheODHoracle.
Finallythesimulatoroutputsmi.
Thatcompletesthedescriptionofthesimulator.
Aswewillseethetheoremnowfollowsimme-diatelyfromthefollowingtwolemmas.
Lemma1.
Ifthesimulator'sinputcomesfromO,thejointdistributionoftheadversary'sviewandthehiddenbitbisstatisticallyindistinguishablefromthatintheactualattack.
Considerthejointdistributionoftheadversary'sviewandthebitbwhentheinputcomesfromthedistributionO.
SayU=gu,V=gv,W=H(guv).
Itisclearinthiscasethattheoutputoftheencryptionoraclehastherightdistribution,since:k=W=H(guv)=H(hu);ψ=U=guTocompletetheproof,weneedtoarguethattheoutputofthedecryptionoraclehastherightdistribution.
Given(ψi,χi),sincetheadversaryisnotallowedtoquerythedecryptionoraclewithciphertextthatψi=ψ=Uwehave:Hv(ψi)=Hv(gri)=H(gvri)=H(Vri)=H(hri)=kiDEM.
Decrypt(ki,χi)=mitherefore,thedecryptionoracleoutputsmijustasitshould.
Sothejointdistributionoftheadversary'sviewandthehiddenbitbisjustthesameasthatintheactualattack.
Lemma2.
Ifthesimulator'sinputcomesfromR,thedistributionofthehiddenbitbis(essentially)independentfromtheadversary'sview.
LetU=gu,V=gv,W=H(gw),w=uv.
Itisclearthatthedistributionofk=Wisindependentfromtheadversary'sviewconditiononψ=U=guandtheadversarycannotgettheinformationofk=Wfromthedecryptionoracletoo.
Sothedistributionofk=Wisindependentfromtheadversary'sview.
SinceDEMisIND-PAsecure,ityieldthatthedistributionofthehiddenbitbisindependentfromtheadversary'sview.
Thiscompletetheproofoftheorem2.
Table1.
EciencycomparisonSchemeEncryption(exp)Decryption(exp)Cipher-textoverhead(bit)AssumptionDEMSecurityDHIES2(2exp+0mexp)1(1exp+0mexp)|q|+|t|ODHIND-CPAKM042(2exp+0mexp)1(1exp+0mexp)|q|ODHIND-CCABoyen072(2exp+0mexp)1(1exp+0mexp)|q|GDH,ROMWDHIES2(2exp+0mexp)1(1exp+0mexp)|q|ODHIND-PA4.
2EciencyCompareTheeciencyofourschemes,DHIES,KM04,Boyen07islistedintable1.
Intable1DHIESistheschemein[7],KM04istheschemein[18],Boyen07istheschemein[27].
Whentabulatingcomputationaleciencyhashfunctionandblockcipherevaluationsareignored,multi-exponentiation(mexp)iscountedas1.
5exponentiations(exp).
Ciphertextoverheadrepresentsthedierencebetweentheciphertextlengthandthemessagelength,and|q|isthelengthofagroupelement,|t|isthelengthofthetaginDHIES.
ItisclearthatWDHIESismoreecientthanDHIESinbandwidthandthesameecientasKM04andBoyen07.
WDHIESonlyneedaIND-PAsecureDEM,whileKM04needaIND-CCAsecureDEM.
ComparedwithBoyen07,WDHIESismoresimpleandsecureinthestandardmodel,whileBoyen07issecureinrandomoraclemodel.
5ConclusionHybridencryptionschemeisakindofpublickeyencryptionschemethatcontainstwoindependentpart,theKEMpartandtheDEMpart.
Accordinglytherearetwoindependentpartinthecipher-textofhybridencryptionschemes,ciphertextoftheKEMpartandciphertextoftheDEMpart.
InthetraditionalIND-CCAattackgameonpublickeyencryptionscheme,theadversaryisnotallowedtoquerythedecryptionoraclewiththechallengeciphertext.
Wenoticethatinthecaseofhybridencryptionschemeifonecanrejecttodecryptciphertextwhichisthesameasthechallengeciphertext,hecanalsorejecttodecryptciphertextswhoseKEMpartisthesameasthatofthechallengeciphertext.
Soweproposeasecuritynotionnamedasweakadaptivechosenciphertextsecurity(IND-WCCA)forhybridencryptionschemes.
IntheIND-WCCAattackgameonahybridencryptionschemetheadversaryisnotallowedtoquerythedecryptionoraclewithciphertextswhoseKEMpartisthesamethatofthechallengeciphertext.
Althoughitisweakerthanadaptivechosenciphertextsecurity(IND-CCA),aIND-WCCAsecurehybridencryptionschemecanbeusedinanycasesthataIND-CCAsecurehybridencryptionschemeusedin.
WeshowthatIND-WCCAsecurehybridencryptionschemecanbeconstructedfromIND-CCAsecureKEMandIND-PAsecureDEM.
SinceIND-PAisthebasicrequirementofsymmetrickeyencryptionschemes,IND-WCCAhybridencryptionschemeisveryexibleandcanusemoststreamciphersandblockciphersastheDEMpartofthescheme.
UsethenewsecurenotionwecanrenecurrentIND-CCAsecurehybridencryptionschemesandgetmoreecientIND-WCCAsecurehybridencryptionschemes.
References1.
T.
ElGamal.
Apublickeycryptosystemandsignatureschemebasedondiscretelogarithms.
IEEETransactionsonInformationTheory,31:469C472,1985.
2.
M.
BellareandP.
Rogaway.
Randomoraclesarepractical:aparadigmfordesigningecientprotocols.
In1stACMCCCS,pages62C73.
AssociationforComputingMachinery,1993.
3.
E.
FujisakiandT.
Okamoto.
Secureintegrationofasymmetricandsymmetricencryptionschemes.
InM.
Wiener,editor,AdvancesinCryptol-ogy-Crypto'99,volume1666ofLectureNotesinComputerScience,pages535-554.
Springer-Verlag,1999.
4.
T.
Okamoto,S.
Uchiyama,andE.
Fujisaki.
EPOC:Ecientprobabilisticpublic-keyencryption.
SubmissiontoP1363a:StandardSpecicationsforPublic-KeyCryptography,AdditionalTechniques,1999.
5.
S.
Lucks.
AvariantoftheCramer-Shoupcryptosystemforgroupsofunknownorder.
InY.
Zheng,editor,AdvancesinCryptology-Asiacrypt2002,volume2501ofLectureNotesinComputerScience,pages27-45.
Springer-Verlag,2002.
6.
M.
Abdalla,M.
Bellare,andP.
Rogaway.
DHAES:AnencryptionschemebasedontheDie-Hellmanproblem.
SubmissiontoP1363a:StandardSpecicationsforPublic-KeyCryptography,AdditionalTechniques,2000.
7.
M.
Abdalla,M.
BellareandP.
Rogaway.
DHIES:AnencryptionschemebasedontheDie-HellmanProblemExtendedabstract,entitledTheOracleDie-HellmanAssumptionsandanAnalysisofDHIES,wasinTopicsinCryptology-CT-RSA01,LectureNotesinComputerScienceVol.
2020,D.
Naccacheed,Springer-Verlag,20018.
V.
Shoup.
Usinghashfunctionsasahedgeagainstchosenciphertextattack.
InB.
Preneel,editor,AdvancesinCryptology-Eurocrypt2000,volume1807ofLectureNotesinComputerScience,pages275-288.
Springer-Verlag,2000.
9.
T.
OkamotoandD.
Pointcheval.
REACT:Rapidenhanced-securityasymmetriccryptosystemtransform.
InRSA2001,LNCS,Springer-Verlag,2001.
10.
R.
CramerandV.
Shoup.
Designandanalysisofpracticalpublic-keyencryptionschemessecureagainstadaptivechosenciphertextattack.
SIAMJournalonComputing,33(1):167-226,2003.
11.
InternationalOrganizationforStandardization.
ISO/IECCD18033-2,Informationtechnology–Securitytech-niques–EncryptionAlgo-rithms–Part2:AsymmetricCiphers,2003.
12.
InternationalOrganizationforStandardization.
ISO/IEC18033-1,Informationtechnology–Securitytechniques–EncryptionAlgorithms–Part1:General,2003.
13.
AmericanNationalStandardsInstitute(ANSI)X9.
F1subcommittee.
ANSIX9.
63PublickeycryptographyfortheFinancialServicesIndustry:Ellipticcurvekeyagreementandkeytransportschemes,July51998.
Workingdraftversion2.
0.
14.
IEEEP1363aCommittee.
IEEEP1363a/D9standardspecicationsforpublickeycryptography:Additionaltechniques.
http://grouper.
ieee.
org/groups/1363/index.
html/,June2001.
DraftVersion9.
15.
Certicomresearch,standardsforecientcryptographygroup(SECG)sec1:Ellipticcurvecryptography.
http://www.
secg.
org/secgdocs.
htm,Sept.
202000.
Version1.
0.
16.
V.
Shoup.
ISO18033-2:Anemergingstandardforpublic-keyencryption(committeedraft).
Availableathttp://shoup.
net/iso/,June32004.
17.
K.
KurosawaandY.
Desmedt.
Anewparadigmofhybridencryp-tionscheme.
InM.
Franklin,editor,AdvancesinCryptology-Crypto2004,volume3152ofLectureNotesinComputerSciene,pages426-442.
Springer-Verlag,2004.
18.
KaoruKurosawaandToshihikoMatsuo.
HowtoremoveMACfromDHIES.
InProceedingsofACISP2004,volume3108ofLNCS,pages236C47.
Springer,2004.
19.
M.
Bellare,A.
Desai,D.
Pointcheval,andP.
Rogaway,"RelationsAmongNotionsofSecurityforPublic-KeyEncryptionSchemes",Adv.
inCryptology-Crypto1998,LNCSvol.
1462,Springer-Verlag,pp.
26-45,1998;20.
D.
Dolev,C.
Dwork,andM.
Naor,"Non-MalleableCryptography",SIAMJ.
Computing,30(2):391-437,2000;21.
C.
RackoandD.
Simon,"Non-InteractiveZero-KnowledgeProofofKnowledgeandChosenCiphertextAttack",Adv.
inCryptology-Crypto1991,LNCSvol.
576,Springer-Vrlag,pp.
433-444,1991;22.
V.
Shoup,"WhyChosenCiphertextSecurityMatters",IBMResearchReportRZ3076,November,1998.
Avail-ableathttp://www.
shoup.
net/papers;23.
MasayukiAbe,RosarioGennaro,KaoruKurosawa,andVictorShoup,Tag-KEM/DEM:AnewframeworkforhybridencryptionandanewanalysisofKurosawa-DesmedtKEM",byAbe,Gennaro,Kurosawa,andShoup,inProc.
Eurocrypt2005.
24.
VictorShoup,Sequencesofgames:atoolfortamingcomplexityinsecurityproofs,manuscript,Nov.
30,2004.
Revised,May27,2005;Jan.
18,2006.
http://shoup.
net/papers/25.
D.
Hofheinz,J.
Herranz,andE.
Kiltz.
TheKurosawa-Desmedtkeyencapsulationisnotchosen-ciphertextsecure.
CryptologyePrintArchive,Report2006/207,2006.
http://eprint.
iacr.
org26.
DennisHofheinzandEikeKiltz.
SecureHybridEncryptionfromWeakenedKeyEncapsulation.
AdvancesinCryptology–CRYPTO2007,pp.
553–571LNCS4622(2007).
Springer-Verlag.
27.
XavierBoyen.
MiniatureCCA2PKEncryption:TightSecurityWithoutRedundancy.
InAdvancesinCryptology(ASIACRYPT2007),volume4833ofLectureNotesinComputerScience,pages485-501.
Springer,2007