Efficient Set Operations in the Presence of Malicious Adversaries CarmitHazay∗ KobbiNissim† May4,2010 Abstract Werevisittheproblemofconstructingefficientsecuretwo-partyprotocolsfortheproblemsofset- intersection and set-union, focusing on the model of malicious parties. Our main results are constant- roundprotocolsthatexhibitlinearcommunicationanda(practically)linearnumberofexponentiations withsimulationbasedsecurity. Intheheartoftheseconstructionsisatechniquebasedonacombination of a perfectly hiding commitment and an oblivious pseudorandom function evaluation protocol. Our protocols readily transform into protocols that are UC-secure, and we discuss how to perform these transformations. Keywords: Securetwo-partycomputation,Simulation-basedsecurity,Set-intersection,Set-union,Obliv- iouspseudorandomfunctionevaluation. 1 Introduction Secure function evaluation (SFE) allows two distrusting parties to jointly compute a function of their re- spectiveinputsasifthecomputationisexecutedinanidealsettingwherethepartiessendinputstoatrusted party that performs the computation and returns its result. Starting with the work of [47, 27, 11, 4], it is by now well known that (in various settings, and considering semi-honest and malicious adversaries) any polynomial-time computation can be generically compiled into a secure function evaluation protocol with polynomial complexity. However, more often than not, the resulting protocols are inefficient for practical usesandhenceattentionwasgiventoconstructingefficientprotocolsforspecificfunctions. Thisapproach hasprovedquitesuccessfulforthesemi-honestsetting(see,e.g.,[36,20,38,1,24,34,5,40,33,37]),while themalicioussettingremained,atlarge,elusive(anotableexceptionis[1]). We focus on the secure computation of basic set operations (intersection and union) where the parties P ,P ,holdinginputsetsX,Y,respectively,wishtocomputeX∩Y orX∪Y. Theseproblemshavebeen 1 2 widely looked at by researchers in the last few years [24, 34, 28, 6, 30, 8, 18], mainly due their potential applicationsfordatingservices,datamining,recommendationsystems,lawenforcement,etc. Ourmaingoal inthisworkistocomeupwithprotocolsforset-intersectionandset-unionthataresecureinthemalicious settingandareofbettercomplexitytothoseknown(includingtheabovegeneralresults). We begin by briefly surveying the current state of affairs with respect to two-party secure computation ofthesefunctionsforpapersthatrelatetoourwork. ∗Dept. of Computer Science and Applied Mathematics, Weizmann Institute and Interdisciplinary Center (IDC) Herzliya. carmit.hazay@weizmann.ac.il.ResearchwassupportedbyanEshkolscholarship. †Dept. of Computer Science, Ben-Gurion University and Microsoft ILDC. [email protected]. Research partly sup- portedbytheIsraelScienceFoundation(grantNo.860/06). 1 • Freedman, Nissim and Pinkas studied set intersection in [24]. They represent a set by a polynomial that zeros on the element of the set. Their construction for the semi-honest setting utilizes oblivious polynomial evaluation and a balanced allocation scheme and exhibits linear communication (count- ing field elements) and (almost) linear computation (counting modular exponentiations). We give a detailedaccountofthisprotocolinSection3. Freedman et al. also present variants of the above protocol, for the case where one of the parties is malicious and the other is semi-honest. In both cases, generic zero-knowledge proofs of adherence to the protocol are avoided to gain in efficiency. The protocol for malicious P (client in [24]) and 1 semi-honest P (server) utilizes a cut-and-choose strategy and hence communication is inflated by 2 a statistical security parameter. The protocol for malicious P and semi-honest P is in the random 2 1 oraclemodel. Aprotocolthatissecureinthefullymalicioussetup,thatcombinesbothtechniques,is sketchedinSection3.1. • Kissner and Song [34] used polynomials to represent multi-sets. Letting the roots of Q (·) and X Q (·)coincidewithelementsofthemulti-setsX andY,KissnerandSongobservedthatifr(·),s(·) Y are polynomials chosen at random then the roots of r(·)·Q (·)+s(·)·Q (·) coincide with high X Y probability with the multi-set X ∩ Y. This beautiful observation yields a set-intersection protocol for the semi-honest case, where the parties use an additively homomorphic encryption scheme (the Paillierschemeissuggestedin[34])toperformthepolynomialmultiplication,introducingquadratic computation costs in the set sizes. For the security of the protocol, it is crucial that no party should be able to decrypt on her own. Hence, the secret key should be shared and joint decryption should be deployed. Assuming a trusted setup for the encryption scheme, the communication costs for the two-partycaseareasintheprotocolforsemi-honestpartiesof[24]. For malicious parties [34] introduced generic zero-knowledge proofs for proving adherence to the prescribedprotocol(e.g.,zero-knowledgeproofsofknowledgeforthemultiplicationoftheencrypted Q (·) with a randomly selected r(·)). While this change seems to be of dire consequences to the x protocolefficiency,theanalysisin[34]ignoresitseffects. Furthermore,thecostsofsettingtheshared key for the Paillier scheme are ignored in the analysis. To the best of our knowledge, there are currently no efficient techniques for generating the shared Paillier keys, which do not incorporate an externaltrusteddealer(thelatterschemesinclude[21,22]referencedin[34]). Inadditiontothat,KissnerandSongpresentedaprotocolforthethresholdset-unionproblem,where only the elements that appear in the combined inputs more than t times are learnt by the parties. Theirprotocolemploysthesametechniqueofpolynomialmultiplicationandthusintroducesquadratic computationcostsasabove. • HazayandLindell[28]revisitedsecuresetintersection,withtheaimofachievingefficientprotocols inpresenceofamorerealisticadversarialbehaviorthaninthebenignsemi-honestmodel,andunder standard cryptographic assumptions. Two protocols were presented, one achieves security in the presenceofmaliciousadversarieswithone-sidedsimulatability,theotherissecureinthepresenceof covertadversaries[2]. Themaintoolusedintheseprotocolsisasecureimplementationofoblivious pseudorandomfunctionevaluation. HavingP ,P holdsetsofsizesm ,m respectively,bothprotocolsin[28]areconstantround,and 1 2 X Y incur the communication of O(m · p(n) + m ) group elements and the computation of O(m · X Y X p(n)+m )modularexponentiations,wheresetelementsaretakenfrom{0,1}p(n). Y We note that the protocols in [28] can be made secure in the malicious setup, e.g., by introducing a securekeyselectionstepfortheobliviousscprfandbyaddingzero-knowledgeproofsofknowledge 2 toshowcorrectnessateachstep. Namely, forprovingthatthesame PRF keyisindeedusedbyparty P ineachiterationandtoenableextractionofitsinput(asapseudorandomfunctionisnotnecessarily 1 invertible). Whilethiswouldpreservethecomplexityoftheseprotocolsasymptotically(inm ,m ), X Y the introduction of such proofs would probably make them inefficient for practical use since there is noeffieicntknownwaytoconstructthem. • Recently, Jarecki, and Liu [30] generalized the technique of [28] and presented a very efficient pro- tocol for computing a pseudorandom function with a committed key (informally, this means that the same key is used in all invocations), and showed that it yields an efficient set-intersection protocol. The main restriction of this construction is that the input domain size of the pseudorandom function shouldbepolynomialinthesecurityparameter(curiously,theproofofsecurityfortheset-intersection protocolmakesuseoftheabilitytoexhaustivelysearchovertheinputdomain). Removingtherestric- tion on the input domain of the pseudorandom function becomes possible using the fact that the functionisapermutation. Thisgivesanefficientprotocolinthecommonreferencestringmodel[31]; seebelowformoredetails. • Finally,Dachman-Soledetal.[18]presentaprotocolforset-intersectioninthepresenceofmalicious adversarieswithoutrestrictingthedomain. Theirconstructionusespolynomialevaluationbuttakesa differentapproachthanoursbyincorporatingasecretsharingoftheinputstothepolynomials. They avoidgenericzero-knowledgebyutilizingthefactthatShamir’ssecretsharingimpliesReedSolomon code. TheirprotocolincurscommunicationofO(mk2log2n+kn)groupelementsandcomputation ofO(mnklogn+mk2log2n). 1.1 OurContributions Our main contributions are efficient set-intersection and set-union protocols that are secure in the setup of malicious parties. Our constructions are in the standard model, and are based on standard cryptographic assumptions (in particular, no random oracle or a trusted setup). We begin by briefly describing the con- structionofFreedmanetal.[24]forsemi-honestpartiesthatservesasourstartingpoint. Secure Set Intersection with Semi-Honest Parties. The main tool used in the construction of [24] is obliviouspolynomialevaluation. Thebasicprotocolworksasfollows: 1. Party P chooses encryption/decryption keys (pk,sk) ← G(1n) for a homomorphic encryption 1 scheme(G,E,D)andsendspk toP . 2 2. P computesthecoefficientsofapolynomialQ(·)ofdegreem ,withrootssettothem elements 1 X X ofX,andsendstheencryptedcoefficientstoP . 2 3. For each element y ∈ Y (in random order), party P chooses a random value r (taken from an 2 appropriate set depending on the encryption scheme), and uses the homomorphic properties of the encryptionschemetocomputeanencryptionofr·Q(y)+y. P sendstheencryptedvaluestoP . 2 1 4. Uponreceivingtheseencryptedvalues,P extractsX∩Y bydecryptingeachvalueandthenchecking 1 iftheresultisinX. Notethatify ∈ X ∩Y thenbytheconstructionofthepolynomialQ(·)weget thatr·Q(y)+y = r·0+y = y. Otherwise,r·Q(y)+yisarandomvaluethatrevealsnoinformation abouty and(withhighprobability)isnotinX. Note that the communication complexity of this simple scheme is linear in m + m , as m + 1 X Y X encrypted values are sent from P to P (these are the encrypted coefficients of Q(·)), and m encrypted 1 2 Y 3 valuesaresentfromP toP (i.e.,Q(y)foreveryy ∈ Y). However,theworkperformedbyP ishigh,as 2 1 2 eachofthem obliviouspolynomialevaluationsincludesperformingO(m )exponentiations, totalingin Y X O(m ·m )exponentiations. X Y Tosaveoncomputationalwork,Freedmanetal.introducedabalancedallocationschemeintotheproto- col. Looselyspeaking,theyusedthebalancedallocationschemeof[3]mentionedabovewithB = mX loglogmX bins,eachofsizeM = O(m /B +loglogB) = O(loglogm ). PartyP nowusesthebalancedalloca- X X 1 tion scheme to hash every x ∈ X into one of the B bins resulting (with high probability) with each bin’s load being at most M. Instead of a single polynomial of degree m party P now constructs a degree-M X 1 polynomial for each of the B bins, i.e., polynomials Q (·),...,Q (·) such that the roots of Q (·) are the 1 B i elementsputinbini. AssomeofthebinscontainlessthanM elements,P padseachpolynomialwithzero 1 coefficientsuptodegreeM. Uponreceivingtheencryptedpolynomials,partyP obliviouslyevaluatesthe 2 encryptionofr ·Q (y)+y andr ·Q (y)+y foreachofthetwobinsh (y),h (y)inwhichy can 0 h0(y) 1 h1(y) 0 1 beallocated,enablingP toextractX ∩Y asabove. 1 Neglecting small constant factors, the communication complexity is not affected as P now sends 1 BM = O(m ) encrypted values and P replies with 2m encrypted values. There is, however, a dra- X 2 Y maticreductionintheworkperformedbyP aseachoftheobliviouspolynomialevaluationsamountsnow 2 to performing just O(M) exponentiations, and hence P performs O(m · M) = O(m · loglogm ) 2 Y Y X exponentiationsoverall. Naturally, our main goal is to come up with protocols that exhibit low asymptotic communication and computationcostsinthepresenceofmaliciousbehavior. Notingthatasymptoticcomplexitydoesnotreveal everything about a protocol’s efficiency or practicality, we avoid using generic zero-knowledge proofs of adherencetotheprescribedprotocols,evenwhentheyinvolverelativelyshortstatements,andcostlysetup commutationsthatmaketheefficientonlyforverylargeinputs. Ourcontributionsarerealizedasfollows, Preventing the Players from Deviating from the Protocol: We inherit the oblivious polynomial eval- uation and balanced allocation techniques used in [24]. On top of these we introduce an efficient zero- knowledge proof that P uses to show that her encrypted polynomials were correctly produced (unlike 1 in [24], our proof does not use a cut-and-choose strategy), and a technique preventing player P from de- 2 viating meaningfully from the protocol. This technique combines a perfectly hiding commitment scheme withanobliviouspseudorandomfunctionevaluationprotocol. EliminatingtheRandomOracle: Insomesense,ourconstructionreplacestherandomoracleusedin[24] in the case of a malicious sender, but this ‘replacement’ is only in a very weak sense: In our construction P holds the key for the pseudorandom function, and hence the function does not look random to P . 2 2 Furthermore, P does not need to invoke the oblivious pseudorandom evaluation protocol to compute it. 2 The consequence is that, unlike with the simulator for the protocol in the random oracle model that can easily monitor all invocations of the oracle, our simulator cannot extract P ’s input to the pseudorandom 2 function. We note that the protocols of [28] also use an oblivious pseudorandom function evaluation primitive, wheretheplayeranalogoustoP knowsthekeyforthefunction. Theirusageofthisprimitiveis,however, 2 very unlike in our protocols. In the protocols of [28] the pseudorandom function is evaluated on the set of elements that P2 holds, using the same PRF key for all evaluations. Whereas in our protocols it is evalu- atedonarandompayloadusing(possibly)differentkeys. Apayloads isarandomelementthatischosen y independently for each element y ∈ Y with the aim to fix the randomness used by P . Meaning that the 2 randomnessfortheobliviouspolynomialevaluationofyisdeterminedbythePRFevaluationofsy. Further- more,theprotocolsin[28]aredesignedforthecovertadversarymodelandfortheone-sidedsimulatability 4 model,andhenceatechniqueenablingfullsimulationofP isnotneeded,whereasourconstructionsallow 2 simulationofbothparties. Choosing the Underlying Encryption Scheme: Our protocols make extensive use of a homomorphic encryption scheme, and would remain secure (with only small modifications) under a variety of choices. We chose to work with the El Gamal scheme (that is multiplicatively homomorphic) although it may seem thatthemorenaturalchoiceisthePaillierscheme[42], thatisadditivelyhomomorphic(indeed, ourinitial constructionswerebasedonthePaillierscheme). Using the Paillier scheme, a subtle problem emerges (this was overlooked, e.g., in [24]). Recall that for the Paillier scheme pk = N,sk = ϕ(N). Now, if P knows sk when she constructs her polynomials, 1 then she may construct a polynomial Q(·) such that Q(y) ̸∈ Z∗ for some specific ‘target’ value y. This N would allow her to learn about P ’s input beyond the intended protocol output. A possible solution is that 2 P ,P wouldfirstengageinaprotocoltojointlygeneratepk andsharesofsk,whereasP wouldlearnsk 1 2 1 onlyaftercommittingtoherpolynomials. This,however,introduceshighkeysetupcosts,andtheresultisa protocolthatexhibitslowasymptoticcosts,but,becauseofitshighsetupcosts,itsefficiencyisgainedonly forverylargeinputs. Efficiency: Ourprotocolsforsetintersectionandsetunionπ∩,π∪areconstantround,workinthestandard modelanddonotrequireatrustedsetup. TheunderlyingencryptionschemeisElGamalwherethekeysare selectedbypartyP . Bothprotocolsdonotemployanygenericzero-knowledgeproof. 1 Assuming the protocols of [23, 28] (that require p(n) oblivious transfers for realizing the oblivious pseudorandom function evaluation), we get that for sets X,Y ⊂ {0,1}p(n) of m ,m elements respec- X Y tively, the costs of π∩,π∪ are of sending O(mX + mY · p(n)) group elements, and the computation of O(m +m ·(loglogm +p(n))) modular exponentiations. Note that this is significantly better than X Y X O(m ·m ). X Y Asignificantimprovementcanbeachievedbyusingamoreefficientpseudorandomfunctionevaluation instead of using the function of [39] which requires a single oblivious transfer for every input bit. A can- didateforthistaskistheBoneh-Boyenpseudorandompermutationusedby[30],whichrequiresaconstant number of exponentiations for each evaluation.1 We note that the construction in [30] for oblivious evalu- ation requires a common reference string for denoting a safe RSA modulus. To the best of our knowledge theredoesnot exista secureprotocol fordistributivelygeneratingsuch amodulus inthe two-partysetting, tolerating malicious behavior. Therefore, the protocol of [30] for set-intersection (and ours, when instanti- atedwiththeBoneh-Boyenfunction)alsorequiresapreprocessingstageforgeneratingacommonreference string of this type. Nevertheless, the asymptotic costs are linear in the sets sizes. Finally, we would like to emphasizethatourprotocolemploysthePRFdifferentlythentheprotocolin[30]. Thatis,whileweemploy the PRF onrandomstrings,[30]generalizesthetechniquepresentedin[28]forwhichtheinputsaretheset values. Inadditiontotheabove,anothersignificantimprovementcanbeachievedforourset-intersectionproto- colifthesizeoftheintersectionmX∩Y isallowedtobeleaked(toP2). Theresultingprotocolisofsending O(mX +mX∩Y ·p(n))andcomputingO(mX +mY ·loglogmX +mX∩Y ·p(n)). WhenmX∩Y ≪ mY wegetaprotocolthatismoreefficientthanthatof[28]. Thistypeofimprovementdoesnotapplyfor[28] aswellsincethepartiesapplythePRFdirectlyontheinputsetY andthuscannotdeducemX∩Y beforethat. UC Security: Our protocols readily transform into the UC framework as all our simulators are straight- line in an hybrid model with access to some specific zero-knowledge proofs. We show how to modify our 1Wenotethat[30]introducesastrongerprimitivethatguaranteestheevaluationsofmultiplestringsusingthesamekey. 5 setintersectionprotocoltoonethatissecureintheUCframework(inthecommonreferencestringmodel). 2 Preliminaries Throughout the paper, we denote the security parameter by n, and, although not explicitly specified, input lengthsarealwaysassumedtobeboundedbysomepolynomialinn. Aprobabilisticmachineissaidtorun inpolynomial-time(PPT)ifitrunsintimethatispolynomialinthesecurityparameternalone. Afunction µ(n) is negligible (in n) if for every polynomial p(·) there exists a value N such that µ(n) < 1 for all p(n) n > N;i.e.,µ(n) = n−ω(1). Let X = {X(n,a)} and Y = {Y(n,a)} be distribution ensembles (over n∈N,a∈{0,1}∗ n∈N,a∈{0,1}∗ strings of length polynomial in n). We say that X and Y are computationally indistinguishable, denoted X ≡c Y,ifforeverypolynomialnon-uniformdistinguisherD thereexistsanegligibleµ(·)suchthat (cid:12) (cid:12) (cid:12) (cid:12) (cid:12)Pr[D(X(n,a)) = 1]−Pr[D(Y(n,a)) = 1](cid:12) < µ(n) foreveryn ∈ N anda ∈ {0,1}∗. 2.1 SecureTwo-PartyComputation–Definitions Webrieflypresentthestandarddefinitionforsecuremultipartycomputationandreferto[25,Chapter7]for moredetailsandmotivatingdiscussion. Two-partycomputation. Atwo-partyprotocolproblemiscastbyspecifyingarandomprocessthatmaps pairs of inputs to pairs of outputs (one for each party). We refer to such a process as a functionality and denote it f = (f ,f ) : {0,1}∗ × {0,1}∗ → {0,1}∗ × {0,1}∗. That is, for every pair of inputs (x,y), 1 2 the output-vector is a random variable (f (x,y),f (x,y)) ranging over pairs of strings where the outputs 1 2 of P ,P are f (x,y),f (x,y) respectively. We use the notation (x,y) 7→ (f (x,y),f (x,y)) to describe 1 2 1 2 1 2 afunctionality. Forexample,theObliviousTransferfunctionalityiswritten((x ,x ),σ) 7→ (λ,x ),where 0 1 σ (x ,x )isthefirstparty’sinput,σisthesecondparty’sinput,andλdenotestheemptystring(meaningthat 0 1 thefirstpartyhasnooutput). Aspecialcaseforatwo-partyfunctionalityisthatofzero-knowledgeproofof knowledgeforarelationR . Thisfunctionalityisdefinedas: ZK { (1,λ) ifR (x,w) = 1 (x,(x,w)) 7→ ZK (⊥,λ) otherwise Securityofprotocols. Weprovethesecurityofourprotocolsinthesettingofmaliciousadversaries,that may arbitrarily deviate from the specified protocol. Security is analyzed by comparing what an adversary can do in a real protocol execution to what it can do in an ideal scenario. In the ideal scenario, the com- putation involves an incorruptible trusted third party to whom the parties send their inputs. The trusted partycomputesthefunctionalityontheinputsandreturnstoeachpartyitsrespectiveoutput. Informally,the protocol is secure if any adversary interacting in the real protocol (i.e., where no trusted third party exists) can do no more harm than what it could do in the ideal scenario. We consider the static setting where the adversary is only able to corrupt a party at the outset of the protocol. There are technical issues that arise, such as that it may be impossible to achieve fairness or guaranteed output delivery. E.g., it is possible for theanadversarialpartytopreventanhonestpartyfromreceivingoutputs. Execution in the ideal model. In an ideal execution, the parties send inputs to a trusted party, that com- putestheoutput. Anhonestpartyreceivesitsinputforthecomputationandjustdirectsittothetrustedparty, 6 whereas a corrupted party can replace its input with any other value of the same length. Since we do not consider fairness, the trusted party first sends the output of the corrupted parties to the adversary, and the adversarythendecideswhetherthehonestpartiesreceivetheir(correct)outputsoranabortsymbol⊥. Let f be a two-party functionality where f = (f ,f ), let A be a non-uniform probabilistic polynomial-time 1 2 machine,andletI ⊆ [2]bethesetofcorruptedparties(eitherP iscorruptedorP iscorruptedorneither). 1 2 Then, the ideal execution of f on inputs (x,y), auxiliary input z to A and security parameter n, denoted IDEALf,A(z),I(x,y,n),isdefinedastheoutputpairofthehonestpartyandtheadversaryAfromtheabove idealexecution. Execution in the real model. In the real model there is no trusted third party and the parties directly interact with each other. The adversary A controls the corrupted parties and hence sends all messages in their place. The adversary is not bound to sending messages according to the protocol, and may follow an arbitrarypolynomial-timestrategy. Anhonestpartyfollowstheinstructionsprescribedintheprotocolπ. Letf beasaboveandletπbeatwo-partyprotocolforcomputingf. LetAbeanon-uniformprobabilis- ticpolynomial-timemachineandletI ⊆ [2]bethesetofcorruptedparties. Then,therealexecutionofπon inputs(x,y),auxiliaryinputz toA,andsecurityparametern,denoted REALπ,A(z),I(x,y,n),isdefinedas theoutputvectorofthehonestpartiesandtheadversaryAfromtherealexecutionofπ. Securityasemulationofarealexecutionintheidealmodel. Havingdefinedtheidealandrealexecution models, we can now define security of protocols. Loosely speaking, the definition asserts that a secure protocol emulates (in the real execution model) the ideal execution model in which a trusted party exists. Thisnotionisformulatedbyrequiringtheexistenceofadversariesintheidealexecutionmodelthatareable tosimulateadversarialbehaviorintherealexecutionmodel. Definition2.1 Letf andπbeasabove. Protocolπissaidtosecurelycomputef withabortinthepresence of malicious adversaries if for every non-uniform probabilistic polynomial-time adversary A for the real model,thereexistsanon-uniformprobabilisticpolynomial-timeadversaryS fortheidealmodel,suchthat foreveryI ⊆ [2], { } { } IDEALf,S(z),I(x,y,n) x,y,z∈{0,1}∗,n∈IN ≡c REALπ,A(z),I(x,y,n) x,y,z∈{0,1}∗,n∈IN where|x| = |y|. The f-hybrid model. In our constructions we will use secure two-party protocols as sub-protocols. A standard way of abstracting out the details of a sub-protocol computing a functionality f is to work in a hybridmodelwherethetwopartiesdirectlyinteractwitheachother(asintherealmodel)aswellasaccessa trustedimplementationoff (asintheidealmodel). Inanexecutionofaprotocolπ thatusesasub-protocol forsecurely computing f, the partiesrun π andissue idealcalls toa trustedparty for computing f instead of invoking the sub-protocol for f. These ideal calls are just instructions to send an input to the trusted party,which,uponreceivingtheinputsfromtheparties,computesf andsendseachpartyitscorresponding output. After receiving these outputs back from the trusted party, the protocol π continues. We stress that thisisasequentialcomposition,i.e.,thepartiesdonotsendmessagesinπ betweenthetimethattheysend inputtothetrustedpartyandthetimethattheyreceivebackoutput. Thetrustedpartymaybeusedanumber oftimesthroughouttheexecutionofπ. However,eachinvocationofthefunctionalityf isindependent(i.e., thetrustedpartydoesnotmaintainanystatebetweenthesecalls). Wecalltheregularmessagesofπthatare sent amongst the parties standard messages and the messages that are sent between parties and the trusted partyidealmessages. 7 Letf beafunctionalityandletπbeatwo-partyprotocolthatusesidealcallstoatrustedpartycomputing f. Furthermore, let A be a non-uniform probabilistic polynomial-time machine and let I be the set of corrupted parties. Then, the f-hybrid execution of π on inputs (x,y), auxiliary input z to A and security parameter n, denoted HYBRIDfπ,A(z),I(x,y,n), is defined as the output vector of the honest parties and the adversaryAfromthehybridexecutionofπ withatrustedpartycomputingf. Letf andπbeasabove,andletρbeaprotocol. Considertherealprotocolπρ thatisdefinedasfollows. Allstandardmessagesofπ areunchanged. WhenapartyP isinstructedtosendanidealmessageα tothe i i trustedparty,itbeginsarealexecutionofρwithinputα instead. Whenthisexecutionofρconcludeswith i output β , party P continues with π as if β was the output received by the trusted party (i.e. as if it were i i i runninginthef-hybridmodel). Then,thecompositiontheoremof[7]statesthatifρsecurelycomputesf, thentheoutputdistributionofaprotocolπinahybridexecutionwithf iscomputationallyindistinguishable fromtheoutputdistributionoftherealprotocolπρ. Thus,itsufficestoanalyzethesecurityofπwhenusing idealcallstof;securityoftherealprotocolπρ isderivedviathiscompositiontheorem. 2.2 TheElGamalEncryptionScheme TheElGamalencryptionschemeoperatesonacyclicgroupGofprimeorderq. Wewillworkinthegroup Z∗q′ whereq′ = 2q+1isprime, andsetGtobethesubgroupofZq′ ofquadraticresiduesmoduloq′ (note that membership in G can be easily checked). Let g denote a random generator in G, then the public and secretkeysare⟨G,q,g,h⟩and⟨G,q,g,x⟩wherex ← Z andh = gx. Amessagem ∈ Gisencryptedby R q choosingy ← Z andtheciphertextis⟨gy,hy ·m⟩. Aciphertextc = ⟨α,β⟩isdecryptedas m = β/αx. R q Weusethepropertythatgiveny = log αonecanreconstructm = β/hy andhenceapartyencryptingm g canproveknowledgeofmbyprovingknowledgeofy. ThesemanticsecurityoftheElGamalschemefollowsfromthehardnessofdecisionalDiffie-Hellman (DDH) in G. The El Gamal scheme is homomorphic relative to multiplication. I.e., if ⟨α1,β1⟩ encrypts m and ⟨α ,β ⟩ encrypts m then ⟨α ·α ,β ·β ⟩ encrypts m m . We additionally consider a modified 1 2 2 2 1 2 1 2 1 2 versionofElGamalwheretheencryptionisperformedbychoosingy ← Z andcomputing⟨gy,hy·gm⟩. R q Decryptionof aciphertextc = ⟨a,b⟩isperformedbycomputing gm = b·a−x. Thefactthat m cannotbe efficientlyrecoveredisnotproblematicforthewayElGamalisincorporatedinourprotocols. Moreover,this variant of El Gamal is additively homomorphic and can be used to perform oblivious linear computations (e.g.,polynomialevaluation)intheexponent. 2.3 PerfectlyHidingCommitment Weuseaperfectly-hidingcommitmentscheme(com,dec)withazero-knowledgeproofofknowledgeπ COM fortherelation {( ) } R = c,(r,m) |c = com(m;r) , COM where com(m;r) denotes the commitment to a message m using random coins r. We instantiate com(·;·) with Pedersen’s commitment scheme [43], using the same underlying group G used for the El Gamal scheme. I.e.,letq′ = 2q+1whereq′,qareprimesandletg,hbegeneratorsofthesubgroupGofquadratic residues modulo q′. A commitment to m is then defined as com(m;r) = gmhr where r ←R Zq−1. The scheme is perfectly hiding as for every m,r,m′ there exists a single r′ such that gmhr = gm′hr′. The scheme is binding assuming hardness of computing log h. However, given log h, it is possible to de- g g commit any commitment c into any message m ∈ Z . We instantiate π with the proof of knowledge q COM from[41](thisproofisnotazero-knowledgeproof,yetcanbemodifiedusingstandardtechniques[26]). 8 2.4 Zero-knowledgeProofs Ourprotocolsemployzero-knowledgeproofsofknowledgeforthefollowingrelations(inthefollowing,G isagroupofprimeorder): ProofType Protocol Relation/Language Reference ZKPK π R = {((G,g,h),x) | h = gx} [45] DL DL ZKPK π R = {((G,g,g ,g ,g ),x) | g = gx∧g = gx}} [13] DDH DDH 1 2 3 1 3 2 ZK π L = {(G,g,h,⟨α,β⟩) | ∃(m ̸= 0,r)s.t.α = gr ∧ β = hrgm} Section2.4.1 NZ NZ 2.4.1 Zero-KnowledgeProofforL NZ Weusestandardtechniquesforconstructingazero-knowledgeproofforthelanguageofencryptions⟨α,β⟩ ofnon-zeroexponentsofg: L = {(G,g,h,⟨α,β⟩) | ∃(m ̸= 0,r)s.t.α = gr ∧ β = hrgm}. NZ Theconstructionisbasedonazero-knowledgeprotocolπ forthelanguage MULT { } L = (G,g,h,c ,c ,c ) | ∃m,m′ ∈ Z s.t.c ,c ,c areencryptionsofgm,gm′,gmm′ resp. . MULT 1 2 3 q 1 2 3 π is a modification of a protocol by Damga˚rd and M. Jurik [15] designed for the Paillier encryption MULT scheme: Protocol1 (zero-knowledgeproofforL ): MULT • Joint statement: A public key h for El Gamal encryption, and encryptions ⟨α,β⟩,⟨α′,β′⟩,⟨α′′,β′′⟩ (where h,α,β,α′,β′,α′′,β′′ ∈G). • Auxiliary input for the prover: Three message-randomness pairs (m,r),(m′,r′),(m′′,r′′) such that ⟨α, β⟩,⟨α′,β′⟩, ⟨α′′, β′′⟩ are encryptions of of gm,gm′,gm′′ with randomness r,r′,r′′ respectively, and m′′ = mm′. • Auxiliaryinputsforbothparties: Aprimepsuchthatp−1=2qforaprimeq,thedescriptionofagroupG oforderqforwhichtheDDHassumptionholds,andageneratorgofG. • Theprotocol: 1. V choosesatrandomc ∈ Z andsendsacommitmentz = com(c;y) = gchy toP. Thepartiesengage q in the protocol π where V proves knowledge of the committed value c and the randomness y. If V COM failstoproveknowledgeofc,thenP aborts. 2. P choosesatrandoma ∈ Z setsb = am′ andsendstoV encryptions⟨α ,β ⟩and⟨α ,β ⟩ofga and q a a b b gb respectively(i.e.,ga isencryptedas⟨αa,βa⟩ = ⟨gra,hraga⟩wherera ischosenatrandomfromZq, andsimilarlyforgb). 3. V opensthecommitmentbysendingy,ctoP. P verifiesthatthecommitmentwasopenedcorrectlyand abortsifthisisnotthecase. 4. Bothpartiesusethehomomorphicpropertiesoftheschemetocomputeanencryption⟨α ,β ⟩ofgdwhere d d d = cm+a. P sends dtoV, andprovesinzeroknowledgethat(g,h,α ,β /gd)isaDiffie-Hellman d d tuple,i.e.,⟨α ,β ⟩isanencryptionofgd. d d 5. Bothpartiesusethehomomorphicpropertiesoftheschemetocomputeanencryption⟨α ,β ⟩ofgewhere e e e=dm′−b−cm′′. Notethatifm′′ =mm′thene=dm′−b−cm′′ =(cm+a)m′−am′−cm′′ =0. P provesinzeroknowledgethat(g,h,α ,β /gd)isaDiffie-Hellmantuple,i.e.,⟨α ,β ⟩isanencryption e e e e ofg0 =1. 9 6. V acceptsifitacceptsinallzero-knowledgeproofs. Proposition2.1 Assume that com is a perfectly-hiding commitment scheme. Then, Protocol 1 is a zero- knowledgeproofforL withperfectcompletenessandnegligiblesoundnesserror. MULT Proof: Ourproofisinthehybridsettingwhereatrustedpartycomputesπ andπ . Itiseasytocheck DDH COM that all of V’s checks pass when interacting with a honest P that follows the protocol, and hence we have perfect completeness. To prove soundness, let a,b be the numbers encrypted in the first two encryptions sent by a. Since V computes the encryption of d, it must be that d = cm+a. The first zero-knowledge proof ensures that V indeed learns d. Similarly, since V computes the encryption of e, it must be that e = dm′−b−cm′′ = (cm+a)m′−b−cm′′ = c(mm′−m′′)+am′−b. Now,ifmm′ ̸= m′′ thene = 0 onlyifc = (b−am′)/(mm′ −m′′). AsV acceptsonlyife = 0,wegetthatitacceptswithprobabilityat most1/q. Zeroknowledge. ConstructasimulatorS forV∗ asfollows. TheinputtoS is(g,h,⟨α,β⟩,⟨α′,β′⟩,⟨α′′, β′′⟩),i.e.,theencryptionofm,m′,m′′,and,furthermore,mm′ = m′′. ThesimulatorreceivesV’scommit- mentz,andtheinputsc,ytothefunctionalityR . Ifthefunctionalityreturns0thenS aborts. Otherwise, COM S computesanencryption⟨α ,β ⟩tog0,choosesd ∈ Z atrandom,andcomputesanencryption⟨α ,β ⟩ e e q d d togd. Finally,S usesthehomomorphicoperationstocomputeencryption⟨α ,β ⟩ofga wherea = d−cm a a and an encryption ⟨α ,β ⟩ of gb where b = dm′ −cm′′. S completes the execution of the protocol using b b encryptions ⟨α ,β ⟩ and ⟨α ,β ⟩, and returning 1 to V in each of the invocation of the zero-knowledge a a b b proofs. V manages to open the commitment to a value that is different from that given as input to R with COM onlyanegligibleprobability. Ifthatisnotthecase, thentheviewsareidentical(toseethat,notethatthea andbaredistributedidenticallyinbothexecutions). Wecontinuewithazero-knowledgeproofπ forlanguageL . NZ NZ Protocol2 (zero-knowledgeproofforL ): NZ • Jointstatement: ApublickeyhforElGamalencryption,andanencryption⟨α,β⟩(h,α,β ∈G). • Auxiliary input for the prover: A pair (m,r) such that m ̸= 0 and ⟨α,β⟩ is an encryption of m with randomnessr,i.e.,α=gr andβ =hrgm. • Auxiliaryinputsforbothparties: Aprimepsuchthatp−1=2qforaprimeq,thedescriptionofagroupG oforderqforwhichtheDDHassumptionholds,andageneratorgofG. • Theprotocol: 1. The prover P chooses a random value m′ ∈ Z \{0} and sets m′′ = mm′. P computes encryptions q ⟨α′,β′⟩,⟨α′′,β′′⟩ofgm′,gm′′ respectively,i.e.,α′ =gr′,β′ =hr′gm′ andα′′ =gr′′,β′′ =hr′′gm′′. 2. P,V engage in π , where P proves that the ciphertexts ⟨α,β⟩,⟨α′,β′⟩,⟨α′′,β′′⟩ encrypt messages gm,gm′,gm′′ suchMUthLTatm′′ =mm′. 3. P sends m′′ and proves that ⟨α′′,β′′⟩ is an encryption of gm′′ by proving that (g,h,α′′,β′′/gm′′) is a Diffie-Hellmantupleusingπ . DDH 4. V acceptsifitacceptsinthezero-knowledgeproofandthereceivedm′′isnon-zero. Proposition2.2 Assuming hardness of the DDH problem Protocol 2 is a computational zero-knowledge proofforL withperfectcompletenessandnegligiblesoundness. NZ 10