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

by Gilad Asharov and Yehuda Lindell

Oded's comments

The abstract talks for itself. I just wish to commend the authors for undertaking this project (which is, unfortunately, unusual in our community). Having a proof of a central theorem, which is widely regarded a classic, is indeed a good reason for celebration.

The original abstract (see ECCC, TR11-036)

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 less than n/2 parties are corrupted, and when the adversary is malicious this holds as long as t less than n/3 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).

Back to list of Oded's choices.