Welcome to the resource topic for 2024/974
Title:
Towards Optimal Parallel Broadcast under a Dishonest Majority
Authors: Daniel Collins, Sisi Duan, Julian Loss, Charalampos Papamanthou, Giorgos Tsimos, Haochen Wang
Abstract:The parallel broadcast (PBC) problem generalises the classic Byzantine broadcast problem to the setting where all n nodes broadcast a message and deliver O(n) messages. PBC arises naturally in many settings including multi-party computation. Recently, Tsimos, Loss, and Papamanthou (CRYPTO 2022) showed PBC protocols with improved communication, against an adaptive adversary who can corrupt all but a constant fraction \epsilon of nodes (i.e., f < (1 - \epsilon)n). However, their study is limited to single-bit messages, and their protocols have large polynomial overhead in the security parameter \kappa: their TrustedPBC protocol achieves \tilde{O}(n^2 \kappa^4) communication and O(\kappa\log n) rounds. Since these factors of \kappa are in practice often close (or at least polynomially related) to n, they add a significant overhead. In this work, we propose three parallel broadcast protocols for L-bit messages, for any size L, that significantly improve the communication efficiency of the state-of-the-art.
We first propose a new extension protocol that uses a \kappa-bit PBC as a black box and achieves i) communication complexity of O(L n^2 + \mathcal{P}(\kappa)), where \mathcal{P}(\kappa) is the communication complexity of the \kappa-bit PBC, and ii) round complexity same as the \kappa-bit PBC. By comparison, the state-of-the-art extension protocol for regular broadcast (Nayak et al., DISC 2020) incurs O(n) additional rounds of communication. Next, we propose a protocol that is secure against a static adversary, for \kappa-bit messages with O(n^2 \kappa^{1+K} + n\kappa^3 + \kappa^4) communication and O(\kappa) round complexity, where K is an arbitrarily small constant such that 0<1. Finally, we propose an adaptively-secure protocol for \kappa-bit messages with \tilde{O}(n^2\kappa^2 + n\kappa^3) communication overhead and O(\kappa \log{n}) round complexity by modifying and improving the next-best protocol TrustedPBC in several key ways. Notably, our latter two protocols are \tilde{O}(\kappa^{2 - K}) and O(\kappa^2) times more communication-efficient, respectively, than the state-of-the-art protocols while achieving the same round complexity.
ePrint: https://eprint.iacr.org/2024/974
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 .