Paper 2020/1236

Round-Efficient Byzantine Broadcast under Strongly Adaptive and Majority Corruptions

Jun Wan, Hanshen Xiao, Srinivas Devadas, and Elaine Shi


The round complexity of Byzantine Broadcast (BB) has been a central question in distributed systems and cryptography. In the honest majority setting, expected constant round protocols have been known for decades even in the presence of a strongly adaptive adversary. In the corrupt majority setting, however, no protocol with sublinear round complexity is known, even when the adversary is allowed to {\it strongly adaptively} corrupt only 51\% of the players, and even under reasonable setup or cryptographic assumptions. Recall that a strongly adaptive adversary can examine what original message an honest player would have wanted to send in some round, adaptively corrupt the player in the same round and make it send a completely different message instead. In this paper, we are the first to construct a BB protocol with sublinear round complexity in the corrupt majority setting. Specifically, assuming the existence of time-lock puzzles with suitable hardness parameters and that the decisional linear assumption holds in suitable bilinear groups}, we show how to achieve BB in $(\frac{n}{n-f})^2 \cdot \poly\log \lambda$ rounds with $1-\negl(\lambda)$ probability, where $n$ denotes the total number of players, $f$ denotes the maximum number of corrupt players, and $\lambda$ is the security parameter. Our protocol completes in polylogarithmically many rounds even when 99\% of the players can be corrupt.

Available format(s)
Cryptographic protocols
Publication info
Published by the IACR in TCC 2020
Contact author(s)
junwan @ mit edu
hanshen @ mit edu
devadas @ csail mit edu
runting @ gmail com
2020-10-09: received
Short URL
Creative Commons Attribution


      author = {Jun Wan and Hanshen Xiao and Srinivas Devadas and Elaine Shi},
      title = {Round-Efficient Byzantine Broadcast under Strongly Adaptive and Majority Corruptions},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1236},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.