International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Unconditionally Reliable Message Transmission in Directed Hypergraphs

Kannan Srinathan
Arpita Patra
Ashish Choudhary
C. Pandu Rangan
Search ePrint
Search Google
Abstract: We study the problem of unconditionally reliable message transmission (URMT), where two non-faulty players, the sender S and the receiver R are part of a synchronous network modeled as a directed hypergraph, a part of which may be under the influence of an adversary having unbounded computing power. S intends to transmit a message $m$ to R, such that R should correctly obtain S's message with probability at least $(1-\delta)$ for arbitrarily small $\delta > 0$. However, unlike most of the literature on this problem, we assume the adversary modeling the faults is threshold mixed, and can corrupt different set of nodes in Byzantine, passive and fail-stop fashion simultaneously. The main contribution of this work is the complete characterization of URMT in directed hypergraph tolerating such an adversary. Working out a direct characterization of URMT over directed hypergraphs tolerating threshold mixed adversary is highly un-intuitive. So we first propose a novel technique, which takes as input a directed hypergraph and a threshold mixed adversary on that hypergraph and outputs a corresponding digraph, along with a non-threshold mixed adversary, such that URMT over the hypergraph tolerating the threshold mixed adversary is possible iff a special type of URMT is possible over the obtained digraph, tolerating the corresponding non-threshold mixed adversary}. Thus characterization of URMT over directed hypergraph tolerating threshold mixed adversary reduces to characterizing special type of a URMT over arbitrary digraph tolerating non-threshold mixed adversary. We then characterize URMT in arbitrary digraphs tolerating non-threshold mixed adversary and modify it to obtain the characterization for special type of URMT over digraphs tolerating non-threshold mixed adversary. This completes the characterization of URMT over the original hypergraph. Surprisingly, our results indicate that even passive corruption, in collusion with active faults, substantially affects the reliability of URMT protocols! This is interesting because it is a general belief that passive corruption (eavesdropping) does not affect reliable communication.
  title={Unconditionally Reliable Message Transmission in Directed Hypergraphs},
  booktitle={IACR Eprint archive},
  keywords={foundations /},
  note={An extended abstract of this paper is going to appear in CANS  2008 14124 received 27 Aug 2008, last revised 2 Sep 2008},
  author={Kannan Srinathan and Arpita Patra and Ashish Choudhary and C. Pandu Rangan},