contentcjblaze

CCA-SecureProxyRe-EncryptionwithoutPairingsJunShao1,2andZhenfuCao11DepartmentofComputerScienceandEngineeringShanghaiJiaoTongUniversity2CollegeofInformationSciencesandTechnologyPennsylvaniaStateUniversitychn.
junshao@gmail.
com;zfcao@cs.
sjtu.
edu.
cn.
Abstract.
Inaproxyre-encryptionscheme,asemi-trustedproxycantransformaciphertextunderAlice'spublickeyintoanotherciphertextthatBobcandecrypt.
However,theproxycannotaccesstheplaintext.
Duetoitstransformationproperty,proxyre-encryptioncanbeusedinmanyapplications,suchasencryptedemailforwarding.
Inthispaper,byusingsignatureofknowledgeandFijisaki-Okamotoconversion,weproposeaproxyre-encryptionschemewithoutpairings,inwhichtheproxycanonlytransformtheciphertextinonedirection.
Theproposalissecureagainstchosenciphertextattack(CCA)andcollusionattackintherandomoraclemodelbasedonDecisionalDie-Hellman(DDH)assumptionoverZN2andintegerfactorizationassumption,respectively.
Tothebestofourknowledge,itistherstunidirectionalPREschemewithCCAsecurityandcollusion-resistance.
Keywords:UnidirectionalPRE,DDH,randomoracle,CCAsecurity,collusion-resistance1IntroductionIn1998,Blaze,Bleumer,andStrauss[6]proposedtheconceptofproxyre-encryption(PRE),whereasemi-trustedproxycantransformaciphertextforAliceintoanotherciphertextthatBobcandecrypt.
3However,theproxycannotgettheplaintext.
Accordingtothedirectionoftransformation,PREschemesSupportedbyResearchFundfortheDoctoralProgramofHigherEducationNo.
20060248008,NationalNaturalScienceFoundationofChinaNo.
60673079,Spe-cialFoundationofHuaweiNo.
YZCB2006001,andNational973ProgramNo.
2007CB311201.
Correspondingauthor.
3Inalmostallrelatedpapers,theconceptofPREisintroducedas"PREallowsasemi-trustedproxytoconvertaciphertextunderAlice'spublickeytoanotherciphertextunderBob'spublickey".
However,allexistingunidirectionalPREschemes(includ-ingours)donotexactlyfollowthedenition.
Inparticular,intheseunidirectionalPREschemes,therearetwokindsofciphertexts,oneistheoriginalciphertext,andcanbeclassiedintotwotypes,oneisbidirectional,i.
e.
,theproxycantransformfromAlicetoBobandviceversa;theotherisunidirectional,i.
e.
,theproxycanonlyconvertinonedirection.
Blazeetal.
[6]alsogaveanothermethodtoclassifyPREschemes:multi-use,i.
e.
,theciphertextcanbetransformedfromAlicetoBobtoCharlieandsoon;andsingle-use,i.
e.
,theciphertextcanbetransformedonlyonce.
Duetoitstransformationproperty,PREcanbeusedinmanyapplications,includingsimplicationofkeydistribution[6],keyescrow[21],distributedlesystems[2,3],securityinpublish/subscribesystems[23],multicast[10],securecertiedemailmailinglists[24,22],theDRMofApple'siTunes[36],interoper-ablearchitectureofDRM[34],accesscontrol[35],andprivacyforpublictrans-portation[19].
Recently,Hohenbergeretal.
gotaresultofsecurelyobfuscatingre-encryption[20],whichistherstpositiveresultforobfuscatinganencryptionfunctionalityandagainstaseriesofimpossibilityresults[18,16,4].
SincetheintroductionofPREbyBlaze,Bleumer,andStrauss[6],therehavebeenmanypapers[6,21,2,3,17,9,11,25]thathaveproposeddierentPREschemeswithdierentsecurityproperties.
Someofthemarerelatedtochosenciphertextattack(CCA)security.
IvanandDodis[21]proposedaCCAsecu-ritymodelforPREandagenericconstructionofsingle-usePREinthesecuritymodel.
Nevertheless,theirsecuritymodelallowsthedelegatee(Bob)tomakeuseoftheproxyasanoracle.
Asaresult,theschemesonlysecureintheirsecuritymodelarenotenoughforsomeapplications.
Forexample,inencryptedemailforwarding,anadversary(Bob)mighthopetogainaccesstotheoriginalen-cryptedemailbyre-formingit,sendingittotheproxy,andthenhopingthattheproxyrespondswith,"Canyouforwardthefollowingtomeagain[Encryptedattachment.
]"Toxtheproblem,GreenandAteniese[17],CanettiandHohenberger[9]proposednewCCAsecuritymodelsforID-basedPREandPRE,respectively.
Inthesetwonewsecuritymodels,itrequiresthattheproxychecksthevalidityoftheciphertextbeforetransformation,whichiscalledpublicveriability.
Follow-ingthisintuition,therstCCAsecure,single-use,unidirectionalID-basedPREschemeintherandomoraclemodelandtherstCCAsecure,multi-use,bidirec-tionalPREschemeinthestandardmodelareproposedin[17,9],respectively.
However,theschemein[17]suersfromtheattackinRemark2.
Furthermore,thegenericconstructionofPREin[21]cannotbeprovedsecureintheCCAsecuritymodelin[9].
(SeeAppendixAfordetails.
Hereafter,wereferCCAse-curitytothedenitionin[9]orSection2ofthispaper.
)ChuandTzeng[11]proposedamulti-use,unidirectionalID-basedPREscheme,andclaimedthatitwasCCAsecureinthestandardmodel.
However,weshowedthatitwasnottrue[31],sinceitstransformedciphertext(Cv1,R,d1,d2,d2)canbemodiedtoanotherwell-formedtransformedciphertext(Cv1,R,d1F2(vk)r,d2,d2gr)bytheotheristhetransformedciphertext.
ThetransformedciphertextisnotexactlyastheciphertextunderBob'spublickey,butBobcandecryptthetransformedci-phertextonlybyhissecretkey.
Tothebestofourknowledge,onlythebidirectionalschemesin[6,9]satisfythedenition.
anyone,whererisrandomnumber.
Recently,LibertandVergnaud[25]pro-posedanewunidirectionalPREscheme,whichisreplayablechosenciphertextattack(RCCA)securebutnotCCA-secure.
ItisfairtosaythatthereisnoCCA-secureunidirectionalPREscheme.
4Furthermore,accordingtotheresultsin[5,29],thetimingofapairingcomputationismorethantwiceofthatofamodularexponentiationcomputation.
Hence,theCCA-secureunidirectionalPREschemeswithoutpairingsaredesired.
AnotherimportantsecuritynotiononunidirectionalPREiscollusion-resistance,whichdisallowsBobandtheproxytocolludetorevealAlice's(longterm)secretkey,butallowstherecoveryofAlice's"weak"secretkeyonly.
Inthiscase,Alicecandelegatedecryptionrights,whilekeepingsigningrightsforthesamepublickey.
Tillnow,thereareonlyafewPREschemes[2,3,25]holdingthissecurity.
5ThoughmanyPREschemeshavebeenproposed,wendthatnounidirec-tionalPREschemewithoutpairingsbutsatisfyingCCAsecurityandcollusion-resistancesimultaneously,evenintherandomoraclemodel.
Inthispaper,weattempttoproposesuchaunidirectionalPREscheme.
1.
1OurContributionWepresentaproxyre-encryptionschemewithoutpairings,namedschemeU,whichisunidirectionalandsingle-use,andprovenCCA-secureandcollusionresistantintherandomoraclemodelbasedonDecisionalDie-Hellman(DDH)assumptionoverZN2andintegerfactorizationassumption,respectively.
Here,Nisasafe-primemodulus.
ThedicultyinconstructingaCCAsecurePREschemeistoaddthepublicveriabilitytooriginalciphertexts.
ThispublicveriabilitycanpreventmaliciousBobfromgainingsomeadvantagebyusingtheproxyasanoracle.
Inpairingsetting,suchas[9],wecanusethegapDie-Hellmanproblem(decisionalDie-Hellmanproblemiseasy,butcomputationalDie-Hellmanproblemishard)toachievethis.
Inparticular,thegapDie-HellmanproblemallowsustocheckwhetherloggA=loghB.
Inthispaper,weusesignatureofknowledge[8,1]toprovideloggA=loghB,henceobtainingpublicveriabilityfororiginalcipher-texts.
Infact,usingthesignatureofknowledgetoprovidepublicveriabilityisduetoShoupandGennaro[33].
Furthermore,weuseFujisaki-Okamotocon-version[14,15]toprovidethevaliditycheckofbothoriginalciphertextsandre-encryptedciphertextsforthedecryptor(AliceorBob).
4Whenwepreparedthecamera-readyversion,wefoundanotherpaper[13]dealingthesimilarproblems,andgettingthesimilarresultswithus.
In[13],theauthorsuseSchnorrsignature[28]tomaketheoriginalciphertextbepubliclyveriable,whileweusesignatureofknowledge[8,1].
Inoursubmissionversion,wehaveaCCA-securebidirectionalPREscheme,however,thebidirectionalonein[13]beatsoursineveryaspects.
Hence,inthecurrentversion,weremovedourbidirectionalone,whichcanbefoundin[30].
Furthermore,theunidirectionalschemein[13]suersfromtheattackinRemark2.
5TheunidirectionalPREschemein[13]suersfromthecollusionattack.
Followingtheconstructionofthepublickeyencryptionschemewithdoubletrapdoorsin[7],schemeUholdscollusion-resistance.
Inparticular,thefactorsofNarethelongtermsecretkey,andanexponentisthe"week"secretkey,andrevealingtheexponentdoesnothurtthesecrecyofthefactorsofN.
Tothebestofourknowledge,schemeUistherstunidirectionalPREschemeholdingCCAsecurityandcollusion-resistancesimultaneously.
Finally,weextendschemeUtoschemeUT,wherethedelegatorcanrevoketheproxy'stransformationability.
Inparticular,theproxycanonlytransformtheciphertextduringarestrictedtimeinterval.
1.
2OrganizationTheremainingpaperisorganizedasfollows.
InSection2,wereviewthede-nitionsrelatedtoourproposals.
Inwhatfollows,wepresentschemeUanditssecurityanalysis,andschemeUTanditssecurityanalysis,inSection3andSection4,respectively.
InSection5wecompareschemeUwithpreviousunidi-rectionalPREschemes.
Finally,weconcludethepaperinSection6.
2PreliminariesInthissection,webrieyreviewthedenitionsrelatedtoourproposals,somesimilarcontentcanbefoundin[8,1,17,9].
2.
1PublicKeyEncryptionDenition1(PublicKeyEncryption(PKE)).
ApublickeyencryptionschemePKEisatripleofPPTalgorithms(KeyGen,Enc,Dec):–KeyGen(1k)→(pk,sk).
Oninputthesecurityparameter1k,thekeygenera-tionalgorithmKeyGenoutputsapublickeypkandasecretkeysk.
–Enc(pk,m)→C.
Oninputapublickeypkandamessageminthemessagespace,theencryptionalgorithmEncoutputsaciphertextC.
–Dec(sk,C)→m.
OninputasecretkeyskandaciphertextC,thedecryptionalgorithmDecoutputsamessageminthemessagespaceor⊥.
Correctness.
Thecorrectnesspropertyisthatforanymessageminthemes-sagespaceandanykeypair(pk,sk)←KeyGen(1k).
Thenthefollowingconditionmusthold:Dec(sk,Enc(pk,m))=m.
2.
2UnidirectionalProxyRe-EncryptionDenition2(UnidirectionalPRE).
Aunidirectionalproxyre-encryptionschemeUniPREisatupleofPPTalgorithms(KeyGen,ReKeyGen,Enc,ReEnc,Dec):–KeyGen,Enc,Dec:Identicaltothoseinpublickeyencryption.
–ReKeyGen(sk1,pk2)→rk1→2.
Oninputasecretkeysk1andapublickeypk2,there-encryptionkeygenerationalgorithmReKeyGenoutputsaunidi-rectionalre-encryptionkeyrk1→2.
–ReEnc(rk1→2,C1)→C2.
Oninputare-encryptionkeyrk1→2andacipher-textC1,there-encryptionalgorithmReEncoutputsare-encryptedciphertextC2or⊥.
Correctness.
Acorrectproxyre-encryptionschemeshouldsatisfytworequire-ments:Dec(sk,Enc(pk,m))=m,andDec(sk,ReEnc(ReKeyGen(sk,pk),C))=m,where(pk,sk),(pk,sk)←KeyGen(1k),andCistheciphertextofmessagemforpkfromalgorithmEncoralgorithmReEnc.
ChosenCiphertextSecurityforUnidirectionalProxyRe-Encryption.
Thissecuritynoteisamodicationofreplayablechosenciphertextsecurityin[25],wherethecorruptedpublickeysarenotdecidedbeforestartoftheUni-PRE-CCAgame,andtheadversaryisallowedadaptivecorruptionofusers6,andproxiesbetweencorruptedanduncorruptedusers.
Butunlike[25],werequirethatonewell-formedciphertextcannotbemodied(butcanbetransformed)tobeanotherwell-formedciphertext.
In[25],anyonecanmodifythetransformedci-phertext,suchthat(C1,C2,C2,C2,C3,C4,σ)→(C1,C2t,C2t1,C2t,C3,C4,σ),wheretisarandomnumberfromZp.
Notethatthissecuritymodelisonlyforsingle-usescheme.
Phase1:TheadversaryAissuesqueriesq1,qn1wherequeryqiisoneof:–PublickeygenerationoracleOpk:Oninputanindexi,7theChallengertakesasecurityparameterk,andrespondsbyrunningalgorithmKeyGen(1k)togenerateakeypair(pki,ski),givespkitoAandrecords(pki,ski)intableTK.
–SecretkeygenerationoracleOsk:OninputpkbyA,wherepkisfromOpk,theChallengersearchespkintableTKandreturnssk.
–Re-encryptionkeygenerationoracleOrk:Oninput(pk,pk)byA,wherepk,pkarefromOpk,theChallengerreturnsthere-encryptionkeyrkpk→pk=ReKeyGen(sk,pk),whereskisthesecretkeycorrespondingtopk.
–Re-encryptionoracleOre:Oninput(pk,pk,C)byA,wherepk,pkarefromOpk,there-encryptedciphertextC=ReEnc(ReKeyGen(sk,pk),C)isreturnedbytheChallenger,whereskisthesecretkeycorrespondingtopk.
–DecryptionoracleOdec:Oninput(pk,C),wherepkisfromOpk,theChal-lengerreturnsDec(sk,C),whereskisthesecretkeycorrespondingtopk.
6Thesecuritymodelin[13]doesnotallowsuchadaptivecorruption.
7Thisindexisjustusedtodistinguishdierentpublickeys.
Thesequeriesmaybeaskedadaptively,thatis,eachqueryqimaydependontherepliestoq1,qi1.
Challenge:OncetheadversaryAdecidesthatPhase1isover,itoutputstwoequallengthplaintextsm0,m1fromthemessagespace,andapublickeypkonwhichitwishestobechallenged.
Therearethreeconstraintsonthepublickeypk,(i)itisfromOpk;(ii)itdidnotappearinanyquerytoOskinPhase1;(iii)if(pk,)didappearinanyquerytoOrk,thendidnotappearinanyquerytoOsk.
TheChallengerpicksarandombitb∈{0,1}andsetsC=Enc(pk,mb).
ItsendsCasthechallengetoA.
Phase2:TheadversaryAissuesmorequeriesqn1+1,qnwherequeryqiisoneof:–Opk:TheChallengerrespondsasinPhase1.
–Osk:OninputpkbyA,ifthefollowingrequirementsareallsatised,theChallengerrespondsasinPhase1;otherwise,theChallengerterminatesthegame.
pkisfromOpk;pk=pk;(pk,pk)isnotaquerytoOrkbefore;(pk,pk,C)isnotaquerytoOrebefore,where(pk,C)isaderivative8of(pk,C).
–Ork:Oninput(pk,pk)byA,ifthefollowingrequirementsareallsatised,theChallengerrespondsasinPhase1;otherwise,theChallengerterminatesthegame.
pk,pkarefromOpk;ifpk=pk,thenpkisnotaquerytoOsk.
–Ore:Oninput(pk,pk,C)byA,ifthefollowingrequirementsareallsatised,theChallengerrespondsasinPhase1;otherwise,theChallengerterminatesthegame.
pk,pkarefromOpk;if(pk,C)isaderivativeof(pk,C),thenpkisnotaquerytoOsk.
–Odec:Oninput(pk,C),ifthefollowingrequirementsareallsatised,theChallengerrespondsasinPhase1;otherwise,theChallengerterminatesthegame.
pkisfromOpk;(pk,C)isnotaderivativeof(pk,C).
8Derivativesof(pk,C)aredenedasfollows[9]:1.
(pk,C)isaderivativeofitself.
2.
If(pk,C)isaderivativeof(pk,C)and(pk,C)isaderivativeof(pk,C),then(pk,C)isaderivativeof(pk,C).
3.
IfAhasqueriedOreoninput(pk,pk,C)andobtained(pk,C),then(pk,C)isaderivativeof(pk,C).
4.
IfAhasqueriedOrkoninput(pk,pk),andC=ReEnc(Ore(pk,pk),C),then(pk,C)isaderivativeof(pk,C).
Thesequeriesmaybealsoaskedadaptively.
Guess:Finally,theadversaryAoutputsaguessb∈{0,1}andwinsthegameifb=b.
WerefertosuchanadversaryAasaUni-PRE-CCAadversary.
WedeneadversaryA'sadvantageinattackingUniPREasthefollowingfunctionofthesecurityparameterk:AdvUniPRE,A(k)=|Pr[b=b]1/2|.
UsingtheUni-PRE-CCAgamewecandenechosenciphertextsecurityforunidirectionalproxyre-encryptionschemes.
Denition3(Uni-PRE-CCAsecurity).
Wesaythataunidirectionalproxyre-encryptionschemeUniPREissemanticallysecureagainstanadaptivechosenciphertextattackifforanypolynomialtimeUni-PRE-CCAadversaryAthefunctionAdvUniPRE,A(k)isnegligible.
Asshorthand,wesaythatUniPREisUni-PRE-CCAsecure.
Remark1.
In[25],theauthorsconsideredthismodelasastaticcorruptionmodel,sinceitdoesnotcapturesomescenarios,suchastheadversarygen-eratepublickeysonbehalfofcorruptedparties.
However,wethinkthismodelisanadaptivecorruptionmodel.
SinceAdaptiveSecurityusuallyreferstotheabilityoftheadversarytochoosewhichpartiestocorruptdependingontheinformationgatheredsofar,buttheChallengerstillgeneratesallparties'keypairs.
Allowingadversariestogeneratemaliciousparties'publickeysontheirownisusuallycalled"chosen-keymodel"[26].
9BesidesCCAsecurity,thereisanothersecuritynotion,collusionresistance,forunidirectionalPREschemes.
Denition4(Uni-PRE-CRsecurity).
10Wesaythataunidirectionalproxyre-encryptionschemeUniPREiscollusionresistantifforanypolynomialboundedadversaryA,thefollowingprobabilityisnegligible:Pr[(sk1,pk1)←KeyGen(1k),{(ski,pki)←KeyGen(1k)},{rki→1←ReKeyGen(ski,pk1)},{rk1→i←ReKeyGen(sk1,pki)},i=2,α→A(pk1,{pki,ski},{rk1→i},{rki→1}):α=sk1].
DuetoitssimilaritywiththatofunidirectionalPREschemes,weputthedeni-tionsofunidirectionalPREschemeswithtemporarydelegationintheAppendix.
2.
3SignatureofKnowledgeInourproposal,weapplythefollowingnon-interactivezero-knowledgeproofofknowledge,namedsignatureofknowledgeofequalityoftwodiscretelogarithms[8,1,32].
9WethankananonymousreviewerofIndocrypt2008topointoutthis.
10Thissecuritynotionisfrom[2,3],calledMasterSecretSecurity.
Denition5.
Lety1,y2,g,h∈G,GbeacyclicgroupofquadraticresiduesmoduloN2(Nisasafe-primemodulus),andH(·):{0,1}→{0,1}k(kisthesecurityparameter).
Apair(c,s),verifyingc=H(y1||y2||g||h||gsyc1||hsyc2||m)isasignatureofknowledgeofthediscretelogarithmofbothy1=gxw.
r.
t.
basegandy2=hxw.
r.
t.
baseh,onamessagem∈{0,1}.
Thepartyinpossessionofthesecretxisabletocomputethesignature,providedthatx=loggy1=loghy2,bychoosingarandomt∈{0,2|N2|+k1}(|n|isthebit-lengthofn).
Andthencomputingcandsas:c=H(y1||y2||g||h||gt||ht||m)ands=tcx.
WedenoteSoK.
Gen(y1,y2,g,h,m)asthegenerationoftheproof.
2.
4ComplexityAssumptionThesecurityofourproposalisbasedontheDecisionalDie-Hellmanassump-tion(DDH)overZN2.
DDHProblem.
TheDDHproblemisasfollows:Giveng,ga,gbforsomea,b∈ord(G)andT∈G,decidewhetherT=gab,whereGisacyclicgroupofquadraticresiduesmoduloN2(Nisasafe-primemodulus),gisarandomnumberofG.
AnalgorithmAhasadvantageεinsolvingDDHproblemif|Pr[A(g,ga,gb,gab)=0]Pr[A(g,ga,gb,T)=0]|≥ε,wheretheprobabilityisovertherandomchoicesofa,binord(G),therandomchoicesofg,TinG,andtherandombitsofA.
Denition6(DDHAssumption).
Wesaythattheε-DDHassumptionholdsifnoPPTalgorithmhasadvantageatleastεinsolvingtheDDHproblem.
NotethattheDDHproblemoverZN2iseasyifthefactorsofNisknown[7].
2.
5ThePublicKeyEncryptionwithDoubleTrapdoorsThebasicpublickeyencryptionofourproposalisthepublickeyencryptionwithdoubletrapdoorsin[7],namedBCP03.
Thefollowingdescriptionisfrom[7].
LetN=pqbeasafeprimemodulus,suchthatp=2p+1,q=2q+1,andp,p,q,qareprimes.
AssumeGisthecyclicgroupofquadraticresiduesmoduloN2,thenwehavetheorderofGisNpq.
–KeyGen(1k)→(pk,sk).
Choosearandomelementα∈ZN2,arandomvaluea∈[1,Npq],andsetg=α2modN2andh=gamodN2.
Thepublickeyis(N,g,h),andthesecretkeyisa.
–Enc(pk,m)→C.
Oninputapublickeypkandamessagem∈ZN,theciphertext(A,B)iscomputedasA=grmodN2,B=hr(1+mN)modN2,whererisarandomnumberfromZN2.
–Dec(sk,C)→m.
Therearetwomethodstodecrypt.
Knowinga,onecancomputembym=B/(Aa)1modN2N.
Knowingp,q,onecancomputembym=D1modN2N·πmodN,whereD=(Bgw1)2pq,w1=armodN,armodpqpq=w1+w2N,πistheinverseof2pqmodN.
NotethevaluesofamodNandrmodNcanbecomputedwhengivenh=gamodN2,A=grmodN2,andp,q,bythemethodin[27](The-orem1in[27]).
3NewUnidirectionalProxyRe-EncryptionSchemewithoutPairingsTheproposedunidirectionalschemeUisbasedontheCPAsecureandcollusionresistantunidirectionalPREschemein[2,3](therstattemptschemein[2,3]),andwiththesignatureofknowledge[8,1]andFujisaki-Okamotoconversion[14,15].
ThebasicpublickeyencryptionisschemeBCP03.
TheintuitioninschemeUisasfollows.
Firstly,sincetherearetwotrapdoors(aandthefactorizationofthemodulus)inschemeBCP03,wecanusethekeysharingtechniquein[17]tosharea.
Inparticular,leta=r1+r2,andsenttheproxyr1andtheciphertextofr2underthedelegatee'spublickey.
Knowingacannothurtthesecrecyofthefactorizationofthemodulus,hence,collusion-resistanceobtained.
Secondly,schemeBCP03isCPA-secure,hence,weuseFijisaki-OkamotoconversiontomakeschemeBCP03beCCA-secure.
Thirdly,weusethesignatureofknowledgetomaketheoriginalciphertextbepubliclyveriable.
3.
1SchemeUwithSingle-UseSchemeUcontainsthreecryptographichashfunctionsforallusers:H1(·):{0,1}→{0,1}k1,H2(·):{0,1}→{0,1}n,andH3(·):{0,1}→{0,1}k2,wherek1andk2arethesecurityparameter,nisthebit-lengthofmessagestobeencrypted.
Thedetailsareasfollows.
KeyGen:Chooseasafe-primemodulusN=pq,threerandomnumbersα∈ZN2,a,b∈[1,ppqq],ahashfunctionH(·),wherep=2p+1,q=2q+1,p,p,q,qareprimes,andH(·):{0,1}→ZN2.
Furthermore,setg0=α2modN2,g1=g0amodN2,andg2=g0bmodN2.
Thepublickeyispk=(H(·),N,g0,g1,g2),the"weak"secretkeyiswsk=(a,b),andthelongtermsecretkeyissk=(p,q,p,q).
ReKeyGen:OninputapublickeypkY=(HY(·),NY,gY0,gY1,gY2),a"weak"secretkeywskX=aX,andalongtermsecretkeyskX=(pX,qX,pX,qX),itoutputstheunidirectionalre-encryptionkeyrkX→Y=(rk(1)X→Y,rk(2)X→Y),whererk(1)X→Y=(˙A,˙B,˙C),andcomputedasfollows:–Choosetworandomnumbers˙σ∈ZN,˙β∈{0,1}k1.
–Computerk(2)X→Y=aX˙βmod(pXqXpXqX).
–ComputerX→Y=HY(˙σ||˙β),˙A=(gY0)rX→Ymod(NY)2,˙C=H1(˙σ)˙β,˙B=(gY2)rX→Y·(1+˙σNY)mod(NY)2.
(1)Enc:Oninputapublickeypk=(H(·),N,g0,g1,g2)andamessagem∈{0,1}n,theencryptordoesthefollowingperformances:–Choosearandomnumberσ∈ZN.
–Computer=H(σ||m),A=(g0)rmodN2,C=H2(σ)m,D=(g2)rmodN2,B=(g1)r·(1+σN)modN2.
(2)–Run(c,s)←SoK.
Gen(A,D,g0,g2,(B,C)),wheretheunderlyinghashfunctionisH3.
–OutputtheciphertextK=(A,B,C,D,c,s).
ReEnc:Oninputare-encryptionkeyrkX→Y=(rk(1)X→Y,rk(2)X→Y)andacipher-textK=(A,B,C,D,c,s)underkeypkX=(HX(·),NX,gX0,gX1,gX2),checkwhetherc=H3(A||D||gX0||gX2||(gX0)sAc||(gX2)sDc||(B||C)).
Ifnothold,output⊥andterminate;otherwise,re-encrypttheciphertexttobeunderkeypkYas:–ComputeA=Ark(2)X→Y=(gX0)r(aX˙β)mod(NX)2.
–Outputthenewciphertext(A,A,B,C,rk(1)X→Y)=(A,A,B,C,˙A,˙B,˙C).
Dec:OninputasecretkeyandanyciphertextK,parseK=(A,B,C,D,c,s),orK=(A,A,B,C,˙A,˙B,˙C).
CaseK=(A,B,C,D,c,s):Checkwhetherc=H3(A||D||g0||g2||(g0)sAc||(g2)sDc||(B||C)),ifnot,output⊥andterminate;otherwise,–iftheinputsecretkeyisthe"weak"secretkeya,computeσ=B/(Aa)1modN2N.
–ifthesecretkeyisthelongtermsecretkey(p,q,p,q),computeσ=(B/gw10)2pq1modN2N·π(modN),wherew1iscomputedasthatinschemeBCP03,andπistheinverseof2pqmodN.
Computem=CH2(σ),ifB=(g1)H(σ||m)·(1+σN)modN2holds,outputm;otherwise,output⊥andterminate.
CaseK=(A,A,B,C,˙A,˙B,˙C):Inthiscase,thedecryptorshouldknowthedelegator's(Alice's)publickey(H(·),N,g0,g1,g2).
–Iftheinputsecretkeyisthe"weak"secretkeyb,compute˙σ=˙B/(˙Ab)1modN2N.
–Iftheinputsecretkeyisthelongtermsecretkey(p,q,p,q),com-putes˙σ=(˙B/gw10)2pq1modN2N·π(modN),wherew1iscomputedasthatinschemeBCP03,andπistheinverseof2pqmodN.
Compute˙β=˙CH1(˙σ),if˙B=(g1)H(˙σ||˙β)·(1+˙σN)modN2holds,thencomputeσ=B/(A·A˙β)1modN2N,m=CH2(σ);otherwise,output⊥andterminate.
IfB=(g1)H(σ||m)·(1+σN)modN2holds,thenoutputm;otherwise,output⊥andterminate.
Notethat(H(·),N,g0,g1,g2)isthepublickeyofthedecryptor.
Remark2.
Thevaluesof˙BandBarecomputeddierently,inparticular,inequation1,thebaseisg1,whileinequation2,thebaseisg2.
Thisdierenceaimstoresistthefollowingattack:AssumethatthereisthedelegationrelationshipasinFig.
1.
AlicedelegatesherdecryptionrightstoBobviatheproxyPAB,andBobdelegateshisdecryptionrightstoCharlieviatheproxyPBC.
AliceandBobareuncorrupted,therestpartiesarecorrupted,andthetarget(challenged)userisAlice.
ThiscorruptionsituationisallowedinthesecuritymodelinSection2(Notethattheattackedschemeshouldbesingle-use).
Ifthebasesinequations(1)and(2)arebothg1,thentheadversarycandecryptanyciphertextforAliceasfollows.
TheproxyPBCandCharliecolludestogetBob'sweaksecretkeyaB,andthentheycolludewiththeproxyPABtogetAlice'sweaksecretkeyaA.
Asaresult,theadversarycanuseaAtodecryptanyciphertextforAlice.
However,inschemeU,theproxyPBCandCharliecannotgetBob'sweaksecretkeybB(whichisfordecryptingpartialre-encryptionkey),hence,theycannotcolludewiththeproxyPABtogetAlice'sweaksecretkeyaA(whichisfordecryptingciphertexts).
Notethattheaboveattackisalsoallowedinthesecuritymodelin[17,13],sincetheyonlydisallowtheadversarytocorrupttheproxybetweenthetargetuserandtheuncorrupteduser.
Theunidirectionalschemesin[17,13]suerfromtheaboveattack.
Toresisttheaboveattack,wecanusethesamemethodinschemeU,inparticular,everyuserhastwopublic/secretkeypairs,oneisfordecryptingciphertextsofmessages,andtheotherisfordecryptingthepartialre-encryptionkey.
Fig.
1.
Anexampleofdelegationrelationship.
Correctness.
ThecorrectnesspropertyiseasilyobtainedbythecorrectnessofschemeBCP03[7]andFujisaki-Okamotoconversion[14,15].
Duetothelimitedspace,weomittheproofsofthefollowingtwotheoremshere,andgivetheminthefullversion.
Theorem1(Uni-PRE-CCAsecurity).
Intherandomoraclemodel,schemeUisCCA-secureundertheassumptionsthatDDHproblemoverZN2ishard,andthesignatureofknowledgeissecure.
Theorem2(Uni-PRE-CRsecurity).
Intherandomoracle,ifNishardtofactor,thenschemeUiscollusionresistant.
4SchemeUTwithTemporaryDelegationThissectiondescribesschemeUT,avariantofschemeU,supportingtempo-rarydelegation.
LikethetemporaryunidirectionalPREschemesin[2,3,25],theproxyisonlyallowedtotransformciphertextsfromthedelegatortothedele-gateeduringalimitedtimeperiod.
ThepointofmodifyingschemeUtoschemeUTistomakedierentg1'sforeverytimeperiod.
SchemeUTalsocontainsthreecryptographichashfunctionsforallusers:H1(·):{0,1}→{0,1}k1,H2(·):{0,1}→{0,1}n,andH3(·):{0,1}→{0,1}k2,wherek1andk2arethesecurityparameter,nisthebit-lengthofmessagestobeencrypted.
Thedetailsareasfollows.
KeyGen:Chooseasafe-primemodulusN=pq,T+2randomnumbersα∈ZN2,a1,aT,b∈[1,ppqq],ahashfunctionH(·),wherep=2p+1,q=2q+1,p,p,q,qareprimes,Tisthenumberoftimeintervals,andH(·):{0,1}→ZN2.
Furthermore,setg0=α2modN2,g(i)1=g0aimodN2(i=1,T),andg2=g0bmodN2.
Thepublickeyispk=(H(·),N,g0,g(i)1(i=1,T),g2),the"weak"secretkeyis(ai(i=1,T),b),andthelong-termsecretkeyissk=(p,q,p,q).
ReKeyGen:OninputapublickeypkY=(HY(·),NY,gY0,g(1)Y1,g(TY)Y1,gY2),a"weak"secretkeyaX,jfortimeperiodj∈{1,TX},andasecretkeyskX=(pX,qX,pX,qX),itoutputstheunidirectionalre-encryptionkeyrkX→Y,j=(rk(1)X→Y,j,rk(2)X→Y,j)forthej-thtimeperiod,whichisgeneratedasfollows.
–Choosetworandomnumbers˙σj∈ZN,˙βj∈{0,1}k1.
–Computerk(2)X→Y,j=aX,j˙βjmod(pXqXpXqX).
–ComputerX→Y,j=HY(˙σj||˙βj),˙Aj=(gY0)rX→Y,jmod(NY)2,˙Bj=(gY2)rX→Y,j·(1+˙σjNY)mod(NY)2,˙Cj=H1(˙σj)˙βj–Setrk(1)X→Y,j=(˙Aj,˙Bj,˙Cj).
Enc:Oninputapublickeypk=(H(·),N,g0,g(1)1g(T)1,g2),atimeperiodj∈{1,T}andamessagem∈{0,1}n,theencryptordoesthefollowingperformances:–Choosearandomnumberσj∈ZN.
–Computerj=H(σj||m),Aj=(g0)rmodN2,Bj=(g(j)1)r·(1+σjN)modN2,Cj=H2(σj)m,Dj=(g2)rmodN2.
–Run(cj,sj)←SoK.
Gen(Aj,Dj,g0,g2,(Bj,Cj)),wheretheunderlyinghashfunctionisH3.
–OutputtheciphertextKj=(Aj,Bj,Cj,Dj,cj,sj)forthej-thtimeperiod.
ReEnc:Oninputare-encryptionkeyrkX→Y,j=(rk(1)X→Y,j,rk(2)X→Y,j)andaci-phertextKj=(Aj,Bj,Cj,Dj,cj,sj)underkeypkX=(HX(·),NX,gX0,g(1)X1,···,g(TX)X1,gX2),wherej∈{1,TX},theproxycheckswhethercj=H3(Aj||Dj||gX0||gX2||(gX0)sj(Aj)cj||(gX2)sj(Dj)cj||(Bj||Cj)).
Ifnothold,out-put⊥andterminate;otherwise,re-encrypttheciphertexttobeunderkeypkYas:–ComputeAj=(Aj)rk(2)X→Y,j=(gX0)r(aX,j˙βj)mod(NX)2.
–Outputthenewciphertext(Aj,Aj,Bj,Cj,rk(1)X→Y,j)=(Aj,Aj,Bj,Cj,˙Aj,˙Bj,˙Cj).
Dec:OninputasecretkeyandanyciphertextKjforthej-thtimeperiod,wherej∈{1,T},thedecryptorparsesKj=(Aj,Bj,Cj,Dj,cj,sj),orKj=(Aj,Aj,Bj,Cj,˙Aj,˙Bj,˙Cj).
CaseKj=(Aj,Bj,Cj,Dj,cj,sj):Checkwhethercj=H3(Aj||Dj||g0||g2||(g0)sj(Aj)cj||(g2)sjDjcj||(Bj||Cj)),ifnot,output⊥andterminate;oth-erwise,–iftheinputsecretkeyisthe"weak"secretkeyaj,computeσj=Bj/((Aj)aj)1modN2N.
–ifthesecretkeyisthelongtermsecretkey(p,q,p,q),computeσj=(Bj/(g0)w1)2pq1modN2N·π(modN),wherew1iscomputedasthatinschemeBCP03,andπistheinverseof2pqmodN.
Computem=CjH2(σj),ifBj=(g1)H(σj||m)·(1+σjN)modN2holds,outputm;otherwise,output⊥andterminate.
CaseKj=(Aj,Aj,Bj,Cj,˙Aj,˙Bj,˙Cj):Inthiscase,thedecryptorshouldknowthedelegator's(Alice's)publickey(H(·),N,g0,g(i)1g(T)1,g2).
–Iftheinputsecretkeyisthe"weak"secretkeyb,compute˙σj=˙Bj/((˙Aj)b)1modN2N.
–Iftheinputsecretkeyisthelongtermsecretkey(p,q,p,q),com-putes˙σj=(˙Bj/gw10)2pq1modN2N·π(modN),wherew1iscomputedasthatinschemeBCP03,andπistheinverseof2pqmodN.
Compute˙βj=˙CjH1(˙σj),if˙Bj=(g1)H(˙σj||˙βj)·(1+˙σjN)modN2holds,thencomputeσj=Bj/(Aj·(Aj)βj)1modN2N,m=CjH2(σj);otherwise,output⊥andterminate.
IfBj=(g(j)1)H(σj||m)·(1+σjN)modN2holds,thenoutputm;otherwise,output⊥andterminate.
Notethat(H(·),N,g0,g(i)1g(T)1),g2)isthepublickeyofthedecryptor.
Correctness.
ThecorrectnesspropertyiseasilyobtainedbythesamemethodforschemeU.
Duetothelimitedspace,weomittheproofsofthefollowingtwotheoremshere,andgivetheminthefullversion.
Theorem3(Uni-PRETD-CCAsecurity).
Intherandomoraclemodel,schemeUTisCCA-secureundertheassumptionsthatDDHproblemoverZN2ishard,andthesignatureofknowledgeissecure.
Theorem4(Uni-PRETD-CRsecurity).
Intherandomoracle,ifNishardtofactor,thenschemeUTiscollusionresistant.
5ComparisonInthissection,wecompareschemeUwiththepreviousCCA-secureunidirec-tionalPREschemes.
Sinceasmentionedabove,theunidirectionalPREschemesin[21,17,11,13]arenotCCA-secure,weonlycompareschemeUwiththeschemein[25](namedLV08).
InTable1,wedenotetp,teb,teN,ts,andtvasthecomputationalcostofabilinearpairings,anexponentiationoverabilineargroup,anexponentiationoverZN2(Nisasafe-primemodulus),aone-timesignatureandverication,respectively.
GeandGTarethebilineargroupsusedinschemeLV08.
NXandNYarethesafe-primemoduluscorrespondingtothedelegatorandthedelegatee,respectively.
svkandσaretheone-timesignature'spublickeyandsignature.
NotethatweonlyconsiderthecaseofusingweaksecretkeytodecryptinDecalgorithmofschemeU.
FromTable1,wecanseethatschemeLV08isalittlebitmoreecientthanschemeU.
InordertoguaranteethatNishardtofactor,Nshouldbe1024-bitatleast,whichmakesschemeUneedmoretimeforanexponentiationandmorestorageforaciphertext.
However,weemphasizethatschemeUisCCA-secureandbasedonthewell-studiedDDHassumption,whileschemeLV08isRCCA-secureandbasedontheless-studied3-quotientdecisionBilinearDie-Hellman(3-QDBDH)assumption.
6ConclusionsInthispaper,byusingsignatureofknowledgeandFijisaki-Okamotoconversion,weproposedtherstCCA-secureandcollusionresistantunidirectionalPREschemewithoutpairings,whichsolvesaproblemproposedin[9,25].
Therearestillmanyopenproblemstobesolved,suchasdesigningmoreecientCCA-secure,collusionresistantunidirectionalPREschemeswithoutpairings,andCCA-securemulti-useunidirectionalPREschemes[9,25].
Table1.
ComparisonbetweenschemeUandschemeLV08.
SchemesLV08UComput.
CostReKeyGen2teb2teNEnc3.
5teb+1ts5teNReEnc2tp+4teb+1tv4teNDecOriginal3tp+2teb+1tv5teNTransformed5tp+2teb+1tv4teNCiphertextSizeOriginal1|svk|+2|Ge|+1|GT|+1|σ|2k+3|NX2|+|m|Transformed1|svk|+4|Ge|+1|GT|+1|σ|k1+3|NX2|+2|NY2|+|m|SecuritySecurityLevelcollusionresistant,RCCAcollusionresistant,CCAStandardmodelYesNoUnderlyingAssumptions3-QDBDHDDHAcknowledgementsWethankPKC2009chairStanislawJareckiandtheanonymousreviewersofPKC2009forinsightfulcommentsandhelpfulsuggestions.
References1.
G.
Ateniese,J.
Camenisch,M.
Joye,andG.
Tsudik.
Apracticalandprovablysecurecoalition-resistantgroupsignaturescheme.
InCRYPTO2000,volume1880ofLNCS,pages255–270,2000.
2.
G.
Ateniese,K.
Fu,M.
Green,andS.
Hohenberger.
Improvedproxyre-encryptionschemeswithapplicationstosecuredistributedstorage.
InInternetSociety(ISOC):NDSS2005,pages29–43,2005.
3.
G.
Ateniese,K.
Fu,M.
Green,andS.
Hohenberger.
Improvedproxyre-encryptionschemeswithapplicationstosecuredistributedstorage.
ACMTransactionsonInformationandSystemSecurity(TISSEC),9(1):1–30,2006.
4.
B.
Barak,O.
Goldreich,R.
Impagliazzo,S.
Rudich,A.
Sahai,S.
P.
Vadhan,andK.
Yang.
Onthe(im)possibilityofobfuscatingprograms.
InCRYPTO2001,volume2139ofLNCS,pages1–18,2001.
5.
H.
Y.
Lynn,B.
ScottM.
Barreto,P.
S.
L.
M.
Kim.
Ecientalgorithmsforpairing-basedcryptosystems.
InCRYPTO,volume2442ofLNCS,pages354–369,2002.
6.
M.
Blaze,G.
Bleumer,andM.
Strauss.
Divertibleprotocolsandatomicproxycryptography.
InEUROCRYPT1998,volume1403ofLNCS,pages127–144,1998.
7.
E.
Bresson,D.
Catalano,andD.
Pointcheval.
Asimplepublic-keycryptosys-temwithadoubletrapdoordecryptionmechanismanditsapplications.
InASI-ACRYPT2003,volume2894ofLNCS,pages37–54,2003.
8.
J.
CamenischandM.
Stadler.
Ecientgroupsignatureschemesforlargegroups.
InCRYPTO1997,volume1296ofLNCS,pages410–424,1997.
9.
R.
CanettiandS.
Hohenberger.
Chosen-ciphertextsecureproxyre-encryption.
InACMCCS2007,2007.
Fullversion:CryptologyePrintArchieve:Report2007/171.
10.
Y-P.
Chiu,C-L.
Lei,andC-Y.
Huang.
Securemulticastusingproxyencryption.
InICICS2005,volume3783ofLNCS,pages280–290,2005.
11.
C.
ChuandW.
Tzeng.
Identity-basedproxyre-encryptionwithoutrandomoracles.
InISC2007,volume4779ofLNCS,pages189–202,2007.
12.
R.
CramerandV.
Shoup.
Apracticalpublickeycryptosystemprovablysecureagainstadaptivechosenciphertextattack.
InCRYPTO1998,volume1462ofLNCS,pages13–25,1998.
13.
R.
H.
Deng,J.
Weng,S.
Liu,andK.
Chen.
Chosen-ciphertextsecureproxyre-encryptionschemeswithoutpairings.
InCANS2008,volume5339ofLNCS,pages1–17,2008.
Fullversion:http://eprint.
iacr.
org/2008/509.
14.
E.
FujisakiandT.
Okamoto.
Howtoenhancethesecurityofpublic-keyencryptionatminimumcost.
InPKC1999,volume1560ofLNCS,pages53–68,1999.
15.
E.
FujisakiandT.
Okamoto.
Secureintegrationofasymmetricandsymmetricencryptionschemes.
InCRYPTO1999,volume1666ofLNCS,pages537–554,1999.
16.
S.
GoldwasserandY.
T.
Kalai.
Ontheimpossibilityofobfuscationwithauxiliaryinput.
InFOCS2005,pages553–562,2005.
17.
M.
GreenandG.
Ateniese.
Identity-basedproxyre-encryption.
InACNS2007,vol-ume4521ofLNCS,pages288–306,2007.
Fullversion:CryptologyePrintArchieve:Report2006/473.
18.
S.
Hada.
Zero-knowledgeandcodeobfuscation.
InASIACRYPT2000,volume1976ofLNCS,pages443–457,2000.
19.
T.
S.
Heydt-Benjamin,H.
Chae,B.
Defend,andK.
Fu.
Privacyforpublictrans-portation.
InPET2006,volume4258ofLNCS,pages1–19,2005.
20.
S.
Hohenberger,G.
N.
Rothblum,A.
Shelat,andV.
Vaikuntanathan.
Securelyobfuscatingre-encryption.
InTCC2007,volume4392ofLNCS,pages233–252,2007.
21.
A.
IvanandY.
Dodis.
Proxycryptographyrevisited.
InInternetSociety(ISOC):NDSS2003,2003.
22.
H.
KhuranaandH-S.
Hahm.
Certiedmailinglists.
InASIACCS2006,pages46–58,2006.
23.
H.
KhuranaandR.
Koleva.
Scalablesecurityandaccountingservicesforcontent-basedpublishsubscribesystems.
InternationalJournalofE-BusinessResearch,2(3),2006.
24.
H.
Khurana,A.
Slagell,andR.
Bonilla.
Sels:Asecuree-maillistservice.
InACMSAC2005,pages306–313,2005.
25.
B.
LibertandD.
Vergnaud.
Unidirectionalchosen-ciphertextsecureproxyre-encryption.
InPKC2008,volume4939ofLNCS,pages360–379,2008.
26.
A.
Lysyanskaya,MicaliS,L.
Reyzin,andH.
Shacham.
Sequentialaggregatesigna-turesfromtrapdoorpermutations.
InEUROCRYPT2004,volume3027ofLNCS,pages74–90,2004.
27.
P.
Paillier.
Public-keycryptosystemsbasedondiscretelogarithmsresidues.
InEUROCRYPT1999,volume1592ofLNCS,pages223–238,1999.
28.
C.
P.
Schnorr.
Ecientidenticationsandsignaturesforsmartcards.
InCRYPTO1998,volume435ofLNCS,pages239–251,1998.
29.
M.
Scott.
Computingthetatepairing.
InCT-RSA,volume3376ofLNCS,pages293–304,2005.
30.
J.
Shao.
Proxyre-cryptography,revisited.
Dec.
2007.
PhDThesis,ShanghaiJiaoTongUniversity.
31.
J.
Shao,D.
Xing,andZ.
Cao.
Analysisofccasecureunidirctionalid-basedprescheme.
2008.
TechnicalReportofTDT.
32.
V.
Shoup.
Practicalthresholdsignatures.
InEUROCRYPT2000,volume1807ofLNCS,pages207–220,2000.
33.
V.
ShoupandR.
Gennaro.
Securingthresholdcryptosystemsagainstchosenci-phertextattack.
InEUROCRYPT1998,volume1430ofLNCS,pages1–16,1998.
34.
G.
Taban,A.
A.
Cardenas,andV.
D.
Gligor.
Towardsasecureandinteroperabledrmarchitecture.
InACMDRM2006,pages69–78,2006.
35.
A.
TalmyandO.
Dobzinski.
Abusefreedominaccesscontrolschemes.
InAINA2006,pages77–86,2006.
36.
Smith.
Tony.
Dvdjon:buydrm-lesstracksfromappleitunes.
2005.
http://www.
theregister.
co.
uk/2005/03/18/itunespymusique.
AAnalysisonIvan-DodisConstructionA.
1Ivan-DodisConstructionTheIvan-DodisconstructionisbasedonanyCCA-securePKE.
Thedetailsareasfollows.
UniPRE.
KGen:Oninputthesecurityparameter1k,itoutputstwokeypairs(pk1,sk1)and(pk2,sk2).
UniPRE.
RKGen:Oninputthedelegator'skeypairs(pk1,sk1)and(pk2,sk2),thedelegatorsendssk1asthere-encryptionkeytotheproxyviaasecurechan-nel,andsendssk2tothedelegateeasthepartialkeyviaanothersecurechannel.
UniPRE.
Enc:Oninputpublickeys(pk1,pk2)andamessagem,itoutputsPKE.
Enc(pk1,PKE.
Enc(pk2,m)).
UniPRE.
ReEnc:Oninputare-encryptionkeysk1andaciphertextC,itoutputsare-encryptedciphertextC=PKE.
Dec(sk1,C).
UniPRE.
Dec:Oninputsecretkeys(sk1,sk2),apartialkeysk2fromitsdelegatorandaciphertextC,UniPRE.
Decdoes:–IfCisanoriginalciphertext,thenitoutputsPKE.
Dec(sk2,PKE.
Dec(sk1,C)).
–IfCisare-encryptedciphertext,thenitoutputsPKE.
Dec(sk2,C).
Notethatthepartialkeysk2canbeencryptedbythedelegatee'spublickey,andforwardedtoBobbytheproxy.
Inthiscase,thedelegateedoesnotrequiretostoreextrasecretsforeverydelegation[2,3].
A.
2ChosenCiphertextAttacksontheIvan-DodisConstructionInthissubsection,wewillshowthattheadversaryalwayswinstheUni-PRE-CCAgamewiththeIvan-Dodisconstruction'sChallenger.
Phase1:Theadversarydoesnotneedtomakeanyqueryinthisphase.
Challenge:Theadversaryoutputstwoequallengthplaintextsm0,m1fromthemessagespace,andanuncorruptedpublickeypk=(pk1,pk2).
TheChallengerwillfollowtheUni-PRE-CCAgame'sspecication,i.
e.
,pickarandombitb∈{0,1}andsetsC=UniPRE.
Enc(pk,mb).
ItsendsCasthechallengeciphertexttoA.
Phase2:Theadversaryperformsasfollows.
1.
TheadversaryqueriesOrewith(pk,pk,C),suchthatpkisuncor-rupted.
ThenastheUni-PRE-CCAgame'sspecication,theadversarycangetthere-encryptedciphertextCsuchthatC=PKE.
Dec(sk1,C),sk1isthekeycorrespondingtopk1.
2.
TheadversarycomputesC=PKE.
Enc(pk1,C).
NotethatC=CsincePKEisCCA-secure,suchastheunderlyingPKEschemeistheCramer-Shoupscheme[12].
3.
TheadversaryqueriesOdewith(pk,C)andgetsamessagem.
Notethat(pk,C)isnotaderivativeof(pk,C),hencethisqueryisvalid.
Guess:Ifm=m0,theadversaryAoutputsb=0;otherwise,outputb=1.
SinceCandCarecorrespondingtothesamemessage,wealwayshaveb=b.
Asaresult,theIvan-DodisconstructionisnotCCA-secureforthesecuritymodelinSection2.
BDenitionsofUnidirectionalPRESchemeswithTemporaryDelegationDenition7(UnidirectionalPREwithTemporaryDelegation).
Auni-directionalproxyre-encryptionschemeUniPREwithtemporarydelegationisatupleofPPTalgorithms(KeyGen,ReKeyGen,Enc,ReEnc,Dec):–KeyGen(1k)→(pk,sk,T).
Oninputthesecurityparameter1k,thekeygen-erationalgorithmKeyGenoutputsapublic/secretkeypair(pk,sk),andthenumberoftimeintervalsT.
–Enc(pk,m,j)→Cj.
Oninputapublickeypk,amessageminthemessagespace,andthetimeperiodj∈{1,T},theencryptionalgorithmEncoutputsaciphertextCjforthej-thtimeperiod.
–ReKeyGen(sk1,pk2,j)→rk1→2,j.
Oninputasecretkeysk1,apublickeypk2,andthetimeperiodj∈{1,T1},whereT1isthenumberoftimeintervalscorrespondingtothedelegator.
There-encryptionkeygenerationalgorithmReKeyGenoutputsaunidirectionalre-encryptionkeyrk1→2,jforthej-thtimeperiod.
–ReEnc(rk1→2,j,C(j)1)→C(j)2.
Oninputare-encryptionkeyrk1→2,andaciphertextC(j)1forthej-thtimeperiod,wherej∈{1,T1},T1isthenumberoftimeintervalscorrespondingtothedelegator.
There-encryptionalgorithmReEncoutputsare-encryptedciphertextC(j)2forthej-thtimeperiodor⊥.
–Dec(sk,Cj)→m.
OninputasecretkeyskandaciphertextCjforthej-thtimeperiod,wherej∈{1,T},Tisthenumberoftimeintervalscorrespondingtothedecryptor.
ThedecryptionalgorithmDecoutputsamessageminthemessagespaceor⊥.
Correctness.
Acorrectproxyre-encryptionschemeshouldsatisfytworequire-ments:Dec(sk,Enc(pk,m,j))=m,andDec(sk,ReEnc(ReKeyGen(sk,pk,j),Cj))=m,where(pk,sk,T),(pk,sk,T)←KeyGen(1k),Cjistheciphertextofmessagemforpkandthej-thtimeperiodfromalgorithmEncoralgorithmReEnc,andj∈{1,T}.
ChosenCiphertextSecurityforUnidirectionalProxyRe-EncryptionwithTemporaryDelegation.
Followingthemethodin[25],weextendUni-PRE-CCAgametoUni-PRETD-CCAgame,whichisdescribedasfollows.
Phase1:TheadversaryAissuesqueriesq1,qn1wherequeryqiisoneof:–Opk,Osk:IdenticaltothoseUni-PRE-CCAgame.
–Re-encryptionkeygenerationoracleOrk:Oninput(pk,pk,j)byA,wherepk,pkarefromOpk,andthetimeperiodj∈{1,T},theChallengerreturnsthere-encryptionkeyrkpk→pk,j=ReKeyGen(sk,pk,j),whereskisthesecretkeycorrespondingtopk.
–Re-encryptionoracleOre:Oninput(pk,pk,C,j)byA,wherepk,pkarefromOpk,andthetimeperiodj∈{1,T},there-encryptedciphertextC=ReEnc(ReKeyGen(sk,pk,j),C)isreturnedbytheChallenger,whereskisthesecretkeycorrespondingtopk.
–DecryptionoracleOdec:Oninput(pk,C,j),wherepkisfromOpk,andthetimeperiodj∈{1,T},theChallengerreturnsDec(sk,C),whereskisthesecretkeycorrespondingtopk.
Thesequeriesmaybeaskedadaptively,thatis,eachqueryqimaydependontherepliestoq1,qi1.
Challenge:OncetheadversaryAdecidesthatPhase1isover,itoutputstwoequallengthplaintextsm0,m1fromthemessagespace,apublickeypk,andthetimeperiodjonwhichitwishestobechallenged.
Therearesomeconstraintsonthepublickeypkandj:(i)pkisfromOpk;(ii)pkdidnotappearinanyquerytoOskinPhase1;(iii)if(pk,,j)didappearinanyquerytoOrk,thendidnotappearinanyquerytoOsk.
TheChallengerpicksarandombitb∈{0,1}andsetsC=Enc(pk,mb,j).
ItsendsCasthechallengetoA.
Phase2:TheadversaryAissuesmorequeriesqn1+1,qnwherequeryqiisoneof:–Opk:TheChallengerrespondsasinPhase1.
–Osk:OninputpkbyA,ifthefollowingrequirementsareallsatised,theChallengerrespondsasinPhase1;otherwise,theChallengerterminatesthegame.
pkisfromOpk;pk=pk;(pk,pk,j)isnotaquerytoOrkbefore;(pk,pk,C,j)isnotaquerytoOrebefore,where(pk,C,j)isaderivative11of(pk,C,j).
11Derivativesof(pk,C,j)aredenedsimilarlywiththatinSection2.
2,andjustaddjintoeveryinput/output.
–Ork:Oninput(pk,pk,j)byA,ifthefollowingrequirementsareallsatised,theChallengerrespondsasinPhase1;otherwise,theChallengerterminatesthegame.
pk,pkarefromOpk;ifpk=pkandj=j,thenpkisnotaquerytoOsk.
–Ore:Oninput(pk,pk,C,j)byA,ifthefollowingrequirementsareallsat-ised,theChallengerrespondsasinPhase1;otherwise,theChallengerter-minatesthegame.
pk,pkarefromOpk;if(pk,C,j)isaderivativeof(pk,C,j),thenpkisnotaquerytoOsk.
–Odec:Oninput(pk,C,j),ifthefollowingrequirementsareallsatised,theChallengerrespondsasinPhase1;otherwise,theChallengerterminatesthegame.
pkisfromOpk;(pk,C,j)isnotaderivativeof(pk,C,j).
Thesequeriesmaybealsoaskedadaptively.
Guess:Finally,theadversaryAoutputsaguessb∈{0,1}andwinsthegameifb=b.
WerefertosuchanadversaryAasaUni-PRETD-CCAadversary.
WedeneadversaryA'sadvantageinattackingUniPREasthefollowingfunctionofthesecurityparameterk:AdvUniPRE,A(k)=|Pr[b=b]1/2|.
UsingtheUni-PRE-CCAgamewecandenechosenciphertextsecurityforunidirectionalproxyre-encryptionschemes.
Denition8(Uni-PRETD-CCAsecurity).
Wesaythataunidirectionalproxyre-encryptionschemeUniPREwithtemporarydelegationissemanticallysecureagainstanadaptivechosenciphertextattackifforanypolynomialtimeUni-PRETD-CCAadversaryAthefunctionAdvUniPRE,A(k)isnegligible.
Asshorthand,wesaythatUniPREisUni-PRETD-CCAsecure.
Denition9(Uni-PRETD-CRsecurity).
Wesaythataunidirectionalproxyre-encryptionschemeUniPREwithtemporarydelegationiscollusionresistantifforanypolynomialboundedadversaryA,thefollowingprobabilityisnegligible:Pr[(sk1,pk1,T1)←KeyGen(1k),{(ski,pki,Ti)←KeyGen(1k)},{rki→1,j←ReKeyGen(ski,pk1,j)}(j=1,Ti),{rk1→i,j←ReKeyGen(sk1,pki,j)}(j=1,T1),i=2,α→A(pk1,{pki,ski},{rk1→i,j},{rki→1,j}):α=sk1].