Secure multi-party computation (MPC) enables n parties P1,…,Pn, with private inputs x1,…,xn, to compute y = f(x1,…,xn) in such a way that all parties learn y but no Pi learns anything about xj, for j≠i, except what is logically implied by y and xi.
Consider the following toy example. Suppose 20 pupils, whom we will call P1 through P20, are in the same class and have received their graded exams from their teacher. They want to compute the average of their grades without revealing their individual grades, which we will denote by g1 through g20. They can use the following simple MPC protocol. P1 chooses a random number r, computes x1 = g1 + r, and sends x1 to P2. Then P2 computes x2 = x1 + g2 and sends x2 to P3. They continue in this fashion until P20 computes x20 = x19 + g20 and sends x20 to P1. In the last step, P1 computes x20 – r, which is of course the sum g1 + g2 + … + g20 of the individual grades. He divides this sum by 20 to obtain the average and broadcasts the result to all of the pupils.
If all of the pupils follow this protocol faithfully, then they all learn the average, but none learns anything about the others’ grades except what is logically implied by the average and his own grade. Here, “following the protocol faithfully” requires not colluding with another pupil to discover someone else’s grade. If, say, P3 and P5 executed all of the steps of the protocol correctly but also got together on the side to pool their information, they could compute P4’s grade g4. That is because g4 = x4 – x3, and, during the execution of the protocol, P3 learns x3 and P5 learns x4. Fortunately, there are techniques (the details of which are beyond the scope of this article) for ensuring that this type of collusion does not reveal private inputs; they include secret-sharing schemes, described below.
One powerful class of MPC protocols proceeds in multiple rounds. In the first round, each Pi breaks xi into shares, using a secret-sharing scheme, and sends one share to each Pj. The information-theoretic properties of secret sharing guarantee that no other party (or even limited-sized coalition of other parties) can compute xi from the share(s). The parties then execute a multi-round protocol to compute shares of y, in which the shares of intermediate results computed in each round also do not reveal xi. In the last round, the parties broadcast their shares of y so that all of them can reconstruct the result.
In the secure-outsourcing protocol architecture, depicted below, the parties P1,…,Pn play the role of input providers and a disjoint, much smaller set of parties S1,…,Sk play the role of secure-computation servers; typically, 2 ≤ k ≤ 4. The input providers share their inputs with the servers, which then execute a basic, k-party MPC protocol to compute y. For an appropriate choice of secret-sharing scheme, the inputs remain private as long as at least one server does not collude with the others. Note that cloud-computing companies are ideally positioned to supply secure computation servers!
Image credit: Joan Feigenbaum
