On tradeoff between network connectivity, phase complexity and communication complexity of reliable communication tolerating mixed adversary

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On tradeoff between network connectivity, phase complexity and communication complexity of reliable communication tolerating mixed adversary

Full text

Pdf (406 KB)

Source

Annual ACM Symposium on Principles of Distributed Computing archive
Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing table of contents

Toronto, Canada

SESSION: R3 table of contents

Pages 115-124

Year of Publication: 2008

ISBN:978-1-59593-989-0

Authors

Ashwinkumar B.V	Indian Institute of Technology Madras, Chennai, India
Arpita Patra	Indian Institute of Technology Madras, Chennai, India
Ashish Choudhary	Indian Institute of Technology Madras, Chennai, India
Kannan Srinathan	International Institute of Information Technology, Hyderabad, India
Chandrasekharan Pandu Rangan	Indian Institute of Technology Madras, Chennai, India

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems
ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 14, Downloads (12 Months): 93, Citation Count: 1

Additional Information:

abstract references cited by index terms 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/1400751.1400768 What is a DOI?

ABSTRACT

In this paper, we study the inherent tradeoff between the network connectivity, phase complexity and communication complexity of perfectly reliable message transmission (PRMT) problem in undirected synchronous network, tolerating a mixed adversary A_{(t_b,t_f)}, who has unbounded computing power and can corrupt t_b and t_f nodes in the network in Byzantine and fail-stop fashion respectively.

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.

	1	S. Agarwal, R. Cramer, and R. de Haan. Asymptotically optimal two-round perfectly secure message transmission. In C. Dwork, editor, Proc. of Advances in Cryptology: CRYPTO 2006, LNCS 4117, pages 394--408. Springer-Verlag, 2006.
	2	Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
	3	R. Cramer, I. Damgard, S. Dziembowski, M. Hirt, and T. Rabin. Efficient multiparty computations secure against an adaptive adversary. In Proc. of EUROCRYPT 1999, volume 1592 of LNCS, pages 311--326. Springer Verlag, 1999.
	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	M. Franklin and R. Wright. Secure communication in minimal connectivity models. Journal of Cryptology, 13(1):9--30, 2000.
	7	F. J. MacWilliams and N. J. A. Sloane. The Theory of Error Correcting Codes. North-Holland Publishing Company, 1978.
	8	K. Menger. Zur allgemeinen kurventheorie. Fundamenta Mathematicae, 10:96--115, 1927.
	9	Arpita Patra , Ashish Choudhary , Chanrasekharan Pandu Rangan, Constant phase efficient protocols for secure message transmission in directed networks, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281153]
	10	A. Patra, A. Choudhary, K. Srinathan, and C. Pandu Rangan. Constant phase bit optimal protocols for perfectly reliable and secure message transmission. In Proc. of INDOCRYPT 2006, volume 4329 of LNCS, pages 221--235. Springer Verlag, 2006.
	11	K. Srinathan, A. Narayanan, and C. Pandu Rangan. Optimal perfectly secure message transmission. In Proc. of Advances in Cryptology: CRYPTO 2004, LNCS 3152, pages 545--561. Springer-Verlag, 2004.