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 λ­₀, λ­_1…, λ­_­w-1. Each λ­_i values are secret shared among all n parties. Then λ_j is reconstructed to party P_i, if ‘j’ is one of the input wires of P_i.

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_­­­­­­­­­ⁱ_w,0 and s_­­­­­­­­­ⁱ_w,1 for each player i, for each wire w. Now we define SuperSeed for a wire w.

            S_w,0 = s¹_w,0 || s²_w,0 || .. sⁱ_w,0 .. || sⁿ_w,0

            S_w,1 = s¹_w,1 || s²_w,1 || .. sⁱ_w,1 .. || sⁿ_w,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 S_w,0 represent the bit λ­_w, and S_w,0 represent the bit λ­_w^c.

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 G¹ and G² 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: C₁ := ( G¹_­(s¹_a,0) ⊕ G¹_­(s²_a,0) .. ⊕ G¹_­(sⁿ_a,0) ) ⊕ ( G¹_­(s¹_b,0) ⊕ G¹_­(s²_b,0) .. ⊕ G¹_­(sⁿ_b,0) ) ⊕ S_c,r  ,

(Where r = 0 if g(λ_a, λ_b) = λ_c ; r = 1 otherwise)

Box 2: C₂ := ( G²_­(s¹_a,0) ⊕ G²_­(s²_a,0) .. ⊕ G²_­(sⁿ_a,0) ) ⊕ ( G¹_­(s¹_b,1) ⊕ G¹_­(s²_b,1) .. ⊕ G¹_­(sⁿ_b,1) ) ⊕ S_c,r  ,

(Where r = 0 if g(λ_a, λ_b^c) = λ_c ; r = 1 otherwise)

Box 3: C₃ := ( G¹_­(s¹_a,1) ⊕ G¹_­(s²_a,1) .. ⊕ G¹_­(sⁿ_a,1) ) ⊕ ( G²_­(s¹_b,0) ⊕ G²_­(s²_b,0) .. ⊕ G²_­(sⁿ_b,0) ) ⊕ S_c,r  ,

(Where r = 0 if g(λ_a^c_, λ_b) = λ_c ; r = 1 otherwise)

Box 4: C₄ := ( G²_­(s¹_a,1) ⊕ G²_­(s²_a,1) .. ⊕ G²_­(sⁿ_a,1) ) ⊕ ( G²_­(s¹_b,1) ⊕ G²_­(s²_b,1) .. ⊕ G²_­(sⁿ_b,1) ) ⊕ S_c,r  ,

(Where r =0 if g(λ_a^c_, λ_b^c) = λ_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 P₁ is the only honest player, then G¹(s¹_a,0)), G²(s¹_a,0)), G¹(s¹_a,1)), G²(s¹_a,1)) are leaked to the adversary, and he can compute all the S_c,r in all Boxes). So C₁, C₂, C₃ and C₄ 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 P_i 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 P_i

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 = b_j ⊕ λ_j

where b_j is the actual bit in a wire, in a specific evaluation. The Δ_j value of the input wire j of P_i can be calculated by the party P_i only; because only P_i 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 sⁱ_w,Δ_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 S_a,Δ_a and S_b,Δ_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 P_i) in the SuperSeed. If that happened to be equal to sⁱ_c,0 then the Δ_c is 0. Otherwise, it will be 1.

In short, after computing and sharing Δ_w values and SuperSeeds S_w,_Δ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 S_c,Δc are correctly computed.

Δ_a = 0 ⇒ b_a = λ_a

Δ_b = 0 ⇒ b_b = λ_b

As per the table of decryptable cypherboxes, we will decrypt C₁.

• If g(λ_a, λ_b) = λ_c , that means g(b_a, b_b) = λ_c and we will be encrypting S_c,0 as message, in C₁ (see definition). We can see that Δ_c = 0, which is consistent with the definition of Δ. In this case,

1.      g(b_a, b_b) = λ_c

2.      g(b_a, b_b) = b_c

1 & 2 ⇒ λ_c = b_c

           ⇒ Δ_c = b_c ⊕ λ_c = 0

•  If g(λ_a, λ_b) = λ_c^c , that means g(b_a, b_b) = λ_c^c. We will de deciphering C₁, which is an encryption of SuperSeed S_c,1. We see Δ_c = 1 here, and consistent with definition of Δ. Here,

1.      g(b_a, b_b) = λ_c^c

2.      g(b_a, b_b) = b_c

1 & 2 ⇒ λ_c = b_c^c

          ⇒ Δ_c = λ_c ⊕ b_c  =  b_c^c ⊕ b_c = 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 b_c using the equation b_c =  λ_c ⊕ Δ_c  for each output wire c.