Broadcast protocols satisfying these properties are known to exist if and only if $t<n/3$, where $n$ denotes the total number of parties, and $t$ denotes the maximal number of corruptions. When a setup allowing signatures is available to the parties, then such protocols exist even for $t<n$.
Broadcast is the probably most fundamental primitive in distributed cryptography, and is used in almost any cryptographic (multi-party) protocol. However, a broadcast protocol ``only'' satisfying the above properties might be insecure when being used in the context of another protocol. In order to be safely usable within other protocols, a broadcast protocol must satisfy a simulation-based security notion, which is secure under composition.
In this work, we show that most broadcast protocols in the literature do not satisfy a (natural) simulation-based security notion. We do not know of any broadcast protocol which could be securely invoked in a multi-party computation protocol in the secure-channels model. The problem is that existing protocols for broadcast do not preserve the secrecy of the message while being broadcasted, and in particular allow the adversary to corrupt the sender (and change the message), depending on the message being broadcasted. For example, when every party should broadcast a random bit, the adversary could corrupt those parties that want to broadcast 0, and make them broadcast 1.
More concretely, we show that simulatable broadcast in a model with secure channels is possible if and only if $t<n/3$, respectively $t \le n/2$ when a signature setup is available. The positive results are proven by constructing secure broadcast protocols.Category / Keywords: cryptographic protocols / broadcast, adaptive adversary, composable security Date: received 22 May 2009 Contact author: vzikas at inf ethz ch Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Version: 20090530:043804 (All versions of this report) Short URL: ia.cr/2009/230 Discussion forum: Show discussion | Start new discussion