Secure Multi-Party Computation in the HBC Model

6.876/18.426: Advanced Cryptography 5/5/03 Lecture 20: Secure Multi-Party Computation in the HBC Model 1 Overview In this lecture, we discuss the problem of constructing a secure multi-party protocol for computing a function whose input is divided among a number of parties. We want such a protocol to compute the function "correctly" and "privately", even when some of the parties are malicious and deviate arbitrarily from the protocol (in a probabilistic polynomial-time manner). A first question one may ask is: Do such protocols exist? It turns out that if trapdoor permutations exist and if less than half of the parties are malicious, then every function has a correct fault-tolerant protocol that offers the maximum degree of privacy. The complexity of the protocol is polynomial in the time-complexity of the function. Furthermore, there exists a polynomial-time algorithm that on input a Turing-Machine specification of the function outputs such a protocol. In this lecture, rather than diving into the formal definitions of the above requirements (correctness and privacy), we will focus on constructions. However, before doing so, let us illustrate the intuitive meaning of these requirements. Consider an environment in which in addition to the participating parties there is a trusted party. In the "trusted party environment", each party sends its input to the trusted party using a secure channel; then the trusted party computes the output and sends it to all the parties. Since the trusted party is non-faulty, the computed value of the function is the correct one (with respect to the inputs given to the trusted party). It is also clear that no collaboration of faulty parties can learn more than what can be computed from the final output and their local inputs. We would like a multi-party protocol that would have the same correctness and privacy properties as a computation in the "trusted party environment". 2 The Main Result We assume, without loss of generality, that all parties compute the same output function f. We can create such a function from the local output functions fi fn. by letting (1)1((1)) (()), where E, is a secure public- key encryption for which only P knows the decryption key. We also assume, without loss of generality, that the function f is binary (into (0,1)). Our general goal is to prove the following theorem. Theorem 1. Let f: ({0,1}) {0,1} be a polynomial-time computable function, and lett. If there exists a trapdoor permutation then there exists an efficient protocol for a parties P Pa, that privately computes f in the presence of t faulty parties. 22-1 Generally speaking, we will prove this theorem in two parts. First, we will present a protocol that privately computes / if all parties are "honest but curious". Then, we will present a method of "compiling" into another protocol, C(x), that privately computes f in the presence of t< faulty parties. In this lecture we will concentrate on the first part. Namely, we will assume that all parties are honest but curious (HBC). 2.1 The HBC Model In the HBC model, we assume that all parties are honest but curious. That is, we assume that cach party executes the original protocol but tries to compute as much additional information as possible. More specifically, we assume that each party uses for its random tape the output of random coin tosses, and that in each communication round it sends exactly the message as instructed in the protocol (the protocol defines a unique message to be sent, as a function of the initial input, the random tape, and the communication received so far). Moreover, we assume that the parties don't listen to any communication other than those sent to them. So, the parties may deviate from the protocol only in their internal computation, but the messages they send are in accordance with the protocol. In the remainder of this lecture we will prove the following theorem. Theorem 2. For any polynomial-time computable function f: (0,1))" (0.1] there ezists an efficient n-party protocol that privately computes f in the HBC model. Actually, we will show that there exists a compiler P such that for any function f. P(f) outputs a algorithms (H... H), which form a protocol that privately compute f. Proof. P. on input a Turing-Machine My. which computes some function : ({0,1})" (0,1), transforms My into a circuit Cf that computes f. Note that since ƒ is polynomial- time computable there exists a Boolean circuit of polynomial-size that computes f. We will assume, without loss of generality, that Cy consists only of and A gates (aVb = a^b), and that the maximum fan-in of a gate is two. We consider these operations as operations over the field F2. The operator is replaced with the function g(x)=x+1 and the A operator is replaced with the multiplication function g(x,y)=zy. P. given Cy, will output (H... H), which are defined as follows. 1. Each H, shares each of his input bits with all other parties, in a way that exactly n parties are needed in order to gain any information about the input bit. More specifically, H, will share a bit b by choosing at random a bits by.....b, satisfying b = b, and sending party j the bit by At this point, the parties hold random shares allowing them to obtain the values of each input wire of the Boolean circuit. Our purpose is that the parties will hold random shares allowing them to obtain the value of the output wire of the circuit. To this end, the parties will scan the circuit from the input gates to the output gate. For each gate, they will generate random shares of the value of its output wire from the random shares of the values of its input wires. This is done as follows. 2. For each gate, the value of its output wire is obtained by adding the constant 1 to the value of its input wire. We assume (by induction) that the value, &, of its input wire is randomly distributed among all parties, as follows: b = b, where party holds the share by. Thus, we will distribute the value of the output wire of as follows: one of the parties, say the first party, will calculate his share by adding the constant 1 to his share of the input wire: b +1. All other parties let their share of the output wire be equal to their share of the input wire. Thus, we obtain the output value (6+1)+by+...+b Σ+1=6+1, as desired. Also note that these shares remain random. 3. For each A gate, the value of its output wire is obtained by multiplying the values of its two input wires. Denote these values by e and d. Assume (by induction) that these two values are randomly shared among all parties as follows: c = and d = ide, where party i holds the shares e, and d. The parties need to compute a random shares (6,, such that (Σ) (d) = (i cich) + Σisiciso (adj + cjd), and such that each party P knows only by. Define by so that for every i, bed and for every ij, bij + bj = adj + cjd, and let b = bij Note that cd = (Σ) (Σ) = (Σ) + Σικι; +cd) = ΣΙΣ Σ Also note that for every i, bd, is uniformly distributed (as c, and di are uniformly distributed) and can be compute by party P. The question is how can two parties, P and P, privately compute by and by, so that the resulting shares will be uniformly distributed among all possible shares? This will be done using a (1) Oblivious Transfer, as follows. Note that b + bcd, cd, implies that badj + coch bj (since the computation is in 72). Thus, P will pick by at random and will transfer to P, using a (1) Oblivious Transfer, one of the following values: by bdj. bytej or bj+j+dj. P will choose to receive the first value (b) if cd0, to receive the second value (by +dy) if e=1 and d₁ = 0, to receive the third value (b+c) if 0 and 1, and to receive the forth value (by + c + d) if=d = 1. P will set by to be equal to the value received. Note that this sub-protocol satisfies that bj+by=Gdjed, and that by and by are both uniformly distributed. Thus, the resulting shares (by, are also uniformly distributed among all shares, as desired. Notice that the above construction relies heavily on the fact that every function con- sists of a sequence of local computations. Also note that the above protocol is information Recall that a construction of a (1) Oblivious Transfer was given in the previous lecture, 22-3 theoretically private, except for the (1) Oblivious Transfer protocol which is only computa tionally private. An interesting question one may ask is whether there exists a (1) Oblivious Transfer protocol which is information theoretically private? Or can we achieve an infor- mation theoretically private multi-party function evaluation in any other way (in the HBC model)?