Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation

URL: https://dl.acm.org/doi/10.1145/62212.62213 Authors: Michael Ben-Or, Shafi Goldwasser, Avi Wigderson

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.”