intuitionncsetting

HashingGarbledCircuitsforFreeXiongFan1,ChayaGanesh2,andVladimirKolesnikov31CornellUniversity,Ithaca,NY,USA.
xfan@cs.
cornell.
edu2NewYorkUniversity,NewYork,NY,USA.
ganesh@cs.
nyu.
edu3BellLabs,MurrayHill,NJ,USA.
kolesnikov@research.
bell-labs.
comAbstract.
WeintroduceFreeHash,anewapproachtogeneratingGar-bledCircuit(GC)hashatnoextracostduringGCgeneration.
Thisisincontrastwithstate-of-the-artapproaches,whichhashGCsatcompu-tationalcostofupto6*ofGCgeneration.
GChashingisatthecoreofthecut-and-choosetechniqueofGC-basedsecurefunctionevaluation(SFE).
Ourmainideaistointertwinehashgeneration/vericationwithGCgenerationandevaluation.
WhileweallowanadversarytogenerateaGCGCwhosehashcollideswithanhonestlygeneratedGC,suchaGCw.
h.
p.
willfailevaluationandcheatingwillbediscovered.
OurGChashissimplya(slightlymodied)XORofallthegatetablerowsofGC.
ItiscompatiblewithFreeXORandhalf-gatesgarbling,andcanbemadetoworkwithmanycut-and-chooseSFEprotocols.
Withtoday'snetworkspeedsbeingnotfarbehindhardware-assistedxed-keygarblingthroughput,eliminatingtheGChashingcostwillsig-nicantlyimproveSFEperformance.
Ourestimatesshowsubstantialcostreductionintypicalsettings,anduptofactor6inspecializedapplica-tionsrelyingonGChashes.
WeimplementedGChashingalgorithmandreportonitsperformance.
Remark.
Inthiswork,weassumeexistenceofahashfunctionthatsatisesbothcorrelationrobustnessandcollisionresistance.
ArecentworkbyGuoetal.
[GKWY19]pointedoutthatourinstantiationofthehashfunctionisnotcollisionresistant,andfurthertheyshowedthatitissignicantlymoreexpensivethanpreviouslythoughttoconstructsuchhashfunctions.
ThissignicantlyimpactsperformanceofFreeHash.
Additionally,amorestreamlinedimplementationofstandardhashingfurtherreducestheperformanceimprovementsofFreeHash[Wan18].
Asaresult,wedon'tbelieveFreeHashimprovesonthestandardGC-based2PCtechniques,withthecurrentstateofaairs.
1IntroductionTodayGarbledCircuit(GC)isthemaintechniqueforsecurecomputation.
Ithasadvantagesofhighperformance,lowroundcomplexity/lowlatency,and,importantly,relativeengineeringsimplicity.
BothcoreGC(garbling),aswellasthemeta-protocols,suchasCut-and-Choose(C&C),havebeenthoroughlyinvestigatedandaretodayhighlyoptimized.
Particularlyinthesemi-honestmodeltherehavebeenfewasymptotic/qualitativeimprovementssincetheorig-inalprotocolsofYao[Yao86]andGoldreichetal.
[GMW87].
PossiblythemostimportantdevelopmentintheareaofpracticalSFEsincethe1980swastheveryecientoblivioustransfer(OT)extensiontechniqueofIshaietal.
[IKNP03].
ThisallowedtherunningofanarbitrarilylargenumberofOTsbyexecutingasmall(securityparameter)numberof(possiblyinecient)"bootstrapping"OTinstancesandanumberofsymmetrickeyprimitives.
ThecheapOTsmadeadramaticdierenceforsecurelycomputingfunctionswithlargeinputsrelativetothesizeofthefunction,aswellasforGMW-likeapproaches,whereOTsareperformedineachlevelofthecircuit.
AnotherimportantGCcoreimprovementistheFree-XORalgorithm[KS08a],whichallowedfortheevaluationofallXORgatesofacircuitwithoutanycomputationalorcommunicationcosts.
AsSFEmovesfromtheorytopractice,even"small"factorimprovementscanhaveasignicanteect.
1.
1MotivationofecientGChashing:cut-and-choose(C&C)andotheruses.
Inthisworkweimprove(actuallyshowhowtoachieveitforfree)acoregarblingfeatureofGC,circuithashing.
WediscusshowthisimprovesstandardGC-basedSFEprotocols.
Wealsodiscussevaluationofcertiedfunctions,andmotivatethisusecase.
GChashingisanessentialtoolforC&C,andisemployedinmanyusesofC&C.
WestartwithdescribingC&Catthehighlevel.
C&C.
Accordingtothe"Cut-and-ChooseProtocol"entryoftheEncyclopediaofCryptographyandSecurity[TJ11],a(non-zero-knowledge)C&CprotocolwasrstmentionedintheprotocolofRabin[Rab77]wherethisconceptwasusedtoconvinceapartythattheotherpartysentitaspeciallyformedintegern.
Theexpression"cutandchoose"wasintroducedlaterbyChaumin[BCC88]inanalogytoapopularcake-sharingproblem:givenacaketobedividedamongtwodistrustfulplayers,oneofthemcutsthecakeintwoshares,andletstheotheronechoose.
Recall,thebasicGCprotocolisnotsecureagainstcheatingGCgenera-tor,whocansubmitamaliciouslygarbledcircuit.
Today,C&Cisthestandardtoolinachievingmalicioussecurityinsecurecomputation.
Atthehighlevel,itproceedsasfollows.
GCgeneratorgeneratesanumberofgarbledcircuitsGC1,.
.
.
,GCnandsendsthemtoGCevaluator,whochoosesasubsetofthem(say,half)atrandomtobeopened(withthehelpofthegenerator)andveriesthecorrectnessofcircuitconstruction.
Ifallcircuitswereconstructedcorrectly,theplayersproceedtosecurelyevaluatetheunopenedcircuits,andtakethemajorityoutput.
ItiseasytoseethattheprobabilityofGCgeneratorsuc-ceedinginsubmittingamaliciouslygarbledcircuitisexponentiallysmallinn.
WenotethatsignicantimprovementintheconcretevaluesofnrequiredforaspecicprobabilityguaranteewasachievedbyrelativelyrecentC&Ctech-niques[LP11,Lin13,HKE13,Bra13,LR14,HKK+14,AO12,KM15].
2UsingGChashingforC&C.
Whatmotivatesourworkisthefollowingnatu-ralidea,whichwasrstformalizedinGoyaletal.
[GMS08].
Tosaveoncommuni-cation(usuallyamorescarceresourcethancomputation),GCgenerator,rstly,generatesallthecircuitsGC1,.
.
.
,GCnfromPRGseedss1,.
.
.
,sn.
Then,insteadofsendingthecircuitsGC1,.
.
.
,GCn,itsendstheirhashesH(GC1),.
.
.
,H(GCn).
Finally,whiletheevaluationcircuitswillneedtobesentinfulloverthenet-work,onlytheseedss1,.
.
.
,snneedtobesenttoverifythatGCgeneratordidnotcheatinthegenerationoftheopenedcircuits,savingasignicantamountofcommunicationatthecostofcomputingandcheckingH(GCi)forallncircuits.
Onmanyoftoday'scomputingarchitectures(e.
g.
IntelPCCPUs,withorwithouthardwareAES),thecostofhashingtheGCcanbeupto6*greaterthanthecostofxed-keygarbling.
Atthesametime,today'snetworkspeedsarecomparableinthroughputwithhardware-assistedxed-keygarbling(seeourcalculationsinSection5.
3).
Hence,eliminatingtheGChashingcostwillimproveSFEperformancebyeliminatingthe(smallerofthe)costofhashingorsendingtheopencircuits.
WestressthattheuseofourFreeHashrequiressyntacticchangesinC&Cprotocolsanditprovidesasecurityguaranteesomewhatdistinctfromcollision-resistanthash.
HenceitsuseinC&Cprotocolsshouldbeevaluatedforsecurity.
SeeSection5.
1formoredetails.
Additionally,weshowthatanewcomputation/communicationcostratiooeredbyourfreeGChashwillallowforreducedcommunication,computation,andexecutiontime,whileachievingthesamecheatingprobability.
SFEofprivatecertiedfunctions.
OneadvantageoeredbyGCisthehidingoftheevaluatedfunctionfromtheevaluator.
Tobemoreprecise,thecircuittopologyofthefunctionisrevealed,butthisinformationleak-agecanberemovedormitigatedbyusingtechniquessuchasuniversalcir-cuit[Val76,KS08b,LMS16,KS16]orcircuitbranchoverlay[KKW16].
Inpracticalscenarios,evaluatedfunctionsaretobeselectedasallowedbyamutuallyagreedpolicy,e.
g.
,topreventevaluationofidentityfunctionoutputtingplayer'sprivateinput.
Thenevaluatingahiddenfunctionpresumeseitherasemi-honestGCgenerator,oremployingamethodforpreventing/deterringout-of-policyGCgeneration.
AnecientC&Capproachdoesnotseemtohelppreventcheatinghere,sincecheckcircuitswillrevealtheevaluatedfunctionandwillnotbeacceptabletotheGCgenerator.
Further,dependingonpolicy/application,thezero-knowledgeproofsofcorrectlyconstructingthecircuitsmaybeveryexpensive.
Inmanyscenarios,CerticateAuthorities(CA)maybeusedtocertifythecorrectgenerationofGCs.
Indeed,thisisquitefeasibleatsmalltomediumscale.
Ourmotivatingapplicationhereistheprivateattribute-basedcredential(ABC)checking.
Veryrecentconcurrentworks[CGM16,KKL+16]showedforthersttimethatABCscanbebasedonGCs.
Whileboth[CGM16,KKL+16]discusspublicpolicyonly,theirGC-basedconstructionswillnotprecludeachievingpri-vatepolicy.
WenotethatthisisanovelpropertyintheABCliterature,whereallpreviouswork(inadditiontosupportingverysmallpoliciesonly)reliedinanessentialmanneronthepolicybeingknowntobothproverandverier.
3Atthehighlevel,thearchitecture/stepsforevaluationofprivateCA-certiedfunctionsisasfollows.
1.
CAgeneratesseedss1,.
.
.
snand,fori=1,.
.
.
n,CAgeneratesGCsGCi,GChashesH(GCi)andsignaturesσi=SignCA(H(GCi)).
Itsendsallsi,H(GCi),σitoABCverierV.
2.
ProverPandVproceedwithexecutionoftheABCproto-cols[CGM16,KKL+16],withthefollowingmodication:(a)WheneverGCGCineedstobesentbyV,insteadVgeneratesGCifromsiandsendstoPthepair(GCi,σi).
(b)PcomputesH(GC)andveriesthesignatureσipriortocontinuing.
IfthevericationorGCevaluationfails,Poutputsabort.
FreeHashwillallowtosignicantly(uptofactor6)reducethecomputationaleortrequiredbytheCAtosupportsuchanapplication.
Indeedthecostofthesignaturegenerationcanbesmallandignoredincaseswherethesignedcircuitsarelarge,orasinglesignaturecancertifyanumberofcircuits.
Thelatterwouldbethecasewheretwoplayersmaybeexpectedtoevaluateanumberofcircuits.
Importantly,evaluationofcertiedfunctionsmaybeessentialinscenarioswherelegislativeand/oroperationaldemandsrequirehighdegreeofaccountabil-ityandauditability(recall,digitalsignaturesarearecognizedlegalinstrumentinmanycountries[Wik]).
Thesescenariosmayfrequentlyariseingovernment,intelligenceormilitaryapplications.
Technicalresultsofthisworkwillhavedirectimpact,uptofactor6improve-ment,inthebottleneck(CAload)inmanyscenariosdiscussedabove.
1.
2OurContributionsandOutlineoftheWorkWestartthepresentationwithabriefdiscussionofrelatedworkandthenpro-vidingahigh-leveltechnicaloverviewofourapproach.
Then,inSection2,weintroduceexistingdenitionsandconstructionsrequiredforthiswork.
InSec-tion3wediscussdenitionalaspects,assumptionsandparameterchoicesofourwork.
WestarttechnicalSection4withintroducingourproposeddenitionofGChashsecurity.
Ourdenitionisweakerthanthestandardhashcollisionguarantees,yetitispossibletomakefreehashingworkwithseveralstandardGCconstructions(cf.
Section5.
1fordiscussionaboutitsC&Cuse).
Wethenpresenthashedgarblingalgorithmsforstandardgarbling(basedonJustGarbleof[BHKR13])aswellasforhalf-gatesgarblingof[ZRE15].
Ourmaincontri-butionistheimprovementofthestate-of-the-arthalf-gates;weconsiderhashedJustGarbleavaluablegeneralizationandaninstructionalexample.
InSection5,wediscusstheimpactofFreeHashgarblingandC&C.
Wereportonourimplementationanditsperformanceevaluation.
Wediscusstheapplicationtocertiedcircuits.
Weproposeauniedcostmetric(time)andshowhigherspeeds/smallercomputationandcommunicationforthesameerrorprobability.
Weestimatetotalexecutiontimereductionofabout43%fortheC&Ccomponentsof[LP11],andofabout64%for[AO12,KM15]insettingsweconsider(1GbpschannelandhardwareAES).
41.
3TechnicalOverviewofFreeGCHashInthissectionwepresentthemainintuitionbehindourtechnicalapproach.
WetakeadvantageoftheobservationthattheinputtothehashisagarbledcircuitGC,whichmustbeevaluatableusingthegarbledcircuitEvalfunction.
WewillnotrequirestandardhashcollisionresilienceofGCstrings,achievingwhichisverycostlyrelativetothecostofGCgeneration.
Instead,weguaranteethatifanadversarycanndanotherstringGCthatmatchesthehashofacorrectlygarbledGC,thenwithhighprobability,thegarbledcircuitpropertyofGCisbrokenanditsevaluationwillfail.
Wepresentourintuitioniteratively;westartwithanaiveecientapproach,whichwethenreneandarriveatasecurehashedgarbling.
Recall,westartwithacorrectlygeneratedGCGCwiththesetofoutputdecodinglabelsd.
Adversary'sgoalistogenerateacircuitGCwiththesamehashasGC,andwhichwillnotfailevaluation/decodinggiventhesameoutputlabelsd.
ThishashguaranteeissucientforcertainGC-basedSFEprotocols.
Asyntacticdierencewith[GMS08]C&ChashingisthatvericationofFreeHashinvolvesGCevaluation,andisonlypossibleonceinputlabelsarereceived(e.
g.
,afterOTofinputlabels).
Moreimportantly,FreeHash,asappliedtoC&C,providesasecurityguaranteesubtlydistinctfromcollision-resistanthash.
Hence,drop-inreplacementof[GMS08]C&ChashingwithFreeHashmaynotbealwayspossible,andingeneralshouldbedonebyhandandoriginalproofsre-checked.
SeeSection5.
1foradditionaldiscussion.
Wepresenttheintuitionfortheclassicalfour-rowGC;weusesimilarideastoachievehalf-gatesGChashingaswell.
WepresentandprovesecurebothFreeHashconstructions.
TherstFreeHashideaistosimplysetthehashofthegarbledcircuittobetheXORofallgarbledtable(GT)rowsofGC.
Thisisclearlyproblematic,sinceacheatinggarblerAcanmount,forexample,thefollowingattack.
AwillsetoneGTentrytobetheencryptionofthewrongwirelabel.
ThisaectstheXORhashasfollowsH(GC)=H(GC).
Nowsupposethegarblerknows(orguesses)whichGTentryanywhereinGCwillnotbeusedinevaluation(inactiveGTrow).
NowAsimplyreplacestheinactiveGTrowXwithvalueX.
Thiswillrestorethehashtothedesiredvalue,andsincethisentrywillnotbeusedintheevaluation,thegarblerwillnotbecaught.
Thefollowingrenementofthisapproachcounterstheaboveattack:wemakethegate'soutputwirekeydepend(inanecientmanner)onallGTrowsofthatgate.
TheideaisthatXORhashcorrection,suchasabove,willnecessarilyinvolvemodicationtoanactiveGTrow,whichwillaectthecomputedwirekeyonthatgate.
Importantly,becausewirekeysandGTrowsarerelatedviaarandom(albeitknown)function,aGTrowosetby(neededto"x"thehash)willresultineectivelyrandomizingtheoutputwirelabelofthegate.
Becauseanon-failingevaluationrequiresoutputwirelabelstobeconsistentwiththexeddecodinginformationd,Awillnowbestuck.
WeattemptthisbystartingwithasecuregarblingschemeG,andmodify-ingthewaythewirelabelsaredened,asfollows.
Thetwowirelabelsw0i,w1i5associatedwithgateGi'soutputwirewillnowbetreatedastemporarylabels.
AlabelWjiofthenewschemewillbeobtainedfromthewjisimplybyXORingitwithalltheGTrowsofGi.
Thisisnotquitesucient,asitstillallowstheattackertomodifyaGTrowandthencorrectitwithinthesamegatetable.
Thisispossiblesincea"x"forthehashdoesnotdisruptthevalidityofthewirelabel,asboththehashandthenewwirelabelaredenedinthesamemanner(asXORofalltheGTrowsofGi).
Ournalidea,istousetheGTrowsasXORpadsinadierentmannerforcomputingtheGChashandforosettingthewirevalues.
Thisway,thexforthehashw.
h.
p.
willnotsimultaneouslykeepthewirelabelvalid.
WeachievethisbymalleatingGTrowspriortousingthemasXORpadsinwirevaluecomputation.
Itisnothardtoshowthattheabovechangespreservetheprivacyandauthenticitypropertiesofthegarblingscheme.
Wesummarizetheintuitionforthehashsecurityoftheaboveconstruction.
ConsideraGC=GCthatcollidesundertheabovehash.
Then,theevaluationofGCwilldeviatefromthatofGCw.
r.
t.
somewirelabel.
Importantly,GCevaluationcansubsequentlyeitherreturntoavalidwirelabelortoacorrectrunninghash,butnotboth.
Thus,evaluationofGCusingencodinginformationecannotgobacktoboththewirelabelandthehashbeingcorrect.
1.
4RelatedWorkToourknowledge,thereisnopriorworkspecicallyaddressinghashingofGCs.
Atthesametime,signicantresearcheorthasbeenexpendedonoptimizingcoreGCperformance.
WorkincludesalgorithmicGCimprovements,suchasFreeXOR[KS08a],FleXOR[KMR14],half-gates[ZRE15],aswellasoptimizingunderlyingprimitives,suchasJustGarble[BHKR13].
OurworkcomplementstheexistingGCimprovementwork.
Ofcourse,thenaturalGChashingapproachworks:justhashthegeneratedGC.
Theproblemwiththisis,ofcourse,itscost.
Relativecostofxed-keyciphergarblingandhashingarestronglyarchitecture-dependent.
Theycanbealmostthesame(e.
g.
,whenbothAESandSHAareimplementedinhardware).
Inanotherextreme,Intel'swhitepaper[GGO+]reportsthatAES-NIevaluationof16-byteblocksis23*fasterthatthatofSHA1(35,965.
9vs793,718.
7KB/sec).
InourexperimentsreportedinSection5.
2,weobservedabout6*performancedierencebetweenAES-NIandSHA1.
Improvingonthis,andmotivatedinpartbytheavailabilityoffasthardwareAESimplementations,therewasashortseriesofworks[BRS02,RS08b,RS08a,B¨OS11],implementingahashfunctionwiththreexed-keyAESfunctioncalls.
ArecentworkofRogawayandStein-berger[RS08a]constructsaclassoflinearly-determined,permutation-basedcompressionfunctions{0,1}mn→{0,1}rnmakingkcallstothedierentpermutationsπifori∈[k],wheretheynamedtheirconstructionasLPmkr.
ThefastestconstructionLP362(12.
09cyclesperbyte)[B¨OS11],with6callsto6xed-keyAESwouldcostabout6*ofthatoffastgarbling.
Davies-Meyer-basedhashconstruction[Win84]intheidealciphermodelconsideredinliteratureisreportedtohavesimilarspeeds[B¨OS11].
Incomparison,ourworkeliminatesthecostofhashwhatsoever,whileaddingnocosttogarblingorGCevaluation.
C&CandusesofhashedGC.
ThereisalongsequenceofGC-basedSFEwork,e.
g.
[Lin13,HKE13,Bra13,LR14,HKK+14,KM15],mostofwhichusessomeformofC&CorchallengingtheGCgenerator.
Basedon[GMS08],theseworkswillbenetfromourresult,tovaryingdegree.
TheexactperformancebenetwilldependonwheretheFreeHashisused,theratioofevaluated/testcircuits,aswellasthecomputational/communicationresourcesavailabletotheplayers.
InSection5,wecalculateperformanceimprovementinseveralC&CprotocolsduetoourGChash.
2PreliminariesNotation.
Letpptdenoteprobabilisticpolynomialtime.
Weletλbethese-curityparameter,[n]denotetheset{1,.
.
.
,n},and|t|denotethenumberofbitsinastring.
Wedenotethei-thbitvalueofastringsbys[i],use||tode-noteconcatenationofbitstrings.
WewritexR←XtomeansamplingavaluexuniformlyfromthesetX.
Forabitstrings,weletsidenotethebitstringobtainedbyshiftingsbyibitstotheleft.
Throughout,byshiftwemeanacircularshift,wherethevacantbitpositionsarellednotbyzerosbutbytheshiftedbits.
lsb(s)denotestheleastsignicantbitofstrings.
Wesayafunctionf(·)isnegligibleifc∈N,thereexistsn0∈Nsuchthatn≥n0,itholdsthatf(n)nandm,narepolynomialsinsecurityparameterλ.
AninstanceH∈H7canbedescribedbyakeywhichispublicknown.
WesayahashfunctionfamilyHiscollision-resistantifforanypptadversaryAPr[HR←H,(x,x)←A(H):x=x∧H(x)=H(x)]=negl(λ)2.
1Yao'sconstructionAcomprehensivetreatmentofYao'sconstructionofgarbledcircuits,wasgivenin[LP09].
Atahigh-level,inYao'sconstruction,eachwireofthebooleancircuitisassociatedwithtworandomstringscalledwirelabelsorwirekeysthatencodelogical0and1wirevalues.
Agarbledtruthtableisconstructedforeverygateinthecircuit,whereeachcombinationofinputwirelabelsisusedtoencrypttheappropriateoutputwirelabelasperthegatefunctionality.
Thisresultsinfourciphertextspergate,oneforeachinputcombinationofthegate.
Theevaluatorknowsonlyonelabelforeachinputwire,andcantherefore,openonlyoneofthefourciphertexts.
2.
2GarbledCircuitsWemakeuseoftheabstractionofgarblingschemes[BHR12]introducedbyBel-lareetal.
Atahigh-level,agarblingschemeconsistsofthefollowingalgorithms:Gbtakesacircuitasinputandoutputsagarbledcircuit,encodinginformation,anddecodinginformation.
EntakesaninputxandencodinginformationandoutputsagarbledinputX.
EvaltakesagarbledcircuitandgarbledinputXandoutputsagarbledoutputY.
Finally,DetakesagarbledoutputYanddecodinginformationandoutputsaplaincircuit-output(oranerror⊥).
Wenotethatthisdeviatesfromthedenitionof[BHR12],inthat,weinclude⊥intherangeofthedecodingalgorithmDe,soitnowoutputsaplainoutputvaluecorrespondingtoagarbledoutputvalueor⊥ifthegarbledoutputvalueisinvalid.
[JKO13]addanadditionalvericationalgorithmVetothegarblingscheme.
Formally,wedeneaveriablegarblingschemebyatupleoffunctionsG=(Gb,En,Eval,De,Ve)witheachfunctiondenedasfollows.
–GarblingalgorithmGb(1λ,C):ArandomizedalgorithmwhichtakesasinputthesecurityparameterandacircuitC:{0,1}n→{0,1}mandoutputsatupleofstrings(GC,{X0j,X1j}j∈[n],{Z0j,Z1j}j∈[m]),whereGCisthegarbledcircuit,thevalues{X0j,X1j}j∈[n]denotetheinput-wirelabels,andthevalues{Z0j,Z1j}j∈[m]denotetheoutput-wirelabels.
–EncodealgorithmEn(x,{X0j,X1j}j∈[n]):adeterministicalgorithmthatout-putstheinputwirelabelsX={Xx[i]i}i∈[n]correspondingtoinputx.
–EvaluationalgorithmEval(GC,{Xj}j∈[n]):AdeterministicalgorithmwhichevaluatesgarbledcircuitGConinput-wirelabels{Xj}j∈[n],andoutputsagarbledoutputY.
–DecodealgorithmDe(Y,{Z0j,Z1j}j∈[m]):Adeterministicalgorithmthatout-putstheplaintextoutputcorrespondingtoYor⊥signifyinganerrorifthegarbledoutputYisinvalid.
8–VericationalgorithmVe(C,GC,{Z0j,Z1j}j∈[m],{X0j,X1j}j∈[n]):Adetermin-isticalgorithmwhichtakesasinputacircuitC,garbledcircuitGC,input-wirelabels{X0j,X1j}j∈[n],andoutput-wirelabels{Z0j,Z1j}j∈[m]andoutputsacceptifGCisavalidgarblingofCandrejectotherwise.
Averiablegarblingschememaysatisfyseveralpropertiessuchascorrect-ness,privacy,obliviousness,authenticityandveriability.
Wenowreviewsomeofthesenotions:(1)correctness,(2)privacy(3)authenticity,and(4)veria-bility.
Thedenitionsforcorrectnessandauthenticityarestandard:correctnessenforcesthatacorrectlygarbledcircuit,whenevaluated,outputsthecorrectoutputoftheunderlyingcircuit;authenticityenforcesthattheevaluatorcanonlylearntheoutputlabelthatcorrespondstothevalueofthefunction.
Veri-ability[JKO13]allowsonetocheckthatthegarbledcircuitindeedimplementsthespeciedplaintextcircuitC.
Weincludethedenitionsofthesepropertiesforcompleteness.
Denition2.
1(Correctness)AgarblingschemeGiscorrectifforallinputlengthsn≤poly(λ),circuitsC:{0,1}n→{0,1}mandinputsx∈{0,1}n,thefollowingprobabilityisnegligibleinλ:Pr(De(Eval(GC,{Xxjj}j∈[n]),{Z0j,Z1j}j∈[m])=C(x):(GC,{X0j,X1j}j∈[n],{Z0j,Z1j}j∈[m])←Gb(1λ,C)).
Denition2.
2(Privacy)AgarblingschemeGhasprivacyifforallinputlengthsn≤poly(λ),circuitsC:{0,1}n→{0,1}m,thereexistsapptsimulatorSimsuchthatforallinputsx∈{0,1}n,forallprobabilisticpolynomial-timeadversariesA,thefollowingtwodistributionsarecomputationallyindistinguish-able:–Real(f,x):run(GC,e,d)←Gb(1λ,C),andoutput(GC,En(x,e),d).
–IdealSim(C,f(x)):outputSim(1λ,C,C(x))Denition2.
3(Authenticity)AgarblingschemeGisauthenticifforallinputlengthsn≤poly(λ),circuitsC:{0,1}n→{0,1}m,inputsx∈{0,1}n,andallprobabilisticpolynomial-timeadversariesA,thefollowingprobabilityisnegligibleinλ:PrY=Eval(GC,{Xxjj}j∈[n])∧De(Y,{Z0j,Z1j}j∈[m])=⊥:(GC,{X0j,X1j}j∈[n],{Z0,Z1}j∈[m])←Gb(1λ,C)Y←A(C,x,GC,{Xxjj}j∈[n]).
Denition2.
4(Veriability)AgarblingschemeGisveriableifforallinputlengthsn≤poly(λ),circuitsC:{0,1}n→{0,1}m,inputsx∈{0,1}n,andallprobabilisticpolynomial-timeadversariesA,thefollowingprobabilityisnegligibleinλ:PrDe(Eval(GC,En(x,e)),d)=C(x):(GC,e,d)←A(1λ,C)Ve(C,GC,d,e)=accept9Inthedenitionofveriabilityabove,wegivethedecodinginformationex-plicitlytothevericationalgorithmsinceinourconstructionthegarbledcircuitincludesonlythegarbledtablesandnotthedecodinginformation.
WenotethatanaturalandecientwaytoobtainaveriablegarblingschemeistogenerateGCbyusingtheoutputofapseudorandomgeneratoronaseedastherandomtapeforGb,andthenprovidetheseedtothevericationprocedureVe.
VewillregeneratetheGCandtheencodinganddecodingtables,andwilloutputacceptforagarbledcircuitifandonlyifitisequaltothegeneratedone.
2.
3Free-XORandotheroptimizationsSeveralworkshavestudiedoptimizationstoreducethesizeofagarbledgatedownfromfourciphertexts.
Garbledrow-reductionwasintroducedbyNaor,PinkasandSumner[NPS99].
There,insteadofchoosingthewirelabelsatran-domforeachwire,theyarechosensuchthattherstciphertextwillbetheall-zerostring,andhenceneednotbesent.
In[PSSW09],theauthorsdescribeawaytofurtherreducethenumberofciphertextspergateto2,byapplyingpoly-nomialinterpolationateachgate.
KolesnikovandSchneider[KS08a]introducedtheFreeXORapproach,allowingevaluationofXORgateswithoutanycost.
Here,theideaistochoosewirelabelssuchthatthetwolabelsonthesamewirehavethesame(secret)osetacrosstheentirecircuit.
Thetwolabelsforagivenwireareoftheform(A,A),whereissecretandcommontoallwires.
Now,asrstproposedin[Kol05],anevaluatorwhohasoneof(A,A)andoneof(B,B)cancomputetheXORbysimplyXORingthewirelabels.
TheresultiseitherCorCwhereC=ABandcorrectlyrepresentstheresultofXOR.
Thus,nociphertextsareneededfortheXORgate.
Kolesnikov,MohasselandRosulekproposedageneralizationofFreeXORcalledFleXOR[KMR14].
InFleXOR,eachXORgatecanbegarbledusing0,1,or2ciphertexts,dependingoncertainstructuralpropertiesofthecircuit.
In[ZRE15],theauthorspresentamethodbuiltonFreeXORthatcangarbleanANDgateusingonlytwocipher-texts.
ThistechniqueisalsocompatiblewithFreeXOR.
TheideaistowriteanANDgateasacombinationofXORandtwohalf-gates,whereahalf-gateisanANDgateforwhichonepartyknowsoneoftheinputs.
Thehalf-gatescanbegarbledwithoneciphertexteach,andtheresultingANDgate,incombinationwithfree-XOR,usestwociphertexts.
3PreliminaryDiscussion3.
1OurTreatmentofGCTopologyandFormalizationoftheGCRepresentationAformalizationofwhatpreciselytheGCdescriptionstringGCincludesisoftennaturalandhenceisusuallyomittedfromdiscussion.
Inoursettingthisanimportantaspect,aswefocusonthecollisionresilience-relatedpropertiesofGCstrings,aswellasonminimizingthesizeofGCanditscomputationtime.
10Firstly,weremindthereaderthatintheBHR[BHR12]notationthefunc-tionGboutputsthegarblingfunctionF.
Sinceitisproblematictooperateonfunctions,BHRregardsGbasoperatingonstringsrepresentinganddeningthecorrespondingfunctions.
Inournotation,GboutputsGC,whichwetreatasastringdeningtheevaluationprocessaswell.
Clearly,GCwillcontainasetofgarbledtables;thequestionishowtotreatthecircuittopology,i.
e.
exactlyhowtodescribe/denehowEvalshouldprocessGC.
Onechoiceistotreattheplaintextcircuit/topologyasapartofGC.
Becausewefocusonsize/computation,thisapproachwouldcausesomewaste.
Indeed,inmostscenarios,thecircuitandtopologyisknowntobothplayers,andhencecouldbeimplicitinGC.
Instead,weopttoconsiderthecircuitdescription,includingthelocationsofthefreeXORgatesasanexternallygeneratedstring.
ItiscertainlythecaseinSFEwheretheevaluatedfunctionisknowntobothplayers,andplayerscanaprioriadoptaconventiononhowtomaptheGCgarbledgatestothecircuitgates,hencedeningtheevaluationprocess.
InPFE,whichisthecaseinourcertiedfunctionevaluationscenario(seeSection1.
1),theevaluatedfunctionisnotknowntotheevaluator.
Inthiscase,westilltreatthetopology/evaluationinstructionsasexternaltoGCandassumethattheyarecorrectlydeliveredtotheevaluator.
Wenotethatinthecertiedfunctioncase,thiscanbenaturallyachievedbytheCAsigningthetopologywithauniqueidentier,andincludingthisidentierwithGCandthehashofGC.
3.
2OurAssumptionsOurworkoptimizeshigh-performanceprimitives,anditisimportanttobeclearontheassumptionswerequireofthemsoastoproperlycomparetorelatedwork.
Weusethesameprimitives,andnearlyidenticalconstructionsasJustGar-ble[BHKR13]andhalf-gates[ZRE15].
Asaresult,privacyandauthenticityprop-ertiesofourschemesholdunderthesameassumptionsas[BHKR13,ZRE15],namelythattheDavies-Meyer(DM)constructionisaprimitivemeetingtheguaranteeoftherandom-permutationmodel(RPM).
While[BHKR13]provesthesecurityoftheirconstructioninRPMdirectly,[ZRE15]abstractstheDMsecuritypropertyasavariantofcorrelation-robustfunction.
Ourrst(auxiliary)construction,namely,theprivacyproperty,isprovenunderassumptionthatDMiscorrelation-robust.
Toachievehashsecurity,weneedtoassumecollisionresistanceofDM.
WenotethatcollisionresistanceofDMcanbeachievede.
g.
,byassumingthatDMmeetstherequirementoftheideal-ciphermodel(ICM)[BRS02].
3.
3CipherInstantiationAsnotedabove,weinstantiatethekeyderivationfunction(KDF)callsasdo[BHKR13,ZRE15],withtheDavies-Meyerconstruction.
Namely,theinput11XtoKDFH(X,i)arethe128-bitlongwirekeys,andiisaninternalintegerthatsimplyincrementsperhashfunctioncall.
WesetHπ(X,i)=π(K)K,whereK=2xi(πisassumedtobeanidealcipher,instantiatedwith128-bitAESwithrandomlychosenkey).
3.
4HashSecurityParametersWeuseλ=128-bitsecurityparameter,whichisstandardforencryptionandGCs.
However,128-bithashdomainisoftenseenasinsucient.
Thisisbe-causeofthebirthdayattack,whichprovidestime-spacetradeoforanattacker.
Specically,acollision-ndingattackercanprecomputeandstoreasquare-rootnumberofhashimages.
Thenbybirthdayparadox,arandomcollisionwillbefoundamongtheseimageswithsignicantprobability.
Thisattackrequires264hashcomputationsandecientlyaccessiblestoragefor264hashvalues.
Wearguethat128-bithashsecurityisneverthelessacceptableinSFE,ifusedcarefully.
Firstly,wenotethatcomputing264hashesisanextremelyexpensivetask.
Indeed,recentBitcoinreports[Bra]suggestthatworld'shashingpowerrecentlypeakedat1PetaHashpersecond(i.
e.
10005n,thusgivingacheatingprobabil-ity2n<2nforthesamecommunicationcomplexity.
Forlargecircuits,weexpectCh,givingconcreteimprovementsinthesecurityatnoadditionalcommunicationcost.
CommunicationkNumberofcircuitsCheatingprobability/Deterrence[LP11]k=125|GC|n=125240[LP11]withhG,q=1/4k=125|GC|n=166251[LP11]withhG,q=1/8k=125|GC|n=200262[KM15]without[GMS08]5k=10|GC|n=100.
9[KM15]withhG,q=1/4k=10|GC|n=360.
972[KM15]withhG,q=1/8k=10|GC|n=720.
986Table25Wenotethat[KM15]incorporatesthe[GMS08]hashingintheprotocol.
Aswediscussed,sendingcircuitsoverafastchannelmayonlybeabout3*slowerthanhardware-assistedgarbling,whilecomputingSHA1maybeupto6*slowerthansuchgarbling.
Hence,sendingcircuitsoverafastchannelmayactuallybefasterthangeneratingSHA1hash.
Therefore,inourcalculationsforthefastchannelsettingasabove,weconsider[KM15]without[GMS08]hash.
24Performanceimprovementforconstantcheatingprobability.
Considerthetaskofevaluatingabillion-gatecircuit(cf.
[KSS12]).
Weshowestimatedimprovementduetoourtechniqueasappliedto[LP11]and[KM15].
Wedothisintermsofexpendedtimebyunifyingthecomputationandcommunicationcostsofgeneratingandsendinggarbledcircuits.
Thesecalculationsarenotbasedonspecicimplementationsorprotocoldenitions.
Insteadtheyarebasedonsimpleestimatesoftimeneededtogenerate,hashandsendGCs,andaddingthemtogether.
Werstcalculateandexplainthecomputationandcommunicationcostsinsecondsofourbasictasks.
Accordingto[BHKR13],usingJustGarbletogarbletheAEScircuit(6660non-XORgates)takes637microseconds.
Adjustingforsize,wecalculatethatthetimetakenforGCgenerationforacircuitwith1billiongatestobe95seconds.
Forcommunication,assumingidealscenarioin1Gbpschannel,assumewecansend1billionbits/sec.
Thusthetimetosendacircuitof1billiongatesis256secondsat(assuminghalfgatesand2*128bitspergate).
Thetotalnumberofsecondsneededinthecut-and-choosephasetoma-liciouslyevaluatea1billion-gatecircuitwith240cheatingprobabilityusingprevioustechniqueandourconstructionusingtheoptimalparameters.
Inourcalculationweincludethecostsofgenerating,hashing(inourscheme)andsend-ingtheGCs.
Wedonotincludethecostofregeneratingthecheckcircuitsattheevaluator'sendthatisincurredbyourtechnique.
Thisisbecausethiscostisalsoincurredbyothertechniques.
Indeed,checkingcorrectnessofacircuitthattheevaluatoralreadyhas(directly,orwhenusing[GMS08]hash)issimplestandfastestbyreceivingitsgeneratingseed,reconstructingandcomparing.
Weareconcernedonlywiththecut-and-choosephase,andignorethetimetakenforOTandGCevaluationintheprotocolandshowhowourconstructionallowforreducedexecutiontimeinthecut-and-choosephase.
ThecostinsecondscalculatedinTable3isobtainedbyaddingthetimetogenerate,hash(ifneeded)andsendalltherequiredgarbledcircuits.
Asexplainedabove,weassumethatittakes95secondstogeneratea1-BilliongateGC,and256secondstosendit.
Finally,wenotethateventhoughwedon'tknowwhetherthedual-executionC&CofHuangetal.
[HKE13]couldbemodiedtotakeadvantageofourFreeHash,wepointoutthatanimprovedbalancebetweenthecheckandevaluationcircuitsispossiblewhen[HKE13]isusedwiththe[GMS08]hash.
Weincludethecalculationsofoptimalparametersfor[HKE13]inAppendixA.
TotalnumberNumberofCircuitsTimeofcircuitscheckcircuitssent(insecs)[LP11]1257512543875[LP11]+hG125755024675Table3:Abillion-gatecircuit.
Executiontimeestimatesofcut-and-choosewithourimprovementstoachievecheatingprobabilityof24025TotalnumberNumberofCircuitsTimeofcircuitscheckcircuitssent(insecs)[AL07]109103510[AL07]+hG10911260[KM15]without[GMS08]5109103510[KM15]+hG10911260Table4:Abillion-gatecircuit.
Executiontimeestimatesofcut-and-choosewithourimprovementstoachievedeterrenceof=0.
9.
Acknowledgments.
WethanktheanonymousreviewersofEurocrypt2017forvaluablecomments.
WealsothankMikeRosulekforadiscussionontheapplicabilityoftheFreeHash.
ThisworkwassupportedbytheOceofNavalResearch(ONR)contractnumberN00014-14-C-0113.
ReferencesAL07.
YonatanAumannandYehudaLindell.
Securityagainstcovertadversaries:Ecientprotocolsforrealisticadversaries.
InSalilP.
Vadhan,editor,TCC2007,volume4392ofLNCS,pages137–156.
Springer,Heidelberg,February2007.
AO12.
GiladAsharovandClaudioOrlandi.
Callingoutcheaters:Covertsecu-ritywithpublicveriability.
InXiaoyunWangandKazueSako,editors,ASIACRYPT2012,volume7658ofLNCS,pages681–698.
Springer,Hei-delberg,December2012.
BCC88.
GillesBrassard,DavidChaum,andClaudeCrepeau.
Minimumdisclosureproofsofknowledge.
J.
Comput.
Syst.
Sci.
,37(2):156–189,1988.
BHKR13.
MihirBellare,VietTungHoang,SriramKeelveedhi,andPhillipRogaway.
Ecientgarblingfromaxed-keyblockcipher.
In2013IEEESymposiumonSecurityandPrivacy,pages478–492.
IEEEComputerSocietyPress,May2013.
BHR12.
MihirBellare,VietTungHoang,andPhillipRogaway.
Foundationsofgarbledcircuits.
InProceedingsofthe2012ACMconferenceonComputerandcommunicationssecurity,pages784–796.
ACM,2012.
BMR90.
DonaldBeaver,SilvioMicali,andPhillipRogaway.
Theroundcomplex-ityofsecureprotocols.
InProceedingsofthetwenty-secondannualACMsymposiumonTheoryofcomputing,pages503–513.
ACM,1990.
B¨OS11.
JoppeW.
Bos,Onur¨Ozen,andMartijnStam.
EcienthashingusingtheAESinstructionset.
InBartPreneelandTsuyoshiTakagi,editors,CHES2011,volume6917ofLNCS,pages507–522.
Springer,Heidelberg,September/October2011.
BR93.
MihirBellareandPhillipRogaway.
Randomoraclesarepractical:Aparadigmfordesigningecientprotocols.
InV.
Ashby,editor,ACMCCS93,pages62–73.
ACMPress,November1993.
26Bra.
DannyBradbury.
Bitcoinminingdicultysoarsashashingpowernudges1petahash.
http://www.
coindesk.
com/bitcoin-mining-difficulty-soars-hashing-power-nudges-1-petahash/.
RetrievedFeb3,2017.
Bra13.
LusT.
A.
N.
Brandao.
Securetwo-partycomputationwithreusablebit-commitments,viaacut-and-choosewithforge-and-losetechnique-(extendedabstract).
InKazueSakoandPalashSarkar,editors,ASI-ACRYPT2013,PartII,volume8270ofLNCS,pages441–463.
Springer,Heidelberg,December2013.
BRS02.
JohnBlack,PhillipRogaway,andThomasShrimpton.
Black-boxanaly-sisoftheblock-cipher-basedhash-functionconstructionsfromPGV.
InMotiYung,editor,CRYPTO2002,volume2442ofLNCS,pages320–335.
Springer,Heidelberg,August2002.
CG13.
RanCanettiandJuanA.
Garay,editors.
CRYPTO2013,PartII,volume8043ofLNCS.
Springer,Heidelberg,August2013.
CGM16.
MelissaChase,ChayaGanesh,andPaymanMohassel.
Ecientzero-knowledgeproofofalgebraicandnon-algebraicstatementswithapplica-tionstoprivacypreservingcredentials.
InMatthewRobshawandJonathanKatz,editors,CRYPTO2016,PartIII,volume9816ofLNCS,pages499–530.
Springer,Heidelberg,August2016.
CPS08.
Jean-SebastienCoron,JacquesPatarin,andYannickSeurin.
Therandomoraclemodelandtheidealciphermodelareequivalent.
InWagner[Wag08],pages1–20.
FVK+15.
BenA.
Fisch,BinhVo,FernandoKrell,AbishekKumarasubramanian,VladimirKolesnikov,TalMalkin,andStevenM.
Bellovin.
Malicious-clientsecurityinblindseer:AscalableprivateDBMS.
In2015IEEESymposiumonSecurityandPrivacy,pages395–410.
IEEEComputerSocietyPress,May2015.
GG14.
JuanA.
GarayandRosarioGennaro,editors.
CRYPTO2014,PartII,volume8617ofLNCS.
Springer,Heidelberg,August2014.
GGO+.
VinodhGopal,JimGuilford,ErdincOzturk,SeanGulley,andWajdiFeghali.
ImprovingOpenSSLperformance.
https://software.
intel.
com/sites/default/files/open-ssl-performance-paper.
pdf.
RetrievedFeb3,2017.
GKWY19.
ChunGuo,JonathanKatz,XiaoWang,andYuYu.
Ecientandsecuremultipartycomputationfromxed-keyblockciphers.
CryptologyePrintArchive,Report2019/074,2019.
https://eprint.
iacr.
org/2019/074.
GMS08.
VipulGoyal,PaymanMohassel,andAdamSmith.
Ecienttwopartyandmultipartycomputationagainstcovertadversaries.
InSmart[Sma08],pages289–306.
GMW87.
OdedGoldreich,SilvioMicali,andAviWigderson.
HowtoplayanymentalgameorAcompletenesstheoremforprotocolswithhonestmajority.
InAlfredAho,editor,19thACMSTOC,pages218–229.
ACMPress,May1987.
HKE13.
YanHuang,JonathanKatz,andDavidEvans.
Ecientsecuretwo-partycomputationusingsymmetriccut-and-choose.
InCanettiandGaray[CG13],pages18–35.
HKK+14.
YanHuang,JonathanKatz,VladimirKolesnikov,RanjitKumaresan,andAlexJ.
Malozemo.
Amortizinggarbledcircuits.
InGarayandGennaro[GG14],pages458–475.
27IKNP03.
YuvalIshai,JoeKilian,KobbiNissim,andErezPetrank.
Extendingobliv-ioustransferseciently.
InDanBoneh,editor,CRYPTO2003,volume2729ofLNCS,pages145–161.
Springer,Heidelberg,August2003.
JKO13.
MarekJawurek,FlorianKerschbaum,andClaudioOrlandi.
Zero-knowledgeusinggarbledcircuits:howtoprovenon-algebraicstatementseciently.
InProceedingsofthe2013ACMSIGSACconferenceonCom-puter&communicationssecurity,pages955–966.
ACM,2013.
KKL+16.
VladimirKolesnikov,HugoKrawczyk,YehudaLindell,AlexJ.
Malozemo,andTalRabin.
Attribute-basedkeyexchangewithgeneralpolicies.
Cryp-tologyePrintArchive,Report2016/518,2016.
http://eprint.
iacr.
org/2016/518.
KKW16.
W.
SeanKennedy,VladimirKolesnikov,andGordonWilfong.
Overlayingcircuitclausesforsecurecomputation.
CryptologyePrintArchive,Report2016/685,2016.
http://eprint.
iacr.
org/2016/685.
KM15.
VladimirKolesnikovandAlexJ.
Malozemo.
Publicveriabilityinthecovertmodel(almost)forfree.
InTetsuIwataandJungHeeCheon,ed-itors,ASIACRYPT2015,PartII,volume9453ofLNCS,pages210–235.
Springer,Heidelberg,November/December2015.
KMR14.
VladimirKolesnikov,PaymanMohassel,andMikeRosulek.
FleXOR:Flex-iblegarblingforXORgatesthatbeatsfree-XOR.
InGarayandGennaro[GG14],pages440–457.
KMRR15.
VladimirKolesnikov,PaymanMohassel,BenRiva,andMikeRosulek.
Richereciency/securitytrade-osin2PC.
InYevgeniyDodisandJes-perBuusNielsen,editors,TCC2015,PartI,volume9014ofLNCS,pages229–259.
Springer,Heidelberg,March2015.
Kol05.
VladimirKolesnikov.
Gateevaluationsecretsharingandsecureone-roundtwo-partycomputation.
InBimalK.
Roy,editor,ASIACRYPT2005,vol-ume3788ofLNCS,pages136–155.
Springer,Heidelberg,December2005.
KS08a.
VladimirKolesnikovandThomasSchneider.
Improvedgarbledcircuit:FreeXORgatesandapplications.
InLucaAceto,IvanDamgrard,LeslieAnnGoldberg,MagnusM.
Halldorsson,AnnaIngolfsdottir,andIgorWalukiewicz,editors,ICALP2008,PartII,volume5126ofLNCS,pages486–498.
Springer,Heidelberg,July2008.
KS08b.
VladimirKolesnikovandThomasSchneider.
Apracticaluniversalcircuitconstructionandsecureevaluationofprivatefunctions.
InGeneTsudik,editor,FC2008,volume5143ofLNCS,pages83–97.
Springer,Heidelberg,January2008.
KS16.
AgnesKissandThomasSchneider.
Valiant'suniversalcircuitispractical.
InMarcFischlinandJean-SebastienCoron,editors,EUROCRYPT2016,PartI,volume9665ofLNCS,pages699–728.
Springer,Heidelberg,May2016.
KSS12.
BenjaminKreuter,AbhiShelat,andChih-HaoShen.
Billion-gatese-curecomputationwithmaliciousadversaries.
InProceedingsofthe21stUSENIXConferenceonSecuritySymposium,Security'12,pages14–14,Berkeley,CA,USA,2012.
USENIXAssociation.
Lin13.
YehudaLindell.
Fastcut-and-choosebasedprotocolsformaliciousandcovertadversaries.
InCanettiandGaray[CG13],pages1–17.
LMS16.
HelgerLipmaa,PaymanMohassel,andSaeedSadeghian.
Valiant'suniver-salcircuit:Improvements,implementation,andapplications.
CryptologyePrintArchive,Report2016/017,2016.
http://eprint.
iacr.
org/2016/017.
28LP09.
YehudaLindellandBennyPinkas.
AproofofsecurityofYao'sprotocolfortwo-partycomputation.
JournalofCryptology,22(2):161–188,April2009.
LP11.
YehudaLindellandBennyPinkas.
Securetwo-partycomputationviacut-and-chooseoblivioustransfer.
InYuvalIshai,editor,TCC2011,volume6597ofLNCS,pages329–346.
Springer,Heidelberg,March2011.
LR14.
YehudaLindellandBenRiva.
Cut-and-chooseYao-basedsecurecomputa-tionintheonline/oineandbatchsettings.
InGarayandGennaro[GG14],pages476–494.
Mal.
AlexJ.
Malozemo.
libgarble:garblinglibrarybasedonjustgarble.
https://github.
com/amaloz/libgarble.
NPS99.
MoniNaor,BennyPinkas,andReubanSumner.
Privacypreservingauc-tionsandmechanismdesign.
InProceedingsofthe1stACMconferenceonElectroniccommerce,pages129–139.
ACM,1999.
PKV+14.
VasilisPappas,FernandoKrell,BinhVo,VladimirKolesnikov,TalMalkin,SeungGeolChoi,WesleyGeorge,AngelosD.
Keromytis,andSteveBellovin.
Blindseer:AscalableprivateDBMS.
In2014IEEESymposiumonSecurityandPrivacy,pages359–374.
IEEEComputerSocietyPress,May2014.
PSSW09.
BennyPinkas,ThomasSchneider,NigelP.
Smart,andStephenC.
Williams.
Securetwo-partycomputationispractical.
InMitsuruMatsui,editor,ASIACRYPT2009,volume5912ofLNCS,pages250–267.
Springer,Heidelberg,December2009.
Rab77.
MichaelO.
Rabin.
Digitalizedsignatures.
Foundationsofsecurecompu-tation.
InRichardADetal.
(eds):Paperspresentedata3dayworkshopheldatGeorgiaInstituteofTechnology,Atlanta,pages155–166.
Academic,NewYork,1977.
RS08a.
PhillipRogawayandJohnP.
Steinberger.
Constructingcryptographichashfunctionsfromxed-keyblockciphers.
InWagner[Wag08],pages433–450.
RS08b.
PhillipRogawayandJohnP.
Steinberger.
Security/eciencytradeosforpermutation-basedhashing.
InSmart[Sma08],pages220–236.
Sma08.
NigelP.
Smart,editor.
EUROCRYPT2008,volume4965ofLNCS.
Springer,Heidelberg,April2008.
TJ11.
HenkC.
A.
TilborgandSushilJajodia.
EncyclopediaofCryptographyandSecurity.
SpringerPublishingCompany,Incorporated,2ndedition,2011.
Val76.
LeslieG.
Valiant.
Universalcircuits(preliminaryreport).
InSTOC,pages196–203,NewYork,NY,USA,1976.
ACMPress.
Wag08.
DavidWagner,editor.
CRYPTO2008,volume5157ofLNCS.
Springer,Heidelberg,August2008.
Wan18.
XiaoWang.
Personalcommunication,2018.
Wik.
Wikipedia.
Electronicsignaturesandlaw.
https://en.
wikipedia.
org/wiki/Electronicsignaturesandlaw.
RetrievedSept21,2016.
Win84.
RobertSWinternitz.
Asecureone-wayhashfunctionbuiltfromdes.
InSecurityandPrivacy,1984IEEESymposiumon,pages88–88.
IEEE,1984.
Yao86.
AndrewChi-ChihYao.
Howtogenerateandexchangesecrets(extendedabstract).
In27thFOCS,pages162–167.
IEEEComputerSocietyPress,October1986.
ZRE15.
SameeZahur,MikeRosulek,andDavidEvans.
Twohalvesmakeawhole-reducingdatatransferingarbledcircuitsusinghalfgates.
InElisabethOswaldandMarcFischlin,editors,EUROCRYPT2015,PartII,volume9057ofLNCS,pages220–250.
Springer,Heidelberg,April2015.
29APerformanceCalculationfortheProtocolof[HKE13]Theideaintheprotocolof[HKE13]istohavebothpartiesplaytheroleofthecircuitconstructorandcircuitevaluatorrespectivelyintwosimultaneousexecutionsofacut-and-chooseoftheprotocol.
Theprotocolisthussymmetric,andsymmetricprotocolsmightbedesirableincertainsituationssincetheyhavelessidletime.
Thenumberofgarbledcircuitsrequiredinthecut-and-choosetoachievestatisticalsecurity2κisκ+O(logκ).
Inthecut-and-chooseof[HKE13],apartysuccessfullycheatsifitgeneratesexactlyncincorrectcircuitsandnoneofthemischeckedbytheotherparty.
Theprobabilitythatacheatinggarblersucceeds,Pr[Awins]=1ncwherenisthenumberofgarbledcircuitsandcisthenumberofcheckcircuits.
Itiseasytoseethattheaboveprobabilityisminimizedbysettingc=n/2.
ThisgivesPr[Awins]=2n+logn.
Wenowapplythehashoptimizationinthecut-and-choosephaseoftheprotocol.
Andnow,wewantcomputetheoptimalvalueofcinthecasewherethecommunicationcostofacircuitisacheckcircuitischeaperthanthecostofagarbledcircuitthatisevaluated.
Lethbethecostofthehashofagarbledcircuit.
Thecostofacheckcircuitisjustthehashandthecostofanevaluationcircuitisthecostofthehashplusthecostofagarbledcircuit.
Letq=hCbetheratioofthecostofacheckcircuitandthecostforanevaluationcircuit,whereC=h+|GC|.
Wehave,thetotalcommunicationcomplexity,k=ch+eCwhereeisthenumberofevaluationcircuits,cthenumberofcheckcircuits,n=c+ethetotalnumberofcircuits.
Now,foraxedk,givenqwendthecandnthatminimizesPr[Awins]=P=1ncUsingStirling'sapproximation,weget,P≈(nc)nc+12cc+12nn+12Letr=cnbetheoptimalfraction.
Usingk=ch+eCandq=hC,dierentiatingPwithrespecttoc,andsettingtherstderivativeto0,weget,r=(1r)q(9)Whenq=1,thisgivesr=cn=12whichisindeedtheoptimalvaluewhennohashesareusedandacheckcircuitcoststhesameasanevaluationcircuit.
Nowwecomparethestandardcut-and-choosewiththecut-and-chooseusinghashandusingoptimalparametersascomputedabove.
Forsecurity2κ,κ+O(logκ)circuitsneedtobesentinthestandardcut-and-choose,whichgivesa30communicationk=|GC|(κ+O(logκ)),(foreachparty)where|GC|isthecostofagarbledcircuit.
NowgiventhecostofahashedGCtobeh,wegetcostofacheckcircuit=h,C=|GC|+h,q=hC.
Wenowsolve(9)forrandsetn=krh+(1r)Candc=rnThisachievesabettercheatingprobabilityforthesamecommunicationk.
Inthetablebelow,wecomparethecheatingprobabilityforvaluesofkandq.
Recall,intheprotocol,bothpartiesactassenderandsendκ+O(logκ)numberofcircuitseach.
TherstcolumninTable5denotingthecommunicationisthetotalcommunicationofthecut-and-choose.
CommunicationOptimalnumberOptimalnumberCheatingkofcircuitsofcheckcircuitsprobability[HKE13]k≈90|GC|n=45c=n/2240[HKE13]+[GMS08]hash,q=1/4k≈90|GC|n=71c=0.
7n≈49260[HKE13]+[GMS08]hash,q=1/8k≈90|GC|n=98c=0.
8n=78268Table531