Paper 2009/410

Authenticated Broadcast with a Partially Compromised Public-Key Infrastructure

S. Dov Gordon, Jonathan Katz, Ranjit Kumaresan, and Arkady Yerukhimovich


Given a public-key infrastructure (PKI) and digital signatures, it is possible to construct broadcast protocols tolerating any number of corrupted parties. Existing protocols, however, do not distinguish between corrupted parties who do not follow the protocol, and honest parties whose secret (signing) keys have been compromised but continue to behave honestly. We explore conditions under which it is possible to construct broadcast protocols that still provide the usual guarantees (i.e., validity/agreement) to the latter. 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.

Note: This is the full version of the paper, and corrects a flaw in an earlier version.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
gordon @ cs umd edu
2012-10-03: revised
2009-09-01: received
See all versions
Short URL
Creative Commons Attribution


      author = {S.  Dov Gordon and Jonathan Katz and Ranjit Kumaresan and Arkady Yerukhimovich},
      title = {Authenticated Broadcast with a Partially Compromised Public-Key Infrastructure},
      howpublished = {Cryptology ePrint Archive, Paper 2009/410},
      year = {2009},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.