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