On the Communication Complexity of Reliable and Secure Message Transmission in Asynchronous Networks

Ashish Choudhury; Arpita Patra

Paper 2011/288

On the Communication Complexity of Reliable and Secure Message Transmission in Asynchronous Networks

Ashish Choudhury and Arpita Patra

Abstract

In this paper, we study the communication complexity of Reliable Message Transmission (RMT) and Secure Message Transmission (SMT) protocols in asynchronous settings. We consider two variants of the problem, namely perfect} (where no error is allowed in the protocol outcome) and statistical (where the protocol may output a wrong outcome with negligible probability). RMT and SMT protocols have been investigated rigorously in synchronous settings. But not too much attention has been paid to the asynchronous version of the problem. In a significant work, Choudhury et al. (ICDCN 2009 and JPDC 2011) have studied the network connectivity requirement for perfect and statistical SMT protocols in asynchronous settings. Their investigation reveals the following two important facts: 1. Perfect SMT protocols require more network connectivity in asynchronous network than synchronous network. 2. Connectivity requirement of statistical SMT protocols is same for both synchronous and asynchronous network. Unfortunately, nothing is known about the communication complexity of RMT and SMT protocols in asynchronous settings. In this paper, we derive tight bounds on the communication complexity of the above problems and compare our results with the existing bounds for synchronous protocols. The interesting conclusions derived from our results are: 1. Asynchrony increases the communication complexity of perfect RMT protocols. However, asynchrony has no impact on the communication complexity of statistical RMT protocols. 2. SMT: Communication complexity of SMT protocols is more in asynchronous network, for both perfect as well as statistical case.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. To appear in ICISC 2011
Contact author(s): partho31 @ gmail com
arpitapatra10 @ gmail com
History: 2011-10-31: revised; 2011-06-03: received; See all versions
Short URL: https://ia.cr/2011/288
License: CC BY

BibTeX

@misc{cryptoeprint:2011/288,
      author = {Ashish Choudhury and Arpita Patra},
      title = {On the Communication Complexity of Reliable and Secure Message Transmission in Asynchronous Networks},
      howpublished = {Cryptology {ePrint} Archive, Paper 2011/288},
      year = {2011},
      url = {https://eprint.iacr.org/2011/288}
}