Paper 2009/470

On The Communication Complexity of Perfectly Secure Message Transmission in Directed Networks

Arpita Patra, Ashish Choudhary, and C. Pandu Rangan

Abstract

In this paper, we re-visit the problem of perfectly secure message transmission (PSMT) in a directed network under the presence of a threshold adaptive Byzantine adversary, having unbounded computing power. Desmedt et.al have given the characterization for three or more phase PSMT protocols over directed networks. Recently, Patra et. al. have given the characterization of two phase PSMT over directed networks. Even though the issue of tradeoff between phase complexity and communication complexity of PSMT protocols has been resolved in undirected networks, nothing is known in the literature regarding directed networks. In this paper, we completely settle down this issue. Specifically, we derive the lower bounds on communication complexity of (a) two phase PSMT protocols and (b) three or more phase PSMT protocols in directed networks. Moreover, we show that our lower bounds are asymptotically tight, by designing communication optimal PSMT protocols in directed networks, which are first of their kind. We re-visit the problem of perfectly reliable message transmission (PRMT) as well. Any PRMT protocol that sends a message containing $\ell$ field elements, has a trivial lower bound of ­O($\ell$) field elements on its communication complexity. Thus any PRMT protocol that sends a message of $\ell$ eld elements by communicating O(\ell) field elements, is referred as communication optimal PRMT or PRMT with constant factor overhead. Here, we characterize the class of directed networks over which communication optimal PRMT or PRMT with constant factor overhead is possible. Moreover, we design a communication optimal PRMT over a directed network that satisfies the conditions stated in our characterization. Our communication optimal PRMT/PSMT protocols employ several new techniques based on coding theory, which are of independent interest.

Note: A preliminary version of the paper got accepted in INSCRYPT08. However the authors could not attend the conference and present the paper and so the paper was rejected. Now a 12 page version of this paper will appear in the proceedings of ICDCN 2010. However the 12 page version only contains protocols and main theorems without complete details and formal proofs. The paper which is submitted for e-print contains complete proofs and formal details.