Efficient Simultaneous Broadcast

Abstract

We present an efficient simultaneous broadcast protocol ν-SimCast that allows n players to announce independently chosen values, even if up to t < n players are corrupt. Independence is guaranteed in the partially syn-2 chronous communication model, where communication is structured into rounds, while each round is asynchronous. The ν-SimCast protocol is more efficient than previous constructions. For repeated executions, we reduce the communication and computation complexity by a factor O(n). Combined with a deterministic extractor, ν-SimCast provides a particularly efficient solution for distributed coin-flipping. The protocol does not require any zero-knowledge proofs and is shown to be secure in the standard model under the Decisional Diffie Hellman assumption.