You are looking at a specific version 20120901:195656 of this paper. See the latest version.

Paper 2012/130

Broadcast-Efficient Secure Multiparty Computation

Juan Garay and Clint Givens and Rafail Ostrovsky

Abstract

Secure multiparty computation (MPC) is perhaps the most popular paradigm in the area of cryptographic protocols. It allows several mutually untrustworthy parties to jointly compute a function of their private inputs, without revealing to each other information about those inputs. In the case of unconditional (information-theoretic) security, protocols are known which tolerate a dishonest minority of players, who may coordinate their attack and deviate arbitrarily from the protocol specification. 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
Keywords
broadcastmultiparty computationpseudosignaturesverifiable secret sharing
Contact author(s)
cgivens @ math ucla edu
History
2013-09-16: last of 2 revisions
2012-03-13: received
See all versions
Short URL
https://ia.cr/2012/130
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.