skip to main content
10.1145/1146381.1146421acmconferencesArticle/Chapter ViewAbstractPublication PagespodcConference Proceedingsconference-collections
Article

Possibility and complexity of probabilistic reliable communication in directed networks

Published: 23 July 2006 Publication History

Abstract

We provide a complete characterization of directed networks in which probabilistic reliable communication is possible. We also outline a round optimal protocol for the same.

References

[1]
Y. Desmedt and Y. Wang. Perfectly Secure Message Transmission Revisited. In Proceedings of EUROCRYPT '02, pages 502--517, 2002.
[2]
W. Diffie and M. E. Hellman. New Directions in Cryptography. IEEE Transactions on Information Theory, IT-22:644--654, November 1976.
[3]
D. Dolev. The Byzantine Generals Strike Again. Journal of Algorithms, 3(1):14--30,1982.
[4]
D. Dolev, C. Dwork, O. Waarts, and M. Yung. Perfectly Secure Message Transmission. JACM, 40(1):17--47, January 1993.
[5]
M. Franklin and R. N. Wright. Secure Communication in Minimal Connectivity Models. In Proceedings of EUROCRYPT, pages 346--360, 1998.
[6]
M. Franklin and M. Yung. Secure Hypergraphs: Privacy from Partial Broadcast. In Proceedings of 27th STOC, pages 36--44. ACM Press, 1995.
[7]
J. A. Garay and K. J. Perry. A Continuum of Failure Models for Distributed Computing. In Proceedings of the 6th WDAG, pages 153--165, 1992.
[8]
M. Hirt and U. Maurer. Complete Characterization of Adversaries Tolerable in Secure Multi-party Computation. In Proceedings of the 16th PODC, pages 25--34. ACM Press, 1997.
[9]
M.V.N.A. Kumar, P. R. Goundan, K. Srinathan, and C. Pandu Rangan. On perfectly secure communication over arbitrary networks. In Proceedings of the 21st PODC, pages 193--202. ACM Press, 2002.
[10]
R. Ostrovsky and M. Yung. How to Withstand Mobile Virus Attacks. In Proceedings of the 10th PODC, pages 51--61. ACM Press, 1991.
[11]
T. Rabin and M. Ben-Or. Verifiable Secret Sharing and Multiparty Protocols with Honest Majority. In Proceedings of the 21st STOC, pages 73--85, 1989.
[12]
H. Sayeed and H. Abu-Amara. Perfectly Secure Message Transmission in Asynchronous Networks. In Seventh IEEE Symposium on Parallel and Distributed Processing, 1995.
[13]
H. Sayeed and H. Abu-Amara. Efficient Perfectly Secure Message Transmission in Synchronous Networks. Information and Computation, 126(1):53--61, 1996.

Cited By

View all
  • (2018)On the Price of Proactivizing Round-Optimal Perfectly Secret Message TransmissionIEEE Transactions on Information Theory10.1109/TIT.2017.277609964:2(1404-1422)Online publication date: 1-Feb-2018
  • (2016)On perfectly secret message transmission in digraphs tolerating dual failuresProceedings of the 17th International Conference on Distributed Computing and Networking10.1145/2833312.2833327(1-10)Online publication date: 4-Jan-2016
  • (2015)Round-Optimal Perfectly Secret Message Transmission with Linear Communication ComplexityInformation Theoretic Security10.1007/978-3-319-17470-9_3(33-50)Online publication date: 2015
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
PODC '06: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing
July 2006
230 pages
ISBN:1595933840
DOI:10.1145/1146381
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 July 2006

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. directed networks
  2. reliable communication

Qualifiers

  • Article

Conference

PODC06

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)4
  • Downloads (Last 6 weeks)0
Reflects downloads up to 14 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2018)On the Price of Proactivizing Round-Optimal Perfectly Secret Message TransmissionIEEE Transactions on Information Theory10.1109/TIT.2017.277609964:2(1404-1422)Online publication date: 1-Feb-2018
  • (2016)On perfectly secret message transmission in digraphs tolerating dual failuresProceedings of the 17th International Conference on Distributed Computing and Networking10.1145/2833312.2833327(1-10)Online publication date: 4-Jan-2016
  • (2015)Round-Optimal Perfectly Secret Message Transmission with Linear Communication ComplexityInformation Theoretic Security10.1007/978-3-319-17470-9_3(33-50)Online publication date: 2015
  • (2013)Interplay between (im)perfectness, synchrony and connectivityTheoretical Computer Science10.1016/j.tcs.2012.12.004496(2-16)Online publication date: 1-Jul-2013
  • (2012)Interplay between (im)perfectness, synchrony and connectivityProceedings of the 13th international conference on Distributed Computing and Networking10.1007/978-3-642-25959-3_10(138-152)Online publication date: 3-Jan-2012
  • (2011)Minimal connectivity for unconditionally secure message transmission in synchronous directed networksProceedings of the 5th international conference on Information theoretic security10.5555/2009144.2009148(32-51)Online publication date: 21-May-2011
  • (2011)Secure message transmission in asynchronous directed graphsProceedings of the 12th international conference on Cryptology in India10.1007/978-3-642-25578-6_26(359-378)Online publication date: 11-Dec-2011
  • (2011)Minimal Connectivity for Unconditionally Secure Message Transmission in Synchronous Directed NetworksInformation Theoretic Security10.1007/978-3-642-20728-0_4(32-51)Online publication date: 2011
  • (2010)On composability of reliable unicast and broadcastProceedings of the 11th international conference on Distributed computing and networking10.5555/2018057.2018070(54-66)Online publication date: 3-Jan-2010
  • (2010)Brief announcementProceedings of the 24th international conference on Distributed computing10.5555/1888781.1888808(201-203)Online publication date: 13-Sep-2010
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media