[BGW88] Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation

Authors: Michael Ben-Or, Shafi Goldwasser, Avi Wigderson | Venue: STOC 1988 | Source

Abstract

Every function of $n$ inputs can be efficiently computed by a complete network of $n$ processors in such a way that: (1) If the number of faulty processors is less than $n/3$, each processor gets the correct value of the function (perfect correctness), and the privacy of the inputs of honest processors is preserved (perfect privacy). (2) If the number of faulty processors is less than $n/2$, (1) holds except with exponentially small probability. The result applies to both active (Byzantine) and passive (eavesdropping) faults, and yields general, non-cryptographic protocols for secret-key agreement, oblivious circuit evaluation, Byzantine agreement, and all “multi-party computations.”

BibTeX

Copy

@inproceedings{BGW88,
  author    = {Michael Ben-Or and Shafi Goldwasser and Avi Wigderson},
  title     = {Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation},
  booktitle = {Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC 1988)},
  pages     = {1--10},
  year      = {1988}
}