Paper 2023/1316

Communication Lower Bounds for Cryptographic Broadcast Protocols

Erica Blum, University of Maryland, College Park
Elette Boyle, Reichman University, NTT Research
Ran Cohen, Reichman University
Chen-Da Liu-Zhang, HSLU, Web3 Foundation

Broadcast protocols enable a set of $n$ parties to agree on the input of a designated sender, even facing attacks by malicious parties. In the honest-majority setting, a fruitful line of work harnessed randomization and cryptography to achieve low-communication broadcast protocols with sub-quadratic total communication and with "balanced" sub-linear communication cost per party. However, comparatively little is known in the dishonest-majority setting. Here, the most communication-efficient constructions are based on the protocol of Dolev and Strong (SICOMP '83), and sub-quadratic broadcast has not been achieved even using randomization and cryptography. On the other hand, the only nontrivial $\omega(n)$ communication lower bounds are restricted to deterministic protocols, or against strong adaptive adversaries that can perform "after the fact" removal of messages. We provide new communication lower bounds in this space, which hold against arbitrary cryptography and setup assumptions, as well as a simple protocol showing near tightness of our first bound. 1) We demonstrate a tradeoff between resiliency and communication for randomized protocols secure against $n-o(n)$ static corruptions. For example, $\Omega(n\cdot {\sf polylog}(n))$ messages are needed when the number of honest parties is $n/{\sf polylog}(n)$; $\Omega(n\sqrt{n})$ messages are needed for $O(\sqrt{n})$ honest parties; and $\Omega(n^2)$ messages are needed for $O(1)$ honest parties. Complementarily, we demonstrate broadcast with $O(n\cdot{\sf polylog}(n))$ total communication facing any constant fraction of static corruptions. 2) Our second bound considers $n/2 + k$ corruptions and a weakly adaptive adversary that cannot remove messages "after the fact." We show that any broadcast protocol within this setting can be attacked to force an arbitrary party to send messages to $k$ other parties. Our bound rules out, for example, broadcast facing $51\%$ corruptions, in which all non-sender parties have sublinear communication locality.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Major revision. DISC 2023
broadcastcommunication complexitylower boundsdishonest majority
Contact author(s)
erblum @ umd edu
eboyle @ alum mit edu
cohenran @ runi ac il
chen-da liuzhang @ hslu ch
2023-09-08: approved
2023-09-04: received
See all versions
Short URL
Creative Commons Attribution


      author = {Erica Blum and Elette Boyle and Ran Cohen and Chen-Da Liu-Zhang},
      title = {Communication Lower Bounds for Cryptographic Broadcast Protocols},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1316},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.