Probabilistic perfectly reliable and secure message transmission - Possibility, feasibility and optimality

We study the interplay of network connectivity and the issues related to feasibility and optimality for probabilistic perfectly reliable message transmission (PPRMT) and probabilistic perfectly secure message transmission (PPSMT) in a synchronous network under the influence of a mixed adversary who possesses unbounded computing power and can corrupt different set of nodes in Byzantine, omission, failstop and passive fashion simultaneously. Our results show that that randomness helps in the possibility of multiphase PPSMT and significantly improves the lower bound on communication complexity for both PPRMT and PPSMT protocols!! © Springer-Verlag Berlin Heidelberg 2007.