Completeness theorems for non-cryptographic fault-tolerant distributed computation
Published 1 January 1988Open access
Michael Ben-Or, Avi Wigderson
Citations2,515
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The above bounds on t, where t is the number of players in actors, are tight!
Abstract
Every function of n inputs can be efficiently computed by a complete network of n processors in such a way that:
Keywords
Computer Science
IEEE Transactions on Information TheoryNew directions in cryptography
14,441 Citations1976Whitfield Diffie, Martin E. Hellman
Communications of the ACMHow to share a secret
13,453 Citations1979Adi Shamir
This technique enables the construction of robust key management schemes for cryptographic systems that can function securely and reliably even when misfortunes destroy half the pieces and security breaches expose all but one of the remaining pieces.
How to generate and exchange secrets
3,712 Citations1986Andrew Chi-Chih Yao
It is shown how two parties A and B can interactively generate a random integer N = p¿q such that its secret, i.e., the prime factors, is hidden from either party individually but is recoverable jointly if desired.
How to play ANY mental game
3,541 Citations1987Oded Goldreich, Silvio Micali +1 more
This work presents a polynomial-time algorithm that, given as a input the description of a game with incomplete information and any number of players, produces a protocol for playing the game that leaks no partial information, provided the majority of the players is honest.
Journal of the ACMReaching Agreement in the Presence of Faults
2,364 Citations1980Marshall C. Pease, Robert E. Shostak +1 more
It is shown that the problem is solvable for, and only for, n ≥ 3m + 1, where m is the number of faulty processors and n is the total number and this weaker assumption can be approximated in practice using cryptographic methods.
Multiparty unconditionally secure protocols
1,515 Citations1988David Chaum, Claude Crépeau +1 more
It is shown that any reasonable multiparty protocol can be achieved if at least 2n/3 of the participants are honest and the secrecy achieved is unconditional.
The knowledge complexity of interactive proof-systems
1,212 Citations1985Sbafi Goldwasser, Silvio Micali +1 more
Proofs that yield nothing but their validity and a methodology of cryptographic protocol design
544 Citations1986Oded Goldreich, Silvio Micali +1 more
This paper demonstrates the generality and wide applicability of zero-knowledge proofs, a notion introduced by Goldwasser, Micali and Rackoff that efficiently demonstrate membership in the language without conveying any additional knowledge.
Polynomial algorithms for multiple processor agreement
149 Citations1982Danny Dolev, H. Raymond Strong
It is proved that no matter what kind of information is exchanged, there is no way to reach agreement with fewer than t+1 rounds of exchange, where t is the upper bound on the number of faults.
Association for Computing Machinery eBooksThe knowledge complexity of interactive proof-systems
128 Citations2019Shafi Goldwasser, Silvio Micali +3 more