Cryptography Reference
In-Depth Information
18.2
MAJOR RESULTS
In the late 1980s, a couple of fundamental results about secure MPC were found and
published. Most importantly, Oded Goldreich, Silvio Micali, and Avi Wigderson
proved that cryptographically secure MPC is possible if and only if
t<n/
2
(
t<n
) players are corrupted actively (passively) [4]. Similarly, Michael Ben-
Or, Goldreich, and Wigderson, as well as David Chaum, Claude Crepeau, and
Ivan B. Damgard, proved that information-theoretic secure MPC is possible in the
synchronous communication model if and only if
t<n/
3(
t<n/
2) players are
corrupted actively (passively) [5, 6]. If a physical broadcast channel is available,
then the last result regarding active corruption can be improved to
t<n/
2 [7, 8].
These fundamental results were published at a time in which intensive elec-
tronic multiparty interactions seemed only a remote possibility. This may explain
the impression that, while generating considerable interest within the community
that deals with the theory of computation, the results went almost unnoticed in the
community that deals with applied cryptography. This situation has changed fun-
damentally, and intensive electronic multiparty interactions are possible today using
the Internet. Against this background, many cryptographers have started to reactivate
the field and to work again on secure MPC. For example, the previously mentioned
results for the information-theoretic setting were improved in the late 1990s by con-
sidering a mixed model in which an adversary can corrupt up to
t
a
players actively,
up to
t
p
players passively, and up to
t
f
players using a fail corruption (see, for exam-
ple, [9, 10] for specific results). As of this writing, secure MPC has become a very
active area of cryptographic research, and many results and findings are published
in the relevant literature.
18.3
FINAL REMARKS
In this chapter, we briefly touched on secure MPC and summarized the major results
that have been achieved. The results suggest that unless a substantial perecentage of
the players are corrupted, secure MPC is possible (in either an information-theoretic
or cryptographic sense).
There are many applications for MPC. If, for example,
n
parties want to
compute a function without revealing their individual input values, then a protocol
for secure MPC can be employed. The following problems are often mentioned for
two parties:
Millionaires' problem:
Two millionaires want to determine who is richer without
involving a trusted person and without revealing any information about each
other's wealth (except who is richer).
