Paper 2002/040

Secure Computation Without Agreement

Shafi Goldwasser and Yehuda Lindell


It has recently been shown that authenticated Byzantine agreement, in which more than a third of the parties are corrupted, cannot be securely realized under concurrent or parallel (stateless) composition. This result puts into question any usage of authenticated Byzantine agreement in a setting where many executions take place. In particular, this is true for the whole body of work of secure multi-party protocols in the case that a third or more of the parties are corrupted. This is because these protocols strongly rely on the extensive use of a broadcast channel, which is in turn realized using authenticated Byzantine agreement. We remark that it was accepted folklore that the use of a broadcast channel (or authenticated Byzantine agreement) is actually essential for achieving meaningful secure multi-party computation whenever a third or more of the parties are corrupted. In this paper we show that this folklore is false. We present a mild relaxation of the definition of secure computation allowing abort. Our new definition captures all the central security issues of secure computation, including privacy, correctness and independence of inputs. However, the novelty of the definition is in {\em decoupling} the issue of agreement from these issues. We then show that this relaxation suffices for achieving secure computation in a point-to-point network. That is, we show that secure multi-party computation for this definition can be achieved for {\em any} number of corrupted parties and {\em without} a broadcast channel (or trusted preprocessing phase as required for running authenticated Byzantine agreement). Furthermore, this is achieved by just replacing the broadcast channel in known protocols with a very simple and efficient echo-broadcast protocol. An important corollary of our result is the ability to obtain multi-party protocols that remain secure under composition, without assuming a broadcast channel.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. An extended abstract appeared in the 16th DISC, 2002. This is the full version.
secure multiparty computationauthenticated Byzantine agreementprotocol composition
Contact author(s)
lindell @ wisdom weizmann ac il
2003-12-31: last of 6 revisions
2002-03-30: received
See all versions
Short URL
Creative Commons Attribution


      author = {Shafi Goldwasser and Yehuda Lindell},
      title = {Secure Computation Without Agreement},
      howpublished = {Cryptology ePrint Archive, Paper 2002/040},
      year = {2002},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.