Welcome to the resource topic for 2013/738
Title:
On the Resilience and Uniqueness of CPA for Secure Broadcast
Authors: Chris Litsas, Aris Pagourtzis, Giorgos Panagiotakos, Dimitris Sakavalas
Abstract:We consider the Secure Broadcast problem in incomplete networks. We study the resilience of the Certified Propagation Algorithm (CPA), which is particularly suitable for ad hoc networks. We address the issue of determining the maximum number of corrupted players t^{\mathrm{CPA}}_{\max} that CPA can tolerate under the t-locally bounded adversary model, in which the adversary may corrupt at most t players in each player’s neighborhood. For any graph G and dealer-node D we provide upper and lower bounds on t^{\mathrm{CPA}}_{\max} that can be efficiently computed in terms of a graph theoretic parameter that we introduce in this work. Along the way we obtain an efficient 2-approximation algorithm for t^{\mathrm{CPA}}_{\max}. We further introduce two more graph parameters, one of which matches $t^{\mathrm{CPA}}_{\max}$exactly. Our approach allows to provide an affirmative answer to the open problem of CPA Uniqueness posed by Pelc and Peleg in 2005.
ePrint: https://eprint.iacr.org/2013/738
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 .