Completeness theorems for non-cryptographic fault-tolerant distributed computation

By Michael Ben-Or, Shafi Goldwasser, Avi Wigderson. 1988

Every function of n inputs can be efficiently computed by a complete network of n processors in such a way that: 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!

Subfields: Privacy & Security, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Privacy & Security

In Algorithms & Complexity

Citations in the corpus

Turbo-Aggregate: Breaking the Quadratic Aggregation Barrier in Secure Federated Learning (2020, background): “Their main bottleneck is the high communication cost, and communication-efficient implementations require an extensive offline computation part [19], [20].”
Private federated learning on vertically partitioned data via entity resolution and additively homomorphic encryption (2017, background): “as garbled circuits [Yao, 1986] and secret sharing [Ben-Or et al., 1988].”
Prio: Private, Robust, and Scalable Computation of Aggregate Statistics (2017, background): “In theory, secure multi-party computation (MPC) protocols [11, 15, 68, 90, 123] allow a set of servers, with some”
A Comprehensive Comparison of Multiparty Secure Additions with Differential Privacy (2015, neutral): “against computationally unbounded attackers [5].”
Privacy-Preserving Ridge Regression on Hundreds of Millions of Records (2013, methodology): “These servers then run the learning algorithm using a distributed protocol such as BGW [1] and privacy is assured as long as a majority of servers do not collude.”
Distributed Private Data Analysis: On Simultaneously Solving How and What (2008, methodology): “SFE has been the subject of extensive cryptographic research (initiated in [18,13,3, 1 ]), and SFE protocols exist for any feasible function f(¢) in a variety of general settings.”
Secure Multiparty Computation for Privacy-Preserving Data Mining (2009, methodology): “These feasibility results hold only in the computational setting; analogous results for the information-theoretic setting cannot be obtained when t ≥ m/2 (7).”
Non-interactive cryptocomputing for NC/sup 1/ (1999, methodology): “Multi-party computations in the information theoretic model were given by Ben-Or, Goldwasser, Wigderson and Chaum, Crepeau and Damgaard [7] [10].”
Mix and Match: Secure Function Evaluation via Ciphertexts (2000, methodology): “Ben-Or, Goldwasser, and Widgerson [ 4 ] and Chaum, Cr´ epeaud, and Damg˚ ard [11] introduced the first protocols enabling security against an active adversary in the non-cryptographic model, that is, one in which players are assumed to have unbounded computing power, but cannot eavesdrop on honest p”
Decentralizing Privacy: Using Blockchain to Protect Personal Data (2015, methodology): “, using Shamir’s Secret Sharing [23]), rather than encrypting them, we could then use secure Multiparty Computation (MPC) to securely evaluate any function [3].”
Verifiable Delegation of Computation over Large Datasets (2011, unknown): “This is similar to the way research over secure multiparty computation has evolved: following generic protocols for the evaluation of arbitrary functions [63, 29, 9, 17], there has been a twenty-plus year effort to come up with efficient distributed protocols for specific computations encountered in”