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 ) .
} 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;
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
Search WWH ::

Custom Search