Welcome to the resource topic for 2009/410
Title:
Authenticated Broadcast with a Partially Compromised Public-Key Infrastructure
Authors: S. Dov Gordon, Jonathan Katz, Ranjit Kumaresan, Arkady Yerukhimovich
Abstract: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.
ePrint: https://eprint.iacr.org/2009/410
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .