On the Price of Proactivizing Round-Optimal Perfectly Secret Message Transmission
- 21 November 2017
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 64 (2) , 1404-1422
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.Keywords
Funding Information
- Tata Consultancy Services, India
This publication has 32 references indexed in Scilit:
- Efficient maximum flow algorithmsCommunications of the ACM, 2014
- Interplay between (im)perfectness, synchrony and connectivity: The case of reliable message transmissionTheoretical Computer Science, 2013
- Unconditionally Reliable Message Transmission in Directed HypergraphsLecture Notes in Computer Science, 2008
- Perfectly Secure Message Transmission in Directed Networks Tolerating Threshold and Non Threshold Adversary2007
- Complete characterization of adversaries tolerable in secure multi-party computation (extended abstract)1997
- Secure hypergraphs1995
- How to withstand mobile virus attacks (extended abstract)1991
- How to share a secretCommunications of the ACM, 1979
- New directions in cryptographyIEEE Transactions on Information Theory, 1976
- Network Flow and Testing Graph ConnectivitySIAM Journal on Computing, 1975