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

Gilad Asharov; Yehuda Lindell

Paper 2011/136

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

Gilad Asharov

, Bar-Ilan University

Yehuda Lindell, Bar-Ilan University

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 .

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: A minor revision of an IACR publication in JOC 2017
Keywords: perfect security multiparty computation BGW
Contact author(s): Gilad Asharov @ biu ac il
Lindell @ biu ac il
History: 2022-06-12: last of 8 revisions; 2011-03-21: received; See all versions
Short URL: https://ia.cr/2011/136
License: CC BY

BibTeX

@misc{cryptoeprint:2011/136,
      author = {Gilad Asharov and Yehuda Lindell},
      title = {A Full Proof of the {BGW} Protocol for Perfectly-Secure Multiparty Computation},
      howpublished = {Cryptology {ePrint} Archive, Paper 2011/136},
      year = {2011},
      url = {https://eprint.iacr.org/2011/136}
}