Cryptography Reference
In-Depth Information
differ in the specific restrictions and/or requirements placed on the parties in the real
computation. This typically is reflected in the definition of the corresponding ideal
model; see the examples that follow.
B.3.1.1. An Example: Computations with Honest Majority
Here we consider an ideal model in which any minority group (of the parties) can
collude as follows. First, this minority shares its original inputs and decides together
on replacement inputs
10
to be sent to the trusted party. (The other parties send their re-
spective original inputs to the trusted party.) When the trusted party returns the output,
each majority player outputs it locally, whereas the colluding minority can compute
an output based on all they know (i.e., the output and all the local inputs of these
parties). A
secure multi-party computation with honest majority
is required to sim-
ulate this ideal model. That is, the effect of any feasible adversary that controls a
minority of the players in the actual protocol can essentially be simulated by a (dif-
ferent) feasible adversary that controls the corresponding players in the ideal model.
This means that in a secure protocol the effect of each minority group is “essentially
restricted” to replacing its own local inputs (independently of the local inputs of the
majority players) before the protocol starts and replacing its own local outputs (depend-
ing only on its local inputs and outputs) after the protocol terminates. (We stress that
in the real execution the minority players do obtain additional pieces of information;
yet in a secure protocol they gain essentially nothing from these additional pieces of
information.)
Secure protocols according to this definition can even tolerate a situation where a
minority of the parties choose to abort the execution. An aborted party (in the real
protocol) is simulated by a party (in the ideal model) that aborts the execution either
before supplying its input to the trusted party (in which case a default input is used)
or after supplying its input. In either case, the majority players (in the real protocol)
are able to compute the output even though a minority aborted the execution. This
cannot be expected to happen when there is no honest majority (e.g., in a two-party
computation) [53].
B.3.1.2. Another Example: Two-Party Computations Allowing Abort
In light of the foregoing, we consider an ideal model where each of the two parties can
“shut down” the trusted (third) party at any point in time. In particular, this can happen
after the trusted party has supplied the outcome of the computation to one party but
before it has supplied it to the second. A
secure two-party computation allowing abort
is
required to simulate this ideal model. That is, each party's “effective malfunctioning”
in such a secure protocol is restricted to supplying an initial input of its choice and
aborting the computation at any point in time. We stress that, as before, the choice of
the initial input of each party cannot depend on the input of the other party.
10
Such replacement can be avoided if the local inputs of parties are verifiable by the other parties. In such a
case, a party (in the ideal model) has the choice of either joining the execution of the protocol with its correct local
input or not joining the execution at all (but it cannot join with a replaced local input). Secure protocols simulating
this ideal model can be constructed as well.
