Informationclienthold

HowtoGarbleRAMPrograms3SteveLu1andRafailOstrovsky21StealthSoftwareTechnologies,Inc.
steve@stealthsoftwareinc.
com2DepartmentofComputerScienceandDepartmentofMathematics,UCLA.
WorkdonewhileconsultingforStealthSoftwareTechnologies,Inc.
rafail@cs.
ucla.
edu3PatentPendingAbstract.
Assumingsolelytheexistenceofone-wayfunctions,weshowhowtoconstructGarbledRAMPrograms(GRAM)whereitssizeonlydependsonxedpolynomialinthesecurityparametertimestheprogramrunningtime.
WestressthatweavoidconvertingtheRAMprogramsintocircuits.
Asanexample,ourtechniquesimpliestherstgarbledbinarysearchprogram(searchingoversortedencrypteddatastoredinacloud)whichispoly-logarithmicinthedatasizeinsteadoflinear.
Ourresultrequirestheexistenceofone-wayfunctionandenjoysthesamenon-interactivepropertiesasYao'soriginalgarbledcircuits.
Keywords:SecureComputation,ObliviousRAM,GarbledCircuits.
21IntroductionOftentimes,suchasincloudcomputation,onepartywantstostoresomedataremotelyandthenhavetheremoteserverperformcomputationsonthatdata.
Iftheclientdoesnotwishtorevealthisdataorthenatureofthecomputationandtheresultsofthecomputa-tiontotheremoteserver,thenonemustresorttousingsecurecomputationmethodsinordertoprocessthisremotelystoreddata.
Inotherwords,supposetwopartieswanttocomputesomeprogramπontheirprivateinputswithoutrevealingtoeachother(orjustoneparty)anythingbuttheoutput.
Theearliestresearchinsecuretwo-partycomputa-tionmodeledπasacircuitandwasaccomplishedunderYao'sGarbledCircuits[33]ortheGoldreich-Micali-Wigderson[10]paradigm.
Bothoftheseapproachesrequiretheprogramπtobeconvertedtoacircuit.
Eventherecentworkofperformingsecurecomputationviafullyhomomorphicencryptionrequiresrepresentingtheprogramπasacircuit.
However,manyalgorithmsaremorenaturallyandcompactlyrepresentedasRAMprograms,andconvertingtheseintocircuitsmayleadtoahugeblowupinprogramsizeanditsrunningtime.
Ofcourse,thereareknownpolynomialtransformationsbetweentime-boundedRAMprograms,time-boundedTuringMachinesandcircuits[8,27]:GivenaT-timeRAMprogram,[8]showshowonecantransformitintoaO(T3)-timeTM,and[27]showshowtotransformaT-timeTMintocircuitsofsizeO(TlogT),whichresultsinaO(T3logT)blowup.
OurworkaimsatcircumventingthesetransformationcostsandexecutingRAMprogramsdirectlyinaprivatemanner,whileretainingthesamenonin-teractivepropertiesasYao'sGarbledcircuits.
Thisgoalisespeciallyimportantforthecaseofcomplexreal-worldRAMprogramswithrunningtimethatismuchlargerthantheinputsize.
UnrollingthesecomplicatedRAMprogramswithmultipleexecutionpaths,recursion,multipleloops,etc.
intoacircuitmakesthecircuitsizepolynomiallylargerandoftenprohibitive.
Itshouldbenotedthatourworkisalsoimportantinpracticalapplicationswherethesizesoftheinputsarevastlydifferent,suchasdatabasesearch,orwheremulti-plequeriesagainstthesamelargedata-setmustbeexecuted.
WhencompilingaRAMprogramintoacircuit,thecompiledcircuitmustinherentlybeabletocomputeallexe-cutionpathsoftheRAMprogram.
Thus,thecircuititselfmustbeatleastbeaslargeastheinputsize,whichinsomeapplicationsmaybeisexponentiallylargerthanexecutionpathoftheinsecuresolution(e.
g.
considerabinarysearch).
Onecanarguethatevenifthecircuitislarge,wecan"charge"thelargecircuitcosttothelargeinputsize,butinmanycasesthisisunacceptable:considerthecasewherealargedataisencryptedanduploadedoff-line,suchasalargedatabase,andmultipleencryptedqueriesaremadeon-line,wheretheinsecureexecutionpathis,forexample,poly-logarithmicinthedatabasesizeandwedonotwantto"pay"anon-linecostofcircuitsizewhichislinearinthedatabasesize.
AnalternativeapproachforsecureconversionofRAMprogramsintocircuitsisdy-namicevaluation:eveniftheresultingcircuitislargeandthetotalsizeoftheisresultingcircuitisprohibitive,onecanexecuteandevencompilethelargecircuitdynamicallyandintelligentlyevaluateonlypartsofthecircuitsoasto"pruneoff"deadpaths(e.
g.
short-circuitingtechniques)tomaketheevaluationefcient,eveninthecaseoflargein-puts.
However,untilnowitwasnotknownhowtoconvertRAMprogramsintocircuits3whichresultinanefcientsecurenon-interactiveexecutioninawaythatdoesnotre-vealtheexecutionpathofthecompiledRAMprogram.
Naturally,usinginteraction,onecanusetheGoldreich-Micali-Wigderson[10]paradigmalongwithrevealingbitsalongthewaytohelppruneanddetermineexecutionpath–howeverourultimategoalistoexplorethenon-interactivegarblingsolutionsforRAMprogramswithoutrevealingtheexecutionpath.
AnotheralternativemethodforcomputingRAMprogramswithoutrstconvert-ingthemtocircuitswasproposedbyOstrovskyandShoup[25]whichusedObliviousRAM[11]asabuildingblock.
TheOstrovsky-ShoupcompilerallowspartiestoexecuteObliviousRAMprogramsdirectly,i.
e.
,withoutrstunrollingitintoacircuit,whichprovidedanalternativeapproachtosecureRAMcomputation.
ThemethodwasfurtherimprovedbyGordonetal.
[16]inordertoperformsublinearamortizeddatabasesearch.
LuandOstrovsky[21]consideredtwo-serverObliviousRAMinsidetheOstrovsky-Shoupcompiler,whichledtologarithmicoverheadinboththecomputationandthecommunicationcomplexity.
NotethatthesethreeworksallowsecureRAMevaluationwithouthavingtounrolltheprogramintoacircuitandrepresentadifferentwaytoperformsecurecomputationthatrevealsonlytheprogramrunningtime.
Amongthese,[21]isthebestresultforprograms(insteadofcircuits)intermsofcomputationcom-plexityandcommunicationcomplexity.
However,intermsofroundcomplexity,thesepapersleavemuchtobedesired:theyallrequireatleastoneroundforeachCPUcom-putationstep,evenusingtheso-callednon-interactiveRAMsolutionof[31],whichreduceseachread/writetooneroundbetweentheclientandtheserver.
Sincetherun-ningtimeofCPUisatleasttstepsforprogramsthatrunintimet,thisleadsto(t)roundcomplexity.
Incontrast,inthispaper,weshowhowtoretainpoly-logoverheadincommunicationandcomputation,andmaketheentirecomputationnon-interactiveintheOT-hybridmodel,justlikeYao.
1.
1TheBlueprintforRAMProgramGarblingWedescribeourapproachatahighlevel:westartwithanORAMcompiler(withcertainpropertieswhichwewilldescribelater)thattakesaprogramandconvertsitintoanobliviousone.
Wecallthisnewprogramthe"ORAMCPU"becauseitcanbethoughtofasaclientrunningaCPUthatperformsalocalcomputationfollowedbyreadingorwritingsomethingontheremoteserver.
Asaconceptualsegue,considerthefollowingchange:insteadoftheORAMCPUlocallyperformingitscomputation,itcreatesagarbledcircuitrepresentingthatcomputation,andalsogarblesalltheinputsforthatcomputation(theinputsarejusttheclientstateandthelastfetcheditem,possiblywithsomerandomness)andsendsittotheserverwhothenevaluatesthecircuit.
Theoutputofthiscomputationisjustthenextstateandthenextread/writequery,andtheserverpreformstheread/writequerylocally,andsendsbacktheresultoftheread/writequeryalongwiththestatetotheORAMCPU.
Weemphasizethatthisisjustaconceptualintermediatestep,sincethisstepdoesnotactuallygiveusanysavingsandpossiblyinterfereswiththesecurityoftheORAMCPUbyhavingitsstaterevealedtotheserver.
Next,wechangewheretheORAMCPUstateisstored:insteadoflettingtheclientholdit,itisstoredontheserveringarbledformat.
Thatistosay,thegarbledcircuitthattheclientsendstotheservernowoutputsagarbledstateinsteadofaregularstate,4whichcanthenbeusedasinputforthenextORAMCPUstep.
AslongasthegarbledcircuitforthenextCPUstepusesthesameinputencodingastheonegeneratedbyourcurrentCPUstep,thentheclientdoesnotneedtointeractwiththeserver.
However,thegarbledCPUalsoperformsread/writeoperationsintoORAMmemorythatneedtobecarefullyinterleavedwithourcomputations.
Weneedtodescribehowthisisdonenext.
LetussupposethattheORAMcompilerhadthepropertythattheORAMCPUknowsexactlywhenthecontentsofamemorylocationthatitwantstoreadnextwaslastwrittento(whichisthecaseformanyORAMschemes).
Weattempttoperformthesamestrategyaswedidwithgarblingthestate:whenevertheORAMCPUwantstowritesomethingtomemory.
WestorememorybitsasYao'sgarbledkeys,basedontheactuallocation,andthetimelastwritten.
Thus,thebitstoredinsomeparticularlocationhasoneofthetwogarbledkeys.
However,thisdoesnotimmediatelywork,becauseifeachmemorylocationusesadifferentencoding,theCPUcircuitdoesnotknowwhichencodingtousewhenreadingatsomefuturetime.
Inordertoresolvethis,weconstructacircuitthatassistswiththistransition:thecircuittakesasinputatimestepandmemorylocationcomputes(inagarbledform)twopossibleencodingsfor0/1encodedinthislocationandoutputsagarbledcircuitencodedforthattimestepto"translate"keysstoredinmemorytokeysneededbytheCPU.
Sincethiscircuitdoesnotrequiretheknowledgeofthememorylocationaheadoftime,theclientcangenerateasmanyoftheseasneededatthestartofthecomputation.
Indeed,iftheORAMprogramrunsintsteps,theclientcangeneratetofthesecircuits,garblethem,andsendthemalltotheserver,non-interactively.
NotethatweneedObliviousRAMwithpoly-logoverheadwheretheclientsizeisatmostsomexedpolynomialinthesecurityparametertimessomepoly-logfactorinn.
ThisisbecauseforeveryORAMfetchoperation,wealsoneedtoemulatetheclient'sinternalcomputationoftheObliviousRAMusinggarbledcircuit,whichincursamultiplicativeoverheadinthesizeandtherunningtimeoftheclient.
Thus,thesmallertheclientofObliviousRAM,themoreefcientoursolutionis:inordertoachievepoly-logoverhead,allObliviousRAMschemeswhereclientmemoryislargerthanpoly-logarithmic(e.
g.
[9,6])isnotusefulforourpurposes.
WeexpandontheintuitioninSection3.
1.
InSection3wegivethemainconstructionforgarbledRAMprograms.
Whencombinedwithoblivioustransfer,thisgivesaone-roundsecuretwo-partyRAMprogramcomputationinthesemi-honestmodel(whichcanbeextendedtomulti-partyusingtheBeaver-Micali-Rogawayparadigm[2]),whichwediscussinSection4.
Inthefullversion[20],wealsoshowhowtoconstructasingle-roundORAM.
1.
2RelatedWorkonSecureRAMComputation.
ObliviousRAMwasintroducedinthecontextofsoftwareprotectionbyGoldreichandOstrovsky[11].
IntheoriginalworkbyGoldreich[9],asolutionwasgivenwithO(√n)andcommunicationoverheadwherelookupscouldbedoneinasingleroundandO(2√lognloglogn)communicationoverheadforarecursivesolution.
Subsequently,Ostrovsky[23,24]gaveasolutionwithonlypoly-logoverheadandconstantclientmem-ory(theso-called"hierarchicalsolution").
SubsequenttoGoldreichandOstrovsky[23,24,9,11],worksonObliviousRAM(e.
g.
[31,32,26,13,14,28,15,18,29])lookedatimprovingtheconcreteandasymptotic5parametersofObliviousRAM.
ThenotionofPrivateInformationStorageintroducedbyOstrovskyandShoup[25]allowsforprivatestorageandretrievalofdata,andwasprimarilyconcentratedintheinformationtheoreticsetting.
ThismodeldiffersfromObliviousRAMinthesensethat,whilethecommunicationcomplexityoftheschemeissub-linear,theserverperformsalinearamountofworkonthedatabase.
TheworkofOstrovskyandShoup[25]givesamulti-serversolutiontothisprobleminboththecom-putationalandtheinformation-theoreticsettingandintroducestheOstrovsky-ShoupcompileroftransformingObliviousRAMintosecureRAMcomputation.
Thenotionofsingle-server"PIRWriting"wassubsequentlyformalizedinBoneh,Kushilevitz,Ostro-vskyandSkeith[5]wheretheyprovideasingle-serversolution.
Thecaseofamortized"PIRWriting"ofmultiplereadsandwriteswasconsideredin[7].
WithregardtosecurecomputationforRAMprograms,theimplicationsoftheOstrovsky-ShoupcompilerwasexploredintheworkofNaorandNissim[22]whichshowshowtoconvertRAMprogramsintoso-calledcircuitswith"lookuptables"(LUT).
TheOstrovsky-ShoupcompilerwasfurtherexploredintheworkofGordonetal.
[16]inthecaseofamortizedprograms.
Namely,consideraclientthatholdsasmallin-putx,andaserverthatholdsalargedatabaseD,andtheclientwishestorepeatedlyperformprivatequeriesf(x,D).
Inthismodel,anexpensiveinitialization(depend-ingonlyonD)isrstperformed.
Afterwards,iffcanbecomputedintimeTwithspaceSwithaRAMmachine,thenthereisasecuretwo-partyprotocolcomputingfintimeO(T)·polylog(S)withtheclientusingO(logS)spaceandtheserverusingO(S·polylog(S))space.
ThesecureRAMcomputationsolutionofLuandOstro-vsky[21]canbeviewedasageneralizationofthe[25]modelwhereserversmustalsoperformsublinearwork.
1.
3OurResultsInthispaper,weshowhowtogarbleanyRandomAccessMachine(RAM)Programπtthatrunsintimeupperboundedbytwhilekeepingallthenon-interactiveadvantagesoftheYao'sGarbledCircuitapproach.
Morespecically,wepresentaprogramgar-blingmethodwhichconsistsofatripleofpolynomial-timealgorithms(G,GI,GE).
GtakesasinputanyRAMprogramπithatincludesanupperboundtonitsrunningtimeandapseudorandomfunction(PRF)familyFandaseedsforPRFofsizek(ase-curityparameter)andoutputsagarbledprogramΠt=G(πt,t,F,s),whereallinputsarepolynomialinthesecurityparameter.
Justlikegabledcircuits,weprovideawaytogarbleanyinputxforπtintoGarbledInputX=GI(x,s),andanalgorithmtoeval-uateagarbledprogramongarbledinputsGE(Πt,t,X).
Thecorrectnessrequirementisthatforanyx,πt,F,sitholdsthatπt(x)=GE(G(πt,t,F,s),GI(x,s))withthesecurityguaranteethatnothingaboutxisrevealedexceptitsrunningtimet,expressedintermsofcomputationalindistinguishability(≈)betweenthesimulatorSimandgar-bledoutputs.
Sofar,theabovedescriptionmatchesYao'sgarbledcircuitdescription.
Thedifferenceisbothintherunningtimeandthesizeofgarbledprogramforournewgarblingmethod.
MainTheoremAssumeone-wayfunctionsexist,andletthesecurityparameterbekandletFbeaPRFfamilybasedontheone-wayfunction.
Then,thereexistsaProgram6Garblingtripleofpoly-timealgorithmsG,GI,GEsuchthatforanytanyπtandanyinputxoflengthnwehavethefollowing.
Correctness:x,πt,F,s:πt(x)=GE[G(πt,t,F,s),GI(x,s)].
Security:poly-timesimulatorSim,suchthatπ,t,x,s,where|s|=k,[G(πt,t,F,s),GI(x,s)]≈Sim1k,t,|x|,πt(x).
GarbledProgramSize:Thesizeofthegarbledprogram|G(πt,t,F,s)|=O((|π|+t)·kO(1)·polylog(n).
GarbledInputSize:Let|x|=nand|s|=k.
x,sthegarbledinputsize|GI(x,s)|=On·kO(1)·polylog(n).
Ourmainconstructionisagarbledprogrambasedonanyone-wayfunction(orablock-cipher),andistime-compactinthesensethatiftheoriginalprogramrunsinttimeandhassizen,ourgarbledRAMrunsinO(t·poly(k,logn)).
1.
4Remarks–Makingprogramsandoutputsprivate.
WenotethatsimilartoYao,wecanmakeπttobeatime-boundeduniversalprogramut,(i.
e.
,aninterpreter)andx=(πt,y)includebothtime-boundedprogramπtandinputy,sothatut(x)=πt(y).
Partofthespecicationofπtmayalsoincludemaskingitsoutput–i.
e.
tohaveoutputblinded(XORed)witharandomstring.
Thatallows,justlikeYao,tokeepboththeprogramandtheoutputhiddenfromamachinethatevaluatesthegarbledprogram.
Suchamodicationhasbeenutilizedintheliterature(see,e.
g.
[1]).
–Reactivefunctionalities.
Ourresultshowsthatwecanrstgarblealargeinputx,|x|=nwithgarbledinputsizeequaltoO(|x|·kO(1)·polylog(n))sothatlater,givenprivateprogramsπ1t1πjtj,.
.
.
forpolynomiallymanyprogramswhereprogramπjrunsintimetjandpotentiallymodiesx,(e.
g.
,databaseupdates)wecangarbleandexecutealloftheseprogramsjustrevealingrunningtimesti,andnothingelse.
ThesizeofeachgarbledprogramremainsO(|πi|+ti)·kO(1)·polylog(n)).
Itisalsoeasytohandlethecasewherethelengthofxchanges,pro-videdthatanupperboundbyhowmucheachprogramchangesthelengthofxisknownpriortogarblingofnextprogram.
–Cloudcomputing.
Asanexampleofthepowerofourresultweoutlinesecurecloudcomputation/delegation.
Inthissimpleapplicationonepartyhasaninputandwantstostoreitremotelyandthenrepeatedlyrundifferentprivateprogramsonthisdata.
Reactivefunctionalitiesallowustodothiswithoneimportantrestriction:wedonotgivetheserverachoiceinadaptivelyselectingtheinputs:butthisisnotanissueastheserveritselfhasnoinputstotheprogram.
Theotherpossibleproblemisiftheprogramsthemselvesarecontrivedandcircularlyreferencethecodeforthegarblingalgorithm.
Suchprogramswouldbehighlyunnaturaltorunondataandsowedisallowtheminoursetting.
–Two-partycomputation.
NotethatjustlikeinYao'sgarbledcircuits,inordertotransmitthegarbledinputscorrespondingtoinputbitsheldbyadifferentpartyforthesakeofsecuretwo-partycomputation,onereliesonObliviousTransfer(OT)thatcanbedonenon-interactivelyintheOT-hybridmodel.
Here,weinsistthattheOT-selectedinputstoourgarbledprogramarecommittedtopriortoreceivingtheRAMgarbledprogram,i.
e.
non-adaptively[3].
7–Optimizations.
WeremarkthatsteptwoofourblueprintisapplicabletoalmostallORAMschemeswithsmallCPUasfollows:insteadofcollapsinginthehierarchi-calObliviousRAMsmultipleroundsofasingleread/writetoasingleround,wecanimplementourstep2directlyforeachroundofeachread/write(e.
g.
eveninsideasingleread/writesimulationofObliviousRAMthatrequiresmultiplerounds)oftheunderlyingObliviousRAM:byimplementinganoraclecallforeachObliviousRAMCPUread/writeusingourmethodofcompilingmemoryfetch"onthey"intogarbledcircuits.
AnyObliviousRAMwheretheCPUcantellpreciselywhenanymemorylocationwasoverwrittenlastcanbecompliedusingourapproach.
(WecallsuchObliviousRAMs"predictivememory"RAMsandexplorethisfur-therinthefullversion.
)Forexample,thispropertyholdsfor[18]ORAM.
Italsoallowsagenericmethodto"collapse"allmulti-roundpredictivememoryObliviousRAMwithsmallCPUintoasingleround.
ObservethattheoverallcomplexityforgarblingprogramsdependsbothontheCPUcomplexityandtheORAMread/writecomplexity.
–TighterInputCompactness.
UsinganORAMschemethathassmallinputencod-ingandsmallsizeCPU(suchas[18])wecanalsomakeInputCompactnessinourmaintheoremtighter:forallprogramswecanmakegarbledinputstobeO(nk),whererecallthatnistheinputsizeandkisthesecurityparameter.
Weremarkthatifwewishtogarbleonly"large"programsthatruntimeatleast(n·logn·kO(1)),wecanmakeInputCompactnessevenbetterundertheassumptionthatonecanen-codeinputstogarbledcircuitstobeofsizeO(n+k)andhavethegarbledprogram"unpack"theinputstothefullO(nk)size.
SuchpackingtechniquesforhavebeenrecentlydevelopedforgarblingtheinputsofgarbledcircuitsbyIshaiandKushile-vitz[17].
–StrongerAdversarialmodels.
Asalreadymentionedwedescribetheschemeinthehonest-but-curiousmodelbasedonhonest-but-curiousYao,andonlyinthenon-adaptivelysecuresetting(see[3]forfurtherdiscussionofadaptivity.
)ThereisaplethoraofworksthatconvertYao'sgarbledcircuitsfromhonest-but-curioustomalicioussetting,aswellstrengtheningitssecurityinvarioussettings.
SinceourmachineryisbuildontopofYao'sgarbledcircuits(andObviousRAMsthatworkinthefullyadaptivesetting),manyofthesetechniquesforstrongerguaranteesforYao'sgarbledcircuitapplyinastraightforwardmannertooursettingaswell.
Wepostponedescriptionofmaliciousmodelstothefullversion.
2Preliminaries2.
1ObliviousRAMWeworkintheRAMmodelwithstoredprograms,wherethereisaCPUthatcanrunaprogramthatperformsasequenceofreadsorwritestolocationsstoredonalargememory.
Thismachine,whichwewillrefertoastheCPUortheclient,canbeviewedasastateful4processorwithonlyafewspecialdataregistersthatstoreprogramcounters,4Wecanconsiderastatelessversionwhereallregistersarestoredinmemory.
Foreaseofexposition,welettheclientholdlocalstate.
8querycounters,andcryptographickeys(primarilyaseedforaPRF)andthatCPUcanrunsmallprogramswhichmodelasingleCPUstep.
GiventheCPUstateΣandthemostrecentlyreadelementx,CPU(Σ,x)doessimpleoperationssuchasaddition,multiplication,updatingprogramcounter,orexecutingPRFfollowedbyproducingthenextread/writecommandaswellasupdatingtothenextstateΣ.
Becausewewishtohidethetypeofaccessperformedbytheclient,weunifybothtypesofaccessesintoaoperationknownasaquery.
Asequenceofnqueriescanbeviewedasalistof(memorylocation,data)pairs(v1,x1)vn,xn),alongwithasequenceofoperationsop1,opn,whereopiisaREADorWRITEoperation.
InthecaseofREADoperations,thecorrespondingxvalueisignored.
Thesequenceofqueries,includingboththememorylocationandthedata,performedbyaclientisknownastheaccesspattern.
Inourmodel,wewishtoobliviouslysimulatetheRAMmachinewithaclient,whichcanbeviewedashavinglimitedstorage,thathasaccesstoaserver.
However,theserverisuntrustedandassumedtomalicious.
AnobliviousRAMissecureiftheviewofaanymaliciousservercanbesimulatedinpoly-timeinawaythatisindistinguishablefromtheviewoftheserverduringarealexecution.
Forconcreteness,wefocusonsequenceofbuffersBk,Bk+1,BLofgeometricallyincreasingsizes.
Typicallyk=O(1)(therstbufferisofconstantsize)andL=logn(thelastbuffermaycontainallnelements),wherenisthetotalnumberofmemorylocations.
Thesebuffersarestandardbucketedhashtables,withbucketsofsizeb.
Wereferthereaderto[11]formoreinformation.
2.
2Yao'sGarbledCircuitsGarbledcircuitswereintroducedbyYao[33].
Aseriesofworkslookedatprovingthesecurityandformalizingthenotionsofgarbledcircuits,includingLindellandPinkas[19],andrecently,theworkofBellareetal.
[4].
Wereferthereadertothelatterworkformoredetails,andwebrieysummarizethekeyproperties.
Acircuitgarblingschemeweviewasatripleofalgorithms(G,GI,GE)whereG(1k,C)takesasinputasecurityparameterkandcircuitCandoutputssomegarbledcircuitΓandgarblingkeygsk.
GI(x,gsk)convertsaninputxandagskintoagarbledinputX,andGE(Γ,X)evaluatesagarbledcircuitonangarbledinput.
Werstmakeanobservationthatthelabels(keys)onagivenwireusedinagarbledcircuitcanbere-usedinadditionalnewlygeneratedgates,aslongasthevaluedoesnotchangebetweentheusesanditisnotrevealedwhetherthislabelrepresents0or1.
(Forexample,assumethatgarbledcircuitevaluatorisgivenalabelonsomeinputwire,whichisakeyrepresentinga0ora1.
Weclaimthatthesamekeycanbeusedasinputkeyforothergarbledcircuitsthataregeneratedlater.
)Thisobservationallowsustoexecutegarbledcircuitsin"parallel"or"sequentially"wheresomelabelsarere-used.
Indeed,thisobservationisimplicitlyusedinclassicgarbledcircuitsingateswherethefan-outisgreaterthan1:alloutgoingwiressharethesamelabels(seee.
g.
Footnote8inLindell-Pinkas[19]).
Lemma1.
SupposeCandCaretwocircuitsandsupposethereissomeinputxforwhichwewanttocomputeC(x)andC(x)(resp.
C(C(x))).
Supposethewiresw0,wn9inCrepresenttheinputwiresforxandsimilarlydenew0,wnrepresentthein-putwiresofxinC(resp.
v0,vnbetheoutputwiresofC).
Letkbwirepresentthelabelindicatingwirewi=b,andletCandCberandomlygarbledintoGC(C)andGC(C)undertherestrictionthatkbwi=kbwi(resp.
kbwi=kbvi).
Thenthetuple(GC(C),GC(C),{kxiwi}ni=0)canbecomputationallysimulated.
Proof.
ConsiderthecompositecircuitD=C||C(resp.
E=CC)whichisjustacopyofCandacopyofCinparallel(resp.
sequence).
TheneverygarblingofDinducesagarblingofCandCwiththerestrictionexactlyasabove.
Bythesecurityofgarbledcircuits,thereexistsasimulatorthatcansimulate(GC(D),{kxiwi}ni=0).
WecanconstructasimulatorforourlemmabysimplytakingthissimulatorandtakingtheoutputandseparateoutGC(C)andGC(C),asthelemmarequires.
Remark:IfthedataisencryptedbitbybitusingYao'skeys,Lemma1allowsustorunarbitrarygarbledcircuitsonthisdata,akintogeneralpurpose"functionevaluation"onencrypteddata.
Thisobservationitselfhasanumberofapplications,wedescribetheseinthefullversionofthepaper.
3Non-interactiveGarbledRAMPrograms3.
1InformaldescriptionofmainideasWeconsidertheRAMmodelofcomputationasintheworksof[11,23,24]whereaRAMprogramalongwithdataisstoredinmemory,andasmall,statefulCPUwithaO(1)instructionsetthatcanstoreO(1)wordsthatcanbeofsizepolylog(n)=poly(k)wherekisthesecurityparameter.
OurstartingpointisaORAMmodelthatcantoleratefullymalicioustamperingadversary(see[24,11]).
EachstepoftheCPUissimplyaread/writecalltomainmemoryfollowedbyexecutingitsnextCPUinstruction.
WenowsummarizeourideasforbuildingGarbledRAMprogramsfromanObliviousRAMprogram.
InordertogarbleaRAMprogramπt,weconsiderthetwofundamentalopera-tionsseparatelyandshowhowtomeshthemtogether:1)Read/Write(v,x)from/tomemory.
2)Executeaninstructionsteptoupdatestateandproducenextread/writequery:Σ,READ/WRITE(v,x)←CPU(Σ,x).
Updatingthestatecanincludeup-datinglocalregisters,incrementingprogramcountersandquerycounters,andupdatingcryptographickeys.
Ourgoalistotransformthisintoanon-interactiveprocessbylettingtheclientsendtheserverenoughgarbledinformationtoevaluatetheprogramuptotsteps,wheretupperboundstheRAMprogramrunningtime.
Wegivesomeintuitionastohowtocon-structacircuitforeachstep,andthenhowtogarblethem.
TherstpartwillbemodeledasthecircuitCORAM,andthesecondpartwillbemodeledasthecircuitCCPU.
Thecir-cuitssatisfyanovelproperty:theplaincircuitCORAMemulatesaqueryfortheORAMclientandoutputsabitrepresentationofagarbledcircuitGCORAM.
ThisGCORAMhasoutputencodingsthatwillbecompatiblewiththegarbledcircuitGC(CCPU)toevaluateagarbledtheCPU'snextstep.
WeremarkthatGCORAMactuallycontains10severalsub-circuits,butiswrittenasasingleobjectforeaseofexposition.
Ifwegener-atetofthesegarbledcircuits,thenapartycanevaluateat-timegarbledRAMprogrambyconsumingonegarbledCORAMandonegarbledCCPUpertimestep.
WerstconsiderthecircuitCCPU,whichisstraightforwardtodescribe.
ThiscircuittakesasinputΣrepresentingtheinternalstateoftheCPU,andxthelastmemorycontentsread.
RecallthattheCPUperformsastepCPU(Σ,x)andupdatesthestatetoΣandgivesthenextread/writequerytomemorylocationvandcontentsx.
Inordertoturnthisintoacircuit,wecansacricesomeefciencyandhavea"universal"instructioninwhichweruneveryatomicinstruction(fromitsconstantsizedinstructionset)andsimplymultiplextheactualresultsusingtheinstructionopcode.
ThisuniversalinstructionismodeledasacircuitwhichisofsizekO(1).
Weremarkthatalthoughthiscircuitissimple,thecomplexityarisesfromwhenwewanttogarblethiscircuit:thegarblingmustbedoneinawaysothatthegarbledinputsandoutputsarecompatiblewithGCORAM.
ThecircuitCORAMmustemulatetheclientinObliviousRAM(wecanthinkofitasbeinganon-interactiveclienteitherbybreakingouteachindividualstepasaseparatecircuit,orusinganon-interactiveORAM).
TheinputofthecircuitisjustanORAMread/writequery5,andtheoutputofthecircuitisabitrepresentationthatdescribesasetofgarbledcircuits,equivalenttowhatwouldhavebeenproducedviatheORAMclientwhichwecallGCORAM.
WegivefulldetailsontheconstructioninSection3.
2.
ItisimportantthatwearguethattheresultofthisfetchcanbecombinedwiththeevaluationoftheCPUstep.
ObservethatsincethelabelsinourORAMaregeneratedaspseudo-randomtime-labeledencodings,soweknowaheadoftimeonlytheencodingoftheoutput(butknowneithertheinputnoroutput)ofthei-thinvocationoftheORAM.
ThuswhengarblingCCPU,theinputencodingsuseexactlytheoutputencodingsfromtherespectiveoutputsoftheORAM.
RecallinourORAMprotocoltheserversendsbacktheencodedoutputtotheclient;here,wedonotsenditback,andinsteadkeeptheresultanduseitasinputinthenextCPUstep(whichissecureandcorrectviaLemma1).
Then,puttingitalltogether,togarbleaRAMprogramπtthatrunsintimet,theprogramgarblingalgorithmGgeneratestgarbledCORAMandCCPUcircuits,andalsoencodestheinitialstateΣ0oftheCPUwiththeprograminitialized,counterssettozero,andwithfreshcryptographickeys.
ThefullconstructionofGisgiventhenextsection,Section3.
2.
3.
2MainConstructionofGarbledProgramsWerstdescribehowtoconstructthealgorithmsG,GI,GE.
Givenaprogramπtrun-ningintimet,wedescribethealgorithmGthatconvertsitintoagarbledprogramΠt.
Inordertodoso,wefollowthetwostepsoutlinedaboveandweconsidertheconstruc-tionofacircuitthatperformsanORAMqueryCORAMandacircuitthatrunsoneCPUstepCCPU.
5SincetheORAMclientusesrandomnessaswellastime-labeledencodings(whichareoutputsofthePRF),wewillallowthesetobeinputstoCORAM,sothattheymaybepre-computed"forfree"ratherthancomputedviathecircuit.
Thecircuitconsumestheseinputsinordertogeneratetheoutputgarbledcircuitwithouthavingtoevaluatetheseitself.
11OurgarblingalgorithmGwillprovideenoughgarbledcircuitstoexecutetstepsofaprogramπt.
EachstepisagarbledRAMquery(doneobliviouslyviaORAM)followedbyagarbledCPUcomputation.
ItstartswithagarbledencodingoftheinitialstateΣ0oftheCPUwiththeprogramπtinitialized,counterssettozero,andwithfreshcryptographickeys.
Foreachofthettimesteps,itcreatesagarbledGC(CORAM)foraread/writeofthattimestep,thenagarbledGC(CCPU)toperformaCPUstep.
WeshowhowtoconstructCORAMandCCPUsuchthattheycanbegarbledandinterleaved.
Wewillshowthatthisgarblingisindependentoftheactualprogrampath,regardlessofwhatmemorylocationshavebeenfetched,andiscorrectandsecure.
First,wedescribeCORAMtomimicanobliviousread/writeaccesstomainmem-ory.
Forthis,itcanjustperformthestepsinourObliviousRAM,withonedifference:Gdoesnotknowaheadoftimewhichmemorylocationwillbeused.
Hence,inordertoovercomethis,thecircuitCORAMmusttakeamemorylocationasinputandinter-nallyformulatewhattheORAMclientcomputes.
CORAMoutputswhatthe"virtual"ORAMclientwouldhavesenttotheserver:agarbledcircuitGCORAMrepresentingaread/writequery.
ThenoveltyinthisconstructionisthatwhenwefeedamemorylocationvintoCORAM,theoutputpreciselyisagarbledORAMread/writequeryrel-ativetothatmemorylocation.
Inordertohidev,bothCORAMandvaregarbledintoGC(CORAM)andVrespectively,andbythecorrectnessofgarbledevaluation,theout-putisstillGCORAM.
BythesecurityoftheunderlyingORAM,thisoutputGCORAMcanactuallybesimulated.
Althoughitisacircuitthatoutputsanothercircuit,thereisnocircularityinthisconstruction:givenaquerylocationandsomexedrandomness,thebehavioroftheORAMclientiscompletelydeterministic,straight-line,andtakeskO(1)·polylog(n)steps,sotheoutputcanberepresentedbyacircuitalsoofthatsize.
ThisORAMclientisindependentofthemainprogramCPUwhichonlyusesORAMasan"oracle".
Weemphasizethisagain,becauseGwillmostlikelyberanbyaclient,GdoesnotplaytheroleoftheORAMclientbutratheremulatestheORAMclientviaCORAM,sothisisnotaclientattemptingtocaptureitsownlogicinacircuit.
WeprovideapseudocodedescriptionofCORAMinFigure1.
Lookingahead,GwillgarblethiscircuitandensurethattheoutputofanORAMqueryhasthesameencodingasthatusedtogarbleCCPU.
ThealgorithmGcanthengarblebothCCPUandCORAMaheadoftime,withouthavingtoknowthememorylocation.
Next,weconsiderbuildingthecircuitwhichperformsasingleCPUstepintheRAMprogram,CCPUthatissupposedtoperformΣ,READ/WRITE(v,x)←CPU(Σ,x).
Inordertohidewhichinstructionisbeingexecuted,webuildthecircuittotakeaninstructionopcodeandweruneverysingle-stepinstructionfromitsconstantsizedin-structionset(notallpossibleprogrampaths)oftheCPU.
Thecircuitmultiplexestheactualresultsusingtheinstructionopcode.
ThisuniversalinstructionismodeledasacircuitwhichisofsizekO(1)andisindependentoftheORAMcircuit,independentofthequeriedlocations,andindependentofthecurrentrunningtime.
Onemayaskthequestion:HowcanthiscircuitbeinterleavedwiththeCORAMcircuitifitisindependentofit12Inputs:AnORAMquerytoread/write(v,x)andaquerynumber.
Thiscircuitinterpretstheclientperformingthe-thORAMquery,whichusesrandomnessandtime-labeledencodingsbasedon.
Assuch,thiscircuitalsotakestheserandomnessbitsandpre-computedencodingsasinputs.
Output:AgarbledcircuitGCORAMrepresentingaread/writeORAMquery.
CircuitDescription:WedescribethefunctionalityofthecircuitCORAM.
WerecallouralgorithmforaORAMquery.
Usingtime-labeledencodingsviaPRFs,itgeneratesasetof|B1|+2L2garbledGC(Cmatch)whichhashard-codedlocationinformationbuiltintoit,withcorrespondinggarbledGC(Cnext)circuits,andonenalGC(Cwrite)garbledcircuitforwritingtheelementbacktothetoplevel(andpossiblyanupdatecircuit).
AlthoughtheORAMclientevaluatesthesePRFsinternally,wedonotencodethisaspartofourcircuitCORAM,butratherwe"consume"themasinput.
Similarly,theORAMclientmustuserandomness,whichwealsoconsumefromtheinputofCORAM.
1.
Forthetoplevel,B1,foreachbucket,CORAMcreatesatime-labeledgarbledcircuitGC(Cmatch)consumingtheinputencodingstobeusedasgarbledlabels.
2.
Forsubsequentlevelsi=2.
.
.
L:(a)ThecircuitCORAMcomputesq0i=hi(v)andconsumesq1ifromtheinput(theinputitselfisuniformlyrandom)(b)Consumetwosecretkeysforencryptionsk0iandsk1ifromtheinputandcreateagarbledcircuitGC(Cnext)(c)Createtwotime-labeledgarbledcircuitsGC(Cmatch),onethatsearchesforwinbucketq0iencryptedundersk0i,andonethatsearchesforwinbucketq1iencryptedundersk1i,againconsumingtheencodingfromtheinputtoCORAM.
3.
CORAMalsocreatesagarbledGC(Cwrite)thatwritestheresultbacktotherstemptypositionthetoplevelbufferBk.
4.
Ifisamultipleof|B1|,thenareshufestepisperformedusingthetime-labeledgarbledupdatecircuitGC(Cupdate).
5.
ThecombinedsetofgarbledcircuitsisreferredtoasGCORAM.
Wepointoutthatthroughoutthisentireprocess,everytimeaquerycircuitiscreated,Gincre-mentsinordertokeeptrackofthetime-labeledencodingsrequiredbytheCORAMcircuits.
Fig.
1.
TheORAMClientCircuitCORAMTheansweristhatwhenGgarblesCCPU,theencodingwilldependontheoutputofCORAMintheprevioustime-step.
Notethatthisconstructionisnotcircularaseachgarblingonlydependsonthepreviousone,leadinguptoatotalofttimesteps.
ThiscanbedonebecauseGknowstheencodingoftheoutputencoding(butnottheoutput)oftheObliviousRAMquery,whichdoesnotdependonthelocationqueried.
ThisoutputencodingisthenusedfortheinputparameterencodingforGC(CCPU).
WeprovideapseudocodedescriptionofGinFigure2.
ThealgorithmGIforgarblinganinputofsizenisjustthetime-labeledencodingsstartingfromwherevertheRAMprogramexpectstheinputstobelocated.
ThealgorithmGEusedtoevaluateagarbledprogramΠtongarbledinputsevalu-atesthegarbledcircuitGC(CORAM),thenexecutingthegarbledinstructionGC(CCPU)oneatatime,uptottimes.
TheprocessispreciselyperformingthesamestepsasG13Inputs:Aprogramπtwithanupperboundonrunningtimet,andapseudo-randomfunctionfamilyFalongwithakeys.
AlgorithmDescription:ThealgorithmGisperformedasfollows.
ItcreatesanencodingoftheinitialstateoftheCPU,Σ0withtheprogramπtinitialized.
Italsoencodesaninitialprogramcounterandcryptographickeys.
WeshowhowtoconstructCORAMandCCPUsuchthattheycanbegarbledandinterleavedacrossttimesteps.
Wemustarguethatthisgarblingisindependentoftheactualprogrampath,regardlessofwhatmemorylocationshavebeenfetched,andiscorrectandsecure.
Foreachtimestepi=1.
.
.
t,Gcreates:1.
Agarbledread/writequerycircuitGC(CORAM)forperformingquerynumberionsome(unknownvariable)garbledlocationVi(andXiinthecaseofawrite).
Gpre-computesrandomnessandPRFevaluationsandhardwiresthem.
AlthoughGdoesnotknowtheeventualoutput,itknowstheencodingofit,whichisindependentofthequeriedlocation.
Itusesthisencodingforthefollowing:2.
AgarbledinstructioncircuitGC(CCPU)withinputwiresofXiusingtheencodingfromabove,andtheinputwiresofΣiusingtheoutputencodingfromthepreviousCPUstep.
TheoutputisagarbledlocationVi+1(andXi+1inthecaseofawrite)tobeusedinthenextread/writequeryandangarbledupdatedstateΣi+1.
Fig.
2.
ProgramGarblingAlgorithmGexceptevaluatinggarbledcircuitsinsteadofgeneratingthem.
Inaddition,onceitgetsthegarbledORAMquery,itmustalsoexecuteitaswell.
WeprovideapseudocodedescriptionofGinFigure3.
Inputs:AgarbledprogramΠtwithgarbledinputX.
AlgorithmDescription:ThealgorithmGEisperformedasfollows.
Itrststorestheinitialencodedprogramstateandinputsintomemory.
Then,foreachtimestepi=1.
.
.
t,GEperforms:1.
EvaluatethegarbledquerycircuitGC(CORAM)onagarbledmemorylocationVi.
TheoutputisGCORAMwhichitselfisagarbledcircuitthatrepresentsaread/writequeryinourORAMprotocol.
ExecutethequeryplayingtheroleoftheservertoobtainsomegarbledoutputXiwhichiskeptlocallyinsteadofsenttotheclient.
2.
EvaluatethegarbledinstructioncircuitGC(CCPU)ongarbledinputsXiandΣi.
Obtainanewread/writequeryVi+1.
Aftertsteps,outputthenalvalueXt+1.
Fig.
3.
GarbledProgramEvaluationAlgorithmGE3.
3MainResultWenowstateourmainresult:14Theorem1.
Assumeone-wayfunctionsexist,andletthesecurityparameterbekandletFbeaPRFfamilybasedontheone-wayfunction.
Then,thereexistsanefcientProgramGarblingtripleofalgorithmsG,GI,GEsuchthatforanyπtanytandanyinputxoflengthn,wehavethefollowing.
Correctness:x,πt,F,s:πt(x)=GE[G(πt,t,F,s),GI(x,s)].
Security:poly-timesimulatorSim,suchthatπ,t,x,s,where|s|=k[G(πt,t,F,s),GI(x,s)]≈Sim1k,t,|x|,πt(x).
ProgramSize:Thesizeofthegarbledprogram|G(πt,t,F,s)|=O(|π|+t)·kO(1)·polylog(n).
InputSize:Let|x|=nand|s|=k.
x,sthegarbledinputsize|GI(x,s)|=On·kO(1)·polylog(n).
Proof.
Wegiveanoutlineoftheproofofsecurity,andreferthereadertothefullver-sion[20]forthefullproofs.
Security.
WedesignthesimulatorSimasfollows.
Weknowthattheserverperformsthefollowing:1.
EvaluatethegarbledquerycircuitGC(CORAM)onagarbledmemorylocationVi.
TheoutputisGCORAMwhichitselfisagarbledcircuitthatrepresentsaread/writequeryintheunderlyingORAM.
2.
ExecutethegarbledORAMqueryGCORAMplayingtheroleoftheservertoobtainsomegarbledoutputXiwhichiskeptlocallyinsteadofsenttotheclient.
3.
EvaluatethegarbledinstructioncircuitGC(CCPU)ongarbledinputsXiandΣi.
Obtainanewread/writequeryVi+1.
TheunderlyingObliviousRAMissecureandusestime-labeledgarbledcircuitsandencodingsandcanbesimulatedbysomeSimORAM.
Furthermore,theunderlyingYao'sgarbledcircuitsaresecure,andcanbesimulatedbysomeSimYao.
Thus,theaccesspatternoftheORAMcanbesimulatedevenfortamperingadversary,andweneedonlyshowthatthegarbledcircuitemulatingtheORAMclientGC(CORAM)andgarbledinstructionsGC(CCPU)canalsobesimulated.
ThegarbledcircuitscanbeinterleavedsecurelyduetoLemma1,andthetime-labeledencodingsthemselvesarejustoutputsofaPRF.
BythesecurityofYao'sgarbledcircuitsandtheunderlyingPRF,thesecanbesimulatedsecurely.
4ApplicationtoSecureRAMComputationWegiveanexampleapplicationinwhichonlyonepartyhasinputandwantstore-peatedlyrunprogramsonthisdata.
Suchisthecaseofsecurecloudcomputing,wheresomeonestoresdatainthecloudandthenlaterrunscomputationsagainstthatdata.
Weemphasizethatinthissetting,thereisnoissueofadaptivitybecausetheserverhasnoinputs.
Inthetypicalsettingoftwo-partysecurecomputation,wedealwiththisbymakingtheserverrstperformOTstoretrieveitsinputsbeforetheclientsendsthe15garbledprogram.
Inthemulti-partysetting,thetechniquecanbeutilizedintheBeaver-Micali-Rogawayparadigm[2]toachieveconstant-roundMPCwiththesameapproachasin[2]butwithgarbledRAMprograms.
Thatistosay,inthisapplication,aclientwishestostoresomedataxonaremoteserverandthenrunvariousRAMprogramsonxwithouttheserverlearningtheresultsoftheprogramsorxitself.
Ofcourse,theclientcouldalwaysignoretheserveraltogetherandrunalltheprogramsonxlocally,soweareenvisioningascenarioinwhichtheclientdoesnotwanttocarryaroundallofitsdatalocallyandwantstoonlystoreafewcryptographickeysorcounters.
ToapplyGarbledRAMprogramstothisapplication,theclientrstgarblestheinputxtogetX=GI(x)andsendsittotheserver.
Thenforeachprogramtheclientwantstorun,itrecallstheencodingofthepreviousoutputandcreatesagarbledprogramusingthelabelsofthepreviousoutputasinputsforthecurrentprogram.
5ConclusionsandOpenProblemsRecently,Goldwasserat.
al.
[12]haveshownhowtoconstructareusableGarbledYao.
ItistemptingtoplugitintoourconstructiontoachievereusableGRAMwithcompact-nessproportionaltoprogramsizeandindependentofitsrunningtime.
Theideaistocomputepoly-manyiterationsoftheCPUcomputationusingreusableYao(insteadofsendingfreshgarbledcircuitforeachCPUstep)whereCPUcomputesitsowngarbledkeysforeachstep.
Thisispossibleonlyifthereexistspoly-timereusablecircular-secureGarbledYaowithinputencodingofsizeindependentofthecircuitsize.
Constructingsuchagadgetisaninterestingopenproblemevenundernon-standardassumptions.
6AcknolwedgementsWethankOdedGoldreichandDanielWichsforveryhelpfuldiscussionsandtheanony-mousreviewersfortheircomments.
16References1.
BennyApplebaum,YuvalIshai,andEyalKushilevitz.
Fromsecrecytosoundness:Efcientvericationviasecurecomputation.
InICALP(1),pages152–163,2010.
2.
DonaldBeaver,SilvioMicali,andPhillipRogaway.
Theroundcomplexityofsecureproto-cols(extendedabstract).
InSTOC,pages503–513,1990.
3.
MihirBellare,VietTungHoang,andPhillipRogaway.
Adaptivelysecuregarblingwithapplicationstoone-timeprogramsandsecureoutsourcing.
InASIACRYPT,pages134–153,2012.
4.
MihirBellare,VietTungHoang,andPhillipRogaway.
Foundationsofgarbledcircuits.
InACMConferenceonComputerandCommunicationsSecurity,pages784–796,2012.
5.
DanBoneh,EyalKushilevitz,RafailOstrovsky,andWilliamE.
SkeithIII.
Publickeyen-cryptionthatallowsPIRqueries.
InCRYPTO,pages50–67,2007.
6.
DanBoneh,DavidMazieres,andRalucaAdaPopa.
Remoteobliviousstorage:MakingobliviousRAMpractical.
CSAILTechnicalReport,MIT-CSAIL-TR-2011-018,2011.
7.
NishanthChandran,RafailOstrovsky,andWilliamE.
SkeithIII.
Public-keyencryptionwithefcientamortizedupdates.
InSCN,pages17–35,2010.
8.
StephenA.
CookandRobertA.
Reckhow.
Timeboundedrandomaccessmachines.
JournalofComputerandSystemSciences,7(4):354–375,1973.
9.
OdedGoldreich.
TowardsatheoryofsoftwareprotectionandsimulationbyobliviousRAMs.
InSTOC,pages182–194,1987.
10.
OdedGoldreich,SilvioMicali,andAviWigderson.
Howtoplayanymentalgameoracompletenesstheoremforprotocolswithhonestmajority.
InSTOC,pages218–229,1987.
11.
OdedGoldreichandRafailOstrovsky.
SoftwareprotectionandsimulationonobliviousRAMs.
J.
ACM,43(3):431–473,1996.
12.
ShaGoldwasser,YaelKalai,RalucaAdaPopa,VinodVaikuntanathan,andNickolaiZel-dovich.
Succinctfunctionalencryptionandapplications:Reusablegarbledcircuitsandbe-yond.
CryptologyePrintArchive,Report2012/733,2012.
13.
MichaelT.
GoodrichandMichaelMitzenmacher.
Privacy-preservingaccessofoutsourceddataviaobliviousRAMsimulation.
InICALP,pages576–587,2011.
14.
MichaelT.
Goodrich,MichaelMitzenmacher,OlgaOhrimenko,andRobertoTamassia.
ObliviousRAMsimulationwithefcientworst-caseaccessoverhead.
InCCSW,pages95–100,2011.
15.
MichaelT.
Goodrich,MichaelMitzenmacher,OlgaOhrimenko,andRobertoTamassia.
Privacy-preservinggroupdataaccessviastatelessobliviousramsimulation.
InSODA,pages157–167,2012.
16.
S.
DovGordon,JonathanKatz,VladimirKolesnikov,FernandoKrell,TalMalkin,MarianaRaykova,andYevgeniyVahlis.
Securetwo-partycomputationinsublinear(amortized)time.
InACMConferenceonComputerandCommunicationsSecurity,pages513–524,2012.
17.
YuvalIshaiandEyalKushilevitz.
Personalcommunication,2012.
18.
EyalKushilevitz,SteveLu,andRafailOstrovsky.
Onthe(in)securityofhash-basedobliviousRAMandanewbalancingscheme.
InSODA,pages143–156,2012.
19.
YehudaLindellandBennyPinkas.
Aproofofsecurityofyao'sprotocolfortwo-partycom-putation.
J.
Cryptology,22(2):161–188,2009.
20.
SteveLuandRafailOstrovsky.
HowtogarbleRAMprograms.
CryptologyePrintArchive,Report2012/601,2012.
21.
SteveLuandRafailOstrovsky.
Distributedobliviousramforsecuretwo-partycomputation.
InTCC,pages377–396,2013.
22.
MoniNaorandKobbiNissim.
Communicationpreservingprotocolsforsecurefunctionevaluation.
InSTOC,pages590–599,2001.
1723.
RafailOstrovsky.
EfcientcomputationonobliviousRAMs.
InSTOC,pages514–523,1990.
24.
RafailOstrovsky.
SoftwareProtectionandSimulationOnObliviousRAMs.
PhDthesis,Mas-sachusettsInstituteofTechnology,Dept.
ofElectricalEngineeringandComputerScience,June1992.
25.
RafailOstrovskyandVictorShoup.
Privateinformationstorage(extendedabstract).
InSTOC,pages294–303,1997.
26.
BennyPinkasandTzachyReinman.
ObliviousRAMrevisited.
InCRYPTO,pages502–519,2010.
27.
NicholasPippengerandMichaelJ.
Fischer.
Relationsamongcomplexitymeasures.
J.
ACM,26(2):361–381,1979.
28.
ElaineShi,T.
-H.
HubertChan,EmilStefanov,andMingfeiLi.
ObliviousRAMwithO((logN)3)worst-casecost.
InASIACRYPT,pages197–214,2011.
29.
EmilStefanov,ElaineShi,andDawnSong.
TowardspracticalobliviousRAM.
InNDSS,2012.
30.
DanielWichs.
PersonalCommunication.
March2013.
31.
PeterWilliamsandRaduSion.
SingleRoundAccessPrivacyonOutsourcedStorage.
InACMCCS,pages293–304,2012.
32.
PeterWilliams,RaduSion,andBogdanCarbunar.
Buildingcastlesoutofmud:practicalac-cesspatternprivacyandcorrectnessonuntrustedstorage.
InACMConferenceonComputerandCommunicationsSecurity,pages139–148,2008.
33.
AndrewChi-ChihYao.
Protocolsforsecurecomputations(extendedabstract).
InFOCS,pages160–164,1982.