Paper 2026/2883
Early-Stopping Dishonest Majority Broadcast with Optimal Round Complexity
Abstract
Early-stopping broadcast protocols guarantee termination as a function of the number $f\le t$ of parties actually corrupted in an execution, rather than of the worst-case bound $t<n$. Loss and Nielsen (Eurocrypt 2024) gave such a protocol for every $t<n$, terminating within $O(\min\{f^2+1,t+1\})$ rounds, with polynomial communication and from a plain public-key infrastructure (PKI). In the other direction, Choi, Choi, Liu, and Zikas (ePrint 2026/1878) recently proved a stopping lower bound which implies that $f+3$ rounds are necessary whenever $n+f<2\min\{t,n-2\}$, a condition that covers a broad part of the dishonest-majority regime. It has remained open whether this bound can be attained, even at the cost of exponential communication. In this work, we present a deterministic early-stopping broadcast protocol in which every honest party outputs and terminates within $\min\{f+3,t+1\}$ rounds for every $t<n$. The protocol is built from exponential information gathering (EIG) graphs and incurs exponential communication. It works in the plain PKI model with idealized signatures and is secure against a strongly adaptive adversary. Its stopping round complexity is therefore optimal throughout the stated range of the lower bound.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- Byzantine BroadcastRound ComplexityEarly Stopping
- Contact author(s)
-
renas bacho @ rub de
kcshi97 @ gmail com - History
- 2026-11-16: approved
- 2026-11-12: received
- See all versions
- Short URL
- https://ia.cr/2026/2883
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/2883,
author = {Renas Bacho and Kecheng Shi},
title = {Early-Stopping Dishonest Majority Broadcast with Optimal Round Complexity},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/2883},
year = {2026},
url = {https://eprint.iacr.org/2026/2883}
}