International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

On Communication Complexity of Perfectly Reliable and Secure Communication in Directed Networks

Authors:
Arpita Patra
Ashish Choudhary
Kannan Srinathan
C. Pandu Rangan
Download:
URL: http://eprint.iacr.org/2008/461
Search ePrint
Search Google
Abstract: In this paper, we re-visit the problem of {\it perfectly reliable message transmission} (PRMT) and {\it perfectly secure message transmission}(PSMT) in a {\it directed network} under the presence of a threshold adaptive Byzantine adversary, having {\it unbounded computing power}. Desmedt et.al have given the necessary and sufficient condition for the existence of PSMT protocols in directed networks. In this paper, we first show that the necessary and sufficient condition (characterization) given by Desmedt et.al does not hold for two phase\footnote{A phase is a send from sender to receiver or vice-versa.} PSMT protocols. Hence we provide a different necessary and sufficient condition for two phase PSMT in directed networks. We also derive the lower bound on communication complexity of two phase PSMT and show that our lower bound is {\it asymptotically tight} by designing a two phase PSMT protocol whose communication complexity satisfies the lower bound. Though the characterization for three or more phase PSMT is resolved by the result of Desmedt et. al, the lower bound on communication complexity for the same has not been investigated yet. Here we derive the lower bound on the communication complexity of three or more phase PSMT in directed networks and show that our lower bound is {\it asymptotically tight} by designing {\it communication optimal} PSMT protocols. Finally, we characterize the class of directed networks over which communication optimal PRMT or PRMT with constant factor overhead is possible. By communication optimal PRMT or PRMT with constant factor overhead, we mean that the PRMT protocol is able to send $\ell$ field elements by communicating $O(\ell)$ field elements from a finite field $\mathbb F$. To design our protocols, we use several techniques, which are of independent interest.
BibTeX
@misc{eprint-2008-18057,
  title={On Communication Complexity of Perfectly Reliable and Secure Communication in Directed Networks},
  booktitle={IACR Eprint archive},
  keywords={foundations /},
  url={http://eprint.iacr.org/2008/461},
  note={This is a full version of the paper which got acepted in INSCRYPT 2008 arpitapatra_10@yahoo.co.in 14286 received 1 Nov 2008, withdrawn 11 Feb 2009},
  author={Arpita Patra and Ashish Choudhary and Kannan Srinathan and C. Pandu Rangan},
  year=2008
}