The BGW Protocol for Perfectly-Secure Multiparty Computation
Gilad Asharov, Yehuda Lindell · IOS Press eBooks · 2013
One of the most fundamental results of secure computation was presented by Ben-Or, Goldwasser and Wigderson (BGW) in 1988. They demonstrated that any n-party functionality can be computed with perfect security, in the private channels model. When the adversary is semi-honest this holds as long as t < n/2 parties are corrupted, and when the adversary is malicious this holds as long as t < n/3 parties are corrupted. In this chapter, we present a full description of the BGW protocol for the semi-honest and malicious settings, along with detailed explanations and intuition regarding the security of the protocols; full proofs can be found in [1].