On proactive perfectly secure message transmission

This paper studies the interplay of network connectivity and perfectly secure message transmission under the corrupting influence of a Byzantine mobile adversary that may move from player to player but can corrupt no more than t players at any given time. It is known that, in the stationary adversary model where the adversary corrupts the same set of t players throughout the protocol, perfectly secure communication among any pair of players is possible if and only if the underlying synchronous network is (2t + 1)-connected. Surprisingly, we show that (2t + 1)-connectivity is sufficient (and of course, necessary) even in the proactive (mobile) setting where the adversary is allowed to corrupt different sets of t players in different rounds of the protocol. In other words, adversarial mobility has no effect on the possibility of secure communication. Towards this, we use the notion of a Communication Graph, which is useful in modelling scenarios with adversarial mobility. We also show that protocols for reliable and secure communication proposed in [15] can be modified to tolerate the mobile adversary, Further these protocols are round-optimal if the underlying network is a collection of disjoint paths from the sender S to receiver R. © Springer-Verlag Berlin Heidelberg 2007.