Monday, September 28, 2015

BMR: Extended version of Yao's protocol for n players

Here we discuss how to extend Yao's protocol for any arbitrary 'n' players. In Yao's protocol, the responsibilities of the two players (Circuit constructor and Circuit Evaluator) are not at all alike. Hence, it is not trivial to see how to extend the protocol for any 'n' number of parties.

We start by assuming that the logical circuit C corresponding to the multi-party computation function f is already given, and we expect Semi-honest behaviour (at worst) from the parties, and the threshold for corrupted parties is (n-1).

In this extended protocol (BMR protocol), both construction and evaluation of the circuit is done collaboratively. Now we see how the protocol works.
BMR Protocol is having an Offline Phase and an Online Phase.

Offline Phase:

In the offline phase, we need to know nothing other than the circuit. Let there be 'W' wires in the circuit, indexed from 0 to W-1. At first, all players will (collaboratively) choose one random bit for each wire, namely λ­0, λ­1…, λ­­w-1. Each λ­i values are secret shared among all n parties. Then λj is reconstructed to party Pi, if ‘j’ is one of the input wires of Pi.

Now, each player will choose two random string (we call them 'two seeds') of length 'k', for each wire. Without loss of generality, we name those seeds s­­­­­­­­­iw,0 and s­­­­­­­­­iw,1 for each player i, for each wire w. Now we define SuperSeed for a wire w.

Sw,0 = s1w,0 || s2w,0 || .. siw,0 .. || snw,0
Sw,1 = s1w,1 || s2w,1 || .. siw,1 .. || snw,1

These two SuperSeeds will act as two different keys, and bears the meaning of the bits; just like two keys for each wire in Yao's protocol. But here, the SuperSeed S­w,j need not represent the bit 'j' ; instead Sw,0 represent the bit λ­w, and Sw,0 represent the bit λ­wc.

Please note that individual players know only their seeds on each wire, and λ values of all wires.
For the implementation of 4 (generally, but for NOT gate it’s 2) encryption boxes of a logic gate, We need two PRGs G1 and G2 both maps {0,1}k → {0,1}nk. Let a and b be the input wires of the gate g, and c be output wire of g. The cyphertexts corresponding to each Encryption Box is of the form:

Box 1: C1 := ( G1­(s1a,0) G1­(s2a,0) .. G1­(sna,0) ) ( G1­(s1b,0) G1­(s2b,0) .. G1­(snb,0) ) ⊕ Sc,r  ,
(Where r = 0 if g(λa, λb) = λc ; r = 1 otherwise)

Box 2: C2 := ( G2­(s1a,0) G2­(s2a,0) .. G2­(sna,0) ) ( G1­(s1b,1) G1­(s2b,1) .. G1­(snb,1) ) ⊕ Sc,r  ,
(Where r = 0 if g(λa, λbc) = λc ; r = 1 otherwise)

Box 3: C3 := ( G1­(s1a,1) G1­(s2a,1) .. G1­(sna,1) ) ( G2­(s1b,0) G2­(s2b,0) .. G2­(snb,0) ) ⊕ Sc,r  ,
(Where r = 0 if g(λac, λb) = λc ; r = 1 otherwise)

Box 4: C4 := ( G2­(s1a,1) G2­(s2a,1) .. G2­(sna,1) ) ( G2­(s1b,1) G2­(s2b,1) .. G2­(snb,1) ) ⊕ Sc,r  ,
(Where r =0 if g(λac, λbc) = λc ; r = 1 otherwise)

We can see that, if each party just shares the PRG outputs of both seeds for the computation of these 4 cypherboxes and adversary have corrupted t parties, then the adversary can gain extra information about the messages in the boxes, that are not supposed to open in an execution (For eg: if t = n-1, and without loss of generality P1 is the only honest player, then G1(s1a,0)), G2(s1a,0)), G1(s1a,1)), G2(s1a,1)) are leaked to the adversary, and he can compute all the Sc,r in all Boxes). So C1, C2, C3 and C4 should be a computed only by a Multi-Party Computation function. If that’s the case, adversary, who doesn’t know the seed(s) of honest party, will see the cypherboxes as One-Time padded messages with PRG outputs.

Now the λi for all output wires i are reconstructed and shared with every party. In the end of Offline phase, every party Pi knows,
•          2 Seeds of each wires
•          4 Cypherboxes for each gate g
•          Secret share of λj , for all wires j
•          λk , for all output wire k
•          λm , for all input wire (m) of the party Pi

Online Phase

Each party will evaluate the circuit in this phase. All parties know their input to their input wires. We define a new bit Δj of a wire j as follows:

Δj = bj λj

where bj is the actual bit in a wire, in a specific evaluation. The Δj value of the input wire j of Pi can be calculated by the party Pi only; because only Pi knows λj. But everybody needs Δ to evaluate the circuit. So the owner of the input wire(s) will broadcast the Δ values of his input wires. In fact, after this step, all parties will get to know the Δ values of all the input wires in the circuit. For decrypting one logic gate, we need exactly one SuperSeed for each input wire. So every party will share their seeds siw,Δw so that every party will get exactly one SuperSeed corresponding to Δj for each input wire j. With this information, players can decrypt exactly one CypherBox as follows:

 Δa Δb Decryptable Box 0 0 C1 0 1 C2 1 0 C3 1 1 C­4

Using the SuperSeeds Sa,Δa and Sb,Δb , all parties can decrypt the CypherBox and get the SuperSeed of the output wire, and so on. But it’s not clear how to get Δ value of the new (output) wire. But every player knows their seeds on all the wires, and SuperSeed is nothing but appending all the seeds of players. So he will just check the seed bits corresponding to that player ((i-1)*k + 1 to i*k for player Pi) in the SuperSeed. If that happened to be equal to sic,0 then the Δc is 0. Otherwise, it will be 1.

In short, after computing and sharing Δw values and SuperSeeds Sw,Δw of all input wires w, no other communication between the parties are required. The entire circuit evaluation is done as local computation. Note that, Δ values are found and propagated in the circuit. As far as λ values are chosen random, by disclosing Δ values, no information about the actual bit b will be leaked.

Correctness

Consider the case when Δa = Δb = 0. We have to prove that Δc and Sc,Δc are correctly computed.
Δa = 0 ba = λa
Δb = 0 bb = λb
As per the table of decryptable cypherboxes, we will decrypt C1.
• If g(λa, λb) = λc , that means g(ba, bb) = λc and we will be encrypting Sc,0 as message, in C1 (see definition). We can see that Δc = 0, which is consistent with the definition of Δ. In this case,

1.      g(ba, bb) = λc
2.      g(ba, bb) = bc
1 & 2 ⇒ λc = bc
⇒ Δc = bc λc = 0
•  If g(λa, λb) = λcc , that means g(ba, bb) = λcc. We will de deciphering C1, which is an encryption of SuperSeed Sc,1. We see Δc = 1 here, and consistent with definition of Δ. Here,

1.      g(ba, bb) = λcc
2.      g(ba, bb) = bc
1 & 2 λc = bcc
Δc = λc bc  =  bcc bc = 1

When both Δa and Δb are 0, SuperSeed and Δc calculated are shown to be correct. All the other cypherboxes, we can prove with similar argument.

At the end of circuit evaluation, all parties will get to know the Δ values of output wires. We know the λ values of output wires (shared in offline phase). Hence we can compute bc using the equation bc =  λc Δc  for each output wire c.