initializes522av.com

VABKS:VeriableAttribute-basedKeywordSearchoverOutsourcedEncryptedDataQingjiZhengShouhuaiXuGiuseppeAtenieseUniversityofTexasatSanAntonio,USASapienzaUniversityofRome,ItalyandJohnsHopkinsUniversity,USAAbstract—Itiscommonnowadaysfordataownerstooutsourcetheirdatatothecloud.
Sincethecloudcannotbefullytrusted,theoutsourceddatashouldbeencrypted.
Thishoweverbringsarangeofproblems,suchas:HowshouldadataownergrantsearchcapabilitiestothedatausersHowcantheauthorizeddatauserssearchoveradataowner'soutsourcedencrypteddataHowcanthedatausersbeassuredthatthecloudfaithfullyexecutedthesearchoperationsontheirbehalfMotivatedbythesequestions,weproposeanovelcryptographicsolution,calledveriableattribute-basedkeywordsearch(VABKS).
Thesolutionallowsadatauser,whosecredentialssatisfyadataowner'saccesscontrolpolicy,to(i)searchoverthedataowner'soutsourcedencrypteddata,(ii)outsourcethetedioussearchoperationstothecloud,and(iii)verifywhetherthecloudhasfaithfullyexecutedthesearchoperations.
WeformallydenethesecurityrequirementsofVABKSanddescribeaconstructionthatsatisesthem.
Performanceevaluationshowsthattheproposedschemesarepracticalanddeployable.
I.
INTRODUCTIONCloudcomputingallowsdataownerstousemassivedatastorageandvastcomputationcapabilitiesataverylowprice.
Despitethebenets,dataoutsourcingdeprivesdataownersofdirectcontrolovertheiroutsourceddata.
Toalleviateconcerns,dataownersshouldencrypttheirdatabeforeoutsourcingtothecloud.
However,encryptioncanhindersomeusefulfunctionssuchassearchingovertheoutsourcedencrypteddatawhileenforcinganaccesscontrolpolicy.
Moreover,itisnaturaltooutsourcethesearchoperationstothecloud,whilekeepingtheoutsourceddataprivate.
Thereisaneedtoallowthedatauserstoverifywhetherthecloudfaithfullyexecutedthesearchoperationsornot.
Tothebestofourknowledge,existingsolutionscannotachievetheseobjectivessimultaneously.
A.
OurContributionsWeproposeanovelcryptographicprimitive,calledveri-ableattribute-basedkeywordsearch(VABKS).
Thisprimitiveallowsadataownertocontrolthesearch,anduseof,itsoutsourcedencrypteddataaccordingtoanaccesscontrolpolicy,whileallowingthelegitimatedatauserstooutsourcethe(oftencostly)searchoperationstothecloudandverifywhetherornotthecloudhasfaithfullyexecutedthesearchoperations.
Inotherwords,adatauserwithpropercredentials(correspondingtoadataowner'saccesscontrolpolicy)can(i)searchoverthedataowner'soutsourcedencrypteddata,(ii)outsourcethesearchoperationstothecloud,and(iii)verifywhetherornotthecloudhasfaithfullyexecutedthesearchoperations.
WeformallydenethesecuritypropertiesofVABKSandpresentaschemethatprovablysatisesthem.
Theschemeisconstructedinamodularfashion,byusingattribute-basedencryption,bloomlter,digitalsignature,andanewbuilding-blockwecallattribute-basedkeywordsearch(ABKS)thatmaybeofindependentvalue.
ExperimentalevaluationshowsthattheVABKSsolutionsarepractical.
B.
RelatedWorkTothebestofourknowledge,noexistingsolutionisadequateforwhatwewanttoachieve.
Inwhatfollowswebrieyreviewtherelevanttechniques.
Attribute-BasedEncryption(ABE).
ABEisapopularmethodforenforcingaccesscontrolpoliciesviacryptographicmeans.
Basically,thistechniqueallowsentitieswithpropercredentialstodecryptaciphertextthatwasencryptedaccord-ingtoanaccesscontrolpolicy[1].
Dependingonhowtheac-cesscontrolpolicyisenforced,therearetwovariants:KP-ABE(key-policyABE)wherethedecryptionkeyisassociatedtotheaccesscontrolpolicy[2],andCP-ABE(ciphertext-policyABE)wheretheciphertextisassociatedtotheaccesscontrolpolicy[3].
ABEhasbeenenrichedwithvariousfeatures(e.
g.
,[4]–[7]).
Inthispaper,weuseABEtoconstructanewprimitivecalledattribute-basedkeywordsearch(ABKS),bywhichkeywordsareencryptedaccordingtoanaccesscontrolpolicyanddatauserswithpropercryptographiccredentialscangeneratetokensthatcanbeusedtosearchovertheoutsourcedencrypteddata.
Thiseffectivelypreventsadataownerfromknowingthekeywordsadatauserissearchingfor,whilerequiringnointeractionsbetweenthedatausersandthedataowners/trustedauthorities.
Thisisincontrastto[8],wherethedatausersinteractwiththedataowners/trustedauthoritiestoobtainsearchtokens.
KeywordSearchoverEncryptedData.
Thistechniqueallowsadataownertogeneratesometokensthatcanbeusedbyadatausertosearchoverthedataowner'sencrypteddata.
Existingsolutionsforkeywordsearchoverencrypteddatacanbeclassiedintotwocategories:searchableencryptioninthesymmetric-keysetting(e.
g.
,[9]–[18])andsearchableencryptioninthepublic-keysetting(e.
g.
,[8],[19]–[22]).
Sev-eralvariants(e.
g.
,[23]–[26])havebeenproposedtosupportcomplexsearchoperations.
Moreover,searchableencryptioninthemulti-userssettinghasbeeninvestigatedaswell[12],[27],wherethedataownercanenforceanaccesscontrolpolicybydistributingsome(stateful)secretkeystotheauthorizedusers.
However,allthesesolutionsdonotsolvetheproblemwestudy,because(i)someofthesesolutionsrequireinteractionsbetweenthedatausersandthedataowners(oratrustedproxy,suchasatrapdoorgenerationentity[8])tograntsearchcapabilities,and(ii)allthesesolutions(except[18])assumethattheserverfaithfullyexecutedsearchoperations.
Incontrast,oursolutionallowsadatauserwithpropercredentialstoissuesearchtokensbywhichthecloudcanperformkeywordsearchoperationsonbehalfoftheuser,withoutrequiringanyinteractionwiththedataowner.
Moreover,thedatausercanverifywhetherornotthecloudhasfaithfullyexecutedthekeywordsearchoperations.
Thisistrueevenforthepowerfultechniquecalledpredicateencryption[28],[29],whichdoesnotofferthedesiredveriability.
VeriableKeywordSearch.
Recently,veriablekeywordsearchsolutionshavebeenproposedin[30]–[32],whereeachkeywordisrepresentedasarootofsomepolynomial.
Itispossibletocheckwhetherakeywordispresentbyevaluatingthepolynomialonthekeywordandverifyingwhethertheoutputiszeroornot.
However,theseapproachesworkonlywhenkeywordsaresentinplaintexttothecloud,andarenotsuitableforourpurposebecausethecloudshouldnotlearnanythingaboutthekeywords.
Itisworthmentioningthatthesecureveriablekeywordsearchinthesymmetric-keysetting[18]canbeinsecureinthepublic-keysettingbecausetheattackercaninferkeywordsinquestionviaanoff-linekeywordguessingattack(inlieuoftheoff-linedictionaryattackagainstpasswords).
PaperOrganization:SectionIIreviewssomecryptographicpreliminaries.
SectionIIIdenesABKSanditssecurityproperties,presentsKP-ABKSandCP-ABKSschemesandanalyzestheirsecurityproperties.
SectionIVdenesVABKSanditssecurityproperties,presentstheVABKSconstructionandanalyzesitssecurity.
SectionVevaluatestheperformanceoftheABKSandVABKSschemes.
SectionVIconcludesthepaper.
II.
PRELIMINARIESLeta←SdenoteselectinganelementafromasetSuniformlyatrandom,||denotetheconcatenationoperationandstring(S)denotetheconcatenationofelementsofSorderedbytheirhashvalues.
LetU={at1,atn}beasetofattributesthatareusedtospecifyaccesscontrolpolicies.
A.
CryptographicAssumptionLetpbean-bitprime,andG,GTbecyclicgroupsofprimeorderpwithgeneratorsg,gT,respectively.
Letebeabilinearmap:e:G*G→GTsatisfying:(i)a,b←Zp,e(ga,gb)=e(g,g)ab,(ii)e(g,g)=1,and(iii)ecanbecomputedefciently.
DecisionalLinearAssumption(DL).
Given(g,f,h,fr1,gr2,Q)whereg,f,h,Q←G,r1,r2←Zp,thisassumptionsaysthatanyprobabilisticpolynomial-timealgorithmAcandetermineQ=hr1+r2atmostwithanegligibleadvantageinsecurityparameter,where"advantage"isdenedas|Pr[A(g,f,h,fr1,gr2,hr1+r2)=1]Pr[A(g,f,h,fr1,gr2,Q)=1]|.
GenericBilinearGroup[33].
Letψ0,ψ1betworandomencodingsoftheadditivegroupZ+p,suchthatψ0,ψ1areinjectivemapsfromZ+pto{0,1}m,wherem>3log(p).
LetG={ψ0(x)|x∈Zp}andGT={ψ1(x)|x∈Zp}.
Thereisanoracletocomputee:G*G→GT.
Gisreferredtoasagenericbilineargroup.
Letgdenoteψ0(1),gxdenoteψ0(x),e(g,g)denoteψ1(1),ande(g,g)ydenoteψ1(y).
PseudorandomGenerator[34].
Apseudorandomgenera-torH:{0,1}→{0,1}m,B.
BloomFilterforMembershipQueryABloomlter[35]isadatastructureforsuccinctlyrepresentingastaticset,whileallowingmembershipqueries.
Am-bitBloomlterisanarrayofmbits,whichareallinitializedas0.
ItuseskindependentuniversalhashfunctionsH′1,H′kwiththesamerange{0,m1}.
Foreachelementw∈S={w1,wn},thebitscorrespondingtoH′j(w)aresetto1,where1≤j≤k.
TodeterminewhetherwbelongstoSornot,oncecancheckwhetherallofthebitscorrespondingtoH′j(w)equalto1,where1≤j≤k.
Ifnot,itiscertainthatw∈S;otherwise,w∈Swithahighprobability(i.
e.
,thereisanon-zerofalse-positiverate).
Supposethehashfunctionsareperfectlyrandomandnelementsarehashedintoam-bitBloomlter,thefalse-positiverateis(1(11m)kn)k≈(1ekn/m)k.
Notethatk=(ln2)m/nhashfunctionsleadtotheminimalfalse-positiverate(0.
6185)m/n.
Am-bitBloomlterhastwoassociatedalgorithms:BF←BFGen({H′1,H′k},{w1,wn}):Thisalgo-rithmgeneratesam-bitBloomlterbyhashingadatasetS={w1,wn}with{H′1,H′k}.
{0,1}←BFVerify({H′1,H′k},BF,w):Thisalgo-rithmreturns1ifw∈S,and0otherwise.
C.
AccessTreesforRepresentingAccessControlPoliciesAccesstreescanrepresentaccesscontrolpolicies[2].
Inanaccesstree,aleafisassociatedwithanattributeandaninnernoderepresentsathresholdgate.
Letnumvbethenumberofchildrenofnodev,andlabelthechildrenfromthelefttotherightas1,numv.
Letkv,1≤kv≤numv,bethethresholdvalueassociatedwithnodev,wherekv=1representstheORgateandkv=numvrepresentstheANDgate.
Letparent(v)denotetheparentofnodev,ind(v)denotethelabelofnodev,att(v)denotetheattributeassociatedtoleafnodev,lvs(T)denotethesetofleavesofaccesstreeT,andTvdenotethesubtreeofTrootedatnodev(e.
g.
,Troot=T).
LetF(Atts,Tv)=1indicatethatanattributesetAttssatisestheaccesscontrolpolicyrepresentedbysubtreeTv,whereF(Atts,Tv)canbeevaluatediterativelyasfollows:Inthecasevisaleaf:Ifatt(v)∈Atts,setF(Atts,Tv)=1;otherwise,setF(Atts,Tv)=0.
Inthecasevisaninnernodewithchildrenv1,vnumv:IfthereexistsasubsetI{1,numv}suchthat|I|≥kvandj∈I,F(Atts,Tvj)=1,setF(Atts,Tv)=1;otherwise,setF(Atts,Tv)=0.
GivenanaccesstreeT,wedenotethealgorithmfordistributingasecretsaccordingtoTby:{qv(0)|v∈lvs(T)}←Share(T,s).
Thisalgorithmgeneratesapolynomialqvofdegreekv1foreachnodevinatop-downfashion(foreachleafnodekv=1):IfvistherootofT(i.
e.
,v=root),setqv(0)=sandrandomlypickkv1coefcientsforpolynomialqv.
IfvisaleafofT,setqv(0)=qparent(v)(ind(v)).
Ifvisaninnernode(butnottheroot),setqv(0)=qparent(v)(ind(v))andrandomlyselectkv1coefcientsforpolynomialqv.
Whenthealgorithmhalts,eachleafvisassociatedwithavalueqv(0),whichisthesecretshareofsatnodev.
GivenanaccesstreeTandasetofvalues{Eu1,.
.
.
,Eum},whereu1,umaretheleavesofT,F({att(u1)att(um)},T)=1,Euj=e(g,h)quj(0)for1≤j≤m,g,h∈G,eisabilinearmap,andqu1(0)qum(0)aresecretsharesofsaccordingtoT,thealgorithmforreconstructinge(g,h)sisdenotedbye(g,h)s←Combine(T,{Eu1Eum}).
Thisalgorithmexecutesthefollowingstepswithrespecttonodevinabottom-topfashionaccordingtoT:IfF({att(u1)att(um)},Tv)=0,thensetEv=⊥.
IfF({att(u1)att(um)},Tv)=1,thenexecutethefollowing:–Ifvisaleaf,setEv=Euj(0)=e(g,h)quj(0)wherev=ujforsomej.
–Ifvisaninnernode(includingtheroot),forv'schildrennodes{v1,vnumv},thereexistsasetofindicesSsuchthat|S|=kv,j∈S,andF({att(u1)att(um)},Tvj)=1.
SetEv=j∈SEvjvj=j∈S(e(g,h)qvj(0))vj=e(g,h)qv(0),wherevj=l∈S,l=jjlj.
Whenthealgorithmhalts,therootofTisassociatedwithEroot=e(g,h)qroot(0)=e(g,h)s.
III.
ATTRIBUTE-BASEDKEYWORDSEARCH(ABKS)Thisnewprimitiveallowsadataownertospecifyapolicyforcontrollingthekeywordsearchoperationsoveritsout-souredencrypteddata.
Thatis,adatauserwhopossessesattributesthatsatisfythedataowner'spolicycanconductkeywordsearchovertheoursourcedencrypteddata.
Thisprimitivenaturallyhastwovariants:KP-ABKS(key-policyABKS)wherethecryptographiccredentialsareassociatedtotheaccesscontrolpolicy,andCP-ABKS(ciphertext-policyABKS)wheretheciphertextisassociatedtotheaccesscontrolpolicy.
Tounifythepresentation,letIEncdenotetheinputtoencryptionfunctionEncandIKeyGendenotetheinputtokeygenerationfunctionKeyGen.
ForCP-ABKS,IEncandIKeyGenarerespectivelytheaccesstreeandtheattributeset;forKP-ABKS,IEncandIKeyGenarerespectivelytheattributesetandtheaccesstree.
LetF(IKeyGen,IEnc)=1denoteIKeyGensatisesIEncinCP-ABKSandIEncsatisesIKeyGeninKP-ABKS.
A.
DenitionandSecurityThemodelofABKSis:Adataowneroutsourcesitsencryptedkeywordstothecloud,adatausergeneratessearchtokensaccordingtosomekeywords,andthecloud,whoreceivessearchtokensfromtheuser,conductsthesearchoperationsoveroutsourcedencryptedkeywords.
Denition1:ABKSconsistsofthefollowingalgorithms:(mk,pm)←Setup(1):Thisalgorithminitializesthepublicparameterpmandgeneratesamasterkeymk.
sk←KeyGen(mk,IKeyGen):Thisalgorithmoutputscre-dentialskforauseraccordingtoIKeyGen.
cph←Enc(w,IEnc):Thisalgorithmencryptskeywordwtoobtainciphertextcph.
tk←TokenGen(sk,w):Thisalgorithmallowsadatausertogenerateasearchtokentkaccordingtoitscredentialskandkeywordw.
{0,1}←Search(cph,tk):Thisalgorithmreturns1if(i)F(IKeyGen,IEnc)=1and(ii)ciphertextcphandtokentkcorrespondtothesamekeyword,andreturn0otherwise.
AnABKSschemeiscorrectifthefollowingholds:Given(mk,pm)←Setup(1),sk←KeyGen(mk,IKeyGen)andF(IKeyGen,IEnc)=1,cph←Enc(w,IEnc)andtk←TokenGen(sk,w),Search(cph,tk)alwaysreturns1.
TheadversarymodelagainstABKSisthefollowing:dataownersandauthorizeddatausersaretrusted,butthecloudistrustedbutcurious(i.
e.
,executingtheprotocolhonestlybutattemptingtoinferprivateinformationaswell).
Intuitively,securitymeansthatthecloudlearnnothingbeyondthesearchresults.
Specically,givenaprobabilisticpolynomial-timeadversaryA(modelingthecloud),anABKSschemeissecureifthefollowingholdsSelectivesecurityagainstchosen-keywordattack:Withoutbeinggivenanymatchingsearchtoken,Acannotinferanyinformationabouttheplaintextkeywordofakeywordciphertextintheselectivesecuritymodel,whereAmustdetermineIEncitintendstoattackbeforethesystemisboostrapped[36].
Weformalizethissecuritypropertyviatheselectivechosen-keywordattackgame.
Keywordsecrecy:Inthepublic-keysetting,itisimpos-sibletoprotectthesearchtokens(aka.
predicateprivacy[37])againstthekeywordguessingattack.
ThisisbecauseAcanencryptakeywordofitschoiceandcheckwhethertheresultingkeywordciphertextandthetargettokencorrespondtothesamekeyword,whichiscausedbytheuseof"deterministicencryption.
"Therefore,weuseaweakersecuritynotioncalledkeywordsecrecy,assuringthattheprobabilityAlearningthekeywordfromthekeywordciphertextandsearchtokensisnegligiblymorethantheprobabilityofcorrectrandomkeywordguess.
Weformalizethissecuritypropertyviathekeywordsecrecygame.
SelectivelyChosen-KeywordAttack(SCKA)Game:Setup:Aselectsanon-trivialchallengeIEnc(atrivialchal-lengeIEncisonethatcanbesatisedbyanydatauserwhodoesnothaveanycredential),andgivesittothechallenger.
ThenthechallengerrunsSetup(1)togeneratethepublicparameterpmandthemasterkeymk.
Phase1:Acanquerythefollowingoraclesforpolynomiallymanytimes,andthechallengerkeepsakeywordlistLkw,whichisinitiallyempty.
OKeyGen(IKeyGen):IfF(IKeyGen,IEnc)=1,thenabort;otherwise,thechallengerreturnstoAcredentialskcorrespondingtoIKeyGen.
OTokenGen(IKeyGen,w):Thechallengergeneratescreden-tialskwithIKeyGen,andreturnstoAasearchtokentkbyrunningalgorithmTokenGenwithinputsskandw.
IfF(IKeyGen,IEnc)=1,thechallengeraddswtoLkw.
Challengephase:Achoosestwokeywordsw0andw1,wherew0,w1/∈Lkw.
Thechallengerselectsλ←{0,1},computescph←Enc(wλ,IEnc),anddeliverscphtoA.
Notethattherequirementofw0,w1/∈LkwistopreventAfromtriviallyguessingλwithtokensfromOTokenGen.
Phase2:AcontinuestoquerytheoraclesasinPhase1.
Therestrictionisthat(IKeyGen,w0)and(IKeyGen,w1)cannotbetheinputtoOTokenGenifF(IKeyGen,IEnc)=1.
Guess:Aoutputsabitλ′,andwinsthegameifλ′=λ.
Let|Pr[λ=λ′]12|betheadvantageofAwinningtheaboveSCKAgame.
Thus,wehaveDenition2:AnABKSschemeisselectivelysecureagainstchosen-keywordattackiftheadvantageofanyAwinningtheSCKAgameisnegligibleinsecurityparameter.
KeywordSecrecyGame:Setup:ThechallengerrunsSetup(1)togeneratethepublicparameterpmandthemasterkeymk.
Phase1:Acanquerythefollowingoraclesforpolynomiallymanytimes:OKeyGen(IKeyGen):ThechallengerreturnstoAcredentialskcorrespondingtoIKeyGen.
ItaddsIKeyGentothelistLKeyGen,whichisinitiallyempty.
OTokenGen(IKeyGen,w):Thechallengergeneratescreden-tialskwithIKeyGen,andreturnstoAasearchtokentkbyrunningalgorithmTokenGenwithinputskandw.
Challengephase:Achoosesanon-trivialIEncandgivesittothechallenger.
ThechallengerselectswfromthemessagespaceuniformlyatrandomandselectsIKeyGensuchthatF(IKeyGen,IEnc)=1.
Thechallengerrunscph←Enc(w,IEnc)andtk←TokenGen(sk,w)anddelivers(cph,tk)toA.
WerequirethatIKeyGen∈LKeyGen,F(IKeyGen,IEnc)=0.
Guess:Afterguessingqdistinctkeywords,Aoutputsakeywordw′,andwinsthegameifw′=w.
Denition3:AnABKSschemeachieveskeywordsecrecyiftheprobabilitythatAwinsthekeywordsecrecygameisatmost1|M|q+,whereMisthekeywordspace,qisthenumberofdistinctkeywordsthattheadversaryhasattempted,andisanegligibleinsecurityparameter.
B.
ConstructionThebasicideaunderlyingtheconstructionisthefollowing:eachkeywordciphertextandeachsearchtokenhastwoparts,oneisassociatedtothekeywordandtheotherisassociatedtotheattributes(oraccesscontrolpolicy).
Iftheattributessatisfytheaccesscontrolpolicy,onecandeterminewhetherthesearchtokenandkeywordciphertextcorrespondtothesamekeywordornot.
ConsiderKP-ABKSasanexample.
LetH1:{0,1}→GbeahashfunctionmodeledasrandomoracleandH2:{0,1}→Zpbeanone-wayhashfunction.
Adatauser'scredentialsaregeneratedbylettingt←Zp,Av=gqv(0)H1(att(v))t,Bv=gtforeachleafv,wheregisageneratorofG,qv(0)istheshareofsecretacforleafvaccordingtoaccesstreeT.
Thekeywordciphertextandsearchtokenaregeneratedasfollows:Keywordwisencryptedintotwoparts:oneisto"blend"wwithrandomnessr1,r2←ZpbylettingW′=gcr1,W=ga(r1+r2)gbH2(w)r1andW0=gr2wherega,gb,gc∈Garepublickeys,andtheotherisassociatedtoattributesetAttsbylettingWj=H1(atj)r2foreachatj∈Atts.
Thetwopartsaretiedtogetherviar2.
Givenasetofcredentials,asearchtokenforkeywordwisgeneratedwithtwoparts:oneisassociatedtowastok1=(gagbH2(w))sandtok2=gcsforsomes←Zp,andtheotherisassociatedtothecredentialsbylettingA′v=Asv,B′v=Bsvforeachv∈lvs(T).
Thetwopartsaretiedtogetherviarandomnesss.
IftheattributesetAttssatisestheaccesstreeT,thecloudcanuseA′v,B′vandW0,Wjtorecovere(g,g)acr2s,whichcanbeusedtotestthekeywordequalityaselaboratedbelow.
1)KP-ABKSConstructionandSecurityAnalysis:Letbetheprimarysecurityparameter.
Itconsistsofthefollowingalgorithms.
Setup(1):Selectabilinearmape:G*G→GT,whereGandGTarecyclicgroupsoforderp,whichisan-bitprime.
LetH1:{0,1}→GbeahashfunctionmodeledasrandomoracleandH2:{0,1}→Zpbeanone-wayhashfunction,selecta,b,c←Zpandg←G,andsetpm=(H1,H2,e,g,p,ga,gb,gc,G,GT),mk=(a,b,c).
KeyGen(mk,T):ExecuteShare(T,ac)toobtainsecretshareqv(0)ofacforeachleavev∈lvs(T)onaccesstreeT.
Foreachleafv∈lvs(T),pickt←Zp,andcomputeAv=gqv(0)H1(att(v))tandBv=gt.
Setsk=(T,{(Av,Bv)|v∈lvs(T)}).
Enc(w,Atts):Selectr1,r2←Zp,andcomputeW′=gcr1,W=ga(r1+r2)gbH2(w)r1andW0=gr2.
Foreachatj∈Atts,computeWj=H1(atj)r2.
Setcph=(Atts,W′,W,W0,{Wj|atj∈Atts}).
TokenGen(sk,w):Selects←Zp,andcomputeA′v=Asv,B′v=Bsvforeachv∈lvs(T).
Computetok1=(gagbH2(w))sandtok2=gcs.
Settk=(tok1,tok2,T,{(A′v,B′v)|v∈lvs(T)})Search(tk,cph):GivenattributesetAttsspeciedincph,selectanattributesetSsatisfyingtheaccesstreeTspec-iedintk.
IfSdoesnotexist,return0;otherwise,foreachatj∈S,computeEv=e(A′v,W0)/e(B′v,Wj)=e(g,g)sr2qv(0),whereatt(v)=atjforv∈lvs(T).
Com-putee(g,g)sr2qroot(0)←Combine(T,{Ev|att(v)∈S})sothatEroot=e(g,g)acsr2.
Return1ife(W′,tok1)Eroot=e(W,tok2),and0otherwise.
Theschemeiscorrectbecausee(W′,tok1)Eroot=e(gcr1,(gagbH2(w))s)Eroot=e(g,g)acs(r1+r2)e(g,g)bcsH2(w)r1,e(W,tok2)=e(ga(r1+r2)gbH2(w)r1,gcs)=e(g,g)acs(r1+r2)e(g,g)bcsH2(w)r1Theschemeissecurebecauseofthefollowingtheorems,whoseproofsaregiveninAppendixAandAppendixB,respectively.
Theorem1:GiventheDLassumptionandone-wayhashfunctionH2,theKP-ABKSschemeisselectivelysecureagainstchosen-keywordattackintherandomoraclemodel.
Theorem2:Giventheone-wayhashfunctionH2,theKP-ABKSschemeachieveskeywordsecrecyintherandomoraclemodel.
2)CP-ABKSConstructionandSecurityAnalysis:Letbetheprimarysecurityparameter.
Itconsistsofthefollowingalgorithms.
Setup(1):Selectabilineargroupe:G*G→GT,whereGandGTarecyclicgroupsoforderp,whichisan-bitprime.
LetH1:{0,1}→GbeahashfunctionmodeledasrandomoracleandH2:{0,1}→Zpbeanone-wayhashfunction,selecta,b,c←Zpandg←G,andsetpm=(H1,H2,e,g,p,ga,gb,gc,G,GT),mk=(a,b,c).
KeyGen(mk,Atts):Selectr←Zp,computeA=g(acr)/b.
Foreachatj∈Atts,selectrj←ZpandcomputesAj=grH1(atj)rjandBj=grj.
Setsk=(Atts,A,{(Aj,Bj)|atj∈Atts}).
Enc(w,T):Selectr1,r2←Zp,andcomputeW=gcr1,W0=ga(r1+r2)gbH2(w)r1andW′=gbr2.
Computesecretsharesofr2foreachleaveofaccesstreeTas{qv(0)|v∈lvs(T)}←Share(T,r2).
Foreachv∈lvs(T),computeWv=gqv(0)andDv=H1(att(v))qv(0).
Setcph=(T,W,W0,W′,{(Wv,Dv)|v∈lvs(T)}).
TokenGen(sk,w):Selects←Zp,andcomputetok1=(gagbH2(w))s,tok2=gcsandtok3=As=g(acsrs)/b.
Foreachatj∈Atts,computeA′j=AsjandB′j=Bsj.
Settk=(Atts,tok1,tok2,tok3,{(A′j,B′j)|atj∈Atts}).
Search(tk,cph):GivenattributesetAttsasspeciedintk,selectanattributesetSthatsatisestheaccesstreeTspeciedincph.
IfSdoesnotexist,return0;otherwise,foreachatj∈S,computeEv=e(A′j,Wv)/e(B′j,Dv)=e(g,g)rsqv(0),whereatt(v)=atjforv∈lvs(T).
Com-putee(g,g)rsqroot(0)←Combine(T,{Ev|att(v)∈S})andEroot=e(g,g)rsr2.
Return1ife(W0,tok2)=e(W,tok1)Eroote(tok3,W′),and0otherwise.
CorrectnessoftheschemecanbeveriedsimilarlytothatofKP-ABKS.
Securityoftheschemeisassuredbythefollowingtheorems,TheproofoftheformeroneisdeferredtoAppendixC,andtheproofofthelatteroneisomittedbecauseitissimilartothatofTheorem2.
Theorem3:Giventheone-wayhashfunctionH2,theCP-ABKSschemeisselectivelysecureagainstchosen-keywordattackinthegenericbilineargroupmodel[33].
Theorem4:Giventheone-wayhashfunctionH2,theCP-ABKSschemeachieveskeywordsecrecyintherandomoraclemodel.
IV.
VERIFIABLEATTRIBUTE-BASEDKEYWORDSEARCHInthemodelofABKS,theparty(e.
g.
,cloud)isassumedtoexecutethesearchoperationfaithfully(despitethatthepartymayattempttoinferusefulinformationaboutthekeywords).
VABKSachievesthegoalofABKSdespitethatthepartyexecutingthesearchoperationmaybemalicious.
A.
ModelWeconsiderthesystemmodelillustratedinFigure1,whichinvolvesfourparties:adataowner,whooutsourcesitsencrypteddataaswellasencryptedkeyword-indextothecloud;acloud,whichprovidesstorageservicesandcanconductkeywordsearchoperationsonbehalfofthedatausers;adatauser,whoistoretrievethedataowner'sencrypteddataaccordingtosomekeyword(i.
e.
,keywordsearch);atrustedauthority,whichissuescredentialstothedataowners/users.
Thecredentialsaresentoverauthenticatedprivatechannels(whichcanbeachievedthroughanotherlayerofmechanisms).
DataownerCloudSearchTokenforKeywordXOutsourcingDatauser(W/orW/ocredentialssatisfyingdataowner'saccesscontrolpolicies)Searchresult&proofTrustedauthority(issuingcredentialsforallcloudusers)YXF2F1F3WVKeywordsDatafilesFig.
1.
VABKSsystemmodel,wherekeywordsX,YandV,Wmaycorrespondtodifferentaccesscontrolpolicies.
Thedataownersarenaturallytrusted.
Bothauthorizedandunauthorizeddatausersaresemi-trusted,meaningthattheymaytrytoinfersomesensitiveinformationofinterest.
Thecloudisnottrustedasitmaymanipulatethesearchoperations,whichalreadyimpliesthatthecloudmaymanipulatetheoutsourcedencrypteddata.
B.
DenitionLetFS={F1,Fn}beasetofdatales.
LetKGj,1≤j≤l,beasetofkeywords(alsocalled"keywordgroup")thatareencryptedwiththesameaccesscontrolpolicy(i.
e.
,accesstree).
LetKG={KG1,KGl}.
Foreachkeywordw,letMP(w)bethesetofidentiersidentifyingdatalesthatcontainkeywordw.
LetMP={MP(w)|w∈∪li=1KGi}.
LetD=(KG,MP,FS)denotekeyword-indexandthedatales.
Denition4:AVABKSschemeconsistsofthefollowingalgorithms:(mk,pm)←Init(1):Thisalgorithmisrunbythetrustedauthoritytoinitializethesystem.
sk←KeyGen(mk,IKeyGen):Thisalgorithmisrunbythetrustedauthoritytoissuecredentialsskfordatausers/owners.
(Au,Index,Dcph)←BuildIndex({IEnc}l,{I′Enc}n,D):ThisalgorithmisrunbyadataownertoencryptD=(KG,MP,FS)todataciphertextDcph,indexciphertextIndexandauxiliaryinformationAu,where{IEnc}listhesetofaccesscontrolpoliciesrespectivelyforencryptingthelkeywordgroupsKG1,KGland{I′Enc}nisthesetofaccesscontrolpoliciesrespectivelyforencryptingthendatalesFS1,FSn(Itmayhappenthattheaccesscontrolpoliciesforkeywordsandtheirrespectivedatalesaredifferent).
tk←TokenGen(sk,w):Thisalgorithmisrunbyanauthorizeddatausertogenerateasearchtokentkforkeywordw.
(proof,rslt)←SearchIndex(Au,Index,Dcph,tk):ThisalgorithmisrunbythecloudtoconductthesearchoperationsoverencryptedindexIndexonbehalfofadatauser.
Itoutputsthesearchresultrsltandaproofproof.
{0,1}←Verify(sk,w,tk,rslt,proof):Thisalgorithmisrunbythedatausertoverifythat(rslt,proof)isvalidwithrespecttosearchtokentk.
AVABKSschemeiscorrectifthefollowingholds:given(mk,pm)←Init(1),sk←KeyGen(mk,IKeyGen),(Au,Index,Dcph)←BuildIndex({IEnc}l,{I′Enc}n,D),tk←TokenGen(sk,w)and(proof,rslt)←SearchIndex(Au,Index,Dcph,tk),Verify(sk,w,tk,rslt,proof)alwaysreturns1.
Informally,securityofVABKSisdenedasthefollowingfourrequirements,wherethecloudistheadversaryA.
Datasecrecy:Givenencryptedkeywordsandsearchtokens,Astillcannotlearnanyinformation(inacompu-tationalsense)abouttheencrypteddatales.
Thisde-nitioncanbeformalizedbythechosen-plaintextsecuritygame,wheretwochallengesD0=(KG,MP,FS0),D1=(KG,MP,FS1)correspondtothesameKGandMP,and|FS0|=|FS1|.
Selectivesecurityagainstchosen-keywordattack:Withoutseeingcorrespondingsearchtokens,Acannotinferanyinformationaboutthekeywordfromthekeywordcipher-text.
Thispropertyisextendedfromtheselectivesecurityagainstchosen-keywordattackofABKS.
Keywordsecrecy:Givenencrypteddatales,theprobabil-itythatAlearntheplaintextkeywordfromthekeywordciphertextaswellasthesearchtokensisnomorethanthatofarandomguess.
ThispropertyisextendedfromthekeywordsecrecyofABKS.
Veriability:IfAreturnsanincorrectsearchresult,itcanbedetectedbytheuserwithanoverwhelmingprobability.
Weformalizethissecuritypropertyviathefollowingveriabilitygame.
VeriabilityGame:Setup:Thechallengerruns(pm,mk)←Init(1).
AselectsD=(KG,MP,FS),{IEnc}land{I′Enc}nandsendsthemtothechallenger.
Thechallengerruns(Au,Index,Dcph)←BuildIndex({IEnc}l,{I′Enc}n,D),andgives(Au,Index,Dcph)toA.
Phase1:Acanquerythefollowingoraclesforpolynomiallymanytimes.
OKeyGen(IKeyGen):ThechallengerreturnstoAcredentialskcorrespondingtoIKeyGen.
OTokenGen(IKeyGen,w):Thechallengergeneratescreden-tialskwithIKeyGen,andreturnstoAasearchtokentkbyrunningalgorithmTokenGenwithinputsskandw.
OVerify(IKeyGen,w,tk,rslt,proof):Thechallengergener-atescredentialskwithIKeyGen,returnsγtoAbyrunningγ←Verify(sk,w,tk,rslt,proof).
Challengephase:Aselectsanon-trivialchallengeIEncandakeywordwandgivesthemtothechallenger.
ThechallengerselectsIKeyGensuchthatF(IKeyGen,IEnc)=1,generatescredentialskwithIKeyGenandreturnstoAasearchtokentkbyrunningtk←TokenGen(sk,w).
Guess:Aoutputs(rslt,proof)tothechallenger.
WesayAwinsthegameif1←Verify(sk,w,tk,rslt,proof)andrslt=rslt,where(rslt,proof)isproducedbythechallengerbyrunningSearchIndex(Au,Index,tk).
Denition5:AVABKSschemeisveriableiftheadvantagethatanyAwinstheveriabilitygameisnegligibleinsecurityparameter.
C.
ConstructionAtrivialsolutionforachievingveriabilityisthatadatauserdownloadsthekeywordciphertextsandconductthesearchoperationslocally.
Thissolutionincursprohibitivecommunicationandcomputationaloverhead.
AshighlightedinFigure2,weinsteadletadatauseroutsourcethekey-wordsearchoperationtothecloud,andthenverifythatthecloudfaithfullyperformedthekeywordsearchoperation.
Morespecically,thedataownerusesthesignaturesandbloomltersasfollows:Akeywordsignatureisgeneratedforeachkeywordciphertextanditsassociateddataciphertexts.
ItisusedYXF2F1F3WVKeywordsencryptedwithaccesscontrolpolicy11:Encryptkeywordsanddatafiles,andgeneratekeywordsignature(e.
g.
,!
X,!
y)foreachkeywordciphertextanditsassociateddataciphertexts.
2:Generateabloomfilterforeachkeywordgroup,encryptarandomnumberthatisusedformaskingthebloomfilter,andgenerateabloomfiltersignature(e.
g.
,!
BF1)forthemaskedbloomfilter(e.
g.
BF'1)andtherandomnumberciphertext(e.
g.
,CphBF1).
3:Foreachkeywordgroup,generatealocalsignature(e.
g.
,!
1)forallkeywordciphertexts.
4:Generateaglobalsignature(e.
g.
,!
)forallrandomnumberciphertexts.
Keywordsencryptedwithaccesscontrolpolicy2!
1!
2!
CphF2CphF1CphF3CphYCphXCphWCphV!
X!
y!
v!
wBF'1CphBF1!
BF1BF'2CphBF2!
BF2Fig.
2.
Basicideaforachievingveriability,wheredatalesF1,F2,F3wereencryptedtocphF1,cphF2,cphF3,keywordsX,YwereencryptedtocphX,cphYwithaccesscontrolpolicy1,andkeywordsV,WwereencryptedtocphV,cphWwithaccesscontrolpolicy2.
Givenasearchtokentk,forkeywordgroupi,thecloudprovides(σw,cphBFi)astheproofwhenitndskeywordciphertextcphwthatmatchestk,and(cphBFi,BF′i,σBFi)otherwise.
forpreventingthecloudfromreturningincorrectdataciphertextsasthesearchresult.
Foreachkeywordgroup,onebloomlterisbuiltfromitskeywords.
Thisallowsadatausertocheckthatthesearchedkeywordwasindeednotinthekeywordgroupwhenthecloudreturnsanullsearchresult,withoutdownloadingallkeywordciphertextsfromthecloud.
Arandomnumberisselectedandencryptedwiththesameaccesscontrolpolicyaskeywords.
Therandomnumbermasksthebloomlterforpreservingkeywordprivacy.
Abloomltersignatureisgeneratedforthemaskedbloomlterandtherandomnumberciphertextforassuringtheirintegrity.
Aglobalsignatureisobtainedbysigningrandomnumberciphertextsofallgroups.
Itallowsadatausertoverifytheintegrityoftherandomnumberciphertexts.
AlocalsignatureisgeneratedforallkeywordciphertextswithinthesamekeywordgroupKGj.
Thissignatureallowstheusertovalidatetheintegrityofkeywordciphertextswithinthekeywordgroup.
Figure3describestheVABKSscheme,whichusesasignatureschemeSig=(KeyGen,Sign,Verify),asymmet-ricencryptionschemeSE=(KeyGen,Enc,Dec),anABEschemeABE=(Setup,KeyGen,Enc,Dec),wherethelattertwoencryptionschemesareusedtoencryptdatales.
TheVABKSschemeisbuiltontopofanABKSschemeABKS=(Setup,KeyGen,Enc,TokenGen,Search),whichencryptsthekeywords.
NotethatABEandABKScanbetheirciphertext-policyvariantortheirkey-policyvariant,butforthesametype.
ThisleadstotwovariantsofVABKS.
NotethatintheVerifyalgorithmofFigure3,whenanauthorizeddatauserveriesanullsearchresultforkeywordgroup{cphw|w∈KGi},wheretheusersearcheskeywordw′,itcanhappenthat1←BFVerify({H′1,H′k},BFi,w′)duetothefalse-positiveoftheBloomlter.
Tovalidatethesearchresultinthiscase,theVerifyalgorithmhastodownload{cphw|w∈KGi},andchecksthekeywordciphertextsonebyone.
Westressthatthisdoesnotincursignicantcommunica-tioncostonaveragebecausewecansetthefalse-positiverateaslowaspossiblebychoosingappropriatemandk(i.
e.
,upononesearchrequest,the"wasted"bandwidthcommunicationandcomputationalcostareproportionaltothisfalse-positiverate).
Forexample,inourexperimentwesetthefalse-positiveratetobe4.
5*109.
D.
SecurityAnalysisSecurityoftheVABKSschemecanbeprovenasthefollowingtheorems,whoseproofsaredeferredtoAppendixD.
Theorem5:IfABEandSEaresecureagainstthechosen-plaintextattack,theVABKSschemeachievesthedatasecrecy.
Theorem6:IfABEissecureagainstchosen-plaintextat-tack,HisasecurepseudorandomgeneratorandABKSisselectivelysecureagainstchosenkeywordattack,theVABKSschemeisselectivelysecureagainstchosen-keywordattack.
Theorem7:IfABEissecureagainstchosen-plaintextattack,HisasecurepseudorandomgeneratorandABKSachieveskeywordsecrecy,theVABKSschemeachieveskeywordse-crecy.
Theorem8:IfSigisasecuresignature,theVABKScon-structionachievestheveriability.
V.
PERFORMANCEEVALUATIONWeevaluatetheefciencyoftheABKSschemesintermsofbothasymptoticcomplexityandactualexecutiontime,andtheefciencyoftheVABKSschemeintermsofactualexecutiontime.
WedonotconsidertheasymptoticcomplexityofVABKSbecauseitusesmultiplebuilding-blocks(e.
g.
,signingandABEschemes)thatcanbeinstantiatedwithanysecuresolutions.
Asymptoticcomplexityismeasuredintermsoffourkindsofoperations:H1denotestheoperationofmappingabit-stringtoanelementofG,Pairdenotesthepairingoperation,EdenotestheexponentiationoperationinG,andETdenotestheexponentiationoperationinGT.
Weignoremultiplicationandhashoperations(otherthanH1)becausetheyaremuchmoreefcientthantheaboveoperations[38].
WeimplementedABKSandVABKSinJAVA,whileusingtheJavaPairingBasedCryptographylibrary(jPBC)[38].
Init(1):Givensecurityparameter,theattributeauthoritychooseskuniversalhashfunctionsH′1,H′k,whichareusedtoconstructam-bitBloomlter.
LetH:{0,1}→{0,1}mbeasecurepseudorandomgenerator,SEbeasecuresymmetricencryptionscheme,ABEbeasecureABEschemeandABKSbeasecureABKSscheme.
Thisalgorithmexecutes(ABE.
pm,ABE.
mk)←ABE.
Setup(1)and(ABKS.
pm,ABKS.
mk)←ABKS.
Setup(1).
Itsetsthepublicparameteraspm=(ABE.
pm,ABKS.
pm,H′1,H′k)andmk=(ABE.
mk,ABKS.
mk).
KeyGen(mk,IKeyGen):TheattributeauthorityrunsABE.
sk←ABE.
KeyGen(ABE.
mk,IKeyGen)andABKS.
sk←ABKS.
KeyGen(ABKS.
mk,IKeyGen),setssk=(ABE.
sk,ABKS.
sk),andsendssktoadataowner/useroveranauthenticatedprivatechannel.
BuildIndex({IEnc}l,{I′Enc}n,D):Thedataownerruns(Sig.
sk,Sig.
pk)←Sig.
KeyGen(1),keepsSig.
skprivateandmakesSig.
pkpublic.
GivenD=(KG={KG1,KGl},MP={MP(w)|w∈∪li=1KGi},FS={F1,Fn}),thedataownerexecutesasfollows:1)Encrypteachdatalewithhybridencryption:Fj∈FS,generateciphertextcphFj=(cphskj,cphSEj)byrunningSE.
skj←SE.
KeyGen(1),cphSEj←SE.
Enc(SE.
skj,Fj),andcphskj←ABE.
Enc(I′Encj,SE.
skj).
2)Encrypteachkeywordandgeneratekeywordsignature:GivenKGi,1≤i≤l,foreachw∈KGi,runcphw←ABKS.
Enc(IEnci,w),setMP(cphw)={IDcphFj|IDFj∈MP(w)},andgenerateσw←Sig.
Sign(Sig.
sk,cphw||string({cphFj|IDcphFj∈MP(cphw)})),whereIDFjandIDcphFjareidentiersforidentifyingdataleFjanddataciphertextcphFj,respectively.
3)Generateabloomlter,abloomltersignatureandalocalsignatureforeachgroupKGi:LetBFi←BFGen({H′1,H′k},KGi),cphBFi←ABE.
Enc(IEnci,M)forsomerandomlychosenMfromthemessagespaceofABE,computeBF′i=H(M)BFiandgenerateσBFi←Sig.
Sign(Sig.
sk,BF′||cphBFi).
Letσi←Sig.
Sign(Sig.
sk,string({cphw|w∈KGi})).
4)Generatetheglobalsignature:Setσ=Sig.
Sign(Sig.
sk,cphBF1cphBFl).
5)LetAu=(σ,σ1,σl,cphBF1cphBFl,σBF1σBFl,{σw|w∈∪li=1KGi}),Index=({cphw|w∈∪li=1KGi},{MP(cphw)|w∈∪li=1KGi})andDcph=({cphFj|Fj∈FS}).
TokenGen(sk,w):Givencredentialssk,adatausergeneratessearchtokentk←ABKS.
TokenGen(ABKS.
sk,w).
SearchIndex(Au,Index,Dcph,tk):Letrsltbeanemptysetandproof=(σ)initially.
Thecloudenumeratesi={cphw|w∈KGi},1≤i≤l,whicharethekeywordciphertextswithrespecttothesameaccesscontrolpolicy.
Foreachcphw∈i,itrunsγ←ABKS.
Search(cphw,tk).
Ifγ=0,itcontinuestoprocessthenextkeywordciphertextini;otherwise,itaddsthetuple(cphw,{cphFj|IDcphFj∈MP(cphw)})torsltand(σw,cphBFi)toproof.
Ifthereexistnoγ=1afterprocessingallcphwini,thenitsadds(BF′i,cphBFi,σBFi)toproof.
Verify(sk,w,tk,proof,rslt):Thedatauserveriesthesearchresultfromthecloudasfollows:1)Verifytheintegrityoftherandomnumberciphertexts:Letγ=Sig.
Verify(Sig.
pk,σ,cphBF1cphBFl).
Ifγ=0,thenreturn0;otherwise,continuetoexecutethefollowing.
2)Fori=1,l,itexecutesasfollowstoverifythatthecloudindeedreturnedthecorrectresultforeachkeywordgroupi:Case1:If(cphw,{cphFj|IDcphFj∈MP(cphw)})∈rslt,meaningthereexiststhekeywordciphertextcphw,whichcorrespondstothesameaccesscontrolpolicyaswhatisspeciedbycphBFi,havingthesamekeywordspeciedbytk,thenitrunsγ←ABKS.
Search(cphw,tk)andγ′←Sig.
Verify(Sig.
pk,σw,cphw||string({cphFj|IDcphFj∈MP(cphw)}))toverifywhetherornotcphwmatchestkandalltheassociateddataciphertextsarereturnedbythecloud.
Ifeitherγ=0orγ′=0,thenreturn0,otherwise,continuetoi=i+1.
Case2:If(BF′i,cphBFi,σBFi)∈proofmeaningthatthereisnomatchingkeywordciphertext,thenitcontinuestoverifytheintegrityofthemaskedBloomlterbyrunningγ′←Sig.
Verify(Sig.
pk,σBFi,BF′i||cphBFi).
Ifγ′=0,return0;otherwise,executethefollowing:Ifthedatauserisauthorized,computeM←ABE.
Dec(ABE.
sk,cphBFi),BFi=H(M)BF′i.
Executeδ←BFVerify({H′1,H′k},BFi,w)tocheckwhetherwornotispresentinthekeywordgroupasrepresentedbyBFi.
–Ifδ=0,meaningthatwisnotpresentinthekeywordgroupasrepresentedbyBFi,thencontinuetoi=i+1.
–Ifδ=1,downloadi={cphw|w∈KGi}andσifromthecloud,andrunη←Sig.
Verify(Sig.
pk,σi,string({cphw|w∈KGi})).
Ifη=0,return0;otherwise,runτ←ABKS.
Search(cphw,tk)byenumeratingcphwincphw|w∈KGi}.
Ifthereexistssomeτ=1afterprocessingallcphw(meaningthatthereexistssomecphwthatmatchestk),return0;otherwise,continuetoi=i+1.
Ifthedatauserisunauthorized,thenitcontinuestoi=i+1becausecphBFicannotbedecrypted.
Case3:Ifnoneoftheabovetwocaseshappens,return0.
3)Return1ifalltuplesinthesearchresulthavebeenveried,and0otherwise.
Fig.
3.
VABKSconstructionInourimplementation,thebilinearmapisinstantiatedasTypeApairing(=512),whichoffersalevelofsecurityequivalentto1024-bitDLOG[38].
ForbothCP-VABKSandKP-VABKS,weinstantiatedthesymmetricencryptionschemeasAES-CBC,andthesignatureschemewithDSAprovidedbyJDK1.
6.
WeinstantiatedABKS,ABEasCP-ABKS,CP-ABE[3]forCP-ABKS,andKP-ABKS,KP-ABE[2]forKP-VABKS,respectively.
Finally,wesettheexampleaccesscontrolpolicyas"at1AND.
.
.
ANDatN.
"A.
EfciencyofABKSAsymptoticComplexityoftheABKSSchemes.
TableIdescribestheasymptoticcomplexitiesoftheABKSschemes.
WeobservethatintheCP-ABKSscheme,thecomplexityofKeyGenisalmostthesameasthatofEnc.
IntheKP-ABKSscheme,KeyGenismoreexpensivethanEnc.
Inbothschemes,thetwoSearchalgorithmsincuralmostthesamecost.
complexityoutputsizeKP-KeyGen3NE+NH12N|G|Enc(S+4)E+SH1(S+3)|G|ABKSTokenGen(2N+2)E(2N+2)|G|Search(2S+2)Pair+SETCP-KeyGen(2S+2)E+SH1(2S+1)|G|Enc(2N+4)E+NH1(2N+3)|G|ABKSTokenGen(2S+4)E(2S+3)|G|Search(2N+3)Pair+NETTABLEIASYMPTOTICCOMPLEXITIESOFCP-ABKSANDKP-ABKS,WHERESISTHENUMBEROFADATAUSER'SATTRIBUTESANDNISTHENUMBEROFATTRIBUTESTHATAREINVOLVEDINADATAOWNER'SACCESSCONTROLPOLICY(I.
E.
,THENUMBEROFLEAVESINTHEACCESSTREE).
ActualPerformanceoftheABKSSchemes.
ToevaluatetheperformanceoftheABKSschemes,werantheexperimentsonaclientmachinewithLinuxOS,2.
93GHzIntelCoreDuoCPU(E7500),and2GBRAM.
WevariedN,thenumberofattributesthatareinvolvedintheexampleaccesscontrolpolicy,from1to50withsteplength10.
Weraneachexperimentfor10timestoobtaintheaverageexecutiontime.
S/N11020304050KP-KeyGen0.
0880.
7861.
5392.
3163.
0813.
863Enc0.
1080.
5391.
0161.
4921.
9832.
434ABKSTokenGen0.
0730.
3310.
6270.
9171.
2111.
504Search0.
0490.
2750.
4800.
7110.
9471.
182CP-KeyGen0.
1070.
6861.
2751.
9012.
5253.
151Enc0.
1210.
6811.
3041.
9232.
5463.
169ABKSTokenGen0.
0880.
3490.
6730.
9321.
2281.
513Search0.
0610.
3290.
4930.
7280.
971.
202TABLEIIEXECUTIONTIME(SECOND)OFTHEALGORITHMSINTHEKP-ABKSANDCP-ABKSSCHEMES,WHERENISTHENUMBEROFATTRIBUTESINVOLVEDINTHEEXAMPLEACCESSCONTROLPOLICY.
THENUMBEROFDATAUSER'SATTRIBUTESISALSOSETTON,NAMELYS=NINTHEEXPERIMENTS.
TableIIshowstheexecutiontimeofthetwoABKSschemes.
Weobservethatforbothschemes,thekeywordencryptionalgorithmEnc(runbythedataowner)ismoreexpensivethanthatofthekeywordsearchalgorithmSearch(runbythecloud)withthesameN.
However,thekeywordencryptionalgorithmisexecutedonlyonceforeachkeyword,whereasthekeywordsearchalgorithmwillbeperformedasmanytimesasneeded.
Furthermore,weadvocatethatthedatausersoutsourcethekeywordsearchoperationstothecloud(i.
e.
,takingadvantageofthecloud'scomputationalresources).
B.
EfciencyofVABKSwithRealDataTodemonstratethefeasibilityofVABKSinpractice,weevaluateditwithrealdata,whichconsistsof2,019distinctkeywordsextractedfrom670PDFdocuments(papers)fromtheACMDigitalLibrarywithatotalsizeof778.
1MB.
Wesetk=28andm=10KBforBloomltersothatmn=10810242019≈40andthefalse-positiverateisaround4.
5*109.
Wevarytheaccesscontrolpolicyrangingfrom1to50attributeswithstep-length10.
Ineachexperiment,weencryptedallkeywordswiththesameaccesscontrolpolicy.
Thealgorithmsrunbythedataownerandthedatausers(i.
e.
BuildIndex,TokenGenandVerify)wereexecutedonaclientmachinewithLinuxOS,2.
93GHzIntelCoreDuoCPU(E7500),and2GBRAM.
Thealgorithmrunbythecloud(i.
e.
,SearchIndex)wasexecutedonaservermachine(alaptop)withWindows7,Inteli52.
60GHzCPU,and8GBRAM.
Figure4(a)showstheexecutiontimeofBuildIndexthatwasrunbythedataowner.
Weobservethatwiththesameattribute/policycomplexity,CP-VABKSismorecostlythanthatofKP-VABKSwhenrunningalgorithmBuildIndex.
Figure4(b)plotstheexecutiontimeofthealgorithmsrunbythedatauserandthecloud.
WesimulatedthatalgorithmSearchIndexneedstoconductsearchoperationsover1,010keywordcipher-textstondthematchedkeywordciphertext.
WeobservethattheexecutiontimeofTokenGenandVerifyisreallysmallcomparedwithkeywordsearchalgorithmSearchIndex.
Thisagainconrmsthatthedatausershouldoutsourcekeywordsearchoperationstothecloud.
Figure4(c)plotsthesizeofindexandauxiliaryinformation,including2,019keywordciphertexts,bloomltersandsignatures.
WealsoseethatCP-VABKSconsumesaroundtwotimesmorestoragespacethanKP-VABKSwiththesameattribute/policycomplexity.
ThesediscrepanciesshouldserveasafactorwhendecidingwhethertouseCP-VABKSorKP-VABKSinpractice.
VI.
CONCLUSIONWehaveintroducedanovelcryptographicprimitivecalledveriableattribute-basedkeywordsearchforsecurecloudcomputingoveroutsourcedencrypteddata.
Thisprimitiveallowsadataownertocontrolthesearchofitsoutsourcedencrypteddataaccordingtoanaccesscontrolpolicy,whiletheauthorizeddatauserscanoutsourcethesearchoperationstothecloudandforcethecloudtofaithfullyexecutethesearch(asacheatingcloudcanbeheldaccountable).
Performanceevaluationshowsthatthenewprimitiveispractical.
Ourstudyfocusedonstaticdata.
Assuch,oneinterestingopenproblemforfutureresearchistoaccommodatedynamicdata.
Acknowledgement.
ZhengandXuweresupportedinpartbytheNationalScienceFoundationunderGrantNo.
1111925.
AteniesewassupportedbyaGoogleFacultyResearchAward,anIBMFacultyAward,andthePRINprojectTENACE.
REFERENCES[1]A.
SahaiandB.
Waters,"Fuzzyidentity-basedencryption,"inProc.
ofEUROCRYPT,pp.
457–473,2005.
1102030405001000200030004000500060007000S(N)Time(second)CPVAKBS.
BuildIndexKPVABKS.
BuildIndex(a)BuildIndex1102030405002004006008001000S(N)Time(second)CPVAKBS.
SearchIndexCPVAKBS.
TokenGenCPVAKBS.
VerifyKPVABKS.
SearchIndexKPVABKS.
TokenGenKPVABKS.
Verify(b)TokenGen,SearchIndexandVerify11020304050051015202530S(N)Indexsize(MB)CPVAKBSKPVABKS(c)SizeofindexandauxiliaryinformationFig.
4.
PerformanceoftheCP-VABKSandKP-VABKSschemes,whereNisthenumberofattributesinvolvedintheexampleaccesscontrolpolicy.
Thenumberofdatauser'sattributesisalsosettoN,namelyS=Nintheexperiments.
[2]V.
Goyal,O.
Pandey,A.
Sahai,andB.
Waters,"Attribute-basedencryp-tionforne-grainedaccesscontrolofencrypteddata,"inProc.
ofACMCCS,pp.
89–98,2006.
[3]J.
Bethencourt,A.
Sahai,andB.
Waters,"Ciphertext-policyattribute-basedencryption,"inProc.
ofIEEES&P,pp.
321–334,2007.
[4]T.
OkamotoandK.
Takashima,"Fullysecurefunctionalencryptionwithgeneralrelationsfromthedecisionallinearassumption,"inProc.
ofCRYPTO,pp.
191–208,2010.
[5]A.
B.
LewkoandB.
Waters,"Newproofmethodsforattribute-basedencryption:Achievingfullsecuritythroughselectivetechniques,"inProc.
ofCRYPTO,pp.
180–198,2012.
[6]M.
Chase,"Multi-authorityattributebasedencryption,"inProc.
ofTCC,pp.
515–534,2007.
[7]M.
ChaseandS.
S.
Chow,"Improvingprivacyandsecurityinmulti-authorityattribute-basedencryption,"inProc.
ofACMCCS,pp.
121–130,2009.
[8]J.
Camenisch,M.
Kohlweiss,A.
Rial,andC.
Sheedy,"Blindandanonymousidentity-basedencryptionandauthorisedprivatesearchesonpublickeyencrypteddata,"inProc.
ofPKC,pp.
196–214,2009.
[9]D.
X.
Song,D.
Wagner,andA.
Perrig,"Practicaltechniquesforsearchesonencrypteddata,"inProc.
ofIEEES&P,pp.
44–,2000.
[10]E.
-J.
Goh,"Secureindexes.
"CryptologyePrintArchive,Report2003/216,2003.
http://eprint.
iacr.
org/2003/216/.
[11]Y.
-C.
ChangandM.
Mitzenmacher,"Privacypreservingkeywordsearchesonremoteencrypteddata,"inProc.
ofACNS,pp.
442–455,2005.
[12]R.
Curtmola,J.
Garay,S.
Kamara,andR.
Ostrovsky,"Searchablesymmetricencryption:improveddenitionsandefcientconstructions,"inProc.
of,pp.
79–88,2006.
[13]M.
ChaseandS.
Kamara,"Structuredencryptionandcontrolleddisclo-sure,"inProc.
ofASIACRYPT,pp.
577–594,2010.
[14]K.
KurosawaandY.
Ohtaki,"Uc-securesearchablesymmetricencryp-tion,"inProc.
ofFC,pp.
285–298,SpringerBerlin/Heidelberg.
[15]S.
KamaraandK.
Lauter,"Cryptographiccloudstorage,"inProc.
ofFC,pp.
136–149,2010.
[16]S.
Kamara,C.
Papamanthou,andT.
Roeder,"Cs2:Asearchablecryp-tographiccloudstoragesystem.
"MicrosoftTechnicalReport,2011.
http://research.
microsoft.
com/apps/pubs/id=148632.
[17]S.
Kamara,C.
Papamanthou,andT.
Roeder,"Dynamicsearchablesymmetricencryption,"inProc.
ofACMCCS,pp.
965–976,2012.
[18]Q.
ChaiandG.
Gong,"Veriablesymmetricsearchableencryptionforsemi-honest-but-curiouscloudservers,"inProc.
ofICC,pp.
917–922,2012.
[19]D.
Boneh,G.
D.
Crescenzo,R.
Ostrovsky,andG.
Persiano,"Publickeyencryptionwithkeywordsearch,"inProc.
ofEUROCRYPT,pp.
506–522,2004.
[20]B.
R.
Waters,D.
Balfanz,G.
Durfee,andD.
K.
Smetters,"Buildinganencryptedandsearchableauditlog,"inProc.
ofNDSS,2004.
[21]M.
Bellare,A.
Boldyreva,andA.
O'Neill,"Deterministicandefcientlysearchableencryption,"inProc.
ofCRYPTO,pp.
535–552,2007.
[22]J.
Baek,R.
Safavi-Naini,andW.
Susilo,"Publickeyencryptionwithkeywordsearchrevisited,"inProc.
ofICCSA,pp.
1249–1259,2008.
[23]P.
Golle,J.
Staddon,andB.
Waters,"Secureconjunctivekeywordsearchoverencrypteddata,"inProc.
ofACNS,pp.
31–45,2004.
[24]E.
Shi,J.
Bethencourt,H.
T.
-H.
Chan,D.
X.
Song,andA.
Perrig,"Multi-dimensionalrangequeryoverencrypteddata,"inProc.
ofIEEES&P,pp.
350–364,2007.
[25]D.
BonehandB.
Waters,"Conjunctive,subset,andrangequeriesonencrypteddata,"inProc.
ofTCC,pp.
535–554,2007.
[26]M.
Li,S.
Yu,N.
Cao,andW.
Lou,"Authorizedprivatekeywordsearchoverencrypteddataincloudcomputing,"inProc.
ofICDCS,pp.
383–392,2011.
[27]F.
Bao,R.
H.
Deng,X.
Ding,andY.
Yang,"Privatequeryonencrypteddatainmulti-usersettings,"inProc.
ofISPEC,pp.
71–85,2008.
[28]T.
OkamotoandK.
Takashima,"Hierarchicalpredicateencryptionforinner-products,"inProc.
ofASIACRYPT,pp.
214–231,2009.
[29]J.
Katz,A.
Sahai,andB.
Waters,"Predicateencryptionsupportingdisjunctions,polynomialequations,andinnerproducts,"inProc.
ofEUROCRYPT,pp.
146–162,2008.
[30]S.
Benabbas,R.
Gennaro,andY.
Vahlis,"Veriabledelegationofcomputationoverlargedatasets,"inProc.
ofCRYPTO,pp.
111–131,2011.
[31]C.
Papamanthou,E.
Shi,andR.
Tamassia,"Signaturesofcorrectcomputation.
"CryptologyePrintArchive,Report2011/587,2011.
http://eprint.
iacr.
org/.
[32]D.
FioreandR.
Gennaro,"Publiclyveriabledelegationoflargepolynomialsandmatrixcomputations,withapplications,"inProc.
ofACMCCS,pp.
501–512,2012.
[33]D.
Boneh,X.
Boyen,andE.
-J.
Goh,"Hierarchicalidentitybasedencryptionwithconstantsizeciphertext,"inProc.
ofEUROCRYPT,pp.
440–456,2005.
[34]J.
KatzandY.
Lindell,IntroductiontoModernCryptography.
ChapmanandHall/CRCPress,2007.
[35]B.
H.
Bloom,"Space/timetrade-offsinhashcodingwithallowableerrors,"Commun.
ACM,vol.
13,pp.
422–426,July1970.
[36]R.
Canetti,S.
Halevi,andJ.
Katz,"Chosen-ciphertextsecurityfromidentity-basedencryption,"inEUROCRYPT,pp.
207–222,2004.
[37]E.
Shen,E.
Shi,andB.
Waters,"Predicateprivacyinencryptionsystems,"inProc.
ofTCC,pp.
457–473,2009.
[38]"Thejavapairingbasedcryptographylibrary.
http://gas.
dia.
unisa.
it/projects/jpbc/.
"APPENDIXAPROOFOFTHEOREM1Proof1:Weshowthatifthereisapolynomial-timead-versaryAthatwinstheSCKAgamewithadvantage,thenthereisachallengeralgorithmthatsolvestheDLproblemwithadvantage/2.
GivenaDLinstance(g,h,f,fr1,gr2,Q),whereg,f,h,Q←Gandr1,r2←Zp,thechallengersimulatestheSCKAgameasfollows.
Setup:Thechallengersetsga=handgc=fwhereaandcareunknown,selectsd←Zpandcomputesgb=fd=gcdbyimplicitlydeningb=cd.
LetH2beanone-wayhashfunctionandpm=(e,g,p,h,fd,f)andmk=(d).
AselectsanattributesetAttsandgivesittothechallenger.
TherandomoracleOH1(atj)isdenedasfollows:Ifatjhasnotbeenqueriedbefore,–ifatj∈Atts,selectβj←Zp,add(atj,αj=0,βj)toOH1,andreturngβj;–otherwise,selectαj,βj←Zp,add(atj,αj,βj)toOH1,andreturnfαjgβj.
Ifatjhasbeenqueriedbefore,retrieve(αj,βj)fromOH1andreturnfαjgβj.
Phase1:Acanadaptivelyquerythefollowingoraclesforpolynomially-manytimesandthechallengerkeepsakeywordlistLkw,whichisemptyinitially.
OKeyGen(T):AgivesanaccesstreeTtothechallenger.
IfF(Atts,T)=1,thenthechallengeraborts;otherwise,thechallengergeneratesattributesasfollows.
Denethefollowingtwoprocedurestodeterminethepoly-nomialforeachnodeofT:PolySat(Tv,Atts,λv):Givensecretλv,thisproceduredeterminesthepolynomialforeachnodeofTvrootedatvwhenF(Atts,Tv)=1.
Itworksasfollows:Supposethethresholdvalueofnodeviskv,itsetsqv(0)=λvandpickskv1coefcientsrandomlytoxthepoly-nomialqv.
Foreachchildnodev′ofv,recursivelycallPolySat(Tv′,Atts,λv′)whereλv′=qv(Index(v′)).
PolyUnsat(Tv,Atts,gλv):Givenelementgλv∈Gwherethesecretλvisunknown,thisproceduredeter-minesthepolynomialforeachnodeofTvrootedatvwhenF(Atts,Tv)=0asfollows.
Supposethethresholdvalueofthenodeviskv.
LetVbetheemptyset.
Foreachchildnodev′ofv,ifF(Atts,Tv′)=1,thensetV=V{v′}.
BecauseF(Atts,Tv)=0,then|V|Foreachnodev′∈V,itselectsλv′←Zp,andsetsqv(Index(v′))=λv′.
Finallyitxestheremainingkv|V|pointsofqvrandomlytodeneqvandmakesgqv(0)=gλv.
Foreachchildnodev′ofv,–ifF(Atts,Tv′)=1,thenrunPolySat(Tv′,Atts,qv(Index(v′)),whereqv(Index(v′))isknowntothechallenger;–otherwise,callPolyUnsat(Tv′,Atts,gλv′),wheregλv′=gqv(Index(v′)isknowntothechallenger.
Withtheabovetwoprocedures,thechallengerrunsPolyUnsat(T,Atts,ga),byimplicitlydeningqroot(0)=a.
Thenforeachv∈lvs(T),thechallengergetsqv(0)ifatt(v)∈Atts,andgetsgqv(0)otherwise.
Becausecqv(0)isthesecretshareofac,duetothelinearproperty,thechallengergeneratescredentialsforeachv∈lvs(T)asfollows:Ifatt(v)=atjforsomeatj∈Atts:Selectt←Zp,setAv=fqv(0)gβjt=gcqv(0)H1(att(v))tandBv=gt;Ifatt(v)/∈Atts(assumingatt(v)=atj):Selectt′←Zp,setAv=(gqv(0))βjαj(fαjgβj)t′andBv=gqv(0)1αjgt′.
Notethat(Av,Bv)isavalidcredentialbecauseBv=gqv(0)1αjgt′=gt′qv(0)αjAv=gqv(0)βjαj(fαjgβj)t′=fqv(0)(fαjgβj)qv(0)αj(fαjgβj)t′=fqv(0)(fαjgβj)t′qv(0)αj=gcqv(0)H1(att(v))t′qv(0)αjbyimplicitlylettingt=t′qv(0)αj.
NotealsothatAcannotconstructAvandBvwithoutknowingαj,βj.
Eventually,thechallengerreturnssk={(Av,Bv)|v∈lvs(T)}toA.
OTokenGen(T,w):ThechallengerrunsOKeyGen(T)togetsk=(T,{Av,Bv|v∈lvs(T)}),computestk←TokenGen(sk,w),andreturnstktoA.
IfF(Atts,T)=1,thechallengeraddswtothekeywordListLkw.
Challengephase:Achoosestwokeywordsw0andw1ofequallength,suchthatw0,w1/∈Lkw.
Thechallengeroutputscphas:Selectλ←{0,1}.
Foreachatj∈Atts,setWj=(gr2)βj.
SetW′=fr1,W=Q(fr1)dH2(wλ),andW0=gr2.
Setcph=(Atts,W′,W,W0,{Wj|atj∈Atts})andreturncphtoA.
WenotethatifQ=hr1+r2,thencphisindeedalegitimateciphertextforkeywordwλ.
ThereasonisthatW′=fr1=gcr1,W=Qfr1dH2(wλ)=Qgr1cdH2(wλ)=ga(r1+r2)gbr1H2(wλ),W0=gr2,andforatj∈Atts,Wj=(gr2)βj=H1(atj)r2.
Phase2:AcontinuestoquerytheoraclesasinPhase1.
Theonlyrestrictionisthat(T,w0)and(T,w1)cannotbetheinputtoOTokenGenifF(Atts,T)=1.
Guess:Finally,Aoutputsabitλ′andgivesittothechal-lenger.
Ifλ′=λ,thenthechallengeroutputsQ=hr1+r2;otherwise,itoutputsQ=hr1+r2.
Thiscompletesthesimulation.
Inthechallengephase,ifQ=hr1+r2,thencphisavalidciphertextofwλ,sotheprobabilityofAoutputtingλ=λ′is12+.
IfQisanelementrandomlyselectedfromG,thencphisnotavalidciphertextofwλ.
TheprobabilityofAoutputtingλ=λ′is12sinceWisanrandomelementinG.
Therefore,theprobabilityofthechallengercorrectlyguessingQ=hr1+r2withtheDLinstance(g,h,f,fr1,gr2,Q)is12(12++12)=12+2.
Thatis,thechallengersolvestheDLproblemwithadvantage/2ifAwinstheSCKAgamewithanadvantage.
APPENDIXBPROOFOFTHEOREM2Proof2:Weconstructachallengerthatexploitsthekeywordsecrecygameasfollows:Setup:Thechallengerselectsa,b,c←Zp,f←G.
LetH2beanone-wayhashfunctionandpm=(e,g,ga,gb,gc,f)andmk=(a,b,c).
TherandomoracleOH1(atj)issimulatedasfollows:Ifatjhasnotbeenqueriedbefore,thechallengerselectsαj←Zp,adds(atj,αj)toOH1,andreturnsgαj;otherwise,thechallengerretrievesαjfromOH1andreturnsgαj.
Phase1:Acanadaptivelyquerythefollowingoraclesforpolynomially-manytimes.
OKeyGen(T):Thechallengergeneratessk←KeyGen(T,mk)andreturnssktoA.
ItaddsTtothelistLKeyGen,whichisinitiallyempty.
OTokenGen(T,w):ThechallengerrunsOKeyGen(T)toob-tainsk=(T,{Av,Bv|v∈lvs(T)}),computestk←TokenGen(sk,w),andreturnstktoA.
ChallengePhase:AselectsanattributesetAtts.
Thechallengerchoosesanaccesscontrolpolicythatisrepre-sentedasTsuchthatF(Atts,T)=1,computessk←KeyGen(mk,T).
BytakingasinputAttsandsk,itselectswfromkeywordspaceuniformlyatrandom,andcomputescphandtkwithEncandTokenGen.
Attsshouldsatisfytherequirementdenedinthekeywordsecrecygame.
Guess:Finally,Aoutputsakeywordw′andgivesittothechallenger.
Thechallengercomputescph′←Enc(Atts,w′)andifSearch(tk,cph′)=1,thenAwinsthegame.
Thisnishesthesimulation.
SupposeAhasalreadyat-temptedqdistinctkeywordsbeforeoutputtingw′,wecanseethattheprobabilityofAwinningthekeywordsecrecygameisatmost1|M|q+.
Thisisbecausethesizeoftheremainingkeywordspaceis|M|q,andastheH2isanonewaysecurehashfunction,meaningderivingwfromH2(w)isatmostanegligibleprobability.
Therefore,givenqdistinctkeywordsAhasattempted,theprobabilityofAwinningthekeywordsecrecygameisatmost1|M|q+.
Thus,ourschemeachieveskeywordsecrecyasinDenition3.
APPENDIXCPROOFOFTHEOREM3ONCP-ABKSProof3:WeshowthattheCP-ABEschemeisselectivelysecureagainstchosen-keywordattackinthegenericbilineargroupmodel,whereH1ismodeledasarandomoracleandH2isaone-wayhashfunction.
IntheSCKAgame,Aattemptstodistinguishga(r1+r2)gbr1H2(w0)fromga(r1+r2)gbr1H2(w1).
Givenθ←Zp,theprobabilityofdistinguishingga(r1+r2)gbr1H2(w0)fromgθisequaltothatofdistinguishinggθfromga(r1+r2)gbr1H2(w1).
Therefore,ifAhasadvantageinbreakingtheSCKAgame,thenithasadvantage/2indistinguishingga(r1+r2)gbr1H2(w0)fromgθ.
Thus,letusconsideramodiedgamewhereAcandistinguishga(r1+r2)fromgθ.
ThemodiedSCKAgameisdescribedasfollows:Setup:Thechallengerchoosesa,b,c←Zpandsendspublicparameters(e,g,p,ga,gb,gc)toA.
AchoosesanaccesstreeT,whichissenttothechallenger.
H1(atj)issimulatedasfollows:Ifatjhasnotbeenqueriedbefore,thechallengerchoosesαj←Zp,adds(atj,αj)toOH1andreturnsgαj;otherwisethechallengerreturnsgαjbyretrievingαjfromOH1.
Phase1:AcanqueryOKeyGenandOTokenGenasfollows:ar(t)js(ac+r(t))/bcr1br(t)+αjr(t)js(r(t)j)qv(0)c(ac+r(t))/bs(r(t)+αjr(t)j)αjqv(0)αjcss(a+bH2(w))br2TABLEIIIPOSSIBLETERMSFORQUERYINGGROUPORACLEGTOKeyGen(Atts):Thechallengerselectsr(t)←Zpandcom-putesA=g(ac+r(t))/b.
Foreachattributeatj∈Atts,thechallengerchoosesr(t)j←Zp,computesAj=gr(t)gαjr(t)jandBj=gr(t)j,andreturns(Atts,A,{(Aj,Bj)|atj∈Atts}).
OTokenGen(Atts,w):ThechallengerqueriesOKeyGen(Atts)togetsk=(Atts,A,{(Aj,Bj)|atj∈Atts})andreturnstk=(Atts,tok1,tok2,tok3,{(A′j,B′j)|atj∈Atts})wheretok1=(gagbH2(w))s,tok2=gcs,tok3=As,A′j=AsjandB′j=Bsjbyselectings←Zp.
IfF(Atts,T)=1,thechallengeraddswtothekeywordListLkw.
Challengephase:Giventwokeywordsw0,w1ofequallengthwherew0,w1/∈Lkw,thechallengerchoosesr1,r2←Zp,andcomputessecretsharesofr2foreachleavesinT.
Thechallengerselectsλ←{0,1}.
Ifλ=0,itoutputsW=gcr1,W0=gθ,W′=gbr2,{(Wv=gqv(0),Dv=gαjqv(0))|v∈lvs(T),att(v)=atj}byselectingθ∈Zp;otherwiseitoutputsW=gcr1,W0=ga(r1+r2),W′=gbr2,{(Wv=gqv(0),Dv=gαjqv(0))|v∈lvs(T),att(v)=atj}.
Phase2:ThisisthesameasintheSCKAgame.
WecanseethatifAcanconstructe(g,g)δa(r1+r2)forsomegδthatcanbecomposedfromtheoracleoutputshehasalreadyqueried,thenAcanuseittodistinguishgθfromga(r1+r2).
Therefore,weneedtoshowthatAcanconstructe(g,g)δa(r1+r2)forsomegδwithanegligibleprobability.
Thatis,Acannotgainnon-negligibleadvantageintheSCKAgame.
Inthegenericgroupmodel,ψ0andψ1arerandominjectivemapsfromZpintoasetofp3elements.
ThentheprobabilityofAguessinganelementintheimageofψ0andψ1isnegligible.
RecallthatG={ψ0(x)|x∈Zp}andGT={ψ1(x)|x∈Zp}.
Hence,letusconsidertheprobabilityofAconstructinge(g,g)δa(r1+r2)forsomeδ∈Zpfromtheoracleoutputshehasqueried.
WelistalltermsthatcanbequeriedtothegrouporacleGTinTableIII.
Letusconsiderhowtoconstructe(g,g)δa(r1+r2)forsomeδ.
Becauser1onlyappearsinthetermcr1,δshouldcontaincinordertoconstructe(g,g)δa(r1+r2).
Thatis,letδ=δ′cforsomeδ′andAwishestoconstructe(g,g)δ′ac(r1+r2).
Therefore,Aneedstoconstructδ′acr2,whichwillusetermsbr2and(ac+r(t))/b.
Because(br2)(ac+r(t))/b=acr2+r(t)r2,Aneedstocancelr(t)r2,whichneedstousethetermsαj,r(t)+αjr(t)j,qv(0)andαjqv(0)becauseqv(0)isthesecretshareofr2accordingtoT.
However,itisimpossibletoconstructr(t)r2withthesetermsbecauser(t)r2onlycanbereconstructediftheattributescorrespondingtor(t)jofr(t)+αjr(t)jsatisestheaccesstreeT.
Therefore,wecanconcludethatAgainsanegligibleadvantageinthemodiedgame,whichmeansthatAgainsanegligibleadvantageintheSCKAgame.
Thiscompletestheproof.
APPENDIXDPROOFSOFTHEOREM5,THEOREM6,THEOREM7ANDTHEOREM8ONVABKSA.
ProofofTheorem5onVABKSProof4:Weshowthatifthereexistsapolynomial-timealgorithmAbreaksVABKS'sdatasecrecywiththeadvantageρ,thenwecanbreakeitherCPAsecurityforABEorCPAsecurityforSEwiththeadvantageρn2wherenisthenumberofdatalestobeencrypted.
ThechallengerproceedstheconventionalCPAsecuritygamewithA.
Inthechallengephase,supposeApresentstwodatacollectionsD0=(KG,MP,FS0={F01,F0n}),D1=(KG,MP,FS1={F11,F1n}),{IEnc}land{I′Enc}n.
Thechallengeselectsλ←{0,1}andencryptsFSλwiththeABEand{I′Enc}n.
NowletusconsidertheadvantageofAcorrectlyguess-ingλ.
Asweknow,giventwomessages,theadvantageofdistinguishingwhichmessagewasencryptedbythehybridencryptionofABEandSEisequal.
Therefore,giventwosetsofdatalesFS0andFS1,iftheadvantageofdistinguishingwhichdatasetwasencryptedisρ,thentheadvantageofdistinguishingwhichdatalewasencryptedisρn2byselectingonedatalefromFS0andonefromFS1.
Therefore,wecanseethatifAbreaksVABKS'sdatase-crecyofwithanon-negligibleadvantageρ,thentheadvantageofbreakingCPAsecurityforABEorCPAsecurityforSEisρn2–anon-negligibleprobability,whichcontractstheassumptionthatABEisCPA-secureandSEisCPA-secure.
B.
ProofofTheorem6onVABKSProof5:Weshowthatifthereexistsapolynomial-timealgorithmAbreakstheselectivesecurityagainstchosen-keywordattackofABKSwiththeadvantageρ,thenwecanbreaktheselectivesecurityagainstchosen-keywordattackgameofABKSwiththeadvantageofρl2,giventhatABEisCPA-secureandHisasecurepseudorandomgenerator.
Thechallengerproceedsselectivesecurityagainstchosen-keywordattackgamewithA.
Inthechallengephase,sup-poseApresentstwodatacollectionsD0=(KG0={KG01,KG0l},MP,FS),and{I′Enc}n.
Thechallengese-lectsλ←{0,1}andencryptsKGwithABKS,andgeneratesBF′i,cphBFiandσiforeachkeywordgroup.
SinceABEisCPA-secureandHisasecurepseudorandomgenerator,theprobabilityofAinferringλviaBF′i,cphBFiisnegligible.
ThenletusconsidertheadvantageofAcorrectlyguessingλfromkeywordciphertexts.
Asweknow,giventwokeywords,theadvantageofdistinguishingwhichkeywordwasencryptedbyABKSisequal.
Therefore,giventwokeywordsetsKG0andKG1,iftheadvantageofdistinguishingwhichkeywordsetwasencryptedisρ,thentheadvantageofdistin-guishingwhichkeywordwasencryptedisρl2byselectingonekeywordfromKG0andonefromKG1.
Therefore,wecanseethatifAbreaksVABKS'sselectivesecurityagainstchosen-keywordattackwithanon-negligibleadvantageρ,thentheadvantageofbreakingABKS'sselectivesecurityagainstchosen-keywordattackisρl2–anon-negligibleprobability,whichcontractstheassumptionthatABKSachieveselectivesecurityagainstchosen-keywordattack,giventhatABEisCPA-secureandHisasecurepseudorandomgenera-tor.
C.
ProofofTheorem7onVABKSProof6:WeshowthatifthereexistspolynomialtimealgorithmAbreakingVABKS'skeywordsecrecy,thenitbreakstheassumptionthatABKSachieveskeywordsecrecy.
SupposeApresentsadatacollectionD=(KG={KG1,KGl},MP,FS),{IEnc}land{I′Enc}n.
Thechal-lengersimulatesthekeywordsecrecygameasinB,wherethekeywordspaceconsistsofkeywordsspeciedbyFS.
WecanseethattheprobabilityofAinferringthekeywordfromasearchtokenandcorrespondingkeywordciphertextisequaltothatofABKS.
Therefore,ifinVABKSAguessesthekeywordfromthesearchtokenandcorrespondingkeywordciphertextwiththeprobabilitymorethan1|M|q+afterguessingqdistinctkeywords,thentheprobabilityofguessingthekeywordfromthesearchtokenandkeywordciphertextinABKSismorethan1|M|q+afterguessingqdistinctkeywords,whichcontractstheassumptionthatABKSachieveskeywordsecrecy.
D.
ProofofTheorem8onVABKSProof7:WeshowthatundertheassumptionsthatSigisunforgeable,anypolynomial-timeadversaryApresentsanincorrectsearchresultandsucceedsinthevericationwithnegligibleprobability.
Thechallengerproceedstheveriabilitygame,whereAprovidesthekeyword-baseddataD=(KG={KG1,KGl},MP={MP(w)|w∈∪li=1KGi},FS={F1,Fn}),{IEnc}land{I′Enc}n.
Thechallengerruns(Au,Index,Dcph)←BuildIndex({IEnc}l,{I′Enc}n,D),andgives(Au,Index,Dcph)toA.
Inthechallengephase,withwandIEncfromA,thechallengerselectsIKeyGensuchthatF(IKeyGen,IEnc)=1whereIEncisselectedbyA,generatescredentialskwithIKeyGenandreturnstoAasearchtokentkbyrunningtk←TokenGen(sk,w).
Areturns(rslt,proof)tothechallenger.
Supposethat(rslt,proof)succeedsintheverication.
Thatis,1←Verify(sk,w,tk,rslt,proof).
LetusconsidertheprobabilityofAcheatingwithincorrectsearchresult.
First,weclaimthattheglobalsignatureσandrandomkeywordciphertextscphBF1cphBFlareincludedinproofwithoutbeingmanipulated;otherwisewecanbreaktheun-forgeabilityofSig.
Second,letusconsiderthesearchresultwithineachgroupwithrespecttoaccesscontrolpolicies,i.
e.
i=1,l:Ifthereexistsnokeywordciphertextmatchedthesearchtokentk,thenweclaimthatAcannotcheatthechal-lengerwithsomekeywordciphertextanddataciphertextsinordertomakeVABKS.
Verifyoutput1.
ThereasonisthatAcannotforgeakeywordsignatureσwforthekeywordciphertextanddataciphertexts;otherwise,wecanbreaktheunforgeabilityofSig.
Ifthereexistsakeywordciphertextmatchedthesearchto-kentk,thenweclaimthatAcannotcheatthechallengerwithanullsearchresultinordertomakeVABKS.
Verifyoutput1.
SupposeAreturnsanullresultandtheproof(BF′i,cphBFi,σBFi).
SinceBF′icannotbemanipulatedduetoσBFi,theunmaskedbloomlterindicatesthatwisamemberwithinthegroup.
Thechallengerdownloadscphw1cphw|KGi|andσiwithoutbeingmanipulated;otherwisewebreaktheSig'sunforgeability.
Thenthechallengercanconductthesearchoperationwitheachkeywordciphertext,andVABKS.
Verifywilloutput0.
Thatis,ifthereexistskeywordciphertextmatchedthesearchtoken,Areturnsanullresult,thenitcannotmakeVABKS.
Verifyoutput1.
Tosumup,inordertomakeVABKS.
Verifyoutput1,Ahastofaithfullyexecutesearchoperationsandreturnthesearchresulthonestly;otherwise,wewillbreakSig'sunforgeability.