On the Price of Proactivizing Round-Optimal Perfectly Secret Message Transmission
Ravi Kishore, Ashutosh Kumar, Chiranjeevi Vanarasa, Kannan Srinathan · IEEE Transactions on Information Theory · 2017
In a network of$n$nodes (modeled as a digraph), the goal of a perfectly secret message transmission (PSMT) protocol is to replicate sender’s message$m$at the receiver’s end without revealing any information about$m$to a computationally unbounded adversary that eavesdrops on any$t$nodes. The adversary may be mobile too that is, it may eavesdrop on a different set of$t$nodes in different rounds. We prove a necessary and sufficient condition on the synchronous network for the existence of$r$-roundPSMTprotocols, for any given$r > 0$; further, we show that round-optimality is achieved without trading-off the communication complexity; specifically, our protocols have an overall communication complexity of$O(n)$elements of a finite field to perfectly transmit one field element. Apart from optimality/scalability, two interesting implications of our results are: 1)adversarial mobility does not affect its tolerability:PSMTtolerating a static$t$-adversary is possibleif and only ifPSMTtolerating mobile$t$-adversary is possible; and 2)mobility does not affect the round optimality:the fastestPSMTprotocol tolerating a static$t$-adversary isnot fasterthan the one tolerating a mobile$t$-adversary.