You are looking at a specific version 20110708:142753 of this paper. See the latest version.

Paper 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 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 \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 detailed proof of these results was never given. In this paper, we remedy this situation and provide a full proof of security of the BGW protocol. We also derive corollaries for security in the presence of adaptive adversaries and under concurrent general composition (equivalently, universal composability). In addition, we give a full specification of the protocol for the malicious setting. This includes one new step for the perfect multiplication protocol in the case of $n/4\leq t<n/3$.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
Keywords
perfect securitymultiparty computationBGW
Contact author(s)
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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.