Paper 2026/2923
Early-Stopping Dishonest Majority Broadcast with Linear Rounds and Polynomial Communication
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
-
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}
}