Unconditionally secure message transmission in arbitrary directed synchronous networks tolerating generalized mixed adversary

ABSTRACT

In this paper, we re-visit the problem of unconditionally secure message transmission (USMT) from a sender S to a receiver R, who are part of a distributed synchronous network, modeled as an arbitrary directed graph. Some of the intermediate nodes between S and R can be under the control of an adversary having unbounded computing power. Desmedt and Wang [4] have given the characterization of USMT in directed networks. However, in their model, the underlying network is abstracted as directed node disjoint paths (also called as wires/channels) between S and R, where the intermediate nodes are oblivious, message passing nodes and perform no other computation. In this work, we first show that the characterization of USMT given by Desmedt et.al [4] does not hold good for arbitrary directed networks, where the intermediate nodes can perform some computation, beside acting as message forwarding nodes. We then give the characterization of USMT in arbitrary directed networks, considering the entire network as a whole. As far our knowledge is concerned, this is the first ever characterization of USMT in arbitrary directed networks.

REFERENCES

• 1: Bernd Altmann , Matthias Fitzi , Ueli M. Maurer, Byzantine Agreement Secure against General Adversaries in the Dual Failure Model, Proceedings of the 13th International Symposium on Distributed Computing, p.123-137, September 27-29, 1999
• 2: Michael Ben-Or , Shafi Goldwasser , Avi Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.1-10, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62213]
• 3: David Chaum , Claude Crépeau , Ivan Damgard, Multiparty unconditionally secure protocols, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.11-19, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62214]
• 4: Yvo Desmedt , Yongge Wang, Perfectly Secure Message Transmission Revisited, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology, p.502-517, May 02, 2002
• 5: Danny Dolev , Cynthia Dwork , Orli Waarts , Moti Yung, Perfectly secure message transmission, Journal of the ACM (JACM), v.40 n.1, p.17-47, Jan. 1993 [doi>10.1145/138027.138036]
• 6: Matthias Fitzi , Martin Hirt , Ueli M. Maurer, Trading Correctness for Privacy in Unconditional Multi-Party Computation (Extended Abstract), Proceedings of the 18th Annual International Cryptology Conference on Advances in Cryptology, p.121-136, August 23-27, 1998
• 7: Matthias Fitzi , Martin Hirt , Ueli M. Maurer, General Adversaries in Unconditional Multi-party Computation, Proceedings of the International Conference on the Theory and Applications of Cryptology and Information Security: Advances in Cryptology, p.232-246, November 14-18, 1999
• 8: M. Franklin and R. Wright. Secure communication in minimal connectivity models. Journal of Cryptology, 13(1):9--30, 2000.
• 9: O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM symposium on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
• 10: F. J. MacWilliams and N. J. A. Sloane. The Theory of Error Correcting Codes. North-Holland Publishing Company, 1978.
• 11: A. Patra, A. Choudhary, K. Srinathan, and C. Pandu Rangan. Unconditionally reliable and secure message transmission in undirected synchronous networks tolerating mixed adversary: Possibility, feasibility and optimality. Cryptology ePrint Archive, Report 2008/141, 2008.
• 12: 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]
• 13: K. Srinathan, A. Patra, A. Choudhary, and C. Pandu Rangan. Unconditionally secure message transmission in arbitrary directed synchronous networks tolerating generalized mixed adversary. Cryptology ePrint Archive, Report 2008/506, 2008.
• 14: 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 [doi>10.1145/1146381.1146421]
• 15: Andrew C. Yao, Protocols for secure computations, Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, p.160-164, November 03-05, 1982

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.5 Reliability

General Terms:
Reliability, Security, Theory

Keywords:
error probability, information theoretic security, mixed adversary