You are looking at a specific version 20181203:030558 of this paper. See the latest version.

Paper 2018/1167

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

Ravi Kishore and Ashutosh Kumar and 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
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.