Universally composable simultaneous broadcast

Abstract

Simultaneous Broadcast protocols allow different parties to broadcast values in parallel while guaranteeing mutual independence of the broadcast values. The problem of simultaneous broadcast was suggested by Chor et al. (FOCS 1985) who proposed a linear-round solution, and later improved by Chor and Rabin (PODC 1987) and Germaro (IEEE Trans. on Parallel and Distributed Systems 2000). The most efficient solution, in terms of round complexity, is the one due to Germaro, which is in the common random string model. This construction has constant round complexity but is not very practical, as it requires generic zero-knowledge proofs, non-interactive zero-knowledge proofs of knowledge, and commitment schemes. All the mentioned solutions were proven secure under security definitions with weak or no composition guarantees - only sequential composition for the initial construction by Chor et al. In this work, we explore the problem of Simultaneous Broadcast under Universally Composable (UC) security (Canetti 2001). We give a definition of Simultaneous Broadcast in this framework, which is shown to imply all past definitions. We also show this notion can be achieved by a computationally efficient, constant-round construction (building on the verifiable secret sharing scheme of Cramer et al. at Eurocrypt 1999), which is secure under an honest majority. Our results rely on (and benefit from) capturing synchronous communication as a functionality within the UC model, as suggested by Canetti (JACR eprint 2005). Indeed, we show that this approach of modeling synchronous communication can lead to better understanding of where synchronicity is needed, and also simpler constructions and proofs.