Completeness Theorems for Non-Cryptographic
Fault-Tolerant Distributed Computation
(Extended Abstract)
Michael Ben-Or*
Shafi Goldwassert
Hebrew University
MIT
Avi Wigdemon*
Hebrew University
Abstract
Every function of n inputs can be efficiently computed
by a complete network of n processors in such a way
that:
1.
2.
If no faults occur, no set of size t < n/2 of players
gets any additional information (other than the
function value),
Even if Byzantine faults are allowed, no set of
size t < n/3 can either disrupt the computation
or get additional information.
Furthermore, the above bounds on t are tight!
Introduction
The rapid development of distributed systems raised
the natural question of what tasks can be performed
by them (especially when faults occur). A large body
of literature over the past ten years addressed this
question. There are two approaches to this question,
depending on whether a limit on the computational
power of processors
is assun or not.
The cryptographic approach, inaugurated by
Difiie
and Hellman [DH],
assumes the players are computa-
tionally bounded, and further assumes the existence
*Supported by Alon Fellowship.
tSupported in part by NSF grant 865727~CCR, AR0
grant DAALOWSK-017,
and US-Israel BSF grant 8640301,
Jerusalem, Israel.
:Supported by Alon Fellowship.
Permission to copy without fee all or part of this material is granted
provided that the copies are not made or distributed for direct
commercial advantage. the ACM copyright notice and the title of
-
the publication and its date appear, a&l notice is given that copying
is by permission of the Association for Computing Machinery. TO
copy otherwise. or to republish.
requires a fee and/or
specfk
permissiotl.
@ 1988 ACM-O-89791-264-O/88/0005/0001 $1.50
of certain (one-way) functions, that can be computed
but not inverted by the player.
This simple assumption was ppstulated in [DH] in
order to achieve the basic task of secure message ex-
change between two of the processors, but turned out
to be universal! In subsequent years ingenious pro-
tocols baaed on the same assumption were given for
increasingly harder tasks such as contract signing, se-
cret exchange, joint coin flipping, voting and playing
Poker. These results culminated, through the defini-
tion of zero-knowledge proofs [GMR], their existence
for NP-complete problems [GMWl] in completeness
theorems for two-party pl] and multi-party [GMW2]
cryptographic distributed computation. In particu-
lar the results of Goldreich, Micali and Wigdesrson
in [GMWB] were the main inspiration to our work.
They show, that if (non-uniform) one way functions
exist then every (probabilistic) function of n input,s
can be computed by n computationally bounded pro-
cessors in such a way that: (1) If no faults occur,
no subset of the players can compute any additional
information, and (2) Even if Byzantine faults are al-
lowed, no set of size t < n/2 can either disrupt the
computation or compute additional information.
The non-Cryptographic (or information-theoretic)
approach does not limit the computational power of
the processors. Here, the notion of privacy is much
stronger - for a piece of data to be unknown to a set of
players it does not suffice that they cannot compute
it within a certain time bound from what they know,
but simply that it cannot be computed at all!
To facilitate the basic primitive of secret message
exchange between a pair of players, we have secure
channels. (For an excellent source of results and prob-
lems in the case no secure channels exist, see [BL]).
Unlike the cryptographic case, very little was known
about the capabilities of this model. Two main basic
problems were studied and solved (in the synchronous
case): Byzantine agreement [LPS,DS,...] and collec-
tive coin flipping p2].
1
