Paper 2013/738

On the Resilience and Uniqueness of CPA for Secure Broadcast

Chris Litsas, Aris Pagourtzis, Giorgos Panagiotakos, and 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.

Note: An earlier version of this paper has appeared as ‘A Graph Parameter that Matchesthe Resilience of the Certified Propagation Algorithm’, by Chris Litsas, Aris Pagourtzis, Dimitris Sakavalas, in Proceedings of ADHOC-NOW 2013.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Major revision. Proceedings of ADHOC-NOW 2013, 12th International Conference, LNCS 7960, pp. 269-280, Springer.
DOI
10.1007/978-3-642-39247-4_23
Keywords
distributed cryptographyad hoc networkssecure broadcastbyzantine generalst-locally bounded adversary model
Contact author(s)
sakaval @ corelab ntua gr
History
2013-11-14: received
Short URL
https://ia.cr/2013/738
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/738,
      author = {Chris Litsas and Aris Pagourtzis and Giorgos Panagiotakos and Dimitris Sakavalas},
      title = {On the Resilience and Uniqueness of CPA for Secure Broadcast},
      howpublished = {Cryptology ePrint Archive, Paper 2013/738},
      year = {2013},
      doi = {10.1007/978-3-642-39247-4_23},
      note = {\url{https://eprint.iacr.org/2013/738}},
      url = {https://eprint.iacr.org/2013/738}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.