Paper 2008/086

Efficient Perfectly Reliable and Secure Communication Tolerating Mobile Adversary

Arpita Patra, Ashish Choudhary, Madhu Gayatri, and C. Pandu Rangan

Abstract

We study the problem of Perfectly Reliable Message Transmission}(PRMT) and Perfectly Secure Message Transmission (PSMT) between two nodes S and R in an undirected synchronous network, a part of which is under the influence of an all powerful mobile Byzantine adversary. In ACISP 2007 Srinathan et. al. has proved that the connectivity requirement for PSMT protocols is same for both static and mobile adversary thus showing that mobility of the adversary has no effect on the possibility of PSMT (also PRMT) protocols. Similarly in CRYPTO 2004, Srinathan et. al. has shown that the lower bound on the communication complexity of any multiphase PSMT protocol is same for static and mobile adversary. The authors have also designed a $O(t)$ phase (A phase is a send from S to R or R to S or both) protocol satisfying this bound where $t$ is the maximum number of nodes corrupted by the Byzantine adversary. In this work, we design a three phase bit optimal PSMT protocol using a novel technique, whose communication complexity matches the lower bound proved in CRYPTO 2004 and thus significantly reducing the number of phases from $O(t)$ to three. Further using our novel technique, we design a three phase bit optimal PRMT protocol which achieves reliability with constant factor overhead against a mobile adversary. These are the first ever constant phase optimal PRMT and PSMT protocols against mobile Byzantine adversary. We also characterize PSMT protocols in directed networks tolerating mobile adversary. All the existing PRMT and PSMT protocols abstracts the paths between S and R as wires, neglecting the intermediate nodes in the paths. However, this causes significant over estimation in the communication complexity as well as round complexity (Round is different from phase. Round is a send from one node to its immediate neighbor in the network} of protocols. Here, we consider the underlying paths as a whole instead of abstracting them as wires and derive a tight bound on the number of rounds required to achieve reliable communication from S to R tolerating a mobile adversary with arbitrary roaming speed (By roaming speed we mean the speed with which the adversary changes the set of corrupted node). We show how our constant phase PRMT and PSMT protocols can be easily adapted to design round optimal and bit optimal PRMT and PSMT protocols provided the network is given as a collection of vertex disjoint paths.