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 multiparty computation function f is already given, and
we expect Semihonest behaviour (at worst) from the parties, and the threshold
for corrupted parties is (n1).
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 W1. At first, all players will (collaboratively)
choose one random bit for each wire, namely λ_{0}, λ_{1…},_{ }λ_{w1. }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_{}^{i}_{w,0} and s_{}^{i}_{w,1}
for each player i, for each wire w. Now we define SuperSeed for a wire w.
S_{w,0 }= s^{1}_{w,0
} s^{2}_{w,0 } .. s^{i}_{w,0} ..  s^{n}_{w,0}
S_{w,1 }= s^{1}_{w,1
} s^{2}_{w,1 } .. s^{i}_{w,1} ..  s^{n}_{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^{1 }and G^{2}
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_{1} := ( G^{1}_{}(s^{1}_{a,0}) ⊕ G^{1}_{}(s^{2}_{a,0}) .. ⊕ G^{1}_{}(s^{n}_{a,0}) ) ⊕ ( G^{1}_{}(s^{1}_{b,0}) ⊕ G^{1}_{}(s^{2}_{b,0}) .. ⊕ G^{1}_{}(s^{n}_{b,0}) ) ⊕ S_{c,r } ,
(Where r = 0 if g(λ_{a, }λ_{b}) = λ_{c }; r = 1 otherwise)
Box
2: C_{2} := ( G^{2}_{}(s^{1}_{a,0}) ⊕ G^{2}_{}(s^{2}_{a,0}) .. ⊕ G^{2}_{}(s^{n}_{a,0}) ) ⊕ ( G^{1}_{}(s^{1}_{b,1}) ⊕ G^{1}_{}(s^{2}_{b,1}) .. ⊕ G^{1}_{}(s^{n}_{b,1}) ) ⊕ S_{c,r } ,
(Where r = 0 if g(λ_{a, }λ_{b}^{c})
= λ_{c }; r = 1
otherwise)
Box
3: C_{3} := ( G^{1}_{}(s^{1}_{a,1}) ⊕ G^{1}_{}(s^{2}_{a,1}) .. ⊕ G^{1}_{}(s^{n}_{a,1}) ) ⊕ ( G^{2}_{}(s^{1}_{b,0}) ⊕ G^{2}_{}(s^{2}_{b,0}) .. ⊕ G^{2}_{}(s^{n}_{b,0}) ) ⊕ S_{c,r } ,
(Where r = 0 if g(λ_{a}^{c}_{, }λ_{b})
= λ_{c }; r = 1
otherwise)
Box
4: C_{4} := ( G^{2}_{}(s^{1}_{a,1}) ⊕ G^{2}_{}(s^{2}_{a,1}) .. ⊕ G^{2}_{}(s^{n}_{a,1}) ) ⊕ ( G^{2}_{}(s^{1}_{b,1}) ⊕ G^{2}_{}(s^{2}_{b,1}) .. ⊕ G^{2}_{}(s^{n}_{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 = n1, and without loss of
generality P_{1 }is the only honest player, then G^{1}(s^{1}_{a,0})),
G^{2}(s^{1}_{a,0})), G^{1}(s^{1}_{a,1})),
G^{2}(s^{1}_{a,1})) are leaked to the adversary, and he
can compute all the S_{c,r }in all Boxes). So C_{1}, C_{2},
C_{3} and C_{4 }should be a computed only by a MultiParty
Computation function. If that’s the case, adversary, who doesn’t know the
seed(s) of honest party, will see the cypherboxes as OneTime 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^{i}_{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

C_{1}

0

1

C_{2}

1

0

C_{3}

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
((i1)*k + 1 to i*k for player P_{i}) in the SuperSeed. If that
happened to be equal to s^{i}_{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_{1}.
 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_{1 }(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_{1}, 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.
No comments:
Post a Comment