It is typically assumed in these results that parties are connected pairwise by authenticated, private channels, and that in addition they have access to a “broadcast” channel. Broadcast allows one party to send a consistent message to all other parties, guaranteeing consistency even if the broadcaster is corrupted. Because broadcast cannot be simulated on the point-to-point network when more than a third of the parties are corrupt, it is impossible to construct general MPC protocols in this setting without using a broadcast channel (or some equivalent addition to the model).
A great deal of research has focused on increasing the efficiency of MPC, primarily in terms of round complexity and communication complexity. In this work we propose a refinement of the round complexity which we term broadcast complexity. We view the broadcast channel as an expensive resource and seek to minimize the number of rounds in which it is invoked.
1. We construct an MPC protocol which uses the broadcast channel only three times in a preprocessing phase, after which it is never required again. Ours is the first unconditionally secure MPC protocol for $t < n/2$ to achieve such a low number of broadcast rounds. In contrast, combining the best previous techniques yields a protocol with twenty-four broadcast rounds.
2. In the negative direction, we show a lower bound of two broadcast rounds for the specific functionality of Weak Secret Sharing (a.k.a. Distributed Commitment), also a very natural functionality and central building block of many MPC protocols.
The broadcast-efficient MPC protocol relies on new constructions of Pseudosignatures and Verifiable Secret Sharing, both of which might be of independent interest.Category / Keywords: cryptographic protocols / broadcast, multiparty computation, pseudosignatures, verifiable secret sharing Date: received 8 Mar 2012, last revised 1 Sep 2012 Contact author: cgivens at math ucla edu Available formats: PDF | BibTeX Citation Version: 20120901:195656 (All versions of this report) Discussion forum: Show discussion | Start new discussion