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):