Consider a network of $n$ parties, where an adversary has compromised the secret keys of up to $t_c$ honest parties and, in addition, fully controls the behavior of up to $t_a$ other parties. We show that for any fixed $t_c > 0$ and any fixed $t_a$, there exists an efficient protocol for broadcast if and only if $2t_a + \min(t_a, t_c) < n$. (When $t_c = 0$, standard results imply feasibility for all $t_a<n$.) We also show that if $t_c, t_a$ are not fixed, but are only guaranteed to satisfy the above bound, then broadcast is impossible to achieve except for a few specific values of $n$; for these ``exceptional'' values of $n$, we demonstrate broadcast protocols. Taken together, our results give a complete characterization of this problem.
Category / Keywords: cryptographic protocols / Date: received 24 Aug 2009, last revised 2 Oct 2012 Contact author: gordon at cs umd edu Available formats: PDF | BibTeX Citation Note: This is the full version of the paper, and corrects a flaw in an earlier version. Version: 20121003:025115 (All versions of this report) Discussion forum: Show discussion | Start new discussion