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

作者：Asharov Gilad^*; Lindell Yehuda

来源：Journal of Cryptology, 2017, 30(1): 58-151.

DOI：10.1007/s00145-015-9214-4

• Multiparty computation
• Perfect security
• BGW
• Cryptographic protocols

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 perfect security, in the private channels model. When the adversary is semi-honest, this holds as long as parties are corrupted, and when the adversary is malicious, this holds as long as 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 <= t < n/3.

• 出版日期2017-1