**
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

Back to Publications List |