Cryptography Reference
In-Depth Information
(1) Each Party
i
locally computes
z
i,i
de
=
x
i
y
i
.
(2) Next, each pair of parties (i.e., Parties
i
and
j
) securely
compute random shares of
x
i
y
j
+
y
i
x
j
.Thatis,Parties
i
and
j
(holding (
x
i
,y
i
)and(
x
j
,y
j
), respectively), need to
securely compute the randomized two-party functionality
((
x
i
,y
i
)
,
(
x
j
,y
j
))
→
(
z
i,j
,z
j,i
), where the
z
's are random sub-
ject to
z
i,j
+
z
j,i
=
x
i
y
j
+
y
i
x
j
.Equivalently,Party
j
uni-
formly selects
z
j,i
∈{
,andParties
i
and
j
securely com-
pute the deterministic functionality ((
x
i
,y
i
)
,
(
x
j
,y
j
,z
j,i
))
→
(
z
j,i
+
x
i
y
j
+
y
i
x
j
,λ
), where
λ
denotes the empty string.
The latter simple two-party computation can be securely
implemented using a 1-out-of-4 Oblivious Transfer (cf. (79)
and (67, Sec. 7.3.3)), which in turn can be implemented using
enhanced trapdoor permutations (see below). Loosely speak-
ing, a 1-out-of-
k
Oblivious Transfer is a protocol enabling one
party to obtain one of
k
secrets held by another party, with-
out the second party learning which secret was obtained by
the first party. That is, we refer to the two-party functionality
0
,
1
}
(
i,
(
s
1
, ..., s
k
))
→
(
s
i
,λ
)
.
(7.4)
}
∗
can
be privately-computed by invoking a 1-out-of-
k
Oblivious
Transfer on inputs
i
and (
f
(1
,y
)
, ..., f
(
k, y
)), where
i
(resp.,
y
) is the initial input of the first (resp., second) party.
(3) Finally, for every
i
=1
, ..., m
, summing-up all the
z
i,j
's yields
the desired share of Party
i
.
}
∗
→{
Note that any function
f
:
k
]
×{
0
,
1
0
,
1
The above construction is analogous to a construction that was briefly
described in (74). A detailed description and full proofs appear in (63;
67).
We mention that an analogous construction has been subsequently
used in the private channel model and withstands computationally
unbounded active (resp., passive) adversaries that control less than
one third (resp., a minority) of the parties (25). The basic idea is to
use a more sophisticated secret sharing scheme; specifically, via a low
degree polynomial (117). That is, the Boolean circuit is viewed as an
