Universally Composable Simultaneous Broadcast against a Dishonest Majority

Simultaneous broadcast (SBC) protocols, introduced in [Chor et al., FOCS 1985], constitute a special class of broadcast channels which, besides consistency, guarantee that all senders broadcast their messages independently of the messages broadcast by other parties. SBC has proved extremely useful in the design of various distributed computing constructions (e.g., multiparty computation, coin flipping, electronic voting, fair bidding). As with any communication channel, it is crucial that SBC security is composable, i.e., it is preserved under concurrent protocol executions. The work of [Hevia, SCN 2006] proposes a formal treatment of SBC in the state-of-the-art Universal Composability (UC) framework [Canetti, FOCS 2001] and a construction that is secure assuming an honest majority.

In this work, we provide a comprehensive revision of SBC in the UC setting and improve the results of [Hevia, SCN 2006]. In particular, we present a new SBC functionality that captures \emph{both simultaneity and liveness} by considering a broadcast period such that (i) within this period all messages are broadcast independently and (ii) after the period ends, the session is terminated without requiring full participation of all parties. Next, we employ time-lock encryption (TLE) over a standard broadcast channel to devise an SBC protocol that realizes our functionality against any adaptive adversary corrupting up to all-but-one parties. In our study, we capture synchronicity via a global clock [Katz et al., TCC 2013], thus lifting the restrictions of the original synchronous communication setting used in [Hevia, SCN 2006]. As a building block of independent interest, we prove the first TLE protocol that is \emph{adaptively} secure in the UC setting, strengthening the main result of [Arapinis et al., ASIACRYPT 2021].

Finally, we formally exhibit the power of our SBC construction in the design of UC-secure applications by presenting two interesting use cases: (i) distributed generation of uniform random strings, and (ii) decentralized electronic voting systems, without the presence of a special trusted party.