Paper 2018/1167

On the Price of Proactivizing Round-Optimal Perfectly Secret Message Transmission

Ravi Kishore, Ashutosh Kumar, Chiranjeevi Vanarasa, and Kannan Srinathan


In a network of $n$ nodes (modelled 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$-round PSMT protocols, 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: (a) adversarial mobility does not affect its tolerability: PSMT tolerating a static $t$-adversary is possible if and only if PSMT tolerating mobile $t$-adversary is possible; and (b) mobility does not affect the round optimality: the fastest PSMT protocol tolerating a static $t$-adversary is not faster than the one tolerating a mobile $t$-adversary.

Available format(s)
Publication info
Published elsewhere. IEEE Transactions on Information Theory 2018
Contact author(s)
ravikishore vasala @ research iiit ac in
2018-12-03: received
Short URL
Creative Commons Attribution


      author = {Ravi Kishore and Ashutosh Kumar and Chiranjeevi Vanarasa and Kannan Srinathan},
      title = {On the Price of Proactivizing Round-Optimal Perfectly Secret Message Transmission},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1167},
      year = {2018},
      doi = {10.1109/TIT.2017.2776099},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.