Round Complexity of Authenticated Broadcast with a Dishonest Majority
Conference Paper
-
- Overview
-
- Identity
-
- Additional Document Info
-
- View All
-
Overview
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 oft < 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/lower bounds on how much randomization can help: For t ≤ n/2 + k, we show a randomized broadcast protocol that runs in expected O(k2) 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 Ω(2n/(n-t)) rounds. This inparticular rules out expected constant-round protocols when the fraction of honest parties is sub-constant. © 2007 IEEE.
name of conference
-
48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07)
published proceedings
-
48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07)
author list (cited authors)
-
Garay, J. A., Katz, J., Koo, C., & Ostrovsky, R
complete list of authors
-
Garay, Juan A||Katz, Jonathan||Koo, Chiu-Yuen||Ostrovsky, Rafail
publication date
publisher
published in
Identity
Digital Object Identifier (DOI)
International Standard Book Number (ISBN) 10
International Standard Book Number (ISBN) 13
Additional Document Info