Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #5 to TR11-036 | 13th June 2022 10:36

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

RSS-Feed




Revision #5
Authors: Gilad Asharov, Yehuda Lindell
Accepted on: 13th June 2022 10:36
Downloads: 180
Keywords: 


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 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).



Changes to previous version:

This version corrects a small error in the proofs of Theorems 4.2 and 7.2.


Revision #4 to TR11-036 | 18th September 2014 11:32

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





Revision #4
Authors: Gilad Asharov, Yehuda Lindell
Accepted on: 18th September 2014 11:32
Downloads: 1410
Keywords: 


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 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).



Changes to previous version:

Final version of paper, accept to the Journal of Cryptology.


Revision #3 to TR11-036 | 8th July 2011 16:34

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





Revision #3
Authors: Gilad Asharov, Yehuda Lindell
Accepted on: 8th July 2011 16:34
Downloads: 3400
Keywords: 


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 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).


Revision #2 to TR11-036 | 4th April 2011 07:57

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





Revision #2
Authors: Gilad Asharov, Yehuda Lindell
Accepted on: 4th April 2011 07:57
Downloads: 3112
Keywords: 


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$.


Revision #1 to TR11-036 | 17th March 2011 12:28

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





Revision #1
Authors: Gilad Asharov, Yehuda Lindell
Accepted on: 17th March 2011 12:28
Downloads: 3619
Keywords: 


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 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).


Paper:

TR11-036 | 17th March 2011 10:35

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





TR11-036
Authors: Gilad Asharov, Yehuda Lindell
Publication: 17th March 2011 10:45
Downloads: 3360
Keywords: 


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 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).



ISSN 1433-8092 | Imprint