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.
Category / Keywords: cryptographic protocols / Broadcast, Byzantine Original Publication (in the same form): IACR-TCC-20 Date: received 7 Oct 2020 Contact author: junwan at mit edu,hanshen@mit edu,devadas@csail mit edu,runting@gmail com Available format(s): PDF | BibTeX Citation Version: 20201009:113217 (All versions of this report) Short URL: ia.cr/2020/1236