A Full Proof of the BGW Protocol for Perfectly-Secure Multiparty Computation

Gilad Asharov and Yehuda Lindell

Abstract:

In the setting of secure multiparty computation, a set of n parties with private inputs wish to jointly compute some functionality of their inputs. One of the most fundamental results of information-theoretically 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<n2 parties are corrupted, and when the adversary is malicious this holds as long as t<n3 parties are corrupted. Unfortunately, a full detailed proof of these results was never provided; in addition, a full specification of the protocol in the malicious setting has also never been published. In this paper, we remedy this situation and provide a full specification of the BGW protocol and a full proof of its security. We also derive corollaries for security in the presence of adaptive adversaries and under concurrent general composition (equivalently, universal composability).

PDF.

Back Home