Cryptology ePrint Archive: Report 2011/136

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 secure computation was presented by Ben-Or, Goldwasser and Wigderson (BGW) in 1988. They demonstrated that any $n$-party functionality can be computed with \emph{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. Unfortunately, a full proof of these results was never published. In this paper, we remedy this situation and provide a full proof of security of the BGW protocol. This includes a full description of the protocol for the malicious setting, including the construction of a new subprotocol for the perfect multiplication protocol that seems necessary for the case of $n/4\leq t<n/3$.

Category / Keywords: cryptographic protocols / perfect security, multiparty computation, BGW

Date: received 17 Mar 2011, last revised 18 Sep 2014

Contact author: lindell at biu ac il

Available format(s): PDF | BibTeX Citation

Version: 20140918:074950 (All versions of this report)

Short URL: ia.cr/2011/136

Discussion forum: Show discussion | Start new discussion