Paper 2026/2923

Early-Stopping Dishonest Majority Broadcast with Linear Rounds and Polynomial Communication

Renas Bacho, Ruhr University Bochum
Kecheng Shi, Helmholtz Center for Information Security, Saarland University
Abstract

Early-stopping Byzantine broadcast protocols adapt their round complexity to the number $f\le t$ of parties that are actually corrupted in an execution, where $t<n$ is the corruption threshold known to the protocol. For every $t<n$, Loss and Nielsen (Eurocrypt 2024) gave a protocol that terminates within $O(\min\{f^2+1,t+1\})$ rounds, using polynomial communication and a plain public key infrastructure (PKI). More recent work attains $O(f+1)$ rounds for every $t<n$ via exponential information gathering, but at the cost of exponential communication. It has therefore remained open whether $O(f+1)$ rounds can be achieved for every $t<n$ with polynomial communication and computation from a plain PKI. We resolve this question with a deterministic Byzantine broadcast protocol that is secure against a strongly adaptive rushing adversary. For every $f\le t<n$, all honest parties output and terminate within $O(f+1)$ rounds, using polynomial communication and computation. This matches the classical early-stopping lower bound of $\min\{f+2,t+1\}$ rounds up to a constant factor. Our basic protocol terminates within $14f+9$ rounds and communicates $O(\kappa n^7)$ bits, where $\kappa$ is the length of a signature. Two optimized variants improve both bounds: the first terminates within $5f+2\lceil\log_2(f+1)\rceil+10$ rounds and communicates $O(\kappa n^5)$ bits, and the second terminates within $5f+2\lfloor\sqrt f\rfloor+11$ rounds and communicates $O(\kappa n^4+n^{9/2})$ bits.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
Byzantine BroadcastEarly StoppingRound Complexity
Contact author(s)
renas bacho @ rub de
kcshi97 @ gmail com
History
2026-11-21: approved
2026-11-17: received
See all versions
Short URL
https://ia.cr/2026/2923
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2026/2923,
      author = {Renas Bacho and Kecheng Shi},
      title = {Early-Stopping Dishonest Majority Broadcast with Linear Rounds and Polynomial Communication},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/2923},
      year = {2026},
      url = {https://eprint.iacr.org/2026/2923}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.