Cryptography Reference
In-Depth Information
adversaries (75; 124; 74). These constructions proceed in two steps (see
details in (63; 67)). First a secure protocol is presented for the model
of passive adversaries (for any number of dishonest parties), and next
such a protocol is “compiled” into a protocol that is secure in one of
the two models of active adversaries (i.e., either in a model allowing
the adversary to control only a minority of the parties or in a model
in which premature suspension of the execution is not considered a
violation of security). These two steps are presented in the following
two corresponding subsections, in which we also present two relatively
simple protocols for two specific tasks, which are used extensively in
the general protocols.
Recall that in the model of passive adversaries, all parties follow
the prescribed protocol, but at termination the adversary may alter
the outputs of the dishonest parties depending on all their intermediate
internal states (during the execution). Below, we refer to protocols that
are secure in the model of passive (resp., active) adversaries by the term
passively-secure
(resp.,
actively-secure
).
7.3.1
Passively-secure computation with shares
For any
m ≥
2, suppose that
m
parties, each having a private input,
wish to obtain the value of a predetermined
m
-argument function
evaluated at their sequence of inputs. Below, we outline a passively-
secure protocol for achieving this goal. We mention that the design
of passively-secure multi-party protocol for any functionality (allowing
different outputs to different parties as well as handling also random-
ized computations) reduces easily to the aforementioned task.
We assume that the parties hold a circuit for computing the value
of the function on inputs of the adequate length, and that the circuit
contains only
and
and
not
gates. The key idea is to have each party
“secretly share” its input with everybody else, and “secretly transform”
shares of the input wires of the circuit into shares of the output wires
of the circuit, thus obtaining shares of the outputs (which allows for
the reconstruction of the actual outputs). The value of each wire in the
circuit is shared in a way such that all shares yield the value, whereas
lacking even one of the shares keeps the value totally undetermined.
