Cryptography Reference
In-Depth Information
That is, we use a simple secret sharing scheme (cf. (117)) such that a
bit
b
is shared by a random sequence of
m
bits that sum-up to
b
mod
2. First, each party shares each of its input bits with all parties (by
secretly sending each party a random value and setting its own share
accordingly). Next, all parties jointly scan the circuit from its input
wires to the output wires, processing each gate as follows:
•
When encountering a gate, the parties already hold shares of
the values of the wires entering the gate, and their aim is to
obtain shares of the value of the wires exiting the gate.
•
For a
not
-gate this is easy: the first party just flips the value
of its share, and all other parties maintain their shares.
•
Since an
and
-gate corresponds to multiplication modulo 2,
the parties need to securely compute the following random-
ized functionality (in which the
x
i
's denote shares of one
entry-wire, the
y
i
's denote shares of the second entry-wire,
the
z
i
's denote shares of the exit-wire, and the shares indexed
by
i
belongs to Party
i
):
((
x
1
,y
1
)
, ...,
(
x
m
,y
m
))
→
(
z
1
, ..., z
m
)
(7.1)
where
i
=1
z
i
=(
i
=1
x
i
)
(
i
=1
y
i
).
·
(7.2)
That is, the
z
i
's are random subject to Eq. (7.2).
Finally, the parties send their shares of each circuit-output wire to the
designated party, which reconstructs the value of the corresponding bit.
Thus, the parties have propagated shares of the input wires into shares
of the output wires, by repeatedly conducting privately-secure compu-
tation of the
m
-ary functionality of Eq. (7.1) & (7.2). That is, securely
evaluating the entire (arbitrary) circuit “reduces” to securely conduct-
ing a specific (very simple) multi-party computation. But things get
even simpler: the key observation is that
m
m
m
x
i
y
i
+
1
≤i<j≤m
x
i
·
y
i
=
(
x
i
y
j
+
x
j
y
i
)
(7.3)
i
=1
i
=1
i
=1
Thus, the
m
-ary functionality of Eq. (7.1) & (7.2) can be computed as
follows (where all arithmetic operations are mod 2):
