Cryptography Reference
In-Depth Information
Generalizing the preceding, we can consider
secure multi-party computation allow-
ing abort
. Here, in the ideal model, each of the parties can “shut down” the trusted party
at any point in time; in particular, this can happen after the trusted party has supplied
the outcome of the computation to some but not all of the parties.
B.3.2. Constructions
Theorem B.3.1 (General Plausibility Results, Loosely Stated):
Suppose that
trapdoor permutations exist. Then
•
any multi-party functionality can be securely computed in a model allowing abort
(cf. [211] for the two-party case and [113] for the case of more than two parties)
.
•
any multi-party functionality can be securely computed provided that a strict ma-
jority of the parties are honest
[112, 113]
.
The proof of each item proceeds in two steps [98]:
1.
Presenting secure protocols for a “semi-honest” model in which the bad parties follow
the protocol, except that they also keep a record of all intermediate results.
11
One key idea is to consider the propagation of values along the wires of a circuit
(which computes the desired function), going from the input wires to the output wires.
The execution of these protocols starts by each party sharing its inputs with all other
parties, using a secret sharing scheme, so that any strict subset of the shares yields no
information about the secret (e.g., each party is given a uniformly chosen share, and the
dealer's share is set to the XOR of all other shares). A typical step consists of the secure
computation of shares of the output wire of a gate from the shares of the input wires of this
gate. That is, the
m
parties employ a secure protocol for computing the randomized
m
-
party functionality ((
a
1
,
b
1
)
,...,
(
a
m
,
b
m
))
→
(
c
1
,...,
c
m
), where the
c
i
's are uniformly
i
=
1
b
i
). Repeating this step for each gate
of the circuit (in a suitable order), the parties securely propagate shares along the wires of
the circuit, going from the input wires of the circuit to its output wires. At the end of this
propagation process, each party announces its shares in the output wires of the circuit,
and the actual output is formed. Thus, securely computing an arbitrary functionality
(which may be quite complex) is reduced to securely computing a few specific simple
functionalities (i.e., given shares for the inputs of a Boolean gate, securely compute
random shares for the output of this gate). Indeed, secure protocols for computing these
simple functionalities are also provided.
2.
Transforming protocols secure in the “semi-honest” model into full-fledged secure pro-
tocols. Here zero-knowledge proofs and protocols for fair coin-tossing are used in order
to “force” parties to behave properly (i.e., as in the “semi-honest” model).
Fair coin-tossing protocols are constructed using non-oblivious commitment schemes
(see Section 4.9.2), which in turn rely on zero-knowledge proofs of knowledge (see
Section 4.7).
i
=
1
c
i
=
i
=
1
a
i
,
⊕
distributed subject to
⊕
gate(
⊕
11
In other words, we need to simulate the local views of the dishonest players when given only the local inputs
and outputs of the honest players. Indeed, this model corresponds to the honest-verifier model of zero-knowledge
(see Section 4.3.1.7).
