Welcome to the resource topic for 2025/931
Title:
Multivalued Broadcast with Optimal Length
Authors: Gabriel Dettling, Martin Hirt, Chen-Da Liu-Zhang
Abstract:A multi-valued broadcast protocol allows a sender P_s to broadcast an \ell-bit message m to n recipients.
For all relevant models, multi-valued broadcast protocols with asymptotically optimal communication complexity \mathcal{O}(\ell n)+\mathrm{Poly}(n) have been published.
Despite their very low communication complexity, these protocols perform poorly in modern networks.
Even if the network allows all n parties to send messages at the same time, the execution time of the protocols is proportional to \ell n (instead of \ell).
Even if the network allows to use all bilateral channels at the same time, the execution time is still proportional to \ell (instead of \ell/n).
We ask the natural question whether multi-valued broadcast protocols exist which take time proportional to \ell if parties can simultaneously send messages, and even take time proportional to \ell/n if the bilateral channels can be used simultaneously. We provide a complete characterization of multi-valued broadcast with a two-fold answer:
On the negative side, we prove that for t< (1-\epsilon)n (for any fixed \epsilon), multi-valued broadcast in time proportional to \ell (when parties can send messages simultaneously), respectively proportional to \ell/n (if bilateral channels can be used simultaneously) is possible. We provide such protocols both with cryptographic security as well as with statistical security.
ePrint: https://eprint.iacr.org/2025/931
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .