Paper 2026/2883

Early-Stopping Dishonest Majority Broadcast with Optimal Round Complexity

Renas Bacho, Ruhr University Bochum
Kecheng Shi, CISPA Helmholtz Center for Information Security, Saarland University
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.