Rafail Ostrovsky - Publications

Round Complexity of Authenticated Broadcast with a Dishonest Majority.

Juan A. Garay, Jonathan Katz, Chiu-Yuen Koo, Rafail Ostrovsky


Broadcast among n parties in the presence of t >= n/3 malicious parties is possible only with some additional setup. The most common setup considered is the existence of a PKI and secure digital signatures, where so-called authenticated broadcast is achievable for any t < n. It is known that t+1 rounds are necessary and sufficient for deterministic protocols achieving authenticated broadcast. Recently, however, randomized protocols running in expected constant rounds have been shown for the case of t < n/2. It has remained open whether randomization can improve the round complexity when an honest majority is not present. We address this question and show upper and lower bounds on how much randomization can help:

comment: FOCS 2007: 658-668

Fetch PostScript file of the paper     Fetch PDF file of the paper

Back to Publications List