Abstract: |
We study the interplay of network connectivity and the issues related to the possibility, feasibility and optimality for {\it unconditionally reliable message transmission} (URMT) and {\it unconditionally secure message transmission} (USMT) in an undirected {\it synchronous} network, under the influence of an adaptive {\it mixed} adversary ${\mathcal A}_{(t_b,t_o,t_f,t_p)}$, who has
{\it unbounded computing power} and can corrupt $t_b$, $t_o$, $t_f$
and $t_p$ nodes in the network in Byzantine, {\it omission}, {\it
fail-stop} and passive fashion respectively. In URMT problem, a sender {\bf S} and a receiver {\bf R} are part of a distributed network, where {\bf S} and {\bf R} are connected by intermediate nodes, of which at most $t_b, t_o, t_f$ and $t_p$ nodes can be under the control of ${\mathcal A}_{(t_b,t_o,t_f,t_p)}$. {\bf S} wants to send a message $m$ which is a sequence of $\ell$ field elements from a finite field ${\mathbb F}$ to {\bf R}. The challenge is to design a protocol,
such that after interacting in phases\footnote{A phase is a send from {\bf S} to {\bf R} or viceversa.} as per the protocol, {\bf R} should output $m' = m$ with probability at least $1 - \delta$, where
$0 < \delta < \frac{1}{2}$. Moreover, this should happen, irrespective of the adversary strategy of ${\mathcal A}_{(t_b,t_o,t_f,t_p)}$. The USMT problem has an additional requirement that ${\mathcal A}_{(t_b,t_o,t_f,t_p)}$ should not know anything about $m$ in {\it information theoretic} sense.
In this paper, we answer the following in context of URMT and USMT: (a) {\sc Possibility:} when is a protocol possible in a given network? (b) {\sc Feasibility:} Once the existence of a protocol is ensured then does there exists a polynomial time protocol on the given network? (c) {\sc Optimality: } Given a message of specific length, what is the minimum communication complexity (lower bound) needed by any protocol to transmit the message and how to design a protocol whose total communication complexity matches the lower bound on the communication complexity? Finally we also show that {\it allowing a negligible error probability significantly helps in the possibility, feasibility and optimality of both reliable and secure message transmission protocols.} To design our protocols, we propose several new techniques which are of independent interest. |