How To Simulate It – A Tutorial on the Simulation Proof ...

1 HowToSimulateIt ATutorialontheSimulationProofTechnique ThistutorialappearedinthebookTutorialson theFoundationsofCryptography,publishedin honorofOdedGoldreich SemanticSecurity44 SecureComputation ObliviousTransfer499 TheCommonReferenceStringModel , realworld towhathappensinan idealworld , , , (thisisan idealworld thatissecurebydefinition),thisimpliestha tintherealworld,wheretheadversaryreceive stheciphertext, , snotatallclearhowtoformalizethenotiontha t nothingislearned .Ifwetrytosaythatanadversarywhoreceivesa ciphertextcannotoutputanyinformationabou ttheplaintext,thenwhathappensiftheadvers aryalreadyhasinformationabouttheplaintex t?Forexample, , (oroutputbytheadversary) , Simulation ; (firstinSection3).Fornow,itsufficestosay thatsecurityproofsfordefinitionsformulat edinthiswayworkbyconstructingasimulatort hatresidesinthealternativeworldthatissec urebydefinition, ,aswewillshow, ; ; , , ,wewilldemonstratethesimulationparadigmi nanumberofdifferentsettings, , ,inSection4,weshowhowtosimulatesecurecom putationprotocolsforthecaseofsemi-honest adversaries(whofollowtheprotocolspecific ation,buttrytolearnmorethanallowedbyinsp ectingtheprotocol2transcript).

2 , ,thecorruptedparty(whoistheverifier) ,thesimulationconsistsofthefirsttaskonly :generatingaviewthatisindistinguishablef romthepotentiallymaliciousverifier ,weproceedtosecurecomputationwithsecurit yinthepresenceof(static) , , ,anadditionalelementofthesimulator sroleisadded.(Inthissection,wealsodemons tratethehybridmodelandthetechniqueofhowt owritesimulation-basedproofsinthismodel. )Then, ,inSection9weshowhowtosimulateinthecommo nreferencestringmodel,andinSection10webr ieflydiscusssomeadvancedtopicsrelatedtos imulation:concurrentcomposition,therando moraclemodel, {0,1} ,wewritex {0,1} ( )isnegligibleifforeverypositivepolynomia lp( )andallsufficientlylargen s,itholdsthat (n)<1/p(n).Finally,wedenotetheemptystrin gby . {X(a,n)}a {0,1} ;n Nisaninfinitesequenceofrandomvariablesin dexedbya {0,1} andn ,thevalueawillrepresenttheparties {X(a,n)}a {0,1} ;n NandY={Y(a,n)}a {0,1} ;n Naresaidtobecomputationallyindistinguish able,denotedbyXc Y,ifforeverynon-uniformpolynomial-timeal gorithmDthereexistsanegligiblefunction ( )suchthatforeverya {0,1} andeveryn N,|Pr[D(X(a,n))=1] Pr[D(Y(a,n))=1]| (n).

3 Allpartiesareassumedtorunintimethatispol ynomialinthesecurityparameter.(Formally, ,aswouldoccurinthecasewhereitsinputislon gerthanitsoverallrunningtime.) , , (notusingthenotion negligiblefunction ).Thatis,Xc Yifforeverynon-uniformpolynomial-timealg orithmDand3everypolynomialp( )thereexistsanN Nsuchthatforeveryn>Nandeverya {0,1} ,|Pr[D(X(a,n))=1] Pr[D(Y(a,n))=1]|<1p(n).Now,thecontradictionofthisisthatthereexistsaDandapolynomialp( )suchthatforeveryN Nthereexistsann>Nandana {0,1} forwhich|Pr[D(X(a,n))=1] Pr[D(Y(a,n))=1]| 1p(n).Statedinshort,thereexistsaDandapol ynomialp( )suchthatforaninfinitenumberofn sthereexistsana {0,1} forwhich|Pr[D(X(a,n))=1] Pr[D(Y(a,n))=1]| 1p(n).Inparticular, ,inordertocarryoutareductionthatbreaksso mecryptographicprimitiveorassumptionifth eensemblesarenotcomputationallyindisting uishable, , {0,1} itholdsthat{X(a,n)}n Nc {Y(a,n)}n ,observethatthisformulationhereguarantee sthatforeveryaandeverynon-uniformprobabi listic-polynomialtimeD,thereexistsanegli giblefunction suchthatforeveryn,DdistinguishesX(a,n)fr omY(a,n)withprobabilityatmost (n).

4 Thismeansthattherecanbeadifferentnegligi blefunctionforeverya, ,considerthenegligiblefunction athatequals1foreveryn<2|a|andequals2 nforeveryn 2|a|,andassumethatforeverya {0,1} thefunction , ,zeroknowledgewouldbecometrivialforallla nguagesinNPsincethesimulatorcouldoutput ifn<2|x|wherexisthestatementbeingproven, andcanjustfindthewitnessinthecasethatn 2|x|.Thisproblemdoesnotarisewiththeactua ldefinitionbecauseitrequiresthatthereexi stsasinglenegligiblefunctionforallvalues ofa {0,1} .3 TheBasicParadigm SemanticSecurityThebirthofcomplexity-bas edcryptography(or provablesecurity )beganwiththefirstrigorousdefinitionofth esecurityofencryption[24]. , , ,andallowsforarbitrarydistributionsoverp laintexts(aslongastheplaintextssampledar eofpolynomiallength).Thedefinitionalsota kesintoaccountanarbitraryauxiliaryinform ationfunctionhof4theplaintextthatmaybele akedtotheadversarythroughothermeans( ,becausethesamemessagexisusedforsomeothe rpurposeaswell).

5 Theaimoftheadversaryistolearnsomefunctio nfoftheplaintext, ,itshouldbepossibletolearnthesameinforma tionfromtheauxiliaryinformationalone(and fromthelengthoftheplaintext), ( [18])Aprivate-keyencryptionscheme(G,E,D) issemanticallysecure(intheprivate-keymod el)ifforeverynon-uniformprobabilistic-po lynomialtimealgorithmAthereexistsanon-un iformprobabilistic-polynomialtimealgorit hmA suchthatforeveryprobabil-ityensemble{Xn} n Nwith|Xn| poly(n),everypairofpolynomially-boundedf unctionsf,h:{0,1} {0,1} ,everypositivepolynomialp( )andallsufficientlylargen:Prk G(1n)!A(1n,Ek(Xn),1|Xn|,h(1n,Xn))=f(1n,X n)"<Pr!A (1n,1|Xn|,h(1n,Xn))=f(1n,Xn)"+1p(n)(Thep robabilityintheabovetermsistakenoverXnas wellasovertheinternalcointossesofthealgo rithmsG,EandAorA .)ObservethattheadversaryAisgiventheciph ertextEk(Xn)aswellasauxiliaryinformation h(1n,Xn),andattemptstoguessthevalueoff(1 n,Xn).AlgorithmA alsoattemptstoguessthevalueoff(1n,Xn),bu tisgivenonlyh(1n,Xn) cancorrectlyguessf(1n,Xn) ,then,theciphertextEk(Xn)doesnotrevealan yinformationaboutf(1n,Xn),foranyf,sincew hatevercanbelearnedbyA(giventheciphertex t)canbelearnedbyA (withoutbeinggiventheciphertext).

6 Simula-tion oranidealworld, resides,itisgivenonlytheauxiliaryinforma tionandplaintextlength, ,A residesinanidealworldwhere,trivially, canlearnasmuchasAcanlearnisexactlythecom parisonbetweentherealworldandtheidealwor ld, thatoutputsf(1n,Xn)withalmostthesameprob abilityasA?HowcanA evenknowwhatAdoes?TheansweristhatA couldperfectlysimulatesuchanexecution byprovidingAwithitsexpectedinputs thenA wouldoutputf(1n,Xn) ,clearlyA cannotdothissinceitdoesnotreceiveEk(Xn) giveAanencryptionofgarbageinstead,asfoll ows:SimulatorA :Uponinput1n,1|Xn|,h=h(1n,Xn),algorithmA runsthekeygenerationalgorithmG(1n)inorde rtoreceivek(notethatA indeedneedstobegiven1ninordertodothis). computesc=Ek#0|Xn|$asanencryptionof garbage (notethatA indeedneedstobegiven1|Xn|inordertodothis ). runsA(1n,c,1|Xn|,h) runsisclearlyflawed; ,ifencryptionsareindistinguishable,thenA shouldoutputf(1n,Xn)withapproximatelythe sameprobabilitywhengivenEk(Xn)aswhengive nEk#0|Xn|$.

7 Otherwise,itwouldbepossibletodistinguish suchencryptionsbyseeingwhetherAsucceedsi noutputtingf(1n,Xn) , ,iftheencryptionworksbyXORingtheplaintex twiththeoutputofapseudorandomgenerator,t henthereductionworksbyshowingthatanynon- negligibledifferencebetweentheprobabilit ythatAcorrectlyoutputsf(1n,Xn) garbage ,theproofproceedsbyshowingthatthesimulat ionis good , (statically,andsoattheonsetofthecomputat ion) , ;iftheadversarydoesanythingnotaccordingt ospecification evenjustchoosingitsrandomtapeinanon-rand omway thenitmaybeabletocompletelybreaktheproto col(andthereareactualexamplesofnaturalpr otocolswiththisproperty).Nevertheless,ap rotocolthatissecureinthepresenceofsemi-h onestadversariesdoesguaranteethatthereis noinadvertentleakageofinformation;whenth epartiesinvolvedessentiallytrusteachothe rbutwanttomakesurethatnorecordoftheirinp utisfoundelsewhere, , ,sinceweknowexactlywhattheadversarywilld o(itjustfollowstheprotocolspecification) .

8 (oneforeachparty).Werefertosuchaprocessa safunctionalityanddenoteitf:{0,1} {0,1} {0,1} {0,1} ,wheref=(f1,f2).That6is,foreverypairofin putsx,y {0,1}n,theoutput-pairisarandomvariable(f 1(x,y),f2(x,y)) (withinputx)wishestoobtainf1(x,y)andthes econdparty(withinputy)wishestoobtainf2(x ,y). , ,sincethepartiesherehaveinputandoutput,t hesimulatormustbegivenaparty ,securityhereisformalizedbysayingthatapa rty , , ,forinputsx,y,theoutputisdefinedtobef(x, y), ,thisisverydifferentinthecaseofmalicious adversaries,forthesimplereasonthatamalic iousadversarycanignoretheinputwrittenont heinputtapeandcantakeanyotherinput.(This issimilartothefactthatamaliciousverifier inzeroknowledgecanignoreitsrandomtapeand useinternalhardcodedrandomnessinstead.) : Letf=(f1,f2)beaprobabilisticpolynomial-t imefunctionalityandlet beatwo-partyprotocolforcomputingf.(Throu ghout,wheneverweconsiderafunctionality,w ealwaysassumethatitispolynomially-timeco mputable.)

9 Theviewoftheithparty(i {1,2})duringanexecutionof on(x,y)andsecurityparameternisdenotedbyv iew i(x,y,n)andequals(w,ri;mi1,..,mit),where w {x,y}(itsinputdependingonthevalueofi),ri equalsthecontentsoftheithparty sinternalrandomtape,andmijrepresentsthej thmessagethatitreceived. Theoutputoftheithpartyduringanexecutiono f on(x,y)andsecurityparameternisde-notedby output i(x,y,n) (x,y,n)=(output 1(x,y,n),output 2(x,y,n)). (f1,f2) securelycomputesfinthepresenceofstaticse mi-honestadversariesifthereexistprobabil isticpolynomial-timealgorithmsS1andS2suc hthat%(S1(1n,x,f1(x,y)),f(x,y))&x,y,nc %(view 1(x,y,n),output (x,y,n))&x,y,n,and%(S2(1n,y,f2(x,y)),f(x ,y))&x,y,nc %(view 2(x,y,n),output (x,y,n))&x,y,n,wherex,y {0,1} suchthat|x|=|y|,andn ,itisnotenoughforthesimulatorSitogenerat eastringindistinguishablefromview i(x,y).Rather,thejointdistributionofthes imulator sout-putandthefunctionalityoutputf(x,y)= (f1(x,y),f2(x,y))mustbeindistinguishable from(view i(x,y),output (x,y)).

10 ,con-siderthecasethatthepartieswishtosec urelycomputesomerandomizedfunctionalityf (x,y), ,letxandybelistsofdataelements,andletfbe afunctionalitythatoutputsanindependentra ndomsampleofx ,consideraprotocolthatsecurelyoutputsthe samerandomsampletobothparties(andwhereea chparty sviewcanbesimulated).Clearly, ,partyP1shouldhavenoinformationaboutthes amplereceivedbyP2, ,considerasimplerdefinitionofsecuritywhi chcomparesthedistributiongeneratedbythes imulatoronlytotheviewoftheadversary(andn otthejointdistribution).Specifically,the definitionrequiresthat:%S1(1n,x,f1(x,y)) &x,y,nc %view 1(x,y,n)&x,y,n,and%S2(1n,y,f2(x,y))&x,y, nc %view 2(x,y,n)&x,y, sviewconsistsofarandomsampleofx y,asrequired, (sinceaclearlyinsecureprotocolis securebydefinition ).Forthisreason, ,theaforementionedsimplerdefinitioncanbe used(alongwithanadditionalcorrectnessreq uirement) , (a)correctness,meaningthattheoutputofthe partiesiscorrect,and(b)privacy,meaningth attheviewofeachpartycanbe(separately) ,correctnessistherequirementthatthereexi stsanegligiblefunction suchthatforeveryx,y {0,1} andeveryn,Pr[output (x,y,n) =f(x,y)] (n),andprivacyistherequirementthattheree xistprobabilistic-polynomialtimeS1andS2s uchthat%S1(1n,x,f1(x,y))&x,y {0,1} ;n Nc %view 1(x,y,n)&x,y {0,1} ;n N,( )%S2(1n,y,f2(x,y))&x,y {0,1} ;n Nc %view 2(x,y,n)&x,y {0,1} ;n N.