当前位置：文档之家 › Searchable Symmetric Encryption

Searchable Symmetric Encryption

  • 格式：pdf
  • 大小：542.49 KB
  • 文档页数：33

下载文档原格式

  / 33

合集下载

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

SearchableSymmetricEncryption:

ImprovedDefinitionsandEfficientConstructions∗

RezaCurtmola†

NJITJuanGaray‡

AT&TLabs–ResearchSenyKamara§

MicrosoftResearchRafailOstrovsky¶

UCLA

Abstract

Searchablesymmetricencryption(SSE)allowsapartytooutsourcethestorageofhisdatatoanotherpartyinaprivatemanner,whilemaintainingtheabilitytoselectivelysearchoverit.Thisproblemhasbeenthefocusofactiveresearchandseveralsecuritydefinitionsandconstructionshavebeenproposed.Inthispaperwebeginbyreviewingexistingnotionsofsecurityandproposenewandstrongersecuritydefinitions.Wethenpresenttwoconstructionsthatweshowsecureunderournewdefinitions.Interestingly,inadditiontosatisfyingstrongersecurityguarantees,ourconstructionsaremoreefficientthanallpreviousconstructions.Further,priorworkonSSEonlyconsideredthesettingwhereonlytheownerofthedataiscapableofsubmittingsearchqueries.Weconsiderthenaturalextensionwhereanarbitrarygroupofpartiesotherthantheownercansubmitsearchqueries.WeformallydefineSSEinthismulti-usersetting,andpresentanefficientconstruction.

1Introduction

Private-keystorageoutsourcing[30,4,33]allowsclientswitheitherlimitedresourcesorlimitedexper-

tisetostoreanddistributelargeamountsofsymmetricallyencrypteddataatlowcost.Sinceregular

private-keyencryptionpreventsonefromsearchingoverencrypteddata,clientsalsolosetheability

toselectivelyretrievesegmentsoftheirdata.Toaddressthis,severaltechniqueshavebeenproposed

forprovisioningsymmetricencryptionwithsearchcapabilities[40,23,10,18];theresultingconstruct

istypicallycalledsearchableencryption.Theareaofsearchableencryptionhasbeenidentifiedby

DARPAasoneofthetechnicaladvancesthatcanbeusedtobalancetheneedforbothprivacyand

nationalsecurityininformationaggregationsystems[1].

Oneapproachtoprovisioningsymmetricencryptionwithsearchcapabilitiesiswithaso-called

secureindex[23].Anindexisadatastructurethatstoresdocumentcollectionswhilesupporting

efficientkeywordsearch,i.e.,givenakeyword,theindexreturnsapointertothedocumentsthat

containit.Informally,anindexis“secure”ifthesearchoperationforakeywordwcanonlybe

performedbyusersthatpossessa“trapdoor”forwandifthetrapdoorcanonlybegeneratedwith

asecretkey.Withoutknowledgeoftrapdoors,theindexleaksnoinformationaboutitscontents.

AsshownbyGohin[23],onecanbuildasymmetricsearchableencryptionschemefromasecure

∗Apreliminaryversionofthisarticleappearedinthe13thACMConferenceonComputerandCommunicationsSecurity(CCS’06)[20].†crix@njit.edu.WorkdoneinpartwhileatBellLabsandJohnsHopkinsUniversity.‡garay@research.att.com.WorkdoneinpartwhileatBellLabs.§senyk@microsoft.com.WorkdoneinpartwhileatJohnsHopkinsUniversity.¶rafail@cs.ucla.edu.

1indexasfollows:theclientindexesandencryptsitsdocumentcollectionandsendsthesecureindex

togetherwiththeencrypteddatatotheserver.Tosearchforakeywordw,theclientgeneratesand

sendsatrapdoorforwwhichtheserverusestorunthesearchoperationandrecoverpointerstothe

appropriate(encrypted)documents.

Symmetricsearchableencryptioncanbeachievedinitsfullgeneralityandwithoptimalsecurity

usingtheworkofOstrovskyandGoldreichonobliviousRAMs[35,25].Moreprecisely,usingthese

techniquesanytypeofsearchquerycanbeachieved(e.g.,conjunctionsordisjunctionsofkeywords)

withoutleakinganyinformationtotheserver,noteventhe“accesspattern”(i.e.,whichdocuments

containthekeyword).Thisstrongprivacyguarantee,however,comesatthecostofalogarithmic(in

thenumberofdocuments)numberofroundsofinteractionforeachreadandwrite.Inthesamepaper,

theauthorsshowa2-roundsolution,butwithconsiderablylargersquare-rootoverhead.Therefore,

thepreviouslymentionedworkonsearchableencryption[40,23,10,18]triestoachievemoreefficient

solutions(typicallyinoneortworounds)byweakeningtheprivacyguarantees.

1.1Ourcontributions

Wenowgiveanoverviewofthecontributionsofthiswork.

Revisitingpreviousdefinitions.Wereviewexistingsecuritydefinitionsforsecureindexes,includ-

ingindistinguishabilityagainstchosen-keywordattacks(IND2-CKA)[23]andthesimulation-based

definitionin[18],andhighlightsomeoftheirlimitations.Specifically,werecallthatIND2-CKAdoes

notguaranteetheprivacyofuserqueries(andisthereforenotanadequatenotionofsecurityfor

constructingSSEschemes)andthenhighlight(andfix)technicalissueswiththesimulation-based

definitionof[18].Weaddressboththeseissuesbyproposingnewgame-basedandsimulation-based

definitionsthatprovidesecurityforbothindexesandtrapdoors.

Newdefinitions.WeintroducenewadversarialmodelsforSSE.Thefirst,whichwerefertoasnon-

adaptive,onlyconsidersadversariesthatmaketheirsearchquerieswithouttakingintoaccountthe

trapdoorsandsearchoutcomesofprevioussearches.Thesecond—adaptive—considersadversaries

thatchoosetheirqueriesasafunctionofpreviouslyobtainedtrapdoorsandsearchoutcomes.All

previousworkonSSE(withtheexceptionofobliviousRAMs)fallswithinthenon-adaptivesetting.

Theimplicationisthat,contrarytothenaturaluseofsearchableencryptiondescribedin[40,23,18],

thesedefinitionsonlyguaranteesecurityforusersthatperformalltheirsearchesatonce.Weaddress

thisbyintroducinggame-basedandsimulation-baseddefinitionsintheadaptivesetting.

Newconstructions.Wepresenttwoconstructionswhichweprovesecureunderournewdefinitions.

Ourfirstschemeisonlysecureinthenon-adaptivesetting,butisthemostefficientSSEconstruction

todate.Infact,itachievessearchesinonecommunicationround,requiresanamountofworkfrom

theserverthatislinearinthenumberofdocumentsthatcontainthekeyword(whichisoptimal),

requiresconstantstorageontheclient,andlinear(inthesizeofthedocumentcollection)storageon

theserver.Whiletheconstructionin[23]alsoperformssearchesinoneround,itcaninducefalse

positives,whichisnotthecaseforourconstruction.Additionally,alltheconstructionsin[23,18]

requiretheservertoperformanamountofworkthatislinearinthetotalnumberofdocumentsin

thecollection.

Oursecondconstructionissecureagainstanadaptiveadversary,butatthepriceofrequiring

ahighercommunicationoverheadperqueryandmorestorageattheserver(comparablewiththe

storagerequiredin[23]).Whileouradaptiveschemeisconceptuallysimple,wenotethatconstructing

efficientandprovablysecureadaptiveSSEschemesisanon-trivialtask.Themainchallengeliesin

provingsuchconstructionssecureinthesimulationparadigm,sincethesimulatorrequirestheability

2