delegation5555tk

AuthorizedKeywordSearchonEncryptedDataJieShi1,2,JunzuoLai2,,YingjiuLi1,RobertH.
Deng1,andJianWeng21SingaporeManagementUniversity,Singapore{jieshi,yjli,robertdeng}@smu.
edu.
sg2JinanUniversity,China{laijunzuo,cryptjweng}@gmail.
comAbstract.
Cloudcomputinghasdrawnmuchattentionfromresearchandindustryinrecentyears.
Plentyofenterprisesandindividualsareoutsourcingtheirdatatocloudservers.
Asthosedatamaycontainsen-sitiveinformation,itshouldbeencryptedbeforeoutsourcedtocloudservers.
Inordertoensurethatonlyauthorizeduserscansearchandfurtheraccesstheencrypteddata,twoimportantcapabilitiesmustbesupported:keywordsearchandaccesscontrol.
Recently,rigorouseortshavebeenmadeoneitherkeywordsearchoraccesscontroloveren-crypteddata.
However,tothebestofourknowledge,thereisnoencryp-tionschemesupportingbothcapabilitiesinapublic-keyscenariosofar.
Inthispaper,weproposeanauthorizedsearchablepublic-keyencryptionschemesupportingexpressivesearchcapabilityandproveitfullysecureinthestandardmodel.
Keywords:AuthorizedSearchablePublic-KeyEncryption,Attribute-BasedEncryption,Public-KeyEncryptionwithKeywordSearch,Public-KeyEncryption.
1IntroductionRecently,asanewcommercialmodel,cloudcomputinghasattractedmuchat-tentionfrombothacademiaandindustry.
Amajoradvantageofcloudcomput-ingisthatitsuppliesvirtuallyunlimitedstoragecapabilitiesandelasticresourceprovisioning[1].
Inordertoreducethecapitalandoperationalexpendituresforhardwareandsoftware,plentyofITenterprisesandindividualsareoutsourcingtheirdatatocloudserversinsteadofbuildingandmaintainingtheirowndatacenters[2].
Despiteclearbenetsprovidedbycloudcomputing,therearemanyimpedi-mentstoitswidespreadadoption.
Datasecurityandprivacyconcernsareproba-blythebiggestchallenges.
Asoutsourceddatamaycontainmuchsensitive/privateinformation,suchasPersonalHealthRecords(PHRs),personalphotosandbusi-nessdocuments,somecloudserversorunauthorizedusersaremotivatedtoaccessandderivesuchsensitive/privateinformation.
Withoutaddressingsuchconcerns,usersmayhesitatetooutsourcetheirdatatocloudservers.
AsitisshowninmanyCorrespondingauthor.
M.
KutylowskiandJ.
Vaidya(Eds.
):ESORICS2014,PartI,LNCS8712,pp.
419–435,2014.
cSpringerInternationalPublishingSwitzerland2014420J.
Shietal.
recentworks[3,2,4],dataencryptionisappliedonusers'databeforeoutsourcingsoastoaddressthesecurityandprivacyconcerns.
Whiledocumentsareencryptedandoutsourcedtocloudservers,twoimportantcapabilitiesshouldbesupported:keywordsearchandaccesscontrol.
Thekeywordsearchcapabilityfacilitatesdatauserstoaccessencrypteddataasitenablesquicklocationofrequireddatabasedonkeywords.
Theaccesscontrolcapabilityallowsdataownerstosharetheirinformationwithrestrictedusersaccordingtotheac-cesscontrolpoliciesassociatedwiththeirencrypteddata.
Intheliterature,muchworkhasbeendoneoneitherkeywordsearchoraccesscontroloverencrypteddata.
However,norigorouseorthasbeendedicatedonsupportingbothkeywordsearchandaccesscontrolatthesametime,whichmeansthatonlyauthorizedusersareallowedtoprocesskeywordsearchandfurtheraccessencrypteddata.
Wecallitauthorizedsearchableencryptionifanencryptionschemeenablesautho-rizedusersonlytoperformkeywordsearch.
Manyreal-worldapplicationsdemandsuchauthorizedsearchableencryption.
OneexampleisthecloudstoragesysteminhealthcareasitisshowninFigure1.
Inthissystem,anypatient(i.
e.
dataowner)outsourceshis/hermedicalrecordstoacloudserversoastosharewithauthorizeduserssuchashospitaldoctors.
Assumingthatthemedicalrecordsaresensitive,theyareencryptedbeforeoutsourcedtothecloud.
Theencrypteddatashouldsup-portbothkeywordsearchandaccesscontrolinthisscenario.
Inparticular,dataowner1Johnoutsourcesanencryptedmedicalrecordtothecloudwithbothkey-wordsandanaccesspolicy.
Thekeywordsspecifythefeaturesabouttheencrypteddatawhichcanbeusedinanyauthorizedusers'queries,whiletheaccesspolicyspecieswhoaretheauthorizedusers(i.
e.
,acardiologistinHospitalAorapatientwithsocialsecuritynumber110-222-1234).
Sincebothkeywordsandaccesspol-icyassociatedwithamedicalrecordcontainsensitive/privateinformation,theyshouldbehiddenfromthecloudserviceprovideroranyunauthorizedusers,justasthemedicalrecorditself.
Everyuserinthissystemisassociatedwithasetofattributes;forexample,theattributesofuser1inFigure1includehername,hersocialsecuritynumber,heraliation,andheroccupation.
Whenauserintendstoobtaincertaininformationfromthecloudserver,theusersubmitsanauthorizedtokenconstructedbyanauthorityaccordingtotheuser'skeywordsqueryandtheuser'sattributes.
Thequerytokenenablesthecloudservertolocateallmedicalrecordssuchthatthekeywordsofthemedicalrecordssatisfytheuser'squeryandtheattributesoftheusermeettheaccesspolicyofthemedicalrecords.
Inthispaper,wefocusonconstructinganauthorizedsearchableencryptionschemeinapublic-keyscenario,whichwecallauthorizedsearchablepublic-keyencryption(AS-PKE).
ItischallengingtodesignanAS-PKEschemesupport-ingbothexpressivesearchcapabilityandbeingfullysecureinthestandardmodel.
Intheliterature,thereexisttwokindsofencryptionschemesclosetoAS-PKE,whicharetheattribute-basedencryptionandthepublic-keyencryp-tionwithkeywordsearch.
First,theattribute-basedencryption(ABE)wasin-troducedbySahaiandWaters[5]andfurtherdevelopedintotwocomplimentaryforms:KP-ABE[6,7]andCP-ABE[8,9].
TherealsoexistmanysolutionsinABEwithhiddenaccessstructures,includingpredicateencryption[10]andCP-ABEAuthorizedKeywordSearchonEncryptedData421DataOwner1DataOwner2DataOwnerm.
.
.
.
.
.
QueryUser1QueryUser2QueryUsern.
.
.
.
.
.
Name:AliceSS#:100-234-5555Affiliation:HospitalAOccupation:CardiologistAttributes:Keywords:Name:JohnAge:25Sex:MaleIllness:cardiopathyProvider:HospitalAORANDSS#:110-222-1234Affiliation:HospitalAOccupation:CardiologistAccessPolicy:Fig.
1.
Anexampleofcloudstoragesystemarchitecturewithhiddenaccessstructures[11].
Second,thepublic-keyencryptionwithkey-wordsearch(PEKS)wasproposedbyBonehetal.
[12],whichsupportsequalityqueriesonly.
Later,Parketal.
proposedthenotionofpublickeyencryptionwithconjunctivekeywordsearch[13]andKatzetal.
proposedthenotionofinner-productpredicateencryption[10],whichcanbeextendedtoconstructpublickeyencryptionwithdisjunctivekeywordsearch.
NeitherABEnorPEKSsatis-estherequirementsofAS-PKE;inotherwords,theydonotsupportkeywordsearchandaccesscontrolatthesametime.
SimplycombiningABEandPEKSschemescannotachieveAS-PKEtoo,asinAS-PKEbothkeywordsandaccesscontrolpoliciesarerequiredtobehiddenandexpressivesearchonencrypteddataisrequiredtobesupported.
1.
1OurContributionIn[11],Laietal.
proposedanewmodelofCP-ABEwithpartiallyhiddenaccessstructures.
Inthismodel,eachattributeconsistsoftwoparts:attributenameanditsvalue.
Intheaccesspolicyassociatedwithaciphertext,allattributevaluesarehidden,whiletheotherinformation,suchasattributenames,abouttheaccessstructureispublic.
TakingtheaccesspolicyinFigure1asanexample,thepolicyispublishedinthefollowingformatinLaietal.
'smodel:SS#:OR(Aliation:ANDOccupation:)422J.
Shietal.
Fig.
2.
Anaccessstructure(a)andthecorrespondingpartiallyhiddenaccessstructure(b)Notethatallattributevalues,suchas"110-222-1234","HospitalA"and"Car-diologist",arehidden.
Figure2showsgraphicallythisexampleofapartiallyhiddenaccessstructure.
BasedontheCP-ABEschemewithpartiallyhiddenaccessstructuregivenin[11]andtheKP-ABEschemeproposedin[7],wedesignaexibleandexpressiveconstructionasanAS-PKEscheme,andprovethatitisfullysecureinthestandardmodel.
TheproposedAS-PKEschemecanbeconsideredasavariantofdual-policyABE[14]inwhichtheobjectattributesandthesubjectaccesspolicyarebothhiddenandtheschemeisfullysecureinthestandardmodel.
Inotherwords,theproposedAS-PKEimpliesafullysecuredual-policyABEscheme.
1.
2RelatedWorkInthissection,webrieyreviewtherelatedworksintheareasofABE,KP-ABE,CP-ABE,PEKS,andPE(PredicateEncryption).
Attribute-BasedEncryption(ABE).
TheconceptofABEwasrstproposedbySahaiandWatersasanapplicationoffuzzyidentity-basedencryption(IBE)scheme[5],wherebothciphertextandsecretkeyarelabeledwithsetsofde-scriptiveattributes.
Thedecryptionofaciphertextisenabledifandonlyifthecardinalityoftheintersectionoftheselabeledattributesexceedsacertainthreshold.
KeyPolicyAttribute-BasedEncryption(KP-ABE).
TwocomplimentaryformsofABE—KP-ABEandCP-ABE—wereformulatedbyGoyaletal.
[6].
InaCP-ABEscheme,eachciphertextisassociatedwithanaccessstructurewhileeachdecryptionkeyisassociatedwithasetofattributes.
Reversely,inaKP-ABEscheme,eachdecryptionkeyisassociatedwithanaccessstructurewhileeachciphertextisassociatedwithasetofattributes.
Generally,aKP-ABEschemecanbetransformedintoaCP-ABEusingthemethodproposedin[15].
WhiletheKP-ABEschemeproposedbyGoyaletal.
[6]supportsmonotonicaccessstructuresonly,Ostrovskyetal.
[16]presentedaKP-ABEsystemsupportingmoreexibleaccesscontrolpolicies—non-monotoneaccessstructures.
CiphertextPolicyAttribute-BasedEncryption(CP-ABE).
Bethencourtetal.
proposedtherstCP-ABEscheme[8],whichwasproventobesecureundertheAuthorizedKeywordSearchonEncryptedData423genericgroupmode.
Later,CheungandNewportpresentedaCP-ABEschemethatissecureunderthestandardmodel[17].
However,theaccessstructuresinthisschemearerestrictedtoconjunctionsofdierentattributes.
Recently,se-cureandexpressiveCP-ABEschemeswereproposedin[9,7].
Inordertohideaccessstructures,Nishideetal.
introducedtheconceptofCP-ABEwithpar-tiallyhiddenaccessstructures[18].
Recently,Laietal.
proposedafullysecure(cf.
selectivelysecure)CP-ABEschemewithpartiallyhiddenaccessstructures[19];however,theschemeonlysupportsrestrictedaccessstructureasin[18].
Later,Laietal.
proposedafullysecureCP-ABEschemewithpartiallyhiddenaccessstructures[11]thatcanbeexpressedasanLSSSwhichismoreexibleandexpressivethanthepreviouswork[18].
PredicateEncryption(PE).
Predicateencryptioncanbeconsideredasattribute-basedencryptionsupportingattribute-hiding.
Katzetal.
introducedtheconceptofPEanddesignedtherstinner-productPE[10].
ShiandWaterspresentedadelegationmechanismforaclassofPE[20];later,OkamotaandTakashimapresenteda(hierarchical)delegationmechanismforaninner-productPEscheme[21].
Shenetal.
introducedanewsecuritynotionofPEcalledpredicateprivacyandalsoproposedasymmetric-keyinner-productPE,whichachievesbothplain-textprivacyandpredicateprivacy[22].
However,theseschemeswereproventobeselectivelysecureonly.
Therstfullysecureinner-productPEwasproposedbyLwekoetal.
[7].
OkamotaandTakashimapresentedafullysecurePEforawideclassofadmissiblepredicates,whicharespeciedusingnon-monotoneaccessstructurescombinedwithinner-productpredicates[23].
Public-keyEncryptionwithKeywordSearch(PEKS).
Bonehetal.
initiatedtheresearchonPEKSandprovidedaspecicscheme,whichsupportsequalityqueryonly[12].
Parketal.
proposedthenotionofpublickeyencryptionwithconjunc-tivekeywordsearch[13];HwanandLeemadeanimprovementonthesizesofciphertextandprivatekey,andextendedtheschemeinamulti-usersetting[24].
BonehandWaterspresentedageneralframeworkforanalyzingandconstructingseveralschemesthatsupportarbitraryconjunctions[25].
Katzetal.
proposedthenotionofinner-productpredicateencryption(IPE),whichcanbeextendedtoconstructpublickeyencryptionwithdisjunctivekeywordsearch[10].
How-ever,asshownin[10],theresultingsolutionsuersfromasuperpolynomialblowupinciphertextsizeandsearch-tokenkeysize.
Others.
Recently,Lietal.
[2]presentedaframeworkforauthorizedprivatekey-wordsearch(APKS)overencryptedclouddataandproposedtwoschemesforAPKS.
Intheirproposedframework,everydataowner'strustisdelegatedtoatrustedauthorityand/orseverallocaltrustedauthoritieswhoareinchargeofdeterminingusers'searchprivileges.
Basedonthisframework,theyemployedthehierarchicalpredicateencryptiontoconstructAPKS.
However,thereexistsasignicantdierencebetweentheAPKSandourAS-PKE:theaccesscon-trolpoliciesaredenedandmaintainedbytrustedauthoritiesinAPKSscheme;however,inourAS-PKEscheme,theaccesscontrolpoliciesaredenedbydataownersthemselves.
Therefore,ourAS-PKEschemeismoregeneralandcanbe424J.
Shietal.
usedinmanyapplicationswhichrequireaccesscontrolpoliciestobedenedbydataowners.
In[26],Sunetal.
proposedanattribute-basedkeywordsearchwithne-grainedowner-enforcedsearchauthorizationscheme,whichsupportslimitedauthorizationpolicieswith"AND"gatesandlimitedkeywordquerieswithconjunctivekeywordsonly.
OurAS-PKEschemesupportsmoreexpressiveauthorizationpoliciesandkeywordqueriessupportingarbitraryBooleanformu-las.
In[27],Narayanetal.
combinedPEKSandABEtocreateasecureelectronichealthrecordsystemprovidingbothkeywordsearchandaccesscontrolfunction-alities;however,itdoesnotaddresstheprivacyofaccesscontrolpoliciesasinourwork.
1.
3OrganizationTherestofthepaperisorganizedasfollows.
InSection2,wereviewnecessarystandardnotationsandcryptographicdenitions.
InSection3,wedenethesecuritymodelofAS-PKE,andproposeaconcreteconstructionofAS-PKE.
InSection4,weconcludeourpaper.
2PreliminariesInthispaper,weuses$←StodenotetheoperationofpickinganelementsuniformlyatrandomfromasetS.
LetNbethesetofnaturalnumbers,and1λdenotethestringofλonesifλ∈N.
Letz←A(x,y,denotetheoperationofrunninganalgorithmAwithinputs(x,y,andoutputz.
Afunctionf(λ)isnegligibleifforeveryc>0thereexistsaλcsuchthatf(λ)λc.
2.
1AccessStructuresDenition1(AccessStructure[28]).
Let{P1,Pn}beasetofparties.
AcollectionA2{P1,.
.
.
,Pn}ismonotoneifB,C:ifB∈AandBC,thenC∈A.
Anaccessstructure(respectively,monotoneaccessstructure)isacollection(respectively,monotonecollection)Aofnon-emptysubsetsof{P1,Pn},i.
e.
,A2{P1,.
.
.
,Pn}\{}.
ThesetsinAarecalledauthorizedsets,andthesetsnotinAarecalledunauthorizedsets.
Inourcontext,attributesplaytheroleofparties.
Wefocusonthemonotoneaccessstructuresinthispaper.
However,itispossibleto(ineciently)realizegeneralaccessstructuresusingtheproposedtechniquebytakingthenegationofanattributeasaseparateattribute.
Inwhatfollows,unlessstatedotherwise,theaccessstructuresaremonotoneaccessstructures.
2.
2LinearSecretSharingSchemesWewillmakeuseoflinearsecretsharingschemesinourdesignofAS-PKE.
Thefollowingdenitionisadaptedfromthosegivenin[28].
AuthorizedKeywordSearchonEncryptedData425Denition2.
[LinearSecret-SharingSchemes(LSSS)]AsecretsharingschemeΠoverasetofpartiesPiscalledlinear(overZp)if1.
ThesharesforeachpartyformavectoroverZp.
2.
ThereexistsamatrixAwithrowsandncolumnscalledtheshare-generatingmatrixforΠ.
Foralli=1,theithrowofAislabeledbyapartyρ(i)(ρisafunctionfrom{1,toP).
Whenweconsiderthecolumnvectorv=(s,r2,rn),wheres∈Zpisthesecrettobeshared,andr2,rn∈Zparerandomlychosen,thenAvisthevectorofsharesofthesecretsaccordingtoΠ.
Theshare(Av)ibelongstopartyρ(i).
Itisshownin[28]thateverylinearsecret-sharingschemeaccordingtotheabovedenitionenjoysthelinearreconstructionproperty,denedasfollows.
SupposethatΠisanLSSSforanaccessstructureA.
LetS∈Abeanyauthorizedset,andI{1,bedenedasI={i|ρ(i)∈S}.
Thenthereexistconstants{ωi∈Zp}i∈Isuchthat,if{λi}arevalidsharesofanysecretsaccordingtoΠ,theni∈Iωiλi=s.
LetAidenotetheithrowofA,wehavei∈IωiAi=(1,0,0).
Theseconstants{ωi}canbefoundintimepolynomialinthesizeoftheshare-generationmatrixA[28].
Notethat,forunauthorizedsets,nosuchconstants{ωi}exist.
BooleanFormulas.
Accessstructuresmightalsobedescribedintermsofmonotonicbooleanformulas.
Usingstandardtechniques[28]onecanconvertanymonotonicbooleanformulaintoanLSSSrepresentation.
Whenabooleanformulaisrepresentedasanaccesstreewithleafnodes,itwillresultinanLSSSmatrixofrows.
Detailsonhowtoperformthisconversionrefertotheappendixof[29].
2.
3CompositeOrderBilinearGroupsWeconstructourschemeincompositeorderbilineargroupswhoseorderistheproductoffourdistinctprimes.
Compositeorderbilineargroupswererstintroducedin[30].
LetGbeagroupgenerator,analgorithmtakingasecurityparameter1λasinputandoutputtingatuple(p1,p2,p3,p4,G,GT,e),wherep1,p2,p3,p4aredistinctprimes,GandGTarecyclicgroupsoforderN=p1p2p3p4,ande:G*G→GTisamapsuchthat1.
Bilinear:Forallg,h∈G,anda,b∈ZN,wehavee(ga,hb)=e(g,h)ab;2.
Non-degeneracy:g∈Gsuchthate(g,g)hasorderNinGT.
ItfurtherrequiresthatthegroupoperationinGandGTandthebilinearmapearebothecientlycomputableintimepolynomialinλ.
LetGp1,Gp2,Gp3,andGp4bethesubgroupsofGhavingorderp1,p2,p3,andp4respectively.
Thus,G=Gp1*Gp2*Gp3*Gp4.
Notethatifg1∈Gp1andg2∈Gp2,thene(g1,g2)=1.
Similarrulesholdwhenevereisappliedtoelementsindistinctsubgroups.
Weadoptthefollowingfourcomplexityassumptionsinthispaper,whichwerealsousedin[11,31].
426J.
Shietal.
Assumption1.
GivenagroupgeneratorG,wedenethefollowingdistribu-tion:(p1,p2,p3,p4,G,GT,e)←G(1λ),N=p1p2p3p4,g$←Gp1,X3$←Gp3,X4$←Gp4,D=(G,GT,N,e,g,X3,X4),T1$←Gp1*Gp2,T2$←Gp1.
TheadvantageofanalgorithmAinbreakingAssumption1isdenedasAdv1A=|Pr[A(D,T1)=1]Pr[A(D,T2)=1]|.
Denition3.
wesayGsatisesAssumption1ifforanypolynomialtimealgo-rithmA,Adv1Aisnegligible.
Assumption2.
GivenagroupgeneratorG,wedenethefollowingdistribu-tion:(p1,p2,p3,p4,G,GT,e)←G(1λ),N=p1p2p3p4,g,X1$←Gp1,X2,Y2$←Gp2,X3,Y3$←Gp3,X4$←Gp4,D=(G,GT,N,e,g,X1X2,Y2Y3,X3,X4),T1$←Gp1*Gp2*Gp3,T2$←Gp1*Gp3.
TheadvantageofanalgorithmAinbreakingAssumption2isdenedasAdv2A=|Pr[A(D,T1)=1]Pr[A(D,T2)=1]|.
Denition4.
wesayGsatisesAssumption2ifforanypolynomialtimealgo-rithmA,Adv2Aisnegligible.
Assumption3.
GivenagroupgeneratorG,wedenethefollowingdistribu-tion:(p1,p2,p3,p4,G,GT,e)$←G(1λ),N=p1p2p3p4,s$←ZN,g,h$←Gp1,g2,X2,B2,D2$←Gp2,X3$←Gp3,B4,D4,X4,Z$←Gp4,D=(G,GT,N,e,g,g2,hX2,hZ,gsB2B4,X3,X4),T1=hsD2D4,T2$←Gp1*Gp2*Gp4.
TheadvantageofanalgorithmAinbreakingAssumption3isdenedasAdv3A=|Pr[A(D,T1)=1]Pr[A(D,T2)=1]|.
Denition5.
wesayGsatisesAssumption3ifforanypolynomialtimealgo-rithmA,Adv3Aisnegligible.
AuthorizedKeywordSearchonEncryptedData427Assumption4.
GivenagroupgeneratorG,wedenethefollowingdistribution:(p1,p2,p3,p4,G,GT,e)←G(1λ),N=p1p2p3p4,a,s$←ZN,g$←GP1,g2,X2,Y2,D2$←Gp2X3$←Gp3,X4,Z,Y4,D4$←Gp4D=(G,GT,N,e,g,g2,gaX2,gaZ,gsY2Y4,X3,X4),T1=gasD2D4,T2$←Gp1*Gp2*Gp4.
TheadvantageofanalgorithmAinbreakingAssumption4isdenedasAdv4A=|Pr[A(D,T1)=1]Pr[A(D,T2)=1]|.
Denition6.
wesayGsatisesAssumption4ifforanypolynomialtimealgo-rithmA,Adv4Aisnegligible.
3AuthorizedSearchablePublicKeyEncryptionInauthorizedsearchablepublickeyencryption(AS-PKE),adocumentisiden-tiedbyavectorofmkeywords(o1,om),whereoxisthekeywordofthedocumentinthex-thkeywordeld.
Fornotationalpurpose,letxbethex-thkeywordeld.
Similarly,auserhasnattributes(s1,sn)witheachattributebelongingtoadierentcategory.
Letibetheattributenameofthei-thcategoryattribute.
OurAS-PKEschemesupportsarbitrarymonotonebooleanpredicateforbothaccesspolicyanduserquery.
WeexpressanaccesspolicybyanLSSS(A,ρ,T)overuserattributes,whereAisanls*nmatrix,ρisamapfromeachrowofAtoanattributeeld(i.
e.
,ρisafunctionfrom{1,ls}to{1,n}),Tcanbeparsedinto(tρ(1)tρ(ls))andtρ(i)isthevalueofattributeeldρ(i).
Similarly,weexpressauserquerybyanLSSS(A,ρ,T)overdocumentkey-words,whereAisanlo*mmatrix,ρisamapfromeachrowofAtoakeywordeld(i.
e.
,ρisafunctionfrom{1,lo}to{1,m}),Tcanbeparsedinto(tρ(1)tρ(lo))andtρ(x)isthevalueofkeywordeldρ(x).
BeforepresentingourAS-PKEscheme,wegivesomeintuitionsofourcon-struction.
SupposethatadocumentisencryptedwithasetofkeywordsO=(o1,om)andanaccesspolicy(A,ρ,T),aquerytokenkeyTKP,SisembeddedwithasetofuserattributesS=(s1,sn)andauserqueryP=(A,ρ,T).
TheencrypteddocumentDwillbereturnedifandonlyifthereexistI{1,ls},I{1,lo}andconstants{wi}i∈I,{wx}x∈Isuchthati∈IwiAi=(1,0,0)andsρ(i)=tρ(i)fori∈I,x∈IwxAx=(1,0,0)andoρ(x)=tρ(x)forx∈I,428J.
Shietal.
whereAiandAxdenotethei-throwofAandthex-throwofA,respectively.
WealsosaythatI{1,ls}satises(A,ρ,T)ifthereexistconstants{wi}i∈Isuchthati∈IwiAi=(1,0,0).
ThiscanbeappliedtoI{1,lo}and(A,ρ,T).
WedeneIA,ρandIA,ρasthesetofminimumsubsetsof{1,ls}and{1,lo}thatsatisfy(A,ρ,T)and(A,ρ,T),respectively.
3.
1AuthorizedSearchablePublicKeyEncryptionInAS-PKEscheme,keywordsO=(o1,o2,on)ofadocumentareencryptedunderanaccesspolicyAandcanbesearchedbyanauthorizedquerytoken.
Anauthorizedquerytokenisgeneratedbyauthorityaccordingtoaqueryanduserattributesset.
Anauthorizedsearchablepublickeyencryption(AS-PKE)schemeconsistsofthefollowingfouralgorithms:Setup(1λ).
ThissetupalgorithmtakesinthesecurityparameterλwithoutputofthepublicparametersPKandasecretkeySK.
Encrypt(PK,O=(o1,om),A=(A,ρ,T)).
ThisencryptionalgorithmtakesinthepublicparameterPK,keywordsO=(o1,om),andanaccesspolicyA=(A,ρ,T).
ItoutputsaciphertextCO,A.
GenToken(PK,SK,P,S=(s1,sn)).
ThisalgorithmtakesinthepublickeyPK,thesecretkeySK,auserattributessetS=(s1,sn)andaquerypredicateP.
ItoutputsanauthorizedquerytokenkeyTKP,S.
Test(PK,TKP,S,CO,A).
ThistestalgorithmtakesinthepublickeyPK,anauthorizedquerytokenTKP,S=GenToken(PK,SK,P,S)andaciphtertextCO,A=Encrypt(PK,O,A).
Itoutputs"Yes"ifthekeywordsinOsatisfythepredicateP(i.
e.
,P(O)=1)andtheuserattributesinsetSsatisfytheaccesspolicyA(i.
e.
A(S)=1);andoutputs"No"otherwise.
Correctness.
Thesystemmustsatisfythefollowingcorrectnessproperty:–Let(PK,SK)←Setup(1λ),CO,A←Encrypt(PK,O,A),TKP,S←GenToke(PK,SK,P,S).
IfP(O)=1andA(S)=1,thenTest(PK,TKP,S,CO,A)="Yes";Otherwise,Pr[Test(PK,TKP,S,CO,A)="No"]>1(λ)where(λ)isanegligiblefunction.
3.
2SecurityModelforAS-PKEWedeneasecuritymodelforAS-PKEinthesenseofsemantic-securityusingthefollowinggamebetweenachallengerandanattacker.
Setup.
ThechallengerrunsSetup(1λ)toobtainapublicPKandasecretkeySK.
ItgivesthepublickeyPKtotheadversaryandkeepsSKbyitself.
Queryphase1.
TheadversaryAadaptivelyqueriesthechallengerfortokenkeysforpairsofuserattributessetandpredicate(S,P).
Inresponse,thechallengerrunsTKPi,Si←GenToken(PK,SK,Pi,Si)andgivestheauthorizedquerytokenTKPi,SitoA,for1≤i≤q.
AuthorizedKeywordSearchonEncryptedData429Challenge.
TheadversaryAsubmitstwopairsofkeywordsandaccesspolicy(O0,A0=(A,ρ,T0)),(O1,A1=(A,ρ,T1))subjecttotherestrictionthat,foranypreviousquery(Pi,Si)inphase1,eitherOjdoesnotsatisfyPiorSidoesnotsatisfyAjforallj∈[0,1].
Thechallengerselectsarandombitβ∈{0,1},setsCOβ,Aβ=Encrypt(PK,Oβ,Aβ),andsendsCOβ,Aβtotheadversaryasitschallengeciphertext.
Notethat,theLSSSmatrixAandρarethesameinthetwoaccessstruc-turesprovidedbytheadversary.
InanAS-PKEscheme,onecandistinguishtheciphertextsiftheassociatedaccessstructureshavedierent(A,ρ),since(A,ρ)issentalongwiththeencrypteddocumentexplicitly.
Queryphase2.
TheadversarycontinuestoadaptivelyquerythechallengerfortokenkeyscorrespondingtopredicatesanduserattributesetswiththesamerestrictioninChallengephrase.
Guess.
TheadversaryAoutputsitsguessβ∈{0,1}forβandwinsthegameifβ=β.
Theadvantageoftheadversaryinthisgameisdenedas|Pr[β=β]12|wheretheprobabilityistakenovertherandombitsusedbythechallengerandtheadversary.
Denition7.
AnAS-PKEschemeissecureifallpolynomialtimeadversarieshaveatmostanegligibleadvantageinthissecuritygame.
3.
3ConstructionsOurconstructionofasecureAS-PKEschemeisshownasfollows.
Setup(1λ).
ThesetupalgorithmrstrunsG(1λ)toobtain(p1,p2,p3,p4,G,GT,e)withG=Gp1*Gp2*Gp3*Gp4,whereGandGTarecyclicgroupsofor-derN=p1p2p3p4.
Then,itchoosesrandomelementsg,u,h1,hn,h1,hm∈Gp1,X3∈Gp3,X4,Z,Z,Z0,Z1,Zn,Z1,Zm∈Gp4andrandomnumbera∈ZN.
ThepublickeyispublishedasPK=(N,gZ,gaZ,U=uZ0,{Hi=hi·Zi}1≤i≤n,{Hi=hi·Zi}1≤i≤m,X4).
ThesecretkeyisSK=(g,u,h1,hn,h1,hm,X3,a).
Encrypt(PK,O=(o1,om)∈ZmN,A=(A,ρ,T)).
Aisanls*nmatrix,ρisamapfromeachrowAiofAtoauserattributeρ(i),andT=(tρ(1)tρ(ls)).
Theencryptionalgorithmchoosesarandomvectorv=(s,v2,vn)∈ZnN.
ForeachrowAiofA,itchoosesarandomri∈ZN.
ItalsochoosesrandomelementsZ1,0,{Z1,i}1≤i≤n,{Z1,i}1≤i≤n∈Gp4,{Z2,x}1≤x≤m∈Gp4.
TheciphertextCT=((A,ρ),C,Ci,Di,Cx)iscomputedas:C=(gZ)s·Z1,0=gs·Z1,0,Ci=(gaZ)Ai·v(Utρ(i)Hρ(i))ri·Z1,i=gaAi·v(Utρ(i)Hρ(i))ri·Z1,i,Di=(gZ)ri·Z1,i=gri·Z1,i,Cx=(Uox·Hx)s·Z2,xx,whereZ1,0=Zs·Z1,0,Z1,i=ZAi·v·Z1,i,Z1,i=Zri·Z1,i.
430J.
Shietal.
GenToken(PK,SK,P=(A,ρ,T),S=(s1,sn)).
Aisanlo*mma-trix,ρisamapfromeachrowAxofAtoakeywordeldρ(x),andT=(tρ(1)tρ(lo)).
Thealgorithmrstchoosestworandomnumberst1,t2∈ZNandarandomvectorv=(t2,v2,.
.
.
,vm)∈ZmN.
Italsochoosesrandomel-ementsR0,R0,Rx,Ri,Rx∈Gp3.
TheauthorizedquerytokenkeyTKP,S=((A,ρ),K,L,Ki,Kx,Kx)iscomputedas:K=ga(t1+t2)R0,L=gt1R0,Ki=(usihi)t1RiKx=gaAx·v(utρ(x)hρ(x))txRxx,Kx=gtxRxxTest(PK,TKP,S,CT).
LetCT=((A,ρ),C,Ci,Di,Cx)andTKP,S=((A,ρ),K,L,Ki,Kx,Kx).
ThetestalgorithmrstcalculatesIA,ρfrom(A,ρ),whereIA,ρdenotesthesetofminimumsubsetsof(1,ls)thatsatisesIA,ρ.
ItsimilarlycalculatesIA,ρfrom(A,ρ).
Then,itchecksifthereexistanI∈IA,ρandanI∈IA,ρthatsatisese(C,K)=i∈I(e(Ci,L)e(Ki,Di))ωi·x∈I(e(Kx,C)e(Cx,Kx))ωx(1)wherei∈IωiAi=(1,0,0)andx∈IωxAx=(1,0,0).
IfnoelementsinIA,ρandIA,ρsatisfytheaboveequation,itoutputs"No";otherwise,itoutputs"Yes".
Thecorrectnessisshownasfollows.
SupposeP(O)=1andA(S)=1,i.
e.
thereexistI{1,ls},I{1,lo}andconstants{wi}i∈I,{wx}x∈Isuchthati∈IwiAi=(1,0,0)andsρ(i)=tρ(i)fori∈I,x∈IwxAx=(1,0,0)andoρ(x)=tρ(x)forx∈I.
Then,theleftsideofEquation(1)isequaltoe(C,K)=e(gs·Z1,0,ga(t1+t2)R0)=e(g,g)as(t1+t2)andtherightsideofEquation(1)isequaltoi∈I(e(Ci,L)e(Ki,Di))ωi·x∈I(e(Kx,C)e(Cx,Kx))ωx=i∈I(e(gaAi·v(Utρ(i)Hρ(i))ri·Z1,i,gt1R0)·e((usihi)tiRi,griZ1,i))wi·x∈I(e(gaAx·v(u(t)ρ(x)hρ(x))txRx,gsZ1,0)·e((UoxHx)s·Z2,x,gtxRx))wx=i∈I(e(gaAi·v(utρi·hi)ri,gt1)·e((usihi)t1,gri))wi·x∈I(e(gaAx·v(utρ(x)hρ(x))tx,gs)·e((uox,hx)s,gtx))wx=e(g,g)at1s·e(g,g)at2s=e(g,g)as(t1+t2)whichisequaltotheleftsideofEquation(1).
AuthorizedKeywordSearchonEncryptedData4313.
4SecurityTheorem1.
Ifassumptions1,2,3and4hold,thentheproposedAS-PKEschemeissecure.
Proof.
FollowingtheapproachbyLewkoandWaters[7],wedenetwoadditionalstructures:semi-functionalciphertextsandsemi-functionalkeys.
Theyarenotusedintherealsystem,onlyinourproof.
Semi-functionalCiphertext.
Letg2denoteageneratorofthesubgroupGp2.
Asemi-functionalciphertextiscreatedasfollows.
WerstusetheencryptionalgorithmtoformanormalciphertextCT=((A,ρ),C,Ci,Di,Cx).
Then,wechooserandomexponentc,b∈ZNandrandomvalueszi∈ZNassociatedtouserattributes,randomvaluesγi∈ZNassociatedtorowsiofmatrixA,randomvalueszx∈ZNassociatedtokeywordsandarandomvectorw∈ZnN.
Then,thesemi-functionalciphertextissettobe:(A,ρ),C=C·gc2,Ci=Ci·gAi·w+γizρ(i)2,Di=Di·gγi2i∈[1,n],Cx=Cx·gbzx2x∈[1,m]Itshouldbenotedthatthevaluesziandzxarechosenrandomlyonceandthenxed—thesamevaluesarealsoinvolvedinsemi-functionalkeysasdenedbelow.
Semi-functionalKey.
Asemi-functionalkeywilltakeononeofthefollowingtwoforms.
Inordertocreateasemi-functionalkey,werstusethekeygenerationalgorithmtoformanormalkeyTKP,S=((A,ρ),K,L,Ki,Kx,Kx).
Then,wechooserandomexponentsd,b∈ZN,randomvaluesγx∈ZNassociatedtorowxofmatrixAandarandomvectorw∈ZnN.
Thesemi-functionalkeyoftype1issetas:(A,ρ),K=K·gd2L=L·gb2,Ki=Ki·gbzi2i∈[1,n]Kx=Kx·gAx·w+γxzρ(x)2x∈[1,m],Kx=Kx·gγx2x∈[1,m]Thesemi-functionalkeyoftype2issetas:(A,ρ),K=K·gd2L=L,Ki=Kii∈[1,n]Kx=Kx·gAx·w2x∈[1,m],Kx=Kxx∈[1,m]WewillprovethesecurityoftheproposedschemebasedontheAssumptions1,2,3and4usingahybridargumentoverasequenceofgames.
Therstgame,Gamereal,istherealsecuritygamewheretheciphertextandalltokenkeysarenormal.
Inthenextgame,Game0,alloftokenkeysarenormal,butthechallengeciphertextissemi-functional.
Letqdenotethenumberoftokenkeyqueriesmadebytheattacker.
Forkfrom1toqandlfrom1tom,wedene:432J.
Shietal.
Gamek,1.
Inthisgame,thechallengeciphertextissemi-functional,therstk1tokenkeysaresemi-functionaloftype2,thekthtokenkeyissemi-functionaloftype1,andtheremainingtokenkeysarenormal.
Gamek,2.
Inthisgame,thechallengeciphertextissemi-functional,therstktokenkeysaresemi-functionaloftype2,theremainingkeysarenormal.
Gamekeywordl.
Inthisgame,alltokenkeysaresemi-functionaloftype2,andthechallengeciphertextCT=(C,Ci,Di,Cx)isasemi-functionalciphertextwithC1,ClrandomlychosenfromGp1*Gp2*Gp4.
GameFinal0.
ThisgameisthesameasGamekeywordm.
GameFinal1.
ThisgameisthesameasGameFinal0,exceptthatinthechal-lengeciphertextCiarechosenfromGp1*Gp2*GG4atrandom.
Weprovethatthesegamesareindistinguishableinvelemmas,whicharegivenintheAppendix.
Therefore,weconcludethattheadvantageofthead-versaryinGamereal,i.
e.
therealsecuritygame,isnegligible.
ThiscompletestheproofofTheorem1.
3.
5EciencyLet|G|bethelengthofthebit-representationofagroupinG.
Thesizeofthepublickey,atokenkey,andaciphertextare(n+m+4)|G|,(n+2m+2)|G|,and(2n+m+1)|G|,respectively.
Forapredicate(A,ρ,T),letl1=|IA,ρ|,IA,ρ={I1,Il1}andl2=|I1|Il1|;forapredicate(A,ρ,T),letl1=|IA,ρ|,IA,ρ={I1,Il1}andl2=|I1|Il1|.
Then,thecomputationalcostsofanencryptionandatestare(4n+2m+1)te+(4n+2m+1)tmand(2l1l2+2l2l1+1)tb+(l1l2+2l2l1)tTm+(l1l2+l2l1)tTe,respectively,wheretb,te,tm,tTe,andtTmdenotethecomputationalcostsofbilinearmap,exponen-tiationinG,multiplicationinG,exponentiationinGT,andmultiplicationinGT,respectively.
WenotethattheproposedAS-PKEschememaynotbehighlypracticalduetotheuseofcompositeorderbilineargroups.
Themajorcontribu-tionofthispaperismoreonthetheoreticalaspects,includingtheconceptandthesecuritymodelofAS-PKE,andtherstAS-PKEschemeanditssecurityproof.
Inthefuture,wewillinvestigatehowtoconstructmoreecientAS-PKEschemes.
3.
6DiscussionTheproposedAS-PKEschemeisbasedontheKP-ABEschemeproposedbyLewkoetal.
andtheCP-ABEwithhiddenaccessstructuresproposedbyLaietal.
[7,11].
DierentfromtheKP-ABEscheme[7]whichworksinasmalluniverseofattributes,thekeywordsintheproposedAS-PKEschemehavealargeuniverse(i.
e.
ZN).
TheproposedAS-PKEschemecanbeeasilyextendedtoobtainananonymousdual-policyABEschemewhichimpliesafullysecuredual-policyABEscheme[14].
SimilartotheKP-ABEschemein[7],theproposedAS-PKEschemehasarestrictionthateachkeywordeldcanonlybeusedonceinapredicate,whichisAuthorizedKeywordSearchonEncryptedData433calledone-useAS-PKE.
WecanconstructasecureAS-PKEschemewherethekeywordeldscanbeusedmultipletimes(uptoaconstantnumberofusesxedatsetup)fromaone-useAS-PKEschemebyapplyingthegenerictransformationgiveninLewkoetal.
[7].
4ConclusionThispaperpresentedAS-PKE,apublic-keyencryptionschemesupportingbothkeywordsearchandaccesscontrolcapabilities.
TheAS-PKEschemeiscon-structedbasedontheKP-ABEschemeproposedbyLewkoetal.
[7]andtheCP-ABEwithhiddenaccessstructureproposedbyLaietal.
[11].
Theschemesupportsmonotonebooleanpredicatesandisproventobefullysecureinthestandardmodel.
Acknowledgments.
TheworkofJieShiwassupportedbytheNationalNatu-ralScienceFoundationofChina(No.
61300227),andtheGuangdongProvincialNaturalScienceFoundation(No.
S2013040015711).
TheworkofJunzuoLaiwassupportedbytheNationalNaturalScienceFoundationofChina(Nos.
61300226,61272534),theResearchFundfortheDoctoralProgramofHigherEducationofChina(No.
20134401120017),theGuangdongProvincialNaturalScienceFoun-dation(No.
S2013040014826),andtheFundamentalResearchFundsfortheCen-tralUniversities.
TheworkofJianWengwassupportedbytheNationalScienceFoundationofChina(Nos.
61272413,61133014),theFokYingTungEducationFoundation(No.
131066),theProgramforNewCenturyExcellentTalentsinUniversity(No.
NCET-12-0680),theResearchFundfortheDoctoralProgramofHigherEducationofChina(No.
20134401110011),andtheFoundationforDistinguishedYoungTalentsinHigherEducationofGuangdong(No.
2012LYM0027).
References1.
Armbrust,M.
,Fox,A.
,Grith,R.
,Joseph,A.
D.
,Katz,R.
H.
,Konwinski,A.
,Lee,G.
,Patterson,D.
A.
,Rabkin,A.
,Stoica,I.
,Zaharia,M.
:Aviewofcloudcomputing.
Commun.
ACM53(4),50–58(2010)2.
Li,M.
,Yu,S.
,Cao,N.
,Lou,W.
:Authorizedprivatekeywordsearchoverencrypteddataincloudcomputing.
In:ICDCS,pp.
383–392(2011)3.
Benaloh,J.
,Chase,M.
,Horvitz,E.
,Lauter,K.
:Patientcontrolledencryption:ensuringprivacyofelectronicmedicalrecords.
In:CCSW,pp.
103–114(2009)4.
Li,M.
,Yu,S.
,Ren,K.
,Lou,W.
:Securingpersonalhealthrecordsincloudcomput-ing:Patient-centricandne-graineddataaccesscontrolinmulti-ownersettings.
In:Jajodia,S.
,Zhou,J.
(eds.
)SecureComm2010.
LNICST,vol.
50,pp.
89–106.
Springer,Heidelberg(2010)5.
Sahai,A.
,Waters,B.
:Fuzzyidentity-basedencryption.
In:Cramer,R.
(ed.
)EU-ROCRYPT2005.
LNCS,vol.
3494,pp.
457–473.
Springer,Heidelberg(2005)434J.
Shietal.
6.
Goyal,V.
,Pandey,O.
,Sahai,A.
,Waters,B.
:Attribute-basedencryptionforne-grainedaccesscontrolofencrypteddata.
In:ACMConferenceonComputerandCommunicationsSecurity,pp.
89–98(2006)7.
Lewko,A.
B.
,Okamoto,T.
,Sahai,A.
,Takashima,K.
,Waters,B.
:Fullysecurefunctionalencryption:Attribute-basedencryptionand(hierarchical)innerproductencryption.
In:Gilbert,H.
(ed.
)EUROCRYPT2010.
LNCS,vol.
6110,pp.
62–91.
Springer,Heidelberg(2010)8.
Bethencourt,J.
,Sahai,A.
,Waters,B.
:Ciphertext-policyattribute-basedencryp-tion.
In:IEEESymposiumonSecurityandPrivacy,pp.
321–334(2007)9.
Waters,B.
:Ciphertext-policyattribute-basedencryption:Anexpressive,ecient,andprovablysecurerealization.
In:Catalano,D.
,Fazio,N.
,Gennaro,R.
,Nicolosi,A.
(eds.
)PKC2011.
LNCS,vol.
6571,pp.
53–70.
Springer,Heidelberg(2011)10.
Katz,J.
,Sahai,A.
,Waters,B.
:Predicateencryptionsupportingdisjunctions,poly-nomialequations,andinnerproducts.
In:Smart,N.
P.
(ed.
)EUROCRYPT2008.
LNCS,vol.
4965,pp.
146–162.
Springer,Heidelberg(2008)11.
Lai,J.
,Deng,R.
H.
,Li,Y.
:ExpressiveCP-ABEwithpartiallyhiddenaccessstruc-tures.
In:ASIACCS,pp.
18–19(2012)12.
Boneh,D.
,DiCrescenzo,G.
,Ostrovsky,R.
,Persiano,G.
:Publickeyencryptionwithkeywordsearch.
In:Cachin,C.
,Camenisch,J.
L.
(eds.
)EUROCRYPT2004.
LNCS,vol.
3027,pp.
506–522.
Springer,Heidelberg(2004)13.
Park,D.
J.
,Kim,K.
,Lee,P.
J.
:Publickeyencryptionwithconjunctiveeldkeywordsearch.
In:Lim,C.
H.
,Yung,M.
(eds.
)WISA2004.
LNCS,vol.
3325,pp.
73–86.
Springer,Heidelberg(2005)14.
Attrapadung,N.
,Imai,H.
:Dual-policyattributebasedencryption.
In:Abdalla,M.
,Pointcheval,D.
,Fouque,P.
-A.
,Vergnaud,D.
(eds.
)ACNS2009.
LNCS,vol.
5536,pp.
168–185.
Springer,Heidelberg(2009)15.
Goyal,V.
,Jain,A.
,Pandey,O.
,Sahai,A.
:Boundedciphertextpolicyattributebasedencryption.
In:Aceto,L.
,Damgard,I.
,Goldberg,L.
A.
,Halldorsson,M.
M.
,Ingolfsdottir,A.
,Walukiewicz,I.
(eds.
)ICALP2008,PartII.
LNCS,vol.
5126,pp.
579–591.
Springer,Heidelberg(2008)16.
Ostrovsky,R.
,Sahai,A.
,Waters,B.
:Attribute-basedencryptionwithnon-monotonicaccessstructures.
In:Proceedingsofthe14thACMConferenceonCom-puterandCommunicationsSecurity,pp.
195–203.
ACM(2007)17.
Cheung,L.
,Newport,C.
C.
:ProvablysecureciphertextpolicyABE.
In:ACMCon-ferenceonComputerandCommunicationsSecurity,pp.
456–465(2007)18.
Nishide,T.
,Yoneyama,K.
,Ohta,K.
:Attribute-basedencryptionwithpartiallyhiddenencryptor-speciedaccessstructures.
In:Bellovin,S.
M.
,Gennaro,R.
,Keromytis,A.
D.
,Yung,M.
(eds.
)ACNS2008.
LNCS,vol.
5037,pp.
111–129.
Springer,Heidelberg(2008)19.
Lai,J.
,Deng,R.
H.
,Li,Y.
:Fullysecurecipertext-policyhidingCP-ABE.
In:Bao,F.
,Weng,J.
(eds.
)ISPEC2011.
LNCS,vol.
6672,pp.
24–39.
Springer,Heidelberg(2011)20.
Shi,E.
,Waters,B.
:Delegatingcapabilitiesinpredicateencryptionsystems.
In:Aceto,L.
,Damgard,I.
,Goldberg,L.
A.
,Halldorsson,M.
M.
,Ingolfsdottir,A.
,Walukiewicz,I.
(eds.
)ICALP2008,PartII.
LNCS,vol.
5126,pp.
560–578.
Springer,Heidelberg(2008)21.
Okamoto,T.
,Takashima,K.
:Hierarchicalpredicateencryptionforinner-products.
In:Matsui,M.
(ed.
)ASIACRYPT2009.
LNCS,vol.
5912,pp.
214–231.
Springer,Heidelberg(2009)22.
Shen,E.
,Shi,E.
,Waters,B.
:Predicateprivacyinencryptionsystems.
In:Reingold,O.
(ed.
)TCC2009.
LNCS,vol.
5444,pp.
457–473.
Springer,Heidelberg(2009)AuthorizedKeywordSearchonEncryptedData43523.
Okamoto,T.
,Takashima,K.
:Fullysecurefunctionalencryptionwithgeneralre-lationsfromthedecisionallinearassumption.
In:Rabin,T.
(ed.
)CRYPTO2010.
LNCS,vol.
6223,pp.
191–208.
Springer,Heidelberg(2010)24.
Hwang,Y.
H.
,Lee,P.
J.
:Publickeyencryptionwithconjunctivekeywordsearchanditsextensiontoamulti-usersystem.
In:Takagi,T.
,Okamoto,T.
,Okamoto,E.
,Okamoto,T.
(eds.
)Pairing2007.
LNCS,vol.
4575,pp.
2–22.
Springer,Heidelberg(2007)25.
Boneh,D.
,Waters,B.
:Conjunctive,subset,andrangequeriesonencrypteddata.
In:Vadhan,S.
P.
(ed.
)TCC2007.
LNCS,vol.
4392,pp.
535–554.
Springer,Heidel-berg(2007)26.
Sun,W.
,Yu,S.
,Lou,W.
,Hou,Y.
T.
,Li,H.
:Protectingyourright:Attribute-basedkeywordsearchwithne-grainedowner-enforcedsearchauthorizationinthecloud.
In:INFOCOM(2014)27.
Narayan,S.
,Gagne,M.
,Safavi-Naini,R.
:PrivacypreservingEHRsystemusingattribute-basedinfrastructure.
In:CCSW,pp.
47–52(2010)28.
Beimel,A.
:Secureschemesforsecretsharingandkeydistribution.
PhDthesis,IsraelInstituteofTechnology,Technion,Haifa,Israel(1996)29.
Lewko,A.
B.
,Waters,B.
:Decentralizingattribute-basedencryption.
In:Paterson,K.
G.
(ed.
)EUROCRYPT2011.
LNCS,vol.
6632,pp.
568–588.
Springer,Heidelberg(2011)30.
Boneh,D.
,Goh,E.
-J.
,Nissim,K.
:Evaluating2-DNFformulasonciphertexts.
In:Kilian,J.
(ed.
)TCC2005.
LNCS,vol.
3378,pp.
325–341.
Springer,Heidelberg(2005)31.
Lai,J.
,Zhou,X.
,Deng,R.
H.
,Li,Y.
,Chen,K.
:Expressivesearchonencrypteddata.
In:Proceedingsofthe8thACMSIGSACSymposiumonInformation,Com-puterandCommunicationsSecurity,ASIACCS2013,pp.
243–252.
ACM,NewYork(2013)ALemmasThefollowingvelemmasareusedintheproofofTheorem1.
Theproofofthelemmasisdetailedin(theappendixof)thefullversionofthispaper,whichisaccessibleathttp://www.
mysmu.
edu/faculty/yjli/ASPKE-full.
pdf.
Lemma1.
SupposethatGsatisesAssumption1.
ThenGamerealandGame0arecomputationallyindistinguishable.
Lemma2.
SupposethatGsatisesAssumption2.
ThenGamek1,2andGamek,1arecomputationallyindistinguishable.
Lemma3.
SupposethatGsatisesAssumption2.
ThenGamek,1andGamek,2arecomputationallyindistinguishable.
Lemma4.
SupposethatGsatisesAssumption3.
ThenGamekeywordl1andGamekeywordlarecomputationallyindistinguishable.
Lemma5.
SupposethatGsatisesAssumption4.
ThenGamenal0andGamenal1arecomputationallyindistinguishable.