Rafail Ostrovsky - Publications

Round Complexity of Authenticated Broadcast with a Dishonest Majority.

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

Abstract:

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:

• For t =< n/2+k, we show a randomized broadcast protocol that runs in expected O(k^2) rounds. In particular, we obtain expected constant-round protocols for t = n/2 + O(1).
• On the negative side, we show that even randomized protocols require \Omega(2n/(n-t)) rounds. This in particular rules out expected constant-round protocols when the fraction of honest parties is sub-constant.

comment: FOCS 2007: 658-668

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