TY - CONF
T1 - Round Complexity of Authenticated Broadcast with a Dishonest Majority
T2 - Foundations of Computer Science, 2007. FOCS '07. 48th Annual IEEE Symposium on
Y1 - 2007
A1 - Garay,J. A
A1 - Katz, Jonathan
A1 - Koo,Chiu-Yuen
A1 - Ostrovsky,R.
KW - broadcast
KW - complexity;cryptographic
KW - complexity;deterministic
KW - cryptography;
KW - key
KW - majority;randomized
KW - PKI;authenticated
KW - protocols;broadcasting;computational
KW - protocols;digital
KW - round
KW - signatures;dishonest
KW - signatures;public
AB - Broadcast among n parties in the presence of t ges 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 lt; 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 lt; 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: ldr For t les n/2 + k, we. show a randomized broadcast protocol that runs in expected O(k^{2}) rounds. In particular, we obtain expected constant-round pivtocols for t = n/2 + O(1). ldr 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.
JA - Foundations of Computer Science, 2007. FOCS '07. 48th Annual IEEE Symposium on
M3 - 10.1109/FOCS.2007.44
ER -