Efficient Perfectly Reliable and Secure Message Transmission Tolerating Mobile Adversary

摘要

In this paper, 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. We design a three phase bit optimal PSMT protocol tolerating mobile adversary, whose communication complexity matches the existing lower bound on the communication complexity of any multi phase PSMT protocol, tolerating mobile adversary. This significantly reduces the phase complexity of the existing O(t) phase bit optimal PSMT protocol tolerating mobile adversary, where t denotes the number of nodes corrupted by the mobile adversary. Furthermore, 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 bit optimal PRMT and PSMT protocols against mobile Byzantine adversary. We also characterize PSMT protocols in directed networks tolerating mobile adversary. Finally, we derive tight bound on the number of rounds required to achieve reliable communication from S to R tolerating a mobile adversary with arbitrary roaming speed1. Finally, we show how our constant phase PRMT and PSMT protocols can be adapted to design round optimal and bit optimal PRMT and PSMT protocols, provided the network is given as collection of vertex disjoint paths.