Universally Composable Simultaneous Broadcast against a Dishonest Majority

Myrto Arapinis, Thomas Zacharias, Nikolaos Lamprou, Liam Medley, Ábel Kocsis

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

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.
Original languageEnglish
Title of host publicationPODC '23: Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing
Place of PublicationNew York
Number of pages11
ISBN (Electronic)9798400701214
Publication statusPublished - 16 Jun 2023
EventThe 42nd ACM Symposium on Principles of Distributed Computing - Orlando, United States
Duration: 19 Jun 202323 Jun 2023
Conference number: 42


ConferenceThe 42nd ACM Symposium on Principles of Distributed Computing
Abbreviated titleACM PODC 2023
Country/TerritoryUnited States
Internet address

Keywords / Materials (for Non-textual outputs)

  • secure broadcast
  • universal composability
  • Time-lock encryption


Dive into the research topics of 'Universally Composable Simultaneous Broadcast against a Dishonest Majority'. Together they form a unique fingerprint.

Cite this