Completeness theorems for non-cryptographic fault-tolerant distributed computation

1988/01/01 by Michael Ben-Or, Avi Wigderson · 4 citations
Computer Science · #Cryptography and Data Security #Distributed systems and fault tolerance #Privacy-Preserving Technologies in Data

paper · pdf · doi:10.1145/62212.62213

openalex publication_date 1988/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04

Abstract

Every function of n inputs can be efficiently computed by a complete network of n processors in such a way that:

Citations

• How to play ANY mental game
• Reaching Agreement in the Presence of Faults
• How to share a secret
• The knowledge complexity of interactive proof-systems
• New directions in cryptography

Cited by

• Searchable symmetric encryption: Improved definitions and efficient constructions
• On Robust Combiners for Oblivious Transfer and Other Primitives
• Distributed computing column
• Secure multi-party computation [wikipedia]