Paper 2026/2785

Optimal Early-Stopping Broadcast via Exponential Information Gathering

Abstract

Early-stopping broadcast protocols guarantee termination based on the actual number of malicious parties, $f \leq t$, encountered during execution, rather than the worst-case scenario of $t < n$ corruptions. The seminal work of Dolev, Reischuk, and Strong~[JACM'90] established that $\min\{f+2,\, t+1\}$ rounds are necessary. The influential works of Berman, Garay, and Perry~[WDAG'92] and Abraham and Dolev~[STOC'15] introduced the first protocols achieving this optimal bound in the $t < n/3$ (unconditional, no setup) regime, while Perry and Toueg~[Tech.\ Report'84] gave the first protocol for the $t < n/2$ setting (with plain PKI), achieving $2 \cdot \min\{f+2,\, t+1\}$ rounds. Despite this early progress, closing the gap to the optimal bound in the computational setting has remained a longstanding open problem, and only recently has progress been made. The best known result in the $t < n/2$ regime is due to Elsheimy, Loss, and Papamanthou~[Eprint'25], achieving $f + O(\sqrt{f})$ rounds. In the dishonest-majority regime, the best known result is due to Deligios, Klasovita, and Liu-Zhang~[Eurocrypt'25], who obtain the first asymptotically optimal protocol, with $O(f)$ round complexity, for $t = (1-\epsilon)n$, where $\epsilon > 0$ is a constant. In this work, we advance the state of the art in two directions. First, in the $t < n/2$ setting with plain PKI, we present a broadcast protocol in which all parties output within optimal $\min\{f+2,\, t+1\}$ rounds. Second, we complete the picture by introducing the first protocol that is optimally resilient ($t < n$) and asymptotically matches the lower bound for any number of corruptions $t < n$. By leveraging exponential information gathering (EIG) graphs, our constructions establish that these round bounds are achievable, providing the first feasibility result for optimal-round protocols, albeit at the cost of exponential communication complexity.