Perfectly secure message transmission

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Perfectly secure message transmission

Full text

Pdf (2.42 MB)

Source

Journal of the ACM (JACM) archive
Volume 40 , Issue 1 (January 1993) table of contents

Pages: 17 - 47

Year of Publication: 1993

ISSN:0004-5411

Authors

Danny Dolev	IBM Almaden Research Center, San Jose, CA
Cynthia Dwork	IBM Almaden Research Center, San Jose, CA
Orli Waarts	Stanford Univ., Stanford, CA
Moti Yung	IBM T. J. Watson Research Center, Yorktown Heights, NY

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 28, Downloads (12 Months): 104, Citation Count: 26

Additional Information:

abstract references cited by index terms review collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/138027.138036 What is a DOI?

ABSTRACT

This paper studies the problem of perfectly secure communication in general network in which processors and communication lines may be faulty. Lower bounds are obtained on the connectivity required for successful secure communication. Efficient algorithms are obtained that operate with this connectivity and rely on no complexity-theoretic assumptions. These are the first algorithms for secure communication in a general network to simultaneously achieve the three goals of perfect secrecy, perfect resiliency, and worst-case time linear in the diameter of the network.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	11	Cynthia Dwork , David Peleg , Eli Upfal, Fault tolerance in networks of bounded degree, SIAM Journal on Computing, v.17 n.5, p.975-988, October 1988 [doi>10.1137/0217061]
	12	~FELDMAN, P. Optimal algorithms for Byzantine agreement. Ph.D. dissertation, Department ~of mathematics, MIT, Cambridge, Mass., 1988.
	13	Paul Feldman , Silvio Micali, Optimal algorithms for Byzantine agreement, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.148-161, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62225]
	14	Michael J. Fischer , Nancy A. Lynch , Michael Merritt, Easy impossibility proofs for distributed consensus problems, Distributed Computing, v.1 n.1, p.26-39, Jan. 1986 [doi>10.1007/BF01843568]
	15	~GALIL, Z., HABER, S., AND YUNG, M. Primitives for designing multiparty protocols from ~specifications. Manuscript, 1989.
	16	O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
	17	~KARL1N, A., AND YAO, h. Probabilistic lower bounds for Byzantine agreement. Manuscript.
	18	R. J. McEliece , D. V. Sarwate, On sharing secrets and Reed-Solomon codes, Communications of the ACM, v.24 n.9, p.583-584, Sept. 1981 [doi>10.1145/358746.358762]
	19	Daniel Lehmann , Michael O. Rabin, On the advantages of free choice: a symmetric and fully distributed solution to the dining philosophers problem, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.133-138, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567547]
	20	T. Rabin , M. Ben-Or, Verifiable secret sharing and multiparty protocols with honest majority, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.73-85, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73014]
	21	Adi Shamir, How to share a secret, Communications of the ACM, v.22 n.11, p.612-613, Nov. 1979 [doi>10.1145/359168.359176]
	22	~YAO, A. How to generate and exchange secrets. In Proceedings of the 29th Sympostum on ~Foundations of Computer Science. IEEE, New York, 1986, pp. 162-167.

CITED BY 26

	Mattias Fitzi , Ueli Maurer, From partial consistency to global broadcast, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.494-503, May 21-23, 2000, Portland, Oregon, United States
	Matthew Franklin , Zvi Galil , Moti Yung, Eavesdropping games: a graph-theoretic approach to privacy in distributed systems, Journal of the ACM (JACM), v.47 n.2, p.225-243, March 2000
	Amos Beimel , Lior Malka, Efficient reliable communication over partially authenticated networks, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.233-242, July 13-16, 2003, Boston, Massachusetts
	M V N Ashwin Kumar , Pranava R. Goundan , K Srinathan , C. Pandu Rangan, On perfectly secure communication over arbitrary networks, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California
	Carlisle Adams , Mike Burmester , Yvo Desmedt , Mike Reiter , Philip Zimmermann, Which PKI (public key infrastructure) is the right one? (panel session), Proceedings of the 7th ACM conference on Computer and communications security, p.98-101, November 01-04, 2000, Athens, Greece
	Luis von Ahn , Andrew Bortz , Nicholas J. Hopper, k-anonymous message transmission, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA
	K. Srinathan , V. Vinod , C. Pandu Rangan, Brief announcement: efficient perfectly secure communication over synchronous networks, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.252-252, July 13-16, 2003, Boston, Massachusetts
	Oded Goldreich, Cryptography and cryptographic protocols, Distributed Computing, v.16 n.2-3, p.177-199, September 2003
	Yongge Wang, Robust key establishment in sensor networks, ACM SIGMOD Record, v.33 n.1, March 2004
	Lakshminarayanan Subramanian , Randy H. Katz , Volker Roth , Scott Shenker , Ion Stoica, Reliable broadcast in unknown fixed-identity networks, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA
	James W. Gray, III , Paul F. Syverson, A logical approach to multilevel security of probabilistic systems, Distributed Computing, v.11 n.2, p.73-90, April 1998
	Amos Beimel , Lior Malka, Efficient reliable communication over partially authenticated networks, Distributed Computing, v.18 n.1, p.1-19, July 2005
	Arvind Narayanan , K. Srinathan , C. Pandu Rangan, Perfectly reliable message transmission, Information Processing Letters, v.100 n.1, p.23-28, 16 October 2006
	Oded Goldreich, Foundations of cryptography: a primer, Foundations and Trends® in Theoretical Computer Science, v.1 n.1, p.1-116, April 2005
	Kannan Srinathan , C. Pandu Rangan, Possibility and complexity of probabilistic reliable communication in directed networks, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA
	Bhavani Shankar , Prasant Gopal , Kannan Srinathan , C. Pandu Rangan, Unconditionally reliable message transmission in directed networks, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.1048-1055, January 20-22, 2008, San Francisco, California
	Sharon Goldberg , David Xiao , Eran Tromer , Boaz Barak , Jennifer Rexford, Path-quality monitoring in the presence of adversaries, ACM SIGMETRICS Performance Evaluation Review, v.36 n.1, June 2008
	Ashwinkumar B.V , Arpita Patra , Ashish Choudhary , Kannan Srinathan , Chandrasekharan Pandu Rangan, On tradeoff between network connectivity, phase complexity and communication complexity of reliable communication tolerating mixed adversary, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada
	Jonathan Katz , Chiu-Yuen Koo , Ranjit Kumaresan, Improving the round complexity of VSS in point-to-point networks, Information and Computation, v.207 n.8, p.889-899, August, 2009
	Arpita Patra , Ashish Choudhary , C. Pandu Rangan , Kannan Srinathan , Prasad Raghavendra, Perfectly reliable and secure message transmission tolerating mobile adversary, International Journal of Applied Cryptography, v.1 n.3, p.200-224, February 2009
	Amos Beimel, On private computation in incomplete networks, Distributed Computing, v.19 n.3, p.237-252, January 2007
	Rachid Hadid , Mehmet Hakan Karaata, An adaptive stabilizing algorithm for finding all disjoint paths in anonymous mesh networks, Computer Communications, v.32 n.5, p.858-866, March, 2009
	Kannan Srinathan , Arpita Patra , Ashish Choudhary , C. Pandu Rangan, Unconditionally secure message transmission in arbitrary directed synchronous networks tolerating generalized mixed adversary, Proceedings of the 4th International Symposium on Information, Computer, and Communications Security, March 10-12, 2009, Sydney, Australia
	Prasant Gopal Anumanchipalli , Anuj Gupta , Pranav K. Vasishta , Piyush Bansal , Kannan Srinathan, Brief announcement: global consistency can be easier than point-to-point communication, Proceedings of the 28th ACM symposium on Principles of distributed computing, August 10-12, 2009, Calgary, AB, Canada
	Arpita Patra , Ashish Choudhary , Chandrasekharan Pandu Rangan, Brief announcement: perfectly secure message transmission in directed networks re-visited, Proceedings of the 28th ACM symposium on Principles of distributed computing, August 10-12, 2009, Calgary, AB, Canada
	Pranav K. Vasishta , Prasant Gopal , Anuj Gupta , Piyush Bansal , K. Srinathan, Brief announcement: topology knowledge affects probabilistic reliable communication, Proceedings of the 28th ACM symposium on Principles of distributed computing, August 10-12, 2009, Calgary, AB, Canada

INDEX TERMS

Primary Classification:
C. Computer Systems Organization
C.2 COMPUTER-COMMUNICATION NETWORKS
C.2.0 General
Subjects: Security and protection (e.g., firewalls)

Additional Classification:
K. Computing Milieux
K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS

General Terms:
Algorithms, Reliability, Security

Keywords:
distributed computing, fault-tolerance, perfectly secure communication

REVIEW

"Morrie Gasser : Reviewer"

Perfect security of communications as defined here refers to both secrecy and integrity of communications. In an environment with perfect security where a sender and receiver have some number n of w more...

Collaborative Colleagues:

Danny Dolev: colleagues

Cynthia Dwork: colleagues

Orli Waarts: colleagues

Moti Yung: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player