Secure Multi-Party Computation without Agreement

It has recently been shown that authenticated Byzantine agreement,in which more than a third of the parties are corrupted, cannot besecurely realized under concurrent or parallel (stateless)composition. This result puts into question any usage ofauthenticated Byzantine agreement in a setting where manyexecutions take place. In particular, this is true for the wholebody of work of secure multi-party protocols in the case that athird or more of the parties are corrupted. This is because theseprotocols strongly rely on the extensive use of a broadcastchannel, which is in turn realized using authenticated Byzantineagreement. We remark that it was accepted folklore that the use ofa broadcast channel (or authenticated Byzantine agreement) isactually essential for achieving meaningful secure multi-partycomputation whenever a third or more of the parties are corrupted.In this paper we show that this folklore is false. We present amild relaxation of the definition of secure computation allowingabort. Our new definition captures all the central security issuesof secure computation, including privacy, correctness andindependence of inputs. However, the novelty of the definition isin decoupling the issue of agreement from these issues. Wethen show that this relaxation suffices for achieving securecomputation in a point-to-point network. That is, we show thatsecure multi-party computation for this definition can be achievedfor any number of corrupted parties and without abroadcast channel (or trusted pre-processing phase as required forrunning authenticated Byzantine agreement). Furthermore, this isachieved by just replacing the broadcast channel in knownprotocols with a very simple and efficient echo-broadcastprotocol. An important corollary of our result is the ability toobtain multi-party protocols that remain secure under composition,without assuming a broadcast channel.