Paper 2018/1167

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

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

Abstract

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.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. IEEE Transactions on Information Theory 2018
DOI
10.1109/TIT.2017.2776099
Contact author(s)
ravikishore vasala @ research iiit ac in
History
2018-12-03: received
Short URL
https://ia.cr/2018/1167
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/1167,
      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{https://eprint.iacr.org/2018/1167}},
      url = {https://eprint.iacr.org/2018/1167}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.