A Completeness Theorem for Protocols with Honest Majority

By O. Goldreich, S. Micali, Avi Wigderson. 1987

How researchers see this paper

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

QUOTIENT: Two-Party Secure Neural Network Training and Prediction (2019, neutral): “In our two-party setting natural choices are garbled circuits and the GMW protocol [18].”
Efficient Pseudorandom Correlation Generators: Silent OT Extension and More (2019, methodology): “This should be contrasted with OT-based MPC protocols, which have total communication complexity Ω(M(2)s) [40, 43] .”
Security and Privacy on Blockchain (2019, background): “proposed a generalization of the two party computation to the multi-party computation in 1987 [45], assuming that all inputs of the computation and zero-knowledge proofs are parts of secret sharing.”
Foundations of garbled circuits (2012, methodology): “The first written account of the method is by Goldreich, Micali, and Wigderson [22].”
SecureNN: 3-Party Secure Computation for Neural Network Training (2019, methodology): “However, general purpose MPC/3PC work over low-level circuits (either arithmetic or boolean) and for complex tasks such as neural network training, this leads to highly inefficient protocols that can take “forever to execute” (also pointed out by [21, 26, 33, 36]).”
Fast and Secure Three-party Computation: The Garbled Circuit Approach (2015, background): “Since the seminal work of [Yao86, GMW87] showing its feasibility in the two-party and multi-party settings, MPC has been the subject of extensive research, focusing on bettering security and eﬃciency.”