CP-ABE

Realization

BrentWaters󰀉

UniversityofTexasatAustinbwaters@cs.utexas.edu

Abstract.WepresentanewmethodologyforrealizingCiphertext-PolicyAttributeEncryption(CP-ABE)underconcreteandnoninteractivecryptographicassumptionsinthestandardmodel.Oursolutionsallowanyencryptortospecifyaccesscontrolintermsofanyaccessformulaovertheattributesinthesystem.Inourmostefficientsystem,ciphertextsize,encryption,anddecryptiontimescaleslinearlywiththecomplexityoftheaccessformula.Theonlypreviousworktoachievetheseparameterswaslimitedtoaproofinthegenericgroupmodel.

Wepresentthreeconstructionswithinourframework.OurfirstsystemisprovenselectivelysecureunderaassumptionthatwecallthedecisionalParallelBilinearDiffie-HellmanExponent(PBDHE)assumptionwhichcanbeviewedasageneralizationoftheBDHEassumption.Ournexttwoconstructionsprovideperformancetradeoffstoachieveprovablese-curityrespectivelyunderthe(weaker)decisionalBilinear-Diffie-HellmanExponentanddecisionalBilinearDiffie-Hellmanassumptions.

1Introduction

Public-Keyencryptionisapowerfulmechanismforprotectingtheconfidentialityofstoredandtransmittedinformation.Traditionally,encryptionisviewedasamethodforausertosharedatatoatargeteduserordevice.Whilethisisusefulforapplicationswherethedataproviderknowsspecificallywhichuserhewantstosharewith,inmanyapplicationstheproviderwillwanttosharedataaccordingtosomepolicybasedonthereceivinguser’scredentials.

SahaiandWaters[35]presentedanewvisionforencryptionwherethedataprovidercanexpresshowhewantstosharedataintheencryptionalgorithmitself.Thedataproviderwillprovideapredicatef(·)describinghowhewantstosharethedataandauserwillbeascribedasecretkeyassociatedwiththeircredentialsX;theuserwithcredentialsXcandecryptaciphertextencrypted

󰀅

SupportedbyNSFCNS-0716199,CNS-0915361,andCNS-0952692,AirForceOfficeofScientificResearch(AFOSR)undertheMURIawardfor“Collaborativepoliciesandassuredinformationsharing”(ProjectPRESIDIO),DepartmentofHomelandSecurityGrant2006-CS-001-000001-02(subaward641),aGoogleFacultyResearchaward,andtheAlfredP.SloanFoundation.

D.Catalanoetal.(Eds.):PKC2011,LNCS6571,pp.53–70,2011.cInternationalAssociationforCryptologicResearch2011󰀃

54B.Waters

withpredicatefiff(X)=1.SahaiandWaters[35]presentedaparticularfor-mulationofthisproblemthattheycalledAttribute-BasedEncryption(ABE),inwhichauser’scredentialsisrepresentedbyasetofstringcalled“attributes”andthepredicateisrepresentedbyaformulaovertheseattributes.SeveraltechniquesusedbySWwereinspiredbypriorworkonIdentity-BasedEncryp-tion[36,13,23,18,10].OnedrawbackoftheSahai-Watersapproachisthattheirinitialconstructionwaslimitedtohandlingformulasconsistingofonethresholdgate.

Insubsequentwork,Goyal,Pandey,Sahai,andWaters[27]furtherclarifiedtheconceptofAttribute-BasedEncryption.Inparticular,theyproposedtwocomplementaryformsofABE.Inthefirst,Key-PolicyABE,attributesareusedtoannotatetheciphertextsandformulasovertheseattributesareascribedtousers’secretkeys.Thesecondtype,Ciphertext-PolicyABE,iscomplementaryinthatattributesareusedtodescribetheuser’scredentialsandtheformulasoverthesecredentialsareattachedtotheciphertextbytheencryptingparty.Inaddition,Goyaletal.[27]providedaconstructionforKey-PolicyABEthatwasveryexpressiveinthatitallowedthepolicies(attachedtokeys)tobeexpressedbyanymonotonicformulaoverencrypteddata.Thesystemwasprovedselec-tivelysecureundertheBilinearDiffie-Hellmanassumption.However,theyleftcreatingexpressiveCiphertextPolicyABEschemesasanopenproblem.

ThefirstworktoexplicitlyaddresstheproblemofCiphertext-PolicyAttribute-BasedEncryptionwasbyBethencourt,Sahai,andWaters[7].Theydescribedanefficientsystemthatwasexpressiveinthatitallowedanencryptortoexpressanaccesspredicatefintermsofanymonotonicformulaoverattributes.TheirsystemachievedanalogousexpressivenessandefficiencytotheGoyaletal.construction,butintheCiphertext-PolicyABEsetting.WhiletheBSWconstructionisveryexpressive,theproofmodelusedwaslessthanideal—theauthorsonlyshowedtheschemesecureinthegenericgroupmodel,anartificialmodelwhichassumestheattackerneedstoaccessanoracleinordertoperformanygroupoperations1.Recently,ABEhasbeenappliedinbuildingavarietyofsecuresystems[34,40,9,8].ThesesystemsmotivatetheneedforABEconstructionsthatarebothfoundationallysoundandpractical.

CiphertextPolicyABEintheStandardModel.ThelackofsatisfactionwithgenericgroupmodelproofshasmotivatedtheproblemoffindinganexpressiveCP-ABEsystemunderamoresolidmodel.Therehavebeenmultipleapproachesinthisdirection.

First,wecanviewtheSahai-Waters[35]constructionmost“naturally”asKey-PolicyABEforathresholdgate.Intheirwork,SahaiandWatersdescribehowtorealizeCiphertext-PolicyABEforthresholdgatesby“grafting”socalled“dummyattributes”overtheirbasicsystem.Essentially,theytransformedaKP-ABEsystemintoaCP-ABEonewiththeexpressivenessofasinglethreshold

1

Alternatively,wecouldderiveaconcrete,butinteractiveandcomplicatedassump-tiondirectlyfromtheschemeitselfandarguethattheschemeissecureunderthisassumption.However,thisviewisalsonotverysatisfactory.

Ciphertext-PolicyAttribute-BasedEncryption55

gate2.CheungandNewport[22]provideadirectconstructionforconstructingapolicywithasingleANDgateundertheBilinearDiffie-Hellmanassumption.Theirapproachhasthedrawbacksthatitonlyallowsafixednumberofsys-temattributesandislimitedtoanANDgate(doesnotenablethresholds).InretrospectthesetwolimitationsactuallymakeitlessexpressivethantheSWtransformation,althoughthiswasn’tnecessarilyimmediatelyapparent.

Mostrecently,Goyal,Jain,Pandey,andSahai[26]generalizedthetransfor-mationalapproachtoshowhowtotransformaKP-ABEsystemintoaCP-ABEoneusingwhattheycalla“universalaccesstree”.Inparticular,theyprovidedamappingontoa“universal”(orcomplete)accesstreeofuptodepthdformulasconsistingofthresholdgatesofinputsizem,wheremanddarechosenbythesetupalgorithm.Theyappliedasimilar”dummyattribute”approach.

Inordertoaccommodateageneralaccessformulaofsizen,theirschemefirsttranslatesthisintoabalancedformula.Understandardtechniquesaformulaofsizencanbe“balanced”suchthatanyformula(tree)ofsizencanbecoveredbyacompletetreeofsizeapproximatelyO(n3.42).TheirworkwasthefirstfeasibilityresultforexpressiveCP-ABEunderanon-interactiveassumption.Unfortunately,theparametersofciphertextandprivatekeysizesaddencryptionanddecryptioncomplexityblowup(intheworstcase)byann3.42factorlimitingitsusefulnessinpractice.Forinstance,inasystemwithUattributesdefinedandnnodestheciphertextoverheadwillbeapproximatelyafactorofU·n2.42greaterthanthatoftheBSWsystem.Togiveaconcreteexample,forthemodestparametersofuniversesizeU=100attributesandaformulaof20nodestheblowupfactorrelativetoBSWisapproximately140,000.

OurContribution.WepresentanewmethodologyforrealizingCiphertext-PolicyABEsystemsfromageneralsetofaccessstructuresinthestandardmodelunderconcreteandnon-interactiveassumptions.BoththeciphertextoverheadandencryptiontimescalewithO(n)wherenisthesizeoftheformula.Inaddi-tion,decryptiontimescaleswiththenumberofnodes.

Ourfirstsystemallowsanencryptionalgorithmtospecifyanaccessformulaintermsofanyaccessformula.Infactourtechniquesareslightlymoregeneral.WeexpressaccesscontrolbyaLinearSecretSharingScheme(LSSS)matrixMovertheattributesinthesystem.Previouslyusedstructuressuchasformulas(equivalentlytreestructures)canbeexpressedsuccinctly[6]intermsofaLSSS.WedonotloseanyefficiencybyusingthemoregeneralLSSSrepresentationasopposedtothepreviouslyusedtreeaccessstructuredescriptions.Thus,weachievethesameperformanceandfunctionalityastheBethencourt,Sahai,andWatersconstruction,butunderthestandardmodel.

Inaddition,weprovidetwootherconstructionsthattradeoffsomeperformanceparametersforprovablesecurityundertherespectiveweakerassumptionsofdecisional-BilinearDiffie-HellmanExponent(d-BDHE)anddecisional-BilinearDiffie-Hellmanassumptions.InTable1wesummarizethecomparisonsbetweenourschemesandtheGJPSandBSWCP-ABEsystemsintermsofciphertextand

2

TheSahai-WatersconstructionwasgivenpriortotheKey-PolicyandCiphertext-Policydistinction;ourinterpretationisaretrospectiveone.

56B.Waters

keysizesandencryptionanddecryptiontimes.TakenalltogetherourfirstschemerealizesthesameefficiencyparametersastheBSWencryptionscheme,butun-deraconcretesecurityassumption.Atthesametime,ourd-BDHconstructionisprovedunderthesameassumptionastheGJPSsystemandachievessignificantlybetterperformance.

OurTechniques.Ourtechniquesprovideaframeworkfordirectlyrealizingprov-ablysecureCP-ABEsystems.Inoursystems,theciphertextdistributessharesofasecretencryptionexponentsacrossdifferentattributesaccordingtotheaccesscontrolLSSSmatrixM.

Auser’sprivatekeyisassociatedwithasetSofattributesandhewillbeabletodecryptaciphertextiffhisattributes“satisfy”theaccessmatrixassociatedwiththeciphertext.AsinpreviousABEsystems,theprimarychallengeistopreventusersfromrealizingcollusionattacks.Ourmaintooltopreventthisistorandom-izeeachkeywithanfreshlychosenexponentt.Duringdecryption,eachsharewillbemultipliedbyafactortintheexponent.Intuitively,thisfactorshould“bind”thecomponentsofoneuser’skeytogethersothattheycannotbecombinedwithanotheruser’skeycomponents.Duringdecryption,thedifferentshares(intheex-ponent)thatthealgorithmcombinesaremultipliedbyafactoroft.Ultimately,theserandomizedsharesareonlyusefultothatoneparticularkey.

Ourconstruction’sstructuresandhighlevelintuitionforsecurityissimilartotheBSWconstruction.Themainnoveltyinourpaperisprovideamethodforprovingsecurityofsuchaconstruction.Theprimarychallengeonecomesacrossis(intheselectivemodel)howtocreateareductionthatembedsacomplexaccessstructureinashortnumberofparameters.AllpriorABEschemesfollowa“partitioning”strategyforprovingsecuritywherethereductionalgorithmsetsupthepublicparameterssuchthatitknowsalltheprivatekeysthatitneedstogiveout,yetitcannotgiveoutprivatekeysthatcantriviallydecryptthechallengeciphertext.InpriorKP-ABEschemesthechallengeciphertextwasassociatedwithasetS∗ofattributes.ThisstructurecouldfairlyeasilybeembeddedinareductionasthepublicparameterforeachattributewassimplytreateddifferentlydependingwhetherornotitwasinS∗.InCP-ABE,thesituationismuchmorecomplicatedasciphertextsareassociatedwithapotentiallylargeaccessstructureM∗thatincludesattributesmultipletimes.Ingeneral,thesizeofM∗ismuchlargerthanthesizeofthepublicparameters3.Consequently,thereisnotasimple“onoroff”methodofprogrammingthisintotheparameters.Arguably,itisthischallengethatleadtheBSWpapertoapplythegenericgroupheuristicandGJPSpapertotranslatetheproblembacktoKP-ABE.

Inthispaper,wecreateamethodfordirectlyembeddinganyLSSSstructure∗

Mintothepublicparametersinourreduction.Intheproofsofoursystemasimulatorcan“program”theLSSSmatrixM∗ofthechallengeciphertext(intheselectivemodelofsecurity).ConsideraLSSSmatrixM∗ofsizel∗×n∗.ForeachrowiofM∗thesimulatorneedstoprogramin󰀚piecesofinformation

3

HereweroughlymeansizetobenumberofrowsintheLSSSsystemornodesinanaccesstree.

Ciphertext-PolicyAttribute-BasedEncryption57

∗∗(Mi,1,...,Mi,󰀐)intotheparametersrelatedtotheattributeassignedtothatrow.InourmostefficientsystemweprograminM∗usingthed-ParallelBDHEassumption;however,inSection5weshowvariationsofourconstructionthatareprovablysecureusingsimilarideas,butunderweakerassumptions.

OurmethodologyofcreatingasystemandproofthatdirectlyaddressesCP-ABEstandsincontrasttotheapproachofGJPSwhichessentiallymapsCP-ABErequirementsontoaKP-ABEscheme.

Table1.ComparisonofCP-ABEsystemsintermsofciphertextsize,privatekeysize,encryptionanddecryptiontimesandassumptions.Weletnbethesizeofanaccessformula,Abethenumberofattributesinauser’skey,andTbe(minimumneeded)numberofnodessatisfiedofaformulabyauser’sattributes,andUbethenumberofattributesdefinedinthesystem.Forourd-BDHEconstructionofthesystemdefinesaparameterkmax,whichisthemaximumnumberoftimesasingleattributewillappearinaparticularformula.IntheGJPSconstructionandourd-BDHoneofSection5thesystemsdefinenmaxasaboundonthesizeanyformula.Theciphertextandprivatekeysizesaregivenintermsofthenumberofgroupelements,encryptiontimeintermsofnumberofexponentiations,anddecryptionintermsofnumberofpairingoperations.SystemCiphetextSizePrivateKeySizeEnc.TimeAssumptionBSW[7]O(n)O(A)O(n)GenericGroup

3.423.423.42

GJPS[26]O(U·nmax)O(A·nmax)O(U·nmax)d-BDHSection3O(n)O(A)O(n)d-ParallelBDHEFullversion[42]O(n)O(kmax·A)O(n)d-BDHE

22

Section5O(n)O(kmax·A+nmax)O(n)d-BDH

1.1RelatedWork

SomeoftherootsofABEcanbetracedbacktoIdentity-BasedEncryption[36,13,23,18,10,41,24,14](IBE).OnecanviewIBEasaveryspecialcaseofABE.

Differentauthors[38,32,4,17,3,5]haveconsideredsimilarproblemswithoutconsideringcollusionresistance.Intheseworksadataproviderspecifiesanaccessformulasuchthatagroupofuserscandecryptiftheunionoftheircredentialssatisfiestheformula.Byonlyrequiringtheunionofthecredentialsonedoesnotworryaboutcollusionattacks.Intheseschemesasetupauthoritysimplyassignsaseparatepublickeytoeachcredentialandgivesthecorrespondingsecretkeytoeachuserthatpossessesthecredential.Encryptionisdonebysplittingsecretsandthenencryptingeachsharetotheappropriatepublickey.Someoftheseschemeswereinspiredbyearlierwork[21,20].

SincetheintroductionofAttribute-BasedEncryptionbySahaiandWaters[35],therehavebeenseveralpapers[27,7,19,33,26]thathaveproposeddifferentvarietiesofABE.Mostofthemhavebeenformonotonicaccessstructuresoverattributes;oneexceptionistheworkofOstrovsky,Sahai,andWaters[33]thatshowedhowtorealizenegationbyintegratingrevocationschemesintotheGPSWABEcryptosystem.

58B.Waters

MostworkonABEisfocusedoncomplexaccesscontrolsforhidinganen-cryptedpayloadofdata.Arelatedlineofworkcalledpredicateencryptionorsearchingonencrypteddataattemptstoevaluatepredicatesovertheencrypteddataitself[39,12,1,16,15,37,29].Thesesystemshavetheadvantagesofhid-ingtheassociatedaccessstructuresthemselvesandthusprovidingalevelof“anonymity”.Theconceptofpredicateencryptionismoregeneralthantheoneweconsider.However,thepredicateencryptionsystemsrealizedthusfartendtobemuchlessexpressivethanaccesscontrolsystemsthatleavetheaccessstructuresintheclear.

Otherexamplesofencryptionsystemswithmore“structure”addedincludeHierarchicalIdentity-BasedEncryption[28,25]andWildcardIBE[2].

Finally,Lewkoet.al.[31]recentlyleveragedtheencodingtechniquefromourworktobuildanABEsystemthatachievesadaptive(non-selective)security.ThesystemofLewkoet.al.isbasedincompositeordergroups,whichresultsinsomelossofpracticalefficiencycomparedtoourmostefficientsystem.Inaddition,ourBDHsystemisbasedoffofmorestandardassumptionsthanthoseusedinLewkoetal.

2Background

WefirstgiveformaldefinitionsforaccessstructuresandrelevantbackgroundonLinearSecretSharingSchemes(LSSS).Thenwegivethesecuritydefinitionsofciphertextpolicyattributebasedencryption(CP-ABE).Finally,wegiveback-groundinformationonbilinearmaps.2.1

AccessStructures

Definition1(AccessStructure[6]).Let{P1,P2,...,Pn}beasetofpar-ties.AcollectionA⊆2{P1,P2,...,Pn}ismonotoneif∀B,C:ifB∈AandB⊆CthenC∈A.Anaccessstructure(respectively,monotoneaccessstruc-ture)isacollection(respectively,monotonecollection)Aofnon-emptysubsetsof{P1,P2,...,Pn},i.e.,A⊆2{P1,P2,...,Pn}\\{∅}.ThesetsinAarecalledtheauthorizedsets,andthesetsnotinAarecalledtheunauthorizedsets.Inourcontext,theroleofthepartiesistakenbytheattributes.Thus,theaccessstructureAwillcontaintheauthorizedsetsofattributes.Werestrictouratten-tiontomonotoneaccessstructures.However,itisalsopossibleto(inefficiently)realizegeneralaccessstructuresusingourtechniquesbyhavingthenotofanattributeasaseparateattributealtogether.Thus,thenumberofattributesinthesystemwillbedoubled.Fromnowon,unlessstatedotherwise,byanaccessstructurewemeanamonotoneaccessstructure.2.2

LinearSecretSharingSchemes

Wewillmakeessentialuseoflinearsecret-sharingschemes.Weadaptourdefi-nitionsfromthosegivenin[6]:

Ciphertext-PolicyAttribute-BasedEncryption59

Definition2(LinearSecret-SharingSchemes(LSSS)).Asecret-sharingschemeΠoverasetofpartiesPiscalledlinear(overZp)if

1.ThesharesforeachpartyformavectoroverZp.

2.ThereexistsamatrixanMwith󰀚rowsandncolumnscalledtheshare-generatingmatrixforΠ.Foralli=1,...,󰀚,thei’throwofMweletthefunctionρdefinedthepartylabelingrowiasρ(i).Whenweconsiderthecolumnvectorv=(s,r2,...,rn),wheres∈Zpisthesecrettobeshared,andr2,...,rn∈Zparerandomlychosen,thenMvisthevectorof󰀚sharesofthesecretsaccordingtoΠ.Theshare(Mv)ibelongstopartyρ(i).Itisshownin[6]thateverylinearsecretsharing-schemeaccordingtotheabovedefinitionalsoenjoysthelinearreconstructionproperty,definedasfollows:Sup-posethatΠisanLSSSfortheaccessstructureA.LetS∈Abeanyauthorizedset,andletI⊂{1,2,...,󰀚}bedefinedasI={i:ρ(i)∈S}.Then,there

Zp}i∈Isuchthat,if{λi}arevalidsharesofanysecretsexistconstants{ωi∈󰀏

accordingtoΠ,theni∈Iωiλi=s.

Furthermore,itisshownin[6]thattheseconstants{ωi}canbefoundintimepolynomialinthesizeoftheshare-generatingmatrixM.

NoteonConvention.Wenotethatweusetheconventionthatvector(1,0,0,...,0)isthe“target”vectorforanylinearsecretsharingscheme.ForanysatisfyingsetofrowsIinM,wewillhavethatthetargetvectorisinthespanofI.

ForanyunauthorizedsetofrowsIthetargetvectorisnotinthespanoftherowsofthesetI.Moreover,therewillexistavectorwsuchthatw·(1,0,0...,0)=−1andw·Mi=0foralli∈I.

UsingAccessTrees.PriorworksonABE(e.g.,[27])typicallydescribedaccessfor-mulasintermsofbinarytrees.Usingstandardtechniques[6]onecanconvertanymonotonicbooleanformulaintoanLSSSrepresentation.Anaccesstreeof󰀚nodeswillresultinanLSSSmatrixof󰀚rows.Wereferthereadertotheappendixof[30]foradiscussionofhowtoperformthisconversion.2.3

Ciphertext-PolicyABE

Aciphertext-policyattributebasedencryptionschemeconsistsoffouralgorithms:Setup,Encrypt,KeyGen,andDecrypt.

Setup(λ,U).Thesetupalgorithmtakessecurityparameterandattributeuniversedescriptionasinput.ItoutputsthepublicparametersPKandamasterkeyMK.Encrypt(PK,M,A).Theencryptionalgorithmtakesasinputthepublicparam-etersPK,amessageM,andanaccessstructureAovertheuniverseofattributes.ThealgorithmwillencryptMandproduceaciphertextCTsuchthatonlyauserthatpossessesasetofattributesthatsatisfiestheaccessstructurewillbeabletodecryptthemessage.WewillassumethattheciphertextimplicitlycontainsA.KeyGeneration(MK,S).ThekeygenerationalgorithmtakesasinputthemasterkeyMKandasetofattributesSthatdescribethekey.ItoutputsaprivatekeySK.

60B.Waters

Decrypt(PK,CT,SK).Thedecryptionalgorithmtakesasinputthepublicparam-etersPK,aciphertextCT,whichcontainsanaccesspolicyA,andaprivatekeySK,whichisaprivatekeyforasetSofattributes.IfthesetSofattributessatisfiestheaccessstructureAthenthealgorithmwilldecrypttheciphertextandreturnamessageM.

Wenowdescribeasecuritymodelforciphertext-policyABEschemes.Likeidentity-basedencryptionschemes[36,13,23]thesecuritymodelallowsthead-versarytoqueryforanyprivatekeysthatcannotbeusedtodecryptthechallengeciphertext.InCP-ABEtheciphertextsareidentifiedwithaccessstructuresandtheprivatekeyswithattributes.Itfollowsthatinoursecuritydefinitionthead-versarywillchoosetobechallengedonanencryptiontoanaccessstructureA∗andcanaskforanyprivatekeySsuchthatSdoesnotsatisfyA∗.Wenowgivetheformalsecuritygame.SecurityModelforCP-ABE.

Setup.ThechallengerrunstheSetupalgorithmandgivesthepublicparameters,PKtotheadversary.

Phase1.TheadversarymakesrepeatedprivatekeyscorrespondingtosetsofattributesS1,...,Sq1.

Challenge.TheadversarysubmitstwoequallengthmessagesM0andM1.InadditiontheadversarygivesachallengeaccessstructureA∗suchthatnoneofthesetsS1,...,Sq1fromPhase1satisfytheaccessstructure.Thechallengerflipsarandomcoinb,andencryptsMbunderA∗.TheciphertextCT∗isgiventotheadversary.

Phase2.Phase1isrepeatedwiththerestrictionthatnoneofsetsofattributesSq1+1,...,Sqsatisfytheaccessstructurecorrespondingtothechallenge.Guess.Theadversaryoutputsaguessb󰀅ofb.

TheadvantageofanadversaryAinthisgameisdefinedasPr[b󰀅=b]−12.Wenotethatthemodelcaneasilybeextendedtohandlechosen-ciphertextattacksbyallowingfordecryptionqueriesinPhase1andPhase2.

Definition3.Aciphertext-policyattribute-basedencryptionschemeissecureifallpolynomialtimeadversarieshaveatmostanegligibleadvantageintheabovegame.

WesaythatasystemisselectivelysecureifweaddanInitstagebeforesetupwheretheadversarycommitstothechallengeaccessstructureA∗.Allofourconstruc-tionswillbeprovedsecureintheselectivesecuritymodel.2.4

BilinearMaps

Wepresentafewfactsrelatedtogroupswithefficientlycomputablebilinearmapsandthengiveournumbertheoreticassumptions.

LetGandGTbetwomultiplicativecyclicgroupsofprimeorderp.LetgbeageneratorofGandebeabilinearmap,e:G×G→GT.Thebilinearmapehasthefollowingproperties:

Ciphertext-PolicyAttribute-BasedEncryption61

1.Bilinearity:forallu,v∈Ganda,b∈Zp,wehavee(ua,vb)=e(u,v)ab.2.Non-degeneracy:e(g,g)=1.

WesaythatGisabilineargroupifthegroupoperationinGandthebilinearmape:G×G→GTarebothefficientlycomputable.Noticethatthemapeissymmetricsincee(ga,gb)=e(g,g)ab=e(gb,ga).

DecisionalParallelBilinearDiffie-HellmanExponentAssumption.Wedefinethedecisionalq-parallelBilinearDiffie-HellmanExponentproblemasfol-lows.ChooseagroupGofprimeorderpaccordingtothesecurityparameter.Leta,s,b1,...,bq∈ZpbechosenatrandomandgbeageneratorofG.Ifanadversaryisgiveny=

g,gs,ga,...,g(a),,g(a

∀1≤j≤qgs·bj,ga/bj,...,g(a

qq

q+2

)

,...,g(a

q+2

2q

)

2q

/bj)

,,g(a

/bj)

,...,g(a

/bj)

∀1≤j,k≤q,k=jga·s·bk/bj,...,g(a

q+1

q

·s·bk/bj)

itmustremainhardtodistinguishe(g,g)as∈GTfromarandomelementinGT.

AnalgorithmBthatoutputsz∈{0,1}hasadvantage󰀄insolvingdecisionalq-parallelBDHEinGif

󰀄󰀄󰀒󰀓󰀄󰀄󰀔󰀂󰀔󰀁󰀃q+1

󰀄PrBy,T=e(g,g)as)=0−PrBy,T=R=0󰀄≥󰀄

󰀄󰀄Definition1.Wesaythatthe(decision)qparallel-BDHEassumptionholdsifno

polytimealgorithmhasanon-negligibleadvantageinsolvingthedecisionalq-parallelBDHEproblem.

Wegiveaproofthattheassumptiongenericallyholdsinthefullversionofourpaper[42].

3OurMostEfficientConstruction

Wenowgiveourmainconstructionthatbothrealizesexpressivefunctionalityandisefficientandisprovablysecureunderaconcrete,non-interactiveassumption.InourconstructiontheencryptionalgorithmwilltakeasinputaLSSSaccessmatrixManddistributearandomexponents∈ZpaccordingtoM.Privatekeysarerandomizedtoavoidcollusionattack.

Setup(U).Thesetupalgorithmtakesasinputthenumberofattributesinthesystem.ItthenchoosesagroupGofprimeorderp,ageneratorgandUrandomgroupelementsh1,...,hU∈GthatareassociatedwiththeUattributesinthesystem.Inaddition,itchoosesrandomexponentsα,a∈Zp.Thepublickeyispublishedas

PK=

g,e(g,g)α,ga,h1,...,hU.

TheauthoritysetsMSK=gαasthemastersecretkey.

62B.Waters

Encrypt(PK,(M,ρ),M).Theencryptionalgorithmtakesasinputthepublicpa-rametersPKandamessageMtoencrypt.Inaddition,ittakesasinputanLSSSaccessstructure(M,ρ).ThefunctionρassociatesrowsofMtoattributes.

LetMbean󰀚×nmatrix.Thealgorithmfirstchoosesarandomvectorv=(s,y2,...,yn)∈Znp.Thesevalueswillbeusedtosharetheencryptionexponents.Fori=1to󰀚,itcalculatesλi=v·Mi,whereMiisthevectorcorrespondingtotheithrowofM.Inaddition,thealgorithmchoosesrandomr1,...,r󰀐∈Zp.TheciphertextispublishedasCT=

C=Me(g,g)αs,C󰀅=gs

r1r1aλ󰀄−rn

(C1=gaλ1h−hρ(󰀐),D󰀐=gr󰀄)ρ(1),D1=g),...,(C󰀐=g

alongwithadescriptionof(M,ρ).

KeyGen(MSK,S).Thekeygenerationalgorithmtakesasinputthemastersecret

keyandasetSofattributes.Thealgorithmfirstchoosesarandomt∈Zp.Itcreatestheprivatekeyas

K=gαgat

L=gt

∀x∈SKx=htx.

Decrypt(CT,SK).ThedecryptionalgorithmtakesasinputaciphertextCTfor

accessstructure(M,ρ)andaprivatekeyforasetS.SupposethatSsatisfiestheaccessstructureandletI⊂{1,2,...,󰀚}bedefinedasI={i:ρ(i)∈S}.Then,

ofconstantssuchthatif{λi}arevalidsharesofanysecretlet{ωi∈Zp}i∈Ibeaset󰀏

saccordingtoM,theni∈Iωiλi=s.(Notetherecouldpotentiallybedifferentwaysofchoosingtheωivaluestosatisfythis.)Thedecryptionalgorithmfirstcomputes

󰀔󰀐󰀁ωi

e(C󰀅,K)/(e(C,L)e(D,K))=iiρ(i)i∈I

󰀁󰀔󰀐taλiωi

=e(g,g)αse(g,g)αse(g,g)ast/i∈Ie(g,g)ThedecryptionalgorithmcanthendivideoutthisvaluefromCandobtainthe

messageM.3.1

Proof

Animportantstepinprovingoursystemsecurewillbeforthereductionto“pro-gram”thechallengeciphertextintothepublicparameters.Onesignificantobstaclethatwewillencounteristhatanattributemaybeassociatedwithmultiplerowsinthechallengeaccessmatrix(i.e.theρfunctionisnotinjective).Thisisanalogoustoanattributeappearinginmultipleleafsinanaccesstree.

Forexample,supposethatinourreductionwewanttoprogramourparameterssuchthatforhxbasedonthei-throwofM∗ifρ∗(i)=x.However,ifthereexisti=jsuchthatx=ρ(i)=ρ(j)thenthereisanissuesincewemustprogrambothrowiandrowjinthesimulation.Intuitively,thereisapotentialconflictinhowtoprogramtheparameters.

Ciphertext-PolicyAttribute-BasedEncryption63

InthisreductionweresolvethisbyusingdifferenttermsfromtheparallelBDHEassumptiontoprogrammultiplerowsofM∗intoonegroupelementcorrespondingtoanattribute.Theextratermsprovidedallowustodosowithoutambiguity4.InSection5weshowatradeoffwhereourreductioncanprogramtheinformationusingjustthedecisionalBilinearDiffie-Hellmanassumption,butatsomelossofefficiency.

Weprovethefollowingtheorem.Theorem1.Supposethedecisionalq-parallelBDHEassumptionholds.Thennopolytimeadversarycanselectivelybreakoursystemwithachallengematrixofsize󰀚∗×n∗,where󰀚∗,n∗≤q.

SupposewehaveanadversaryAwithnon-negligibleadvantage󰀄=AdvAintheselectivesecuritygameagainstourconstruction.Moreover,supposeitchoosesachallengematrixM∗wherebothdimensionsareatmostq.Weshowhowtobuildasimulator,B,thatplaysthedecisionalq-parallelBDHEproblem.

Init.Thesimulatortakesinaq-parallelBDHEchallengey,T.Theadversarygivesthealgorithmthechallengeaccessstructure(M∗,ρ∗),whereM∗hasn∗columns.Setup.Thesimulatorchoosesrandomα󰀅∈Zpandimplicitlysetsα=α󰀅+aq+1

q󰀂

bylettinge(g,g)α=e(ga,ga)e(g,g)α.

Wedescribehowthesimulator“programs”thegroupelementsh1,...,hU.Foreachxfor1≤x≤Ubeginbychoosingarandomvaluezx.LetXdenotethesetofindicesi,suchthatρ∗(i)=x.Thesimulatorprogramshxas:

󰀑∗∗∗∗zxaMi,/bia2Mi,/bianMi,n∗/bi12g·g···g.hx=g

i∈X

NotethatifX=∅thenwehavehx=gzx.Alsonotethattheparametersare

distributedrandomlyduetothegzxvalue.

PhaseI.Inthisphasethesimulatoranswersprivatekeyqueries.Supposethesim-ulatorisgivenaprivatekeyqueryforasetSwhereSdoesnotsatisfyM∗.

Thesimulatorfirstchoosesarandomr∈Zp.Thenitfindsavectorw=

∗

(w1,...,wn∗)∈Zpnsuchthatw1=−1andforalliwhereρ∗(i)∈Swehavethatw·Mi∗=0.BythedefinitionofaLSSSsuchavectormustexist.Notethatifsuchavectordidnotexistthenthevector(1,0,0,...,0)wouldbeinthespanofS.SeethediscussioninSection2.

Thesimulatorbeginsbyimplicitlydefiningtasr+w1aq+w2aq−1+···+wn∗aq−n+1.

󰀐q+1−i

ItperformsthisbysettingL=gri=1,...,n∗(ga)wi=gt.

4

∗

Wenotethatcertainassumptionshavebeenleveragedto“program”alargeamountofinformationintosinglegroupelementsinothercontexts.Gentry’sreduction[24]embedsadegreeqpolynomialintoasinglegroupelement.

64B.Waters

q+1

Weobservethatbyourdefinitionoft,wehavethatgatcontainsatermofg−a,whichwillcanceloutwiththeunknowntermingαwhencreatingK.ThesimulatorcancomputeKas:󰀑󰀂q+2−i

K=gαgar(ga)wi.

i=2,...,n∗

NowwemustcalculateKx∀x∈S.First,weconsiderx∈Sforwhichthereisno

isuchthatρ∗(i)=x.ForthosewecansimplyletKx=Lzx.

ThemoredifficulttaskistocreatekeycomponentsKxforattributesx∈S,wherexisusedintheaccessstructure.Forthesekeyswemustmakesurethat

q+1

therearenotermsoftheformga/bithatwecan’tsimulate.However,wehavethatMi∗·w=0;therefore,allofthesetermscancel.

Again,letXbethesetofallisuchthatρ∗(i)=x.ThesimulatorcreatesKxinthiscaseasfollows.

⎛

Kx=Lzx

󰀑

󰀑

⎜(aj/b)r

i⎜g

⎝

󰀑

k=1,...,n∗

k=j

∗⎞Mi,j

(ga

q+1+j−k

/biwk⎟

)

i∈Xj=1,...,n∗

⎟⎠

Challenge.Finally,webuildthechallengeciphertext.TheadversarygivestwomessagesM0,M1tothesimulator.Thesimulatorflipsacoinβ.ItcreatesC=

󰀂

MβT·e(gs,gα)andC󰀅=gs.

ThetrickypartistosimulatetheCivaluessincethiscontainstermsthatwemustcancelout.However,thesimulatorcanchoosethesecretsplitting,suchthat

󰀅󰀅,...,ynthesecancelout.Intuitively,thesimulatorwillchooserandomy2∗andthe

sharethesecretusingthevector

n󰀅󰀅󰀅

,sa2+y3,...,san−1+yn.v=(s,sa+y2∗)∈Zp

󰀅󰀅

Inaddition,itchoosesrandomvaluesr1,...,r󰀐.

∗

Fori=1,...,n,wedefineRiasthesetofallk=isuchthatρ∗(i)=ρ∗(k).Inotherwords,thesetofallotherrowindicesthathavethesameattributeasrowi.Thechallengeciphertextcomponentsarethengeneratedas

∗

Di=g−rig−sbi

󰀇Ci=hρi∗(i)

r󰀂

󰀂

󰀑

󰀈

(ga)Mi,jyj

∗

󰀂

⎛

(gbi·s)−zρ∗(i)·⎝

󰀑

k∈Ri

󰀑

j=1,...,n∗

⎞

(ga

j

∗

·s·(bi/bk)Mk,j⎠

)

j=2,...,n∗

PhaseII.SameasphaseI.

Guess.Theadversarywilleventuallyoutputaguessβ󰀅ofβ.Thesimulatorthen

q+1

outputs0toguessthatT=e(g,g)asifβ=β󰀅;otherwise,itoutputs1toindi-catethatitbelievesTisarandomgroupelementinGT.

WhenTisatuplethesimulatorBgivesaperfectsimulationsowehavethat

󰀆󰀓1󰀒󰀅

aq+1s

=0=+AdvA.PrBy,T=e(g,g)

2

Ciphertext-PolicyAttribute-BasedEncryption65

WhenTisarandomgroupelementthemessageMβiscompletelyhiddenfromtheadversaryandwehavePr[B(y,T=R)=0]=12.Therefore,Bcanplaythedecisionalq-parallelBDHEgamewithnon-negligibleadvantage.

4ConstructionsfromWeakerAssumptions

Ourfirstconstructionprovidedaveryefficientsystem,butunderastrong(butstillnon-interactive)assumption.Tobridgethisgapweintroducetwoadditionalconstructionsthatprovideatradeoffofperformanceversusstrengthofassump-tions.Weeffectivelyexploreaspectrumbetweensystemefficiencyandstrengthofassumption.Thefinalconstructionisprovensecureunderthesimpledecisional-BDHassumption.

Overview.TheprimaryobstacleinachievingsecurityfromweakerassumptionsisthatwemustbeabletoreflectthechallengeaccessstructureM∗intheparam-etersduringthereduction.Wecreatetwodifferentconstructionsusingthesameframework.

Inourfullversion[42]wegiveaconstructionprovablysecureundertheexistingd-BDHEassumptionintroducedbyBoneh,BoyenandGoh[11].Toaccommodateaweakerassumptionweintroduceaparameterkmaxwhichisthemaximumnum-beroftimesanyoneattributecanappearinanaccessformula.Aprivatekeyinthissystemwillbeafactorofkmaxlargerthanourmainconstruction.

Next,inSection5wegiveaconstructionprovablysecureunderthemuchmorestandarddecisionalBilinearDiffie-Hellmanassumption.Torealizesecurityunderthisassumptionoursystemmustadditionallyintroduceaparameternmax,whereperformanceparameterswillbeafactorofnmaxlargerthanourmostefficientconstruction.

5BilinearDiffie-HellmanConstruction

Whileourunrestrictedconstructionrealizesapotentiallyidealtypeofefficiency,wewouldliketoalsoshowthatsecureCP-ABEsystemscanberealizedfromstaticassumptions.HereweshowhowtorealizeourframeworkunderthedecisionalBi-linearDiffieHellmand-(BDH)assumption.

TheprimarychallengewithrealizingaconstructionprovablysecureunderBDHisweneedawayforareductiontoembedthechallengematrixM∗intheparam-eters.SincetheBDHassumptiongivesthereductionlesscomponentstoembedthis,thereisnoobviouspathforreducingthepreviousconstructionstod-BDH.Wesurmountthisobstaclebyexpandingourciphertextsandpublicparameterspace.Bydoingthisweenableourreductiontoembedthechallengematrix.Ourconstructionisparametrizedbyaintegernmaxthatspecifiesthemaximumnumberofcolumnsinaciphertextpolicy.Thepublicparameters,keysandcipher-textsizewillallgrowlinearlyinthisparameter5.

5

Onecouldachievesmallerciphertextsbycreatingmultiplesystemswithdifferentnmaxvaluesandusetheonethatfittheactualpolicymosttightly.

66B.Waters

Likeourfirstconstructionwerestrictρ()tobeaninjectivefunction,butcanalleviatethisrestrictionbyapplyingasimilartransformationtoallowanattributetoappearkmaxtimesforsomespecifiedkmax.Ourconstructionfollows.

Setup(U,nmax).Thesetupalgorithmtakesasinput,U,thenumberofattributesinthesystemUandnmaxthemaximumnumberofcolumnsinanLSSSmatrix(ornumberofnodesinanaccessformula).ItthencreatesagroupGofprimeorderpandageneratorgandchoosesrandomelements(h1,1,...,h1,U),...,(hnmax,1,...,hnmax,U)Inaddition,itchoosesrandomexponentsα,a∈Zp.Thepublickeyispublishedas

PK=

g,e(g,g)α,ga,

(h1,1,...,h1,U),...,(hnmax,1,...,hnmax,U)

TheauthoritysetsMSK=gαasthemastersecretkey.

Encrypt(PK,(M,ρ),M).Theencryptionalgorithmtakesasinputthepublicpa-rametersPKandamessageMtoencrypt.Inaddition,ittakesasinputanLSSSaccessstructure(M,ρ).ThefunctionρassociatesrowsofMtoattributes.Inthisconstructionwelimitρtobeaninjectivefunction,thatisanattributeisassociatedwithatmostonerowofM.

LetMbean󰀚×nmaxmatrix.(IfoneneedstocreateapolicyfornCT=C=Me(g,g)αs,C󰀅=gs,∀

alongwithadescriptionofM,ρ.

KeyGen(MSK,S).ThekeygenerationalgorithmtakesasinputthemastersecretkeyandasetSofattributes.Thealgorithmfirstchoosesarandomt1,...,tnmax∈Zp.Itcreatestheprivatekeyas

K=gαgat1

∀x∈S

L1=gt1,...,Ln=gtnmaxKx=

󰀑

j=1,...,nmax

jhj,x.

i=1,...,󰀐Ci,j

j=1,...,nmax

s

=gaMi,jvjh−j,ρ(i)

t

Decrypt(CT,SK).ThedecryptionalgorithmtakesasinputaciphertextCTfor

accessstructure(M,ρ)andaprivatekeyforasetS.SupposethatSsatisfiestheaccessstructureandletI⊂{1,2,...,󰀚}bedefinedasI={i:ρ(i)∈S}.Then,let{ωi∈Zp}i∈Ibeasetof󰀏constantssuchthat,if{λi}arevalidsharesofanysecretsaccordingtoM,theni∈Iωiλi=s.(Notetherecouldpotentiallybedifferentwaysofchoosingtheωivaluestosatisfythis.)

Ciphertext-PolicyAttribute-BasedEncryption67

Thedecryptionalgorithmfirstcomputes

⎛⎞

󰀑󰀑󰀑

ωi⎠ωi󰀅

e(C󰀅,K)/⎝e(Lj,Ci,j)e(Kρ(i),C)

j=1,...,nmax

i∈I

i∈I

=e(C󰀅,K)/e(g,

tj

󰀔

󰀑

j=1,...,nmax

e(gtj,g

󰀏

i∈I

aMi,jvjωi

)·

󰀑

i∈I

sωi

h−j,ρ(i))

󰀁󰀑

i∈I

ωis

e(Kρ(i),g)

=e(C󰀅,K)/

󰀑

e(gtj,g

󰀏

i∈I

aMi,jvjωi

)

=e(C󰀅,K)/e(g,g

=e(gs,gαgat1)/e(g,g)at1s=e(g,g)αs

j=1,...,nmax

󰀏t1i∈IaMi,1v1ωi

)

ThedecryptorcanthendivideoutthisvaluefromCandobtainthemessageM.5.1

Proof

Weprovethefollowingtheorem.

Theorem2.SupposethedecisionalBDHassumptionholds.Thennopolytimead-versarycanselectivelybreakoursystem.

Duetospacelimitationswedefertheproofofthesystemtoourfullversion[42].

6LargeUniverseofAttributes

Oneaspectofourmainconstructionisthatitdefinesthesetofattributestobeused

intheparameters.Oneusefulfeatureistobeabletodynamicallyuseanystringasanattribute.Inourfullversion[42]weshowhowintherandomoraclewecanrealizeanynumberofattributeswithconstantsizeparametersbysimplyhashingtheattributestring.Alsoinourfullversionprovidealargeuniverseconstructioninthestandardmodel.

Acknowledgements

WethankMattGreen,KazukiYoneyamaandanonymousreviewersforusefulcomments.

References

[1]Abdalla,M.,Bellare,M.,Catalano,D.,Kiltz,E.,Kohno,T.,Lange,T.,Malone-Lee,J.,Neven,G.,Paillier,P.,Shi,H.:Searchableencryptionrevisited:Consis-tencyproperties,relationtoanonymousIBE,andextensions.In:Shoup,V.(ed.)CRYPTO2005.LNCS,vol.3621,pp.205–222.Springer,Heidelberg(2005)

68B.Waters

[2]Abdalla,M.,Catalano,D.,Dent,A.W.,Malone-Lee,J.,Neven,G.,Smart,N.P.:

Identity-basedencryptiongonewild.In:Bugliesi,M.,Preneel,B.,Sassone,V.,Wegener,I.(eds.)ICALP2006,PartII.LNCS,vol.4052,pp.300–311.Springer,Heidelberg(2006)

[3]Al-Riyami,S.S.,Malone-Lee,J.,Smart,N.P.:Escrow-freeencryptionsupporting

cryptographicworkflow.Int.J.Inf.Sec.5(4),217–229(2006)

[4]Bagga,W.,Molva,R.,Crosta,S.:Policy-basedencryptionschemesfrombilinear

pairings.In:ASIACCS,p.368(2006)

[5]Barbosa,M.,Farshim,P.:Securecryptographicworkflowinthestandardmodel.

In:Barua,R.,Lange,T.(eds.)INDOCRYPT2006.LNCS,vol.4329,pp.379–393.Springer,Heidelberg(2006)

[6]Beimel,A.:SecureSchemesforSecretSharingandKeyDistribution.PhDthesis,

IsraelInstituteofTechnology,Technion,Haifa,Israel(1996)

[7]Bethencourt,J.,Sahai,A.,Waters,B.:Ciphertext-policyattribute-basedencryp-tion.In:IEEESymposiumonSecurityandPrivacy,pp.321–334(2007)

[8]Baden,R.,Bender,A.,Spring,N.,Bhattacharjee,B.,Starin,D.:Persona:Anonline

socialnetworkwithuserdefinedprivacy.In:ACMSIGCOMM(2009)

[9]Bobba,R.,Fatemieh,O.,Khan,F.,Gunter,A.K.C.A.,Khurana,H.,Prab-hakaran,M.:Attribute-basedmessaging:Accesscontrolandconfidentiality(2009)(manuscript)

[10]Boneh,D.,Boyen,X.:Efficientselective-IDsecureidentity-basedencryptionwith-outrandomoracles.In:Cachin,C.,Camenisch,J.L.(eds.)EUROCRYPT2004.LNCS,vol.3027,pp.223–238.Springer,Heidelberg(2004)

[11]Boneh,D.,Boyen,X.,Goh,E.-J.:Hierarchicalidentitybasedencryptionwithcon-stantsizeciphertext.In:Cramer,R.(ed.)EUROCRYPT2005.LNCS,vol.3494,pp.440–456.Springer,Heidelberg(2005)

[12]Boneh,D.,DiCrescenzo,G.,Ostrovsky,R.,Persiano,G.:Publickeyencryption

withkeywordsearch.In:Cachin,C.,Camenisch,J.L.(eds.)EUROCRYPT2004.LNCS,vol.3027,pp.506–522.Springer,Heidelberg(2004)

[13]Boneh,D.,Franklin,M.K.:Identity-basedencryptionfromtheweilpairing.In:Kil-ian,J.(ed.)CRYPTO2001.LNCS,vol.2139,pp.213–229.Springer,Heidelberg(2001)

[14]Boneh,D.,Gentry,C.,Hamburg,M.:Space-efficientidentitybasedencryption

withoutpairings.In:FOCS,pp.647–657(2007)

[15]Boneh,D.,Waters,B.:Conjunctive,subset,andrangequeriesonencrypted

data.In:Vadhan,S.P.(ed.)TCC2007.LNCS,vol.4392,pp.535–554.Springer,Heidelberg(2007)

[16]Boyen,X.,Waters,B.:Anonymoushierarchicalidentity-basedencryption(Without

randomoracles).In:Dwork,C.(ed.)CRYPTO2006.LNCS,vol.4117,pp.290–307.Springer,Heidelberg(2006)

[17]Bradshaw,R.W.,Holt,J.E.,Seamons,K.E.:Concealingcomplexpolicieswithhid-dencredentials.In:ACMConferenceonComputerandCommunicationsSecurity,pp.146–157(2004)

[18]Canetti,R.,Halevi,S.,Katz,J.:Aforward-securepublic-keyencryptionscheme.

In:Biham,E.(ed.)EUROCRYPT2003.LNCS,vol.2656,pp.255–271.Springer,Heidelberg(2003)

[19]Chase,M.:Multi-authorityattributebasedencryption.In:Vadhan,S.P.(ed.)

TCC2007.LNCS,vol.4392,pp.515–534.Springer,Heidelberg(2007)

Ciphertext-PolicyAttribute-BasedEncryption69

[20]Chen,L.,Harrison,K.,Moss,A.,Soldera,D.,Smart,N.P.:CertificationofPub-licKeyswithinanIdentityBasedSystem.In:Chan,A.H.,Gligor,V.D.(eds.)ISC2002.LNCS,vol.2433,pp.322–333.Springer,Heidelberg(2002)

[21]Chen,L.,Harrison,K.,Soldera,D.,Smart,N.P.:ApplicationsofMultipleTrust

AuthoritiesinPairingBasedCryptosystems.In:Davida,G.I.,Frankel,Y.,Rees,O.(eds.)InfraSec2002.LNCS,vol.2437,pp.260–275.Springer,Heidelberg(2002)[22]Cheung,L.,Newport,C.C.:Provablysecureciphertextpolicyabe.In:ACMCon-ferenceonComputerandCommunicationsSecurity,pp.456–465(2007)

[23]Cocks,C.:Anidentitybasedencryptionschemebasedonquadraticresidues.In:

IMAInt.Conf.,pp.360–363(2001)

[24]Gentry,C.:Practicalidentity-basedencryptionwithoutrandomoracles.In:Vau-denay,S.(ed.)EUROCRYPT2006.LNCS,vol.4004,pp.445–464.Springer,Hei-delberg(2006)

[25]Gentry,C.,Silverberg,A.:HierarchicalID-basedcryptography.In:Zheng,Y.(ed.)

ASIACRYPT2002.LNCS,vol.2501,pp.548–566.Springer,Heidelberg(2002)[26]Goyal,V.,Jain,A.,Pandey,O.,Sahai,A.:Boundedciphertextpolicyattribute

basedencryption.In:Aceto,L.,Damg˚ard,I.,Goldberg,L.A.,Halld´orsson,M.M.,Ing´olfsd´ottir,A.,Walukiewicz,I.(eds.)ICALP2008,PartII.LNCS,vol.5126,pp.579–591.Springer,Heidelberg(2008)

[27]Goyal,V.,Pandey,O.,Sahai,A.,Waters,B.:Attribute-basedencryptionforfine-grainedaccesscontrolofencrypteddata.In:ACMConferenceonComputerandCommunicationsSecurity,pp.89–98(2006)

[28]Horwitz,J.,Lynn,B.:Towardhierarchicalidentity-basedencryption.In:Knudsen,

L.R.(ed.)EUROCRYPT2002.LNCS,vol.2332,pp.466–481.Springer,Heidelberg(2002)

[29]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)

[30]Lewko,A.,Waters,B.:Decentralizingattribute-basedencryption.Cryptology

ePrintArchive,Report2010/351(2010),http://eprint.iacr.org/

[31]Lewko,A.,Okamoto,T.,Sahai,A.,Takashima,K.,Waters,B.:FullySecureFunc-tionalEncryption:Attribute-BasedEncryptionand(Hierarchical)InnerProductEncryption.In:Gilbert,H.(ed.)EUROCRYPT2010.LNCS,vol.6110,pp.62–91.Springer,Heidelberg(2010)

[32]Miklau,G.,Suciu,D.:Controllingaccesstopublisheddatausingcryptography.In:

VLDB,pp.898–909(2003)

[33]Ostrovsky,R.,Sahai,A.,Waters,B.:Attribute-basedencryptionwithnon-monotonicaccessstructures.In:ACMConferenceonComputerandCommunica-tionsSecurity,pp.195–203(2007)

[34]Pirretti,M.,Traynor,P.,McDaniel,P.,Waters,B.:Secureattribute-basedsys-tems.In:ACMConferenceonComputerandCommunicationsSecurity,pp.99–112(2006)

[35]Sahai,A.,Waters,B.:Fuzzyidentity-basedencryption.In:Cramer,R.(ed.)

EUROCRYPT2005.LNCS,vol.3494,pp.457–473.Springer,Heidelberg(2005)[36]Shamir,A.:Identity-basedcryptosystemsandsignatureschemes.In:Blakely,G.R.,

Chaum,D.(eds.)CRYPTO1984.LNCS,vol.196,pp.47–53.Springer,Heidelberg(1985)

[37]Shi,E.,Bethencourt,J.,Chan,H.T.-H.,Song,D.X.,Perrig,A.:Multi-dimensional

rangequeryoverencrypteddata.In:IEEESymposiumonSecurityandPrivacy,pp.350–364(2007)

70B.Waters

[38]Smart,N.P.:AccessControlUsingPairingBasedCryptography.In:Joye,M.(ed.)

CT-RSA2003.LNCS,vol.2612,pp.111–121.Springer,Heidelberg(2003)

[39]Song,D.X.,Wagner,D.,Perrig,A.:Practicaltechniquesforsearchesonencrypted

data.In:IEEESymposiumonSecurityandPrivacy,pp.44–55(2000)

[40]Traynor,P.,Butler,K.R.B.,Enck,W.,McDaniel,P.:Realizingmassive-scalecon-ditionalaccesssystemsthroughattribute-basedcryptosystems.In:NDSS(2008)[41]Waters,B.:Efficientidentity-basedencryptionwithoutrandomoracles.In:Cramer,

R.(ed.)EUROCRYPT2005.LNCS,vol.3494,pp.114–127.Springer,Heidelberg(2005)

[42]Waters,B.:Ciphertext-policyattribute-basedencryption:Anexpressive,efficient,

andprovablysecurerealization.CryptologyePrintArchive,Report2008/290(2008),http://eprint.iacr.org/