ABSTRACT Secure Function Evaluation with Ordered Binary Decision Diagrams

LouisKrugerandSomeshJha

UniversityofWisconsin-Madison

Eu-JinGohandDanBoneh

StanfordUniversity

[lpkruger,jha]@cs.wisc.edu[eujin,dabo]@cs.stanford.edu

ABSTRACT

Privacy-preservingprotocolsallowmultiplepartieswithpri-vateinputstoperformjointcomputationwhilepreservingtheprivacyoftheirrespectiveinputs.Animportantcryp-tographicprimitivefordesigningprivacy-preservingproto-colsissecurefunctionevaluation(SFE).TheclassicsolutionforSFEbyYaousesagaterepresentationofthefunctionthatthetwopartieswanttojointlycompute.FairplayisasystemthatimplementstheclassicsolutionforSFE.Inthispaper,wepresentanewprotocolforSFEthatusesagraph-basedrepresentationofthefunction.Specificallyweusethegraph-basedrepresentationcalledorderedbinaryde-cisiondiagrams(OBDDs).ForalargenumberofBooleanfunctions,OBDDsaremoresuccinctthanthegate-basedrepresentation.Preliminaryexperimentalresultsbasedonaprototypeimplementationshowsthatforseveralfunctions,ourprotocolresultsinasmallerbandwidththanFairplay.Forexample,fortheclassicmillionaire’sproblem,ournewprotocolresultsinaapproximately45%bandwidthreduc-tionoverFairplay.Therefore,ourprotocolswillbepartic-ularlyusefulforapplicationsforenvironmentswithlimitedbandwidth,suchasapplicationsforwirelessandsensornet-works.

CategoriesandSubjectDescriptors

C.2.0[Computer-CommunicationNetworks]:SecurityandProtection

GeneralTerms

Security,Algorithms,Theory

Keywords

BinaryDecisionDiagrams,SecureFunctionEvaluation

1.INTRODUCTION

TheeaseandtransparencyofinformationflowontheIn-ternethasheightenedconcernsofpersonalprivacy[10,25].

Permissiontomakedigitalorhardcopiesofallorpartofthisworkforpersonalorclassroomuseisgrantedwithoutfeeprovidedthatcopiesarenotmadeordistributedforprofitorcommercialadvantageandthatcopiesbearthisnoticeandthefullcitationonthefirstpage.Tocopyotherwise,torepublish,topostonserversortoredistributetolists,requirespriorspecificpermissionand/orafee.

CCS’06,October30–November3,2006,Alexandria,Virginia,USA.Copyright2006ACM1-59593-518-5/06/0010...$5.00.

VariousInternetactivities,suchasWebsurfing,email,andotherservicesleaksensitiveinformation.Asaresult,therehasbeeninterestindevelopingtechnologies[9,13,24]andprotocolstoaddresstheseconcerns.Inparticular,privacy-preservingprotocols[11,12,18,20]thatallowmultiplepar-tiestoperformjointcomputationswithoutrevealingtheirprivateinputshavebeenthesubjectofmuchinterest.Ourfocusinthispaperisontwopartyprivacy-preservingpro-tocols.

Oneofthefundamentalcryptographicprimitivesforde-signingprivacy-preservingprotocolsissecurefunctioneval-uation(SFE).AprotocolforSFEenablestwopartiesAandBwithinputsxandyrespectivelytojointlycomputeafunc-tionf(x,y)whilepreservingtheprivacyofthetwoparties(i.e.,attheendoftheprotocol,partyAonlyknowsitsinputxandthevalueofthefunctionf(x,y),andsimilarlyforB).Yaoshowedthatforapolynomial-timecomputablefunctionf,thereexistsaSFEprotocolthatexecutesinpolynomialtime[15,27](detailsaboutthisprotocolcanbefoundinGoldreich’sbook[14,Chapter7]).Yao’sclassicsolutionforSFEhasbeenusedtodesignprivacy-preservingprotocolsforvariousapplications[1].TheimportanceofYao’spro-tocolspurredresearcherstodesignacompilerthattakesadescriptionofthefunctionfandemitscodecorrespondingtoYao’sprotocolforsecureevaluationoff.Suchcom-pilers,forexampleFairplay[22],enablewiderapplicabilityofSFE.MacKenzieetal.[21]implementedacompilerforgeneratingsecuretwo-partyprotocolsforarestrictedbutimportantclassoffunctions,whichisparticularlysuitedforapplicationswherethesecretkeyisprotectedusingthresh-oldcryptography.Formostapplications,theclassicprotocolforSFEisquiteexpensive,whichhasledresearcherstode-velopmoreefficientprivacy-preservingprotocolsforspecificproblems[11,12,18,20].

IntheclassicSFEprotocol,thefunctionfisrepresentedascircuitcomprisedofgates.Fairplayusesthiscircuitrep-resentationoff.OrderedBinaryDecisionDiagrams(OB-DDS)areagraph-basedrepresentationofBooleanfunctionsthathavebeenusedinavarietyofapplicationsincomputer-aideddesign,includingsymbolicmodelchecking(atech-niqueforverifyingdesigns),verificationofcombinationallogic,andverificationoffinite-stateconcurrentsystems[3,7].OBDDscanbereadilyextendedtorepresentfunctionswitharbitrarydomainsandranges.

GivenanOBDDrepresentationofthefunctiontobejointlycomputedbythetwoparties,Yao’sprotocolcanbedirectlyusedbyfirstconvertingtheOBDDintoacircuit.Convert-inganOBDDtoacircuit,however,incursablow-upin

410

thenumberofgatesrequired.Toempiricallymeasurethisblowup,weimplementedacompilerthattakesanOBDDandconvertsitintoacircuitdescriptionthatcanbeusedinFairplay.Ontheaverage,thisconversionfromOBDDtocircuitresultedinaincreaseinsizebyafactorof10.DetailsofthisexperimentcanbefoundinSection4.

Inthispaper,wepresentaSFEalgorithmthatdirectlyusesanOBDDrepresentationofthefunctionfthatthetwopartieswanttojointlycompute.TheadvantageofusinganOBDDrepresentationoverthegate-representationisthatOBDDsaremoresuccinctforcertainwidelyusedclassesoffunctionsthanthegaterepresentation.Forexample,amongotherfunctions,ourresultsshowtheOBDDrepresentationismoreefficientthanthegaterepresentationfor8-bitAND,8-bitaddition,andthemillionaire’sandbillionaire’sprob-lems[27].Asaresult,ourprotocolhasreducedbandwidthconsumptionovertheclassicYaoprotocolimplementedinFairplay.Becauseprocessorspeedshaveincreasedatamorerapidpacethanbandwidthavailabilityoverthepastyears,networkbandwidthislikelytobethebottleneckforanum-berofapplications.Inparticular,ourprotocolsareespe-ciallyusefulforapplicationsoperatingovernetworkswithlimitedbandwidth,suchaswirelessandsensornetworks.Furthermore,wehaveempiricallyconfirmedthisstatementbyimplementingourprotocolandcomparingitwithFair-play.

Thispapermakesthefollowingcontributions:•WepresentaSFEprotocolthatusestheOBDDrepre-sentationofthefunctiontobejointlycomputedbytwoparties.OurnewprotocolalongwiththecorrectnessproofisprovidedinSection3.•Experimentalresultsbaseduponaprototypeimple-mentationofourprotocoldemonstratethatforcer-tainfunctions,ourimplementationresultsinasmallerencryptedcircuitthanFairplay.Forexample,fortheclassicmillionaire’sproblem,ourimplementationre-ducesthebandwidthbyapproximately45%overFair-play.OurimplementationandexperimentalresultsaredescribedinSection4.Insummary,thispaperpresentsanewSFEprotocolthatusestheOBDDrepresentation.TheOBDDrepresenta-tionismoreefficientforseveralpracticalfunctionsofinter-est.Forotherfunctions,thecircuitdescription(andthere-foreFairPlay)willbemoreefficient.ThispaperpresentsagenericalternativetoBooleancircuitsthatcanbeusedwhenappropriate.

forf,denotedbyOBDD(f),isarooted,directedacyclicgraph(DAG)withtwotypesofvertices:terminalandnon-terminalvertices.OBDD(f)alsohasthefollowingcompo-nents:

•Eachvertexvhasalevel,denotedbylevel(v),between0andn.Thereisadistinguishedvertexcalledrootwhoselevelis0.•Eachnonterminalvertexvislabeledbyavariablevar(v)∈{x1,···,xn}andhastwosuccessors,low(v)andhigh(v).Eachterminalvertexislabeledwithei-ther0or1.ThereareonlytwoterminalverticesinanOBDD.Moreover,thelabelingofverticesrespectsthetotalorderingExample1.Figure1showstheOBDDforthefunctionf(x1,x2,x3,x4)=(x1=x2)∧(x3=x4)offourvariablesx1,x2,x3,x4withthetotalorderingx1OneoftheadvantagesofOBDDsisthattheycanbema-nipulatedefficiently,i.e.,givenOBDDsforfandg,OB-DDsforf∧g,f∨g,and¬fcanbecomputedefficiently.Wenowdescribeanoperationcalledrestriction,whichisusedinourprotocol.GivenanvariableBooleanfunctionf(x1,x2,···,xn)andaBooleanvalueb,f|xi←bisaBooleanfunctionofn−1variablesx1,···,xi−1,xi+1,···,xndefinedasfollows:

f|xi←b(x1,···,xi−1,xi+1,···,xn)isequalto

f(x1,···,xi−1,b,xi+1,···,xn).Essentiallyf|xi←bisthefunctionobtainedbysubstitutingthevaluebforthevariablexiinthefunctionf.GiventheOBDDforf,theOBDDforf|xi←bcanbeefficientlycomputed[3,Section4].Therestrictionoperationcanbeextendedtomultiplevariablesinastraightforwardmanner,e.g.,f|xi←b,xj←b󰀂canbecom-putedas(f|xi←b)|xj←b󰀂.Weexplainthealgorithmusingourexample;thereaderisreferredto[3]fordetails.Con-siderthefunctionf(x1,x2,x3,x4)describedinexample1.OBDDsaresensitivetovariableordering,e.g.,withtheorderingx11

2.

ORDEREDBINARYDECISIONDIAGRAMS(OBDDS)

Orderedbinarydecisiondiagrams(OBDDs)areacanon-icalrepresentationforBooleanformulas[3].Theyareoftensubstantiallymorecompactthantraditionalnormalforms,suchasconjunctivenormalform(CNF)anddisjunctivenor-malform(DNF),andtheycanbemanipulatedefficiently.Therefore,theyarewidelyusedforavarietyofapplicationsincomputer-aideddesign,includingsymbolicmodelcheck-ing,verificationofcombinationallogic,andverificationoffinite-stateconcurrentsystems[7].AdetaileddiscussionofOBDDscanbefoundinBryant’sseminalarticle[3].

GivenaBooleanfunctionf(x1,x2,···,xn)ofnvariablesx1,···,xnandatotalorderingonthenvariables,theOBDD

411

x1 1x2 1x3 0x4 10 0 0 0 1x4 11 1 0x2 0x2 1 0x4 10 01Figure2:OBDDfortherestrictionf|x1←1,x3←0wheref(x1,x2,x3,x4)=(x1=x2)∧(x3=x4).

Figure1:OBDDforthefunctionf(x1,x2,x3,x4)=(x1=x2)∧(x3=x4).

TheOBDDcorrespondingtof|x1←1,x3←0isshowninFig-ure2.Sincex1←1,therootofOBDD(f|x1←1,x3←0)istheleftvertexlabeledwithx2.Considerthetwoverticesv1andv2labeledwithx2.Ifv1hasanedgethatpointstothevertexlabeledwithx3,thenthatedgeischangedtopointtotherightvertexlabeledwithx4(becausethisisthever-texreachedifx3isequalto1).NoticethatinthereducedOBDDshowninFigure2theverticesthatarelabeledwithx1andx3havebeeneliminated.

Booleanvariablesx1,x2,···,xn.LetOBDD(f)denotetheOBDDforfwiththeorderingx13.TWOPARTYSFEWITHOBDDS

3.1Protocol1

Forthisprotocol,weassumethatAliceholdstheinputs(i1,...,ik)correspondingtothefirstkvariablesx1,...,xk,andBobhastheinputs(ik+1,...,in)correspondingtolastn−kvariablesxk+1,...,xn.Inourprotocol,AliceandBobwanttocomputef(x1,···,xn)ontheirinputsusingtheOBDDforf.Astheoutcome,Boblearnsf(i1,...,in).ThisprotocolisdescribedinFigure3.

Oneofthedifficultiesindevelopingandprovingthepro-tocolisthatOBDDsallowskippingoflevels.Forexam-ple,Figure4(a)showstheOBDDfortheBooleanfunctionx1∧x2.Assumethatthevertexatlevel0islabeledwithx1andverticesatlevel1arelabeledwithx2.SupposeAliceownsvariablex1andBobownsvariablex2.IfAlice’sinputis1,thenBobfollowsonemoreedgethanifAlice’sinputwere0,whichallowsBobtodetermineAlice’sinput.Com-parethistoFigure4(b),whereadummyvertexisaddedsothat,regardlessofAlice’sinput,Bobhastofollowthesamenumberofedges.Inthiscase,BoblearnsnothingaboutAlice’sinput.BeforeAlicegarblestheOBDDs,sheaddsdummyverticessothateachpathfromtheroottoatermi-nalnodehasthesamenumberofedges.AliceaddsdummynodeswheneverOBDD(f)allowsBobtoskiplevelswhenevaluatingtheOBDDonhisshareoftheinput.Recallthatthe0-successorand1-successorofvisdenotedbylow(v)

Forourprotocols,werequireasymmetricencryptionschemewithtwoeasilyattainedspecialproperties[19],whichare(1)elusiverange:anencryptionunderonekeyisintherangeofanencryptionwithadifferentkeywithnegligibleprob-ability,and(2)efficientlyverifiablerange:givenakey,ausercanefficientlyverifythataciphertextisintherangeofthatkey.Thesepropertiesarerequiredsothatthere-ceiverofthegarbledOBDDcancorrectlydecryptnodesintheOBDD.TheformaldefinitionofthesepropertiesbyLindellandPinkas[19]isprovidedwiththeproofs.Anexampleofasymmetrickeyencryptionschemethatful-fillsthesepropertiesisEk(m)=(r,fk(r)⊕m󰀓0n),wheref:{0,1}n×{0,1}n→{0,1}2nisapseudo-randomfunction

R

andr←{0,1}nisan-bitrandomsequence.Unlessstatedotherwise,allsymmetrickeyencryptionschemesinthispa-per,besidesbeingsemanticallysecure[14,Chapter5],alsorequirethesetwoproperties.

Ourprotocolalsousesa1-out-of-2oblivioustransfer(de-2k)protocol.A1-out-of-koblivioustransferOT1notedOT1

isaprotocolthatletsBobobtainoneofksecretsheldbyAlice,withoutAlicelearningwhichsecretBobobtains.

WenowgivetheprotocolforsecurelycomputinganOBDDbetweentwopartieswhereeachpartyholdsapartofthein-put.AssumefisaBooleanfunctionf(x1,x2,···,xn)ofn

412

Input:Bothparties’inputsincludetheOBDD(f)fortheBooleanfunctionf(x1,x2,···,xn)withtheorderingx11.Aliceperformsthefollowingsteps:

(a)ShetraversestheOBDD(f)usingherinput(i1,···,ik),whichresultsinanodevinitatlevelk.

101(b)Sheuniformlyandindependentlyatrandomcreates(n−k)pairsofsecrets(s01,s1),···,(sn−k,sn−k).Inaddition,

foreachnodevintheOBDD(f)whoselevelisbetweenkandn−1,Alicealsocreatesasecretsv.

(c)Sheassignsauniformlyrandomlabeltoeachnodewhoselevelisbetweenkandn.Werefertotherandomly

assignedlabelofnodevusingthenotationlabel(v).(d)Next,AliceaugmentsOBDD(f)withsomenumberofdummynodes(toensurethatBobalwaystraversesn−k

nodesinhisphaseoftheprotocol).(e)Alicegarblesallnodeswhoselevelisbetweenkandn−1inthefollowingmanner.LetvbeanodeinOBDD(f)

suchk≤level(v)≤n−1anddefinelevel(v)=󰀙.Theencryptionofnodev,denotedbyE(v),isalabelandarandomlyorderedciphertextpair

“”label(v),Esv⊕s0(label(low(v))󰀈slow(v)),Esv⊕s1(label(high(v))󰀈shigh(v)),

󰀉−k+1

󰀉−k+1

wherethelabelsarepre-pendedtothesecretwithaseparatorsymbolandtheorderoftheciphertextsisdetermined

byafaircoinflip.Roughlyspeaking,thesecretscorrespondingtothe0-successorand1-successorofnodevareencryptedwiththesecretcorrespondingtovanditslevel.

Notethatdummynodeshavethesamestructureasnormalnodes,exceptthattheciphertextpaircontainencryptionsofthesamemessagesincedummynodeshavethesame0and1-successors.Providedtheencryptionschemeissemanticallysecure,thisposesnoproblemsincethekeysarechosenuniformlyatrandom.

Lastly,therearetwoterminalnodesoftheform(b,label(tb))forb=0or1.RecallthatOBDD(f)hastwoterminalnodes,denotedas0and1,thatareatleveln.

(f)OnceAliceisdoneencrypting,shesendstoBobtheencryptionofallnodeswhoselevelisbetweenkandnand

thesecretsvinitcorrespondingtonodevinitatlevelk.WecalledthisthegarbledOBDD.2.Bobperformsthefollowingsteps:

(a)Heengagesinn−k1-out-of-2oblivioustransferstoobtainthesecretscorrespondingtohisinput.Forexample,

1ifhisinputijis0,thenheobtainsthe(level)secrets0j−k;otherwise,heobtainsthesecretsj−k.(b)NowBobisreadytostarthiscomputation.Supposeik+1=0.Withs01andsvinit,hedecryptsbothciphertexts

(v)initanddecideswhichgivesthecorrectresultbyusingtheverifiablerangepropertyoftheencryptioninE

scheme.Bobnowhasbothslow(v)(thesecretcorrespondingtothe0-successorofvinit)andlabel(low(v))(whichtellsBobwhichencryptednodeisusedtoevaluatehisnextinput).Continuingthisway,Bobeventuallyobtainsalabelcorrespondingtooneoftheterminalnodes,whichdeterminestheresultoftheOBDDonthesharedinputs.BobsendsthisresulttoAlice.

Figure3:Protocol1.

andhigh(v).Forexample,ifnodenatleveljhasnoden󰀆󰀆󰀆atlevelj+3asits0-successor,thenAliceinsertstwodummynodesn󰀆andn󰀆󰀆atlevelj+1andj+2respectively.The0-successorofnodenischangedton󰀆,both0and1-successorsofn󰀆aresetton󰀆󰀆,andboth0and1-successorsofn󰀆󰀆aresetton󰀆󰀆󰀆.

Weprovecorrectnessandsecurityinthecaseofsemi-honestparties.Inthesemi-honestmodel,bothpartiesareassumedtoperformcomputationsandsendmessagesac-cordingtotheirprescribedactionsintheprotocol.Theymayalsorecordwhatevertheyseeduringtheprotocol(i.e.theirowninputandrandomness,andthemessagestheyre-ceive).WereferreaderstoGoldreich’sbook[14]forthecom-pletedefinitions.Claim1provesthattheprotocolshowninFigure3iscorrect;thatis,Bobcomputesthefunctionf(i1,···,in).Claim2provesthatprotocol1issecureinthesemi-honestmodel;thatis,attheendofprotocol1,Aliceonlyknowsitsinputandthevalueofthefunctionf(i1,···,in),andsimilarlyforBob.Forourproofs,were-quirethedefinitionofelusiverangeandefficientlyverifiablerangefromLindellandPinkas[19].

Definition1.Let(G,E,D)beasymmetrickeyencryp-tionschemewithkey-generation,encryption,anddecryptionalgorithms.DenotetherangeoftheschemebyRangen(k)={Ek(x)}x∈{0,1}n.Wesaythat

1.(G,E,D)hasanelusiverangeifforeveryprobabilisticpoly-timemachineA,everypolynomialp(·),andallsufficientlylargen,Prk←G(1n)[A(1n)∈Rangen(k)]<1/p(n).2.(G,E,D)hasanefficientlyverifiablerangeifthereexistsaprobabilisticpoly-timemachineMsuchthatM(1n,k,c)=1ifandonlyifc∈Rangen(k).Claim1.Iftheencryptionschemehasanelusiverangeandtheoblivioustransferprotocolissecure,thenProtocol1iscorrectforsemi-honestAliceandBob.

Proof:FirstweshowthateverynodeinthegarbledOBDDsenttoBobcanbeevaluatedcorrectly.Foranencryptednodev,letc0andc1bethefirstandsecondciphertextterm.SupposekisthekeythatBobobtainstodecrypttheciphertextinnodev.BecausetheencryptionschemeiselusiveandallthekeysusedinthegarbledOBDDarechosenuniformlyandindependentlyatrandom,itfollows

413

x10 1x2 00 11x1 0x2 0 1 00 1 1x2x2x2x2x20Figure5(a)

0101Figure5(b)Figure5(c)

Figure5:OBDDrestriction

1Figure4(a)Figure4(b)

Figure4:Addingdummyvertices

immediatelythat,exceptwithnegligibleprobability,onlyoneciphertextinanencryptednodedecryptscorrectly;thatis,eitherc0∈Range(k)orc1∈Range(k)butnotboth.Hence,exceptwithnegligibleprobability,everynodeinthegarbledOBDDcanbeevaluatedcorrectly.

Byinduction,weshowthatthecorrectkeyisobtainedforeverynodeinputandoutput.Thebasecaseisthekeysvinit

i+1in

andthekeysskk

+1,...,sn(correspondingtoBob’sinput)

obtainedfromAlicethroughthen−koblivioustransfers.Theinductivestepatnodevassumesthatthecorrectlabel(pointingBobtonodev)andnodekeysvwasobtainedin

l

thepreviousstep.Furthermore,thecorrectlevelkeysilwasobtainedbyexecutinganoblivioustransferprotocol.SinceeverynodeinthegarbledOBDDcanbeevaluatedcorrectlyandthegarbledOBDDisbuiltbyasemi-honestAlice,Bobobtainsthecorrectlabelandkeyoutputatnodev,whichconcludestheinductivestep.WecanconcludethattheentiregarbledOBDDcanbeevaluatedtogivethecorrectresult.2󰀁Claim2.Iftheencryptionschemeissemanticallysecureandhasanefficientlyverifiableelusiverange,andtheobliv-ioustransferprotocolissecure,thenProtocol1issecureagainstsemi-honestAliceandBob.

ProofofthisclaimistediousandisgiveninAppendixA.

Input:Bothparties’inputsincludetheOBDD(f)fortheBooleanfunctionf(x1,x2,···,xn)withtheorderingx1(a)AlicecomputestheOBDDOAforthefunction

f|XA.Thisistherestrictionoperationde-scribedinSection2.(b)AliceencryptstheOBDDforthefunctionf|XA

andsendsittoBob.ThisstepisexactlythesameasforProtocol1describedinFigure3.AlicealsosendsthesecretcorrespondingtotherootoftheOBDDOA.2.ThecomputationforBobisexactlythesameasthatforProtocol1.

Figure6:Protocol2.

Figure5(a),whereAlice’svalueis0,thereareonly2nodes,butinFigure5(b),thereare3nodes.Figure5(c)showstheresultofretainingextravertices,inwhichcasethereare4nodesregardlessofAlice’sinputs.ThedescriptionofthisprotocolisgiveninFigure6.TheproofofcorrectnessofthisprotocolisalmostidenticaltotheonepresentedinSec-tion3.1.Example2showsanexecutionofthisprotocolonasmallfunction.

Example2.AssumethatAliceandBobwanttocomputef(x1,x2)=x1∧x2,whereAlicehasinputx1andBobhasinputx2,orinotherwordsXA={x1}andXB={x2}.Assumethatx1=0andx2=1.OBDD(f)withdummynodesisshowninfigure4(b).AlicecomputestheOBDDforthefunctionf|x1←0,whichresultsinastructureshowninFigure5(c).LetthetwononterminalnodesinFigure5(c)bev1andv2.First,Alicegenerates2secretssv1andsv2,whichareassignedtothenodesv1andv2,respectively.AlicealsogeneratesrandomlabelsforthefournodesinFigure5(c),

1

andgeneratesapairofsecrets(s01,s1).ThegarbledOBDDcorrespondingtoFigure5(c)isshownbelow(terminalnodesareshownas0and1andlabdenoteslabel).

(lab(v1),Esv⊕s0(lab(0)󰀓s0),Esv⊕s1(lab(0)󰀓s0))

1111

(lab(v2),Esv⊕s0(lab(0)󰀓s0),Esv⊕s1(lab(1)󰀓s1))

1122

(0,lab(0))(1,lab(1))

Alicerevealsthesecretsv1correspondingnodev1.Aliceand

2

)protocolandBobobtainsBobengageina1-out-of-2(OT1

1

thesecrets1(recallthatx2=1).BobcannowdecryptthesecondcomponentofthefirstentryofthegarbledOBDDandobtainlabel(0)󰀓s0,andBobcaninferthattheoutputis0.

3.2Protocol2

TheprotocolpresentedinthissectionallowsbothAliceandBobtopossessarbitraryinputsetsinsteadofassumingthatAlice(andalsoBob)holdseitherthefirstkorthelastn−kinputvariables.Inthisnewprotocol,beforegarblingtheOBDD,AlicecanreducethesizeoftheOBDDbyelim-inatingverticeswhoselabelscorrespondtoAlice’sinputs.Letf(x1,···,xn)bethefunctiontobecomputedandXAdenotestheinputsofAlice.AlicefirstcomputestheOBDDfortherestrictionf|XAoffforthevariablesinitsinputsetXA.AlicethenencryptsthereducedOBDDandsendsittoBob.Duringtherestrictionoperation,allverticeswhoselabelscorrespondtoBob’sinputshouldbeincluded.Ifthisisnotthecase,thenthereisariskthatdifferentrestrictionscouldproducedifferentnumbersofnodes,whichwouldleakinformationtoBobaboutAlice’sinputs.Forexample,inNotethatthenegligibleprobabilityoferrorduringdecryp-tioncanberemovedbyAlicefirstcheckingthateveryen-cryptednodedecryptscorrectlybeforesendingthegarbledOBDDtoBob.

2

414

Claim3.Iftheencryptionschemehasanelusiverangeandtheoblivioustransferprotocolissecure,thenProtocol2iscorrectforsemi-honestAliceandBob.

Proof:TheproofofthisclaimisexactlysameastheproofofClaim1.OnehastoassumethattherestrictionoperationusedbyAliceiscorrect.󰀁Claim4.Iftheencryptionschemeissemanticallysecureandhasanefficientlyverifiableelusiverange,andtheobliv-ioustransferprotocolissecure,thenProtocol2issecureagainstsemi-honestAliceandBob.

ProofofthisclaimistediousandisgiveninAppendixA.

4.

IMPLEMENTATIONANDEXPERIMENTALRESULTS

Inthissectionwedescribevariouscomponentsofourim-plementation(calledSFE-OBDD),whichisbasedonproto-col2describedinSection3.2.WealsopresentexperimentalresultscomparingtheperformanceofourimplementationagainstFairplay.Thefollowingmajorconclusionscanbedrawnfromourexperimentalinvestigation:

•Therestrictionoperationusedinprotocol2cansignif-icantlyreducethesizeoftheOBDD,whichcanleadtoreducedbandwidthwhileexecutingtheprotocol.•OurOBDDprotocoloutperformsFairplaycircuitintermsofbandwidthinmostfunctionsinourbench-mark.However,somefunctionswhichhaveinefficientOBDDrepresentationscanperformfarworse.•ExecutiontimesofourimplementationandFairplayaredominatedbytheoblivious-transferprotocol.Sincetheoblivious-transfercomponentofourprotocolandtheprotocolusedbyFairplayisthesame,withre-specttoexecutiontimeswedidnotobserveasmuchimprovementasinbandwidth.•ConvertinganOBDDintoacircuitresultsinablowupinsize.WeimplementedareversecompilerthattakesanOBDDandconvertsitintoacircuitdescription,whichcanbeusedinFairplay.Typicallythiscon-versionfromOBDDtocircuitresultedinablowupinsizebyafactorof5−10,dependingonpost-conversionoptimizations.However,iftheoriginalcircuitispar-ticularlyinefficient,itispossibleforsomegaintobeachievedduetothecanonicalrepresentationpropertyofOBDDs.

Forthecryptographicprimitivesweuseexactlythesame

2

implementationasFairplay.Weusethe1-out-of-2(OT1)proposedbyNoarandPinkas[23],andtheencryptionfunc-tionisEk(m)wasSHA−1(k)⊕(m󰀓0n).

OurOBDDcompilerallowsustodirectlycomparetheef-ficiencyofourimplementationtoFairplay.TheOBDDcom-pilertakesasinputafilecontaininganSHDLdescriptionandproducesafilecontainingthedescriptionofthecorre-spondingOBDD.ThisfilecanthenbeusedasaninputtotheSFEprotocol.OurcompilerusestheJavaBDD[16],andBuDDy[5]libraries,whichprovidefunctionstoconstructandmanipulateOBDDs.ItiswellknownthatthesizeofanOBDDcanbesensitivetotheorderingofvariables[3].Insomecases,variableorderingcanmakethedifferencebe-tweenaOBDDthatislinearversusexponentialinthenum-berofvariables.OurSHDLtoOBDDcompilerallowstheusertospecifyaparticularvariableordering,whichisuse-fuliftheuserhasdomainknowledgeaboutthefunction.Ifthisisnotpractical,thecompilerincludesanoptimizerthatattemptstoautomaticallyfindavariableorderingthatyieldsanefficientOBDD,makinguseofheuristicfunctionsbuiltintotheBuDDylibrary.AlthoughingeneralfindingtheoptimalvariableorderingisNP-hard[2],wehavefoundthatinpracticetheoptimizercanfindgoodorderingsforvariousfunctionsweconsidered.

4.2ExperimentalResults

Weusedvariousfunctions,someofwhichareincludedintheFairplaydistribution,astestcasestoperformacom-parisonoftheFairplayprotocolwithourOBDD-basedSFEprotocol.ThedescriptionofthefunctionsaregiveninFig-ure7.Eachfunctionwasevaluatedatseveralwordsizestoevaluatescalability.

Foreachfunction,Figure8showsthesizesoftheOBDDsandthecorrespondingcircuitusedbyFairplay.ThesizeofanOBDDisthenumberofverticesinit.ThesizeofaFair-playcircuitwithn1gatesofarity1,n2gatesofarity2,andn3gatesofarity3wascomputedas2×n1+4×n2+8×n3(thisrepresentsthenumberofentriesinthetruthtableforthecircuit).FortheOBDDs,weshowthesizesoftheorigi-nalOBDDs(incolumnmarkedasOriginal),withthedummynodesadded(incolumnmarkedasFull),andafterAlicehasperformedtherestrictionoperationonOBDDswithdummynodes(incolumnmarkedasRes).RecallthatdummynodesareaddedsothatregardlessofAlice’sinputsBobhastofol-lowthesamenumberofedges.Inprotocol2AlicecomputestheOBDDforrestrictiononitsinputofthefunctiontobejointlycomputedforthevariable.Theseoperationsarede-scribedindetailinSection3.TwoobservationscanbemadefromFigure8.

•RestrictioncansignificantlyreducethesizeoftheOBDD.Forexample,forthefunctionMil16restrictionreducesthesizeoftheOBDDbymorethanhalf.•NoticethatforallfunctionsexceptMUL8,MUL16,KDS4,KDS8,andKDS16thesizeoftheOBDDafterrestrictionissmallerthanthesizeofthecircuitusedinFairplay.ThissuggeststhechoiceofwhentouseoursystemoverFairplaydependsonthefunctiontobecomputed.Ourexperimentalresultswereobtainedusingapairofmachinesconnectedonalocal100-megabitnetwork.The

4.1Implementation

Ourimplementationconsistsofthefollowingcomponents:1.Animplementationofprotocol2asdescribedinSec-tion3.2.2.Fairplayusesthesecurehardwaredefinitionlanguage(SHDL)todescribecircuits.BecausewewantedtocomparetheperformanceofourprotocolwiththeYaocircuitprotocolonidenticalfunctions,weimplementedanOBDDcompilerthattakesasinputafiledescribingafunctioninSHDL,andproducesthecorrespondingOBDD.NotethatboththeSHDLusedbyFairplayandtheBDDrepresentationoriginatefromthesamehighlevelSFDLdescription,thismeansthattheOBDDandcircuitareevaluatingthesamefunctions.

415

AndAddEqMulKDSMilParity

ThisisacircuitthatcomputesthebitwiseANDoftwoNbitnumbers.AlicehasNinputs,BobhasNinputs,andthereareNbitsofoutput.

ThisisacircuitthatcomputestheadditionoftwoNbitnumbers.AlicehasNinputs,BobhasNinputs,andthereareNbitsofoutput.Thehighbitisdiscarded.

ThisisasimpleequalitycomparatoroftwoN-bitnumbers.Thereisonebitofoutput.

ThisisacircuitthatcomputestheunsignedmultiplicationoftwoNbitnumbers.AlicehasNinputs,BobhasNinputs,andthereareNbitsofoutput.Theoutputismodulo2N.WewereunabletotestN=16becauseofexponentialblowupintheBDD

Thisisacircuitthatimplementsasimply-keyeddatabaselookup.AlicesuppliesNkey/valuepairs,andBobsuppliesakey.Theoutputisthevalueofthatkey,or0ifthekeyisnotfound.Thekeysarelog2(N)bits,andthedataare24bits.WewereunabletotestN=16becauseofexponentialblowupintheBDD.Thisisthemillionaire’sproblem.AliceandBobeachhaveandNbitintegerasinputs,andthereis1bitofoutputindicatingifAlice’sinputislargerthanBob’s.

AliceandBobeachhaveN-bitsofinput.Theywanttojointlycomputetheparityoftheircombinedinputbits.Thereisonebitofoutput.

Figure7:Descriptionofthefunctionsusedinourexperiments.EachfunctionwastestedwithN=4,N=8,andN=16exceptwhereindicated

machineswereconfiguredwith3.0GhzIntelPentium4pro-cessors,1gigabyteofmemory,andtheCentosLinux4.0op-eratingsystemusingamodifiedLinux2.6.9kernel.ForeachfunctionshowninFigure7weexecutedourOBDD-basedandFairplaycodeonaSunMicrosystemsJava1.5.004JVM.Alicewasrunononemachine,andBobontheother.Foreachexecution,wemeasuredthenetworkbandwidthused(numberofbytestransferredbetweenAliceandBob)andtheexecutiontime.Thenumberreportedforeachtrialistheaverageofthreetrials.Figure9showsthesizeofthegarbledOBDDandgarbledcircuitinbytesandthenetworkbandwidthforourimplementationandFairplay.RecallthatthegarbledOBDDisthestructurethatAlicesendstoBobtoevaluate.Withrespecttonetworkbandwidthourimple-mentationoutperformedFairplayforsevenoutoftheninefunctions.WehaveimplementedareversecompilerthattakesasinputanOBDD,andoutputsanSHDLdescriptionofabooleancircuittoevaluatetheOBDD.ThisisperformedviaastraightforwardtransformationthattakeseachnodeintheOBDDandproducescorresponding3-inputMUXgateinthebooleancircuit.Then,anoptimizationpassisrunusingthesametechniquesdescribedin[22].Thecolumnlabeledas“ConvertedFairplay”inFigure9showsthesizeoftheencryptedcircuitsproducedbyrunningtheFairPlayprotocolontheconvertedBDDs.Notethatinafewcases,theconvertedcircuitisactuallymoreefficientthanthecor-respondingFairplaycircuit.ThisoccursbecauseFairPlayisnotguaranteedtoproduceanoptimalcircuitfromthefunctiondescription.However,itisclearthatourprotocolthatdirectlyusesOBDDismuchmoreefficientthantheprotocolproducedbythereversecompiler.

Figures10and11showtheexecutiontimesforSFE-OBDDandFairplay.Theelapsedexecutiontimes(EET)areshowninthelastcolumn.Columns2-5showthebreak-downbysub-task,whichareIPCG(initializations,parsing,andgarbling),CC(circuitcommunication,AlicesendingthegarbledstructuretoBob),OT(ObliviousTransfer,Bobob-tainingsecretscorrespondingtoitsinput),andEV(circuitevaluation,Bobevaluatingthegarbledstructure).Thesesub-taskswerealsousedbytheFairplaypaper[22].Ingen-eral,becausethetimeforOTdominatestheexecutiontime,weonlyobservemoderateimprovementinSFE-BDDoverFairplayforexecutiontimes.

Add4Add8Add16And4And8And16Eq4Eq8Eq16KDS4KDS8KDS16MUL4MUL8MUL16Mil4Mil8Mil16parity4parity8parity16

BDD

OriginalFull3240729615220814182634506618242741518141657840847149**7516851800**2434467094150181834346666

FairPlay

Res

221181018341118344666283*281087*224090101834

56128272244610223048635678022441145862682521162443062126

Figure8:SizeoftheOBDDsandthecircuitusedinFairplayforfunctionsshowninFigure7.Val-ueslabeled“*”couldnotbeconvertedtoOBDDsbecauseofexponentialblowup.

416

FunctionAdd4Add8Add16And4And8And16Eq4Eq8Eq16KDS4KDS8MUL4MUL8Mil4Mil8Mil16parity4parity8parity16

SFE-OBDD

97019793992739120621345828281324149661852821108322062140027905778281324Sizeinbytes.

FairplayConvertedFairplay191553824214114088821234421080186621533140429956297726906527391813626701212248659462560868233332868315706288317166242783282487306168591092323721816172435911983Bandwidthinbytes

SFE-OBDDFairplay

360446846590900012557175337338495813693810696131173214571634112409222295512191398426107727838373960523681420493352443996012825611356159723209383038679813033

Figure9:SizeinbytesofthegarbledOBDD,garbledcircuit,andgarbledcircuitusingthereversecompiler.

Networkbandwidthinbytes.

FnAdd4Add8Add16And4And8And16Eq4Eq8Eq16KDS4KDS8MUL4MUL8Mil4Mil8Mil16parity4parity8parity16IPCG13.75%13.08%11.39%12.42%9.38%7.44%12.66%9.33%8.97%4.79%10.91%14.77%31.80%13.44%11.37%10.55%10.67%9.37%8.55%CC5.62%3.80%2.36%5.73%4.02%2.75%5.38%3.90%2.48%0.95%1.69%5.23%4.11%5.62%3.86%3.03%4.78%3.92%2.62%OT79.69%82.07%84.42%81.21%85.94%.39%81.33%86.12%88.14%93.86%87.13%79.38%63.45%80.00%84.12%85.88%83.71%86.06%88.41%Eval0.94%1.05%1.83%0.%0.67%0.41%0.63%0.65%0.41%0.40%0.27%0.62%0.63%0.94%0.%0.53%0.84%0.65%0.41%EET0.320.470.760.310.450.730.320.460.722.525.500.330.630.320.470.760.360.460.72

FnAdd4Add8Add16And4And8And16Eq4Eq8Eq16KDS4KDS8MUL4MUL8Mil4Mil8Mil16parity4parity8parity16IPCG17.65%16.13%10.74%11.92%11.78%9.78%19.51%15.44%13.23%33.33%35.98%21.%21.75%38.27%16.98%18.78%20.78%49.55%14.63%CC19.00%15.96%9.67%20.44%16.07%6.35%11.85%16.52%9.84%12.75%11.92%2.16%7.99%8.26%9.25%9.01%11.25%0.39%1.15%OT63.12%67.38%79.12%67.40%71.96%83.48%68.15%67.68%76.70%53.33%51.43%75.41%69.%53.28%73.40%71.99%67.73%49.94%83.97%Eval0.23%0.53%0.48%0.24%0.19%0.38%0.49%0.36%0.23%0.58%0.66%0.%0.37%0.19%0.38%0.22%0.24%0.13%0.25%EET0.440.560.840.410.0.790.410.560.850.340.450.370.0.530.530.920.410.770.79

Figure10:Elapsedexecutiontime(EET)insec-ondsandtheirbreakdownsintosub-tasksforSFE-OBDD.

Figure11:Elapsedexecutiontime(EET)insecondsandtheirbreakdownsintosub-tasksforFairplay.

417

5.FUTUREWORK

ThereareotheroptimizationstoOBDDsthatwehavenotexploredinthispaper.Forexample,addingnegatededgestoOBDDscanresultinsmallerstructuresforsomeBooleanfunctions.3Incorporatingtheseoptimizationsinourprotocolwhilepreservingprivacyisadirectionforfu-turework.ThereareseveralotherOBDD-likerepresenta-tionsdevelopedbythecomputer-aideddesignandcomputeraidedverificationresearchcommunities,suchasBinaryMo-mentDiagrams(BMDs)[4]andHybridDecisionDiagrams(HDDs)[8].Foracertainclassoffunctions,theserepre-sentationsaremoresuccinctthanOBDDs.Forexample,BMDscanefficientlyrepresentintegermultiplication,whichcannotberepresentedefficientlyatthebit-levelwithOB-DDs.Extendingourprotocolfortheserepresentationsisanimportantdirectionoffutureresearch.Ourvisionistoprovideanoptionforalltheserepresentationsinoursystemsothatausercanchoosetherepresentationthatissuitablefortheproblem.

OBDDshavebeenusedforavarietyofapplications,suchefficientfilteringinpublish-subscribesystems[6],programanalysis[26],andplanning[17].Inthefuturewewillin-vestigatewhetherourprotocolcanbeextendedtodesignprivacy-preservingalgorithmsfortheseapplications.

6.REFERENCES

[1]GaganAggarwal,NinaMishra,andBennyPinkas.

Securecomputationofthek-thrankedelement.InChristianCachinandJanCamenisch,editors,

ProceedingsofEurocrypt2004,volume3027ofLNCS,pages40–55.Springer-Verlag,May2004.

[2]BeateBolligandIngoWegener.Improvingthe

variableorderingofOBDDsisNP-complete.IEEETransactionsonComputers,45(9),September1996.[3]RandalE.Bryant.Graph-basedalgorithmsfor

booleanfunctionmanipulation.IEEETransactionsonComputers,35(8):677–691,1986.

[4]RandalE.BryantandYirng-AnChen.Verificationof

arithmeticcircuitswithbinarymomentdiagrams.InProceedingsofthe32ndConferenceonDesignAutomation(DAC),1995.

[5]Buddy.http://sourceforge.net/projects/buddy.[6]A.Campailla,S.Chaki,E.M.Clarke,S.Jha,and

H.Veith.Efficientfilteringinpublish-subscribesystemsusingbinarydecisiondiagrams.In

Proceedingsofthe23rdInternationalConferenceonSoftwareEngineering(ICSE),2001.

[7]E.M.Clarke,O.Grumberg,andD.A.Peled.Model

Checking.TheMITPress,2000.

[8]E.M.Clarke,M.Khaira,andX.Zhao.Hybriddecision

diagrams:OvercomingthelimitationsofMTBDDsandBMDs.InProceedingsoftheInternationalConferenceonComputer-AidedDesign(ICCAD),1995.

[9]LorrieCranor,MarcLangheinrich,Massimo

Marchiori,MartinPresler-Marshall,andJosephReagle.ThePlatformforPrivacyPreferences1.0(P3P1.0)Specification.W3CRecommendation,16April2002.FollowinganegatededgeinanOBDDflipsthevalueoftheresult.

3

[10]LorrieFaithCranor.Internetprivacy.

CommunicationsoftheACM,42(2):28–38,1999.[11]J.Feigenbaum,B.Pinkas,R.Ryger,and

F.Saint-Jean.Securecomputationofsurveys.In2004EUWorkshoponSecureMultipartyProtocols(SMP),2004.

[12]MichaelFreedman,KobbiNissim,andBennyPinkas.

Efficientprivatematchingandsetintersection.InChristianCachinandJanCamenisch,editors,

ProceedingsofEurocrypt2004,volume3027ofLNCS,pages1–19.Springer-Verlag,May2004.

[13]IanGoldberg,DavidWagner,andEricBrewer.

Privacy-enhancingtechnologiesfortheinternet.InProc.of42ndIEEESpringCOMPCON.IEEEComputerSocietyPress,February1997.

[14]O.Goldreich.TheFoundationsofCryptography—

Volume2.CambridgeUniversityPress,2004.

[15]O.Goldreich,S.Micali,andA.Wigderson.Howto

playanymentalgame–acompletenesstheoremforprotocolswithhonestmajority.In19thSTOC,pages218–229,1987.

[16]Javabdd-javabinarydecisiondiagramlibrary.

http://javabdd.sourceforge.net/.

[17]R.M.JensenandM.M.Veloso.Obdd-baseduniversal

planningformultiplesynchronizedagentsin

non-deterministicdomains.InProceedingsoftheFifthInternationalConferenceonArtificialIntelligencePlanningSystems(AIPS),2000.

[18]Y.LindellandB.Pinkas.Privacypreservingdata

mining.JournalofCryptology,15(3),2002.

[19]YehudaLindellandBennyPinkas.AproofofYao’s

protocolforsecuretwo-partycomputation.

CryptologyePrintArchive,Report2004/175,2004.http://eprint.iacr.org/2004/175.

[20]B.PinkasM.NaorandR.Sumner.Privacypreserving

auctionsandmechanismdesign.InProceedingsofthe1stACMconf.onElectronicCommerce,1999.

[21]PhilipD.MacKenzie,AlinaOprea,andMichaelK.

Reiter.Automaticgenerationoftwo-party

computations.InProceedingsofACMConferenceonComputerandCommunicationsSecurity,2003.

[22]D.Malkhi,N.Nisan,B.Pinkas,andY.Sella.Fairplay

—asecuretwo-partycomputationsystem.In

Proceedingsofthe13thUsenixSecuritySymposium,SanDiego,CA,USA,August2004.

[23]MoniNaorandBennyPinkas.Efficientoblivious

transferprotocols.InProceedingsoftheTwelfth

AnnualSymposiumonDiscreteAlgorithms(SODA),pages448–457,2001.

[24]D.M.Rind,I.S.Kohane,P.Szolovits,C.Safran,

H.C.Chueh,andG.O.Barnett.Maintainingtheconfidentialityofmedicalrecordssharedovertheinternetandtheworldwideweb.AnnalsofInternalMedicine,127(2),July1997.

[25]JosephTurow.Americansandonlineprivacy:The

systemisbroken.Technicalreport,AnnenbergPublicPolicyCenter,June2003.

[26]J.WhaleyandM.S.Lam.Cloning-based

context-sensitivepointeraliasanalysisusingbinarydecisiondiagrams.InProceedingsoftheACMSIGPLAN2004ConferenceonProgramming

LanguageDesignandImplementation(PLDI),2004.

418

[27]A.C.Yao.Howtogenerateandexchangesecrets.In

Proceedingsofthe27thIEEESymposiumonFoundationsofComputerScience,1986.

APPENDIX

A.PROOFOFCORRECTNESS

Proof:[ProofofClaim2]Intuitively,Bob’ssecurityfollowsdirectlyfromthesecurityofthe1-out-of-2oblivioustrans-ferprotocolheusestoobtainthesecretscorrespondingtohisinput.Alice’ssecurityfollowsfromboththesecurityoftheoblivioustransferprotocol(allowingBobtoonlyob-tainonlyonekeypernode)andthesemanticsecurityoftheencryptionscheme(whichallowsBobtoonlydecryptoneentryineachnode).WenowfleshoutthedetailsbyprovidingasimulationprooffromAliceandBob’sviewoftheprotocol.LetxandybetheinputsofAliceandBobrespectivelyandΠbeaprotocolforsecure-functionevalu-Π

ationoff(x,y).LetVIEWΠA(x,y)andVIEWB(x,y)betheviewofAliceandBobfortherunoftheprotocolΠoninputxandy(viewofapartyconsistsofitsinput,out-put,andallmessagesitreceivesduringtheexecutionoftheprotocol).Inasimulationproofoneneedstoshowtwoprobabilisticpolynomial-timealgorithmsSAandSBsuchthatSA(x,f(x,y))andSB(y,f(x,y))arecomputationally

Π

indistinguishablefromVIEWΠA(x,y)andVIEWB(x,y),re-spectively.Foraprecisedefinitionofasimulationproofthereadershouldreferto[14,Chapter7].

WefirstconsiderthecasewhereAliceiscorrupt.Alice’sviewinanexecutionofProtocol1consistsofherviewoftheoblivioustransferprotocolexecutionsandtheoutputofthefunctionfromBobattheend.WenowbuildasimulatorthatsimulatesAlice’sviewgivenaccessonlytoherinputandout-put.Becausetheoblivioustransferprotocolissecure,thereexistsasimulatorthatcansimulatethetranscriptofAl-ice’sviewoftheoblivioustransferprotocolwithoutknowingBob’sinput.Oninput(i1,...,ik,f(i1,...,in)),thesimula-torfirstsimulatesAlice’sviewofalln−kexecutionsoftheoblivioustransferprotocolbyrepeatedlyrunningtheobliv-ioustransferprotocolsimulator.Usingastandardhybridargumentonthetranscriptsofalln−kexecutionsoblivi-oustransferprotocols,weseethatiftheoblivioustransferprotocolissecure,thenthedistributionsofthesimulatedandrealcombinedtranscriptsofalln−koblivioustransferexecutionsareindistinguishablewithnon-negligibleproba-bility.

Finally,thesimulatorwritesf(i1,...,in)onthetranscriptofAlice’sview.Wenowshowthatthedistributionoftheoutputfisindistinguishable(exceptwithnegligibleproba-bility)fromtherealoutput,whichamountstoshowingthatBoboutputsf(i1,...,in))correctlyonarealinteraction.Bythesecurityoftheoblivioustransferprotocol,Bobispro-videdwiththecorrectkeyscorrespondingtoitsinputduringeachexecutionoftheoblivioustransferprotocol.Applyingclaim1,itfollowsimmediatelythat,exceptwithnegligibleprobability,AliceobtainsthecorrectoutputfromBob,ex-ceptwithnegligibleprobability.Therefore,thedistributionofthesimulatedtranscriptisindistinguishable,exceptwithnegligibleprobability,fromarealtranscript,concludingthecasewhenAliceiscorrupt.

WenowconsiderthecasewhenBobiscorrupt.Given

(ik+1,...,in,f(i1,...,in)),thesimulatorSmustsimulatebothagarbledOBDDthatBobcanusetocorrectlycom-putef(i1,...,in),andBob’sviewofthen−kexecutionsoftheoblivioustransferprotocol.WefirstshowhowSsim-ulatesthen−koblivioustransferprotocolexecutions.Asinthepreviouscase,becausetheoblivioustransferproto-colissecure,thereexistsasimulatorthatcansimulatethetranscriptofBob’sviewoftheoblivioustransferprotocolwithoutknowingAlice’sinput.Therefore,SsimulatesBob’sviewofalln−kexecutionsoftheoblivioustransferprotocolbyrunningtheoblivioustransferprotocolsimulatorn−ktimes.Usingastandardhybridargumentonthetranscriptsoftheoblivioustransferprotocols,weseethatiftheoblivi-oustransferprotocolissecure,thenthedistributionsofthesimulatedandrealtranscriptsofalln−koblivioustrans-ferexecutionsareindistinguishableexceptwithnegligibleprobability.

WenowshowhowSbuildsagarbledOBDDthatBobcanusetosuccessfullycomputef(i1,...,in).SinceSdoesnotknowi1,...,ik,itcannotgeneratethegarbledOBDDac-cordingtotheprotocolinstructions.Instead,SgeneratesagarbledOBDDthatalwaysevaluatestof(i1,...,in)regard-lessofthekeysused.SuchagarbledOBDDisbuiltbyfirstgeneratingachainofn−kgarblednodesnk+1,...,nnsuchthatBob’scomputationstartsatnk+1andproceedsalongthechainthroughnk+2andsoon,beforeendingatnodenn;notethatthereisonesuchnodeforeverylevelfromk+1ton.Toensurethecomputationalwaysproceedsalongthischain,bothciphertextsingarblednodesnk+1,...,nn−1areencryptions(underdifferentkeys)ofthesamelabel-keymes-sagesuchthatthelabelpointstothenextnodealongthechainandthenodekeycombinedwiththelevelkeyallowssuccessfuldecryptionofthatnode;forexample,simulatednodenjfork+1≤j≤n−1hastheform

“

label(nj),Esn⊕s0(label(nj+1)󰀓snj+1)

jl”

Esn⊕s1(label(nj+1)󰀓snj+1).

j

l

Nodennistheterminalnodeanditissettof(i1,...,in).Oncenk+1,...,nnisgenerated,thesimulatorgeneratesanumberof“fake”nodessothatthesimulatedgarbledOBDDcontainsthecorrectnumberofnodes;thisnumbercanbedeterminedfromOBDD(f).Fakenodesarenodeswhoseciphertextpaircontainencryptionsunderdifferentkeysofthesamelabel-keymessage;inafakenode,thelabel,thekeysusedtoencrypttheciphertextpair,andthelabel-keymessageencryptedintheciphertextpairarechosenran-domly.

AllthatremainsistoshowthatthedistributionofthesimulatedgarbledOBDDisindistinguishablefromthatofarealgarbledOBDD.WedothisbyusingastandardhybridargumentoverthenodesinthegarbledOBDD.Specifically,werunhybridexperimentswithgarbledOBDDswhererealnodesarereplacedbysimulatednodes.WedefinethehybriddistributionssuchthatH0(i1,...,in)containstherealgar-bledOBDDandHB(i1,...,in)containsthesimulatedgar-bledOBDDwhereBisthenumberofnon-dummynodesintherealgarbledOBDD.WedonotneedtoconsiderdummynodesinourhybridexperimentOBDDsbecausedummynodeshavethesamedistributionasthesimulatedfakenodesanddonotaffectourargument.

WenowdefinethehybridgarbledOBDDinexperimentHi(i1,...,in);thedifficultyhereisthatthehybridOBDD

419

containsbothrealandsimulatednodesbutmuststillallowBobtocorrectlycomputef(i1,...,in).First,wetraversetherealgarbledOBDDandlabelanodeasactiveifitisusedbyBobintheprocessofevaluatingtheOBDDandinactiveotherwise.Notethattherewillbeonlyn−kactivenodes.Next,weorderthenodesinthegarbledOBDDbytheirlevelwithlevelj+1nodesplacedaheadoflevelj+2andsoon;withinthesamelevel,nodesareorderedarbitrarily.ThehybridOBDDisdefinedasfollows:firsttaketherealgarbledOBDDandreplacethefirstinon-dummynodesasfollows:inactivenodesarereplacedwithsimulatedfakenodes.Anactivenodeatleveljisalteredbyreplacingitscurrentciphertextpairwithtwoencryptionsofthelabel-keymessagecorrespondingtothenextactivenodeatlevelj+1.Thesereplacementciphertextsarecreatedwiththekeysusedtocreatetheoriginalciphertextpair.Notethatthedistributionofthisalteredactivenodeisidenticaltothatofthesimulatednodenjinthenodechaindescribedabove.ItiseasytoseethatagarbledOBDDbuiltwiththisdefinitionhasthesamedistributionas1)arealgarbledOBDDwheni=0(i.e.forH0),and2)asimulatedgarbledOBDDwheni=B(i.e.forHB).

Wearenowreadytoshowthatthedistributionofthesim-ulatedgarbledOBDDisindistinguishablefromthatofarealgarbledOBDD;thatis,wewillshowthat{H0(i1,...,in)}={HB(i1,...,in)}.Supposetothecontrarythatthedistri-butionsaredistinguishable;thatis,thereexistsapoly-timedistinguisherDthat

|Pr[D(H0(i1,...,in))=1]−

Pr[D(HB(i1,...,in))=1]>1/p|

forsomepolynomialp.Thenthereexistsajsuchthat

|Pr[D(Hj−1(i1,...,in))=1]−Pr[D(Hj(i1,...,in))=1]>1/pB|

UsingD,wenowbuildanadversarythatbreaksthese-manticsecurityoftheencryptionschemeusedtoencryptthegarblednodes.Recallinasemanticsecuritygame,theadversarysendstwomessagesm0,m1tothechallengerandreceivestheencryptionofmbforb={0,1};theadversary’sgoalistodetermineb.Letnjbethejthnodeandwede-j

noteitstwociphertexttermsascj0andc1.Notethatnode∗njinthehybridOBDDindistributionHj−1isarealgar-∗blednode,whereasthesamenodefordistributionHjisa

jj

simulatedgarblednode;specifically,c0andc1indistribu-∗

tionHj−1areencryptionsofdifferentlabel-keymessages,whereastheyareencryptionsofthesamelabel-keymessage

∗

.Weexploitthisfacttobuildthead-indistributionHj

versaryAthatbreakssemanticsecurityoftheencryptionscheme.

First,AcreatesthehybridgarbledOBDDcorresponding

∗

tothedistributionHj−1(i1,...,in).Oneofthetwocipher-jj

textsc0andc1innodenjisanencryptionofthelabelandkeyfortheactivenodenj+1,whereastheotherciphertextisanencryptionofthelabelandkeyforaninactivenode.Let󰀤0bethelabel-keymessageencryptedincj0and󰀤1bethat

j

encryptedinc1.Next,Asends󰀤0and󰀤1tothesemanticsecuritychallengerandreceivesc∗,whichisanencryptionofeither󰀤0or󰀤1.Withoutlossofgenerality,let󰀤0bethelabel-keymessage(containedinciphertextcj0)thatleadsto

j∗

thenextactivenode.Areplacesc1withcinnodenjinthegarbledOBDDthatitbuiltinthefirststep,andthenfeedsthealteredOBDDtogetherwiththeotherrequiredinputs

tothehybriddistinguisherD.Notethatc∗cannotbede-cryptedwiththenodeandlevelkeysfornodenj.Thisfact,however,doesnotpreventthegarbledOBDDfrombeingevaluatedcorrectlybecausec∗replacescj1,whichcontainsthelabelandkeytoaninactivenode,andwouldnotbesuccessfullydecryptedwhileevaluatingthegarbledOBDDontheinputs(i1,...,in).

Deventuallyoutputsaresultstatingthattheinputisof

∗∗

distributionHj−1orHj.IfDoutputsthattheinputisof

∗∗

distributionHj−1,thenAoutputsthatcisanencryptionof󰀤1;otherwiseAoutputsthatc∗isanencryptionof󰀤0.No-ticethatifc∗isanencryptionof󰀤0,thenbothciphertextsinnodenjareencryptionsofthesamelabel-message,andthe

∗

inputtoDhasdistributionHj.Similarly,ifc∗isanencryp-∗tionof󰀤1,thentheinputtoDhasdistributionHj−1.Since

∗∗

DdistinguishesbetweenHj−1andHjwithnon-negligibleprobability,weseethatAwinsthesemanticsecuritygamewithnon-negligibleadvantage.Sinceweassumethattheen-cryptionschemeissemanticallysecure,thisimplicationisacontradiction,andthereisnosuchdistinguisherDthatdis-tinguishesbetweenH0(i1,...,in)andHB(i1,...,in);thatis,thedistributionofthesimulatedgarbledOBDDisindis-tinguishablefromthatofarealgarbledOBDD.Therefore,Bob’ssimulatedviewisindistinguishable,exceptwithneg-ligibleprobability,totherealview,concludingtheproof.

󰀁Proof:[ProofSketchforClaim4]ThefullproofisverysimilarforthatinClaim2,andweprovideonlyasketch.ThecasewhenAliceiscorruptisidenticaltothatinClaim2.WebrieflydiscusswhytheproofisalsoalmostidenticalinthecasewhenBobiscorrupt.ThemainobservationisthatthesimulatorSbuildsthesimulatedgarbledOBDDinthesamewayasinClaim2becausethereisnodifferenceinhowProtocol2requiresBobtotraversethegarblednodesgiventhesamelevelkeys.Therefore,thehybriddistributionsaredefinedthesamewayandtherestoftheprooffollows.

󰀁

420