Cryptography Reference
In-Depth Information
•
If, however, such a (trusted) party does not exist, then the situation is more
involved. The question that arises immediately is whether and to what extent
the trusted party can be simulated by the
n
(mutually distrusting) parties. This
is what
secure function evaluation
as originally introduced by Andrew C. Yao
2
in the early 1980s [2] and MPC are all about: finding cryptographic protocols
that can be used to simulate (and hence replace) trusted parties.
For the sake of simplicity, we consider only the case where the specified
random process is deterministic (e.g., computing a function) and the
n
local outputs
(for the
n
parties) are essentially the same. In this case, we consider an arbitrary
n
-
ary function and
n
parties that wish to obtain the evaluation of the function on their
private inputs. More specifically, we allow a set
P
=
{
P
1
,P
2
,...,P
n
}
of
n
players to compute an arbitrary agreed function of their private inputs, even if
an adversary may corrupt and control some of the players in various ways (see the
following). Two communication models must be distinguished:
•
In a
synchronous
communication model, any pair of players can communi-
cate synchronously over a secure channel. Sometimes, it is assumed that a
broadcast channel is available that guarantees the consistency of the received
values if a player sends a value to several players. In practice, however, such
a broadcast channel seldom exists. If one is needed, then it must be simulated
by a quite inefficient Byzantine agreement protocol (e.g., [3]).
•
In the
asynchronous
communication model, any pair of players can only
communicate asynchronously. This suggests that one does not have guarantees
about the arrival times of sent messages. This complicates things considerably.
Security in MPC means that the players' inputs remain secret during the
evaluation of the function and that the results of the computation (i.e., function
evaluation) are guaranteed to be correct. More specifically, security in MPC is
defined relative to an ideal-world specification involving a trusted party. If anything
an adversary can achieve in the real world (i.e., the world in which the MPC protocol
is executed) can also be achieved in the ideal world (i.e., the world in which there
exists a trusted party), then we are talking about a
secure multiparty computation
.A
secure multiparty computation does not, for example, protect against the possibility
of having players provide wrong inputs. Such a manipulation is possible in either
world (i.e., in the real world and in the ideal world). There is nothing a cryptographic
2
Andrew C. Yao received the ACM Turing Award in 2000.
