Feasibility of Broadcast with Dynamic Committees

A significant number of works have considered the problem of multi-party computation over dynamic committees in synchronous networks, including YOSO MPC [Crypto'21], Fluid MPC [Crypto'21], SCALES MPC [TCC'22] and Layered MPC [Crypto'23]. However, prior works assume that every party has access to an ideal synchronous broadcast channel towards the next committee.

While this assumption is partly justified due to the seminal work of Garay [WDAG'94] stating that deterministic broadcast with dynamic committees is impossible, it is open whether there are randomized solutions.

We answer this question in the affirmative, by providing a complete characterization of broadcast with dynamic committees. We use the formalization introduced in the Layered MPC setting and achieve the following results for layered broadcast: - A statistically secure protocol tolerating $t<n/3$ corruptions with no setup. - A computationally secure protocol tolerating $t<n/2$ corruptions, assuming only a bulletin-board PKI for signatures. - A matching impossibility result showing that broadcast is impossible for $t \geq n/2$ corruptions.

Using our broadcast, we achieve the following polynomial-time results: - YOSO MPC protocols without broadcast (statistical for $t<n/3$ without setup; and computational for $t<n/2$ assuming a plain PKI for signatures). - Assuming plain PKIs for signatures and public-key encryption, a Layered MPC protocol without broadcast for $t<n/2$. - Assuming homomorphic commitments, a Layered MPC without broadcast for $(t+1)^2 \le n$. To achieve this, we introduce a secure-message-transmission protocol for $(t+1)^2 \le n$ which has linear communication in $\ell$ and polynomial communication in $n$ when transmitting a message across $\ell$ layers. This result is of independent interest.