Cryptology ePrint Archive: Report 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.

Category / Keywords:

Original Publication (in the same form): IEEE Transactions on Information Theory 2018

Date: received 29 Nov 2018, last revised 29 Nov 2018

Contact author: ravikishore vasala at research iiit ac in

Available format(s): PDF | BibTeX Citation

Version: 20181203:030558 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]