Paper 2009/230

Adaptively Secure Broadcast

Martin Hirt and Vassilis Zikas

Abstract

A broadcast protocol allows a sender to distribute a message through a point-to-point network to a set of parties, such that (i) all parties receive the same message, even if the sender is corrupted, and (ii) this is the sender's message, if he is honest. 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.