Paper 2025/779 Original: eprint.iacr.org/2025/779 ↗

Towards Reliable Broadcast with Optimal Communication and Round Complexity

Abstract

The reliable broadcast protocol with the best communication complexity for long messages to date is the MiniCast protocol of Locher & Shoup (2024). To reliably broadcast a message m to n parties, MiniCast has communication complexity ~ 1.5|m|n when the size |m| of m is large. However, the round complexity of MiniCast is 4, which is worse than the 3 rounds of the classical protocol of Bracha. We give a new reliable broadcast protocol whose communication complexity is essentially the same as that of MiniCast, but whose round complexity is just 3. For large |m|, the communication complexity of our new protocol is essentially optimal (for 3-round protocols with sufficiently well-balanced communication). Like MiniCast, our new protocol does not rely on any cryptography other than hash functions. We also give two new 2-round protocols that rely on signatures. The communication complexity of the first protocol is also ~ 1.5|m| n, unless the sender provably misbehaves, in which case its communication complexity may degrade to at most ~ 2|m|n. The communication complexity of the second protocol is ~ 1.5|m|n, even in the worst case, but (unlike our other protocols) the communication is unbalanced.