Rumors MPC: GOD for Dynamic Committees, Low Communication via Constant-Round Chat

Constructing MPC with ephemeral committees has gained a lot of attention since the seminal works on Fluid MPC and YOSO MPC (CRYPTO'21). However, most protocols in this setting focus on the extreme case of ephemeral committees who can only act for one round (i.e., the maximally fluid case). The Layered MPC model (CRYPTO'23) recasts this notion as a protocol execution against an adaptive rushing adversary over a layered interaction graph, where each committee sits on a layer and can only communicate with the immediate next committee. Although protocols with abort allow for linear communication complexity (CRYPTO'23, CiC'24), Perfect Layered MPC with guaranteed output delivery (GOD) and its statistically secure counterpart (TCC'24) suffer from {\$}{\$}O(n^9){\$}{\$}O(n9)and {\$}{\$}O({\backslash}kappa n^{\{}18{\}}){\$}{\$}O($\kappa$n18)communication complexity for n parties per committee, respectively. In this work, we investigate communication complexity improvements gained in a relaxed Multi-Layered MPC model that allows for limited interaction among the parties in each committee, while still allowing only one round to communicate with the immediate next committee. We construct Rumors MPC protocols, where the interaction among each committee's members is constant-round. Our protocols achieve GOD and optimal corruption threshold in the perfect (resp. statistical) security setting with committees acting for {\$}{\$}{\backslash}delta =5{\$}{\$}$\delta$=5(resp. {\$}{\$}{\backslash}delta =13{\$}{\$}$\delta$=13) rounds and {\$}{\$}O(n^6){\$}{\$}O(n6)(resp. {\$}{\$}O({\backslash}kappa n^8){\$}{\$}O($\kappa$n8)) communication.