Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE Transactions on Information Theory

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

Ravi Kishore, Ashutosh Kumar, Chiranjeevi Vanarasa, Kannan Srinathan

Published Nov 21, 2017• 3 citations
Publisher

Abstract

In a network of$n$nodes (modeled 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$-roundPSMTprotocols, 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: 1)adversarial mobility does not affect its tolerability:PSMTtolerating a static$t$-adversary is possibleif and only ifPSMTtolerating mobile$t$-adversary is possible; and 2)mobility does not affect the round optimality:the fastestPSMTprotocol tolerating a static$t$-adversary isnot fasterthan the one tolerating a mobile$t$-adversary.

DOI
10.1109/tit.2017.2776099

Related papers

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

Ravi Kishore, Ashutosh Kumar, Chiranjeevi Vanarasa +1 more

In a network of $n$ nodes (modeled 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: 1) 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 2) 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.

•Jan 1, 2018•0 citations

Perfectly Secure Message Transmission in Two Rounds

Gabriele Spini, Gilles Zémor

In the model that has become known as "Perfectly Secure Message Transmission"(PSMT), a sender Alice is connected to a receiver Bob through n parallel two-way channels. A computationally unbounded adversary Eve controls t of these channels, meaning she can acquire and alter any data that is transmitted over these channels. The sender Alice wishes to communicate a secret message to Bob privately and reliably, i.e. in such a way that Eve will not get any information about the message while Bob will be able to recover it completely. In this paper, we focus on protocols that work in two transmission rounds for n= 2t+1. We break from previous work by following a conceptually simpler blueprint for achieving a PSMT protocol. We reduce the previously best-known communication complexity, i.e. the number of transmitted bits necessary to communicate a 1-bit secret, from O(n^3 log n) to O(n^2 log n). Our protocol also answers a question raised by Kurosawa and Suzuki and hitherto left open: their protocol reaches optimal transmission rate for a secret of size O(n^2 log n) bits, and the authors raised the problem of lowering this threshold. The present solution does this for a secret of O(n log n) bits. Additionally, we show how our protocol can be adapted to a Network Coding context.

arXiv:1608.01909•Aug 5, 2016•1 citation

Perfectly reliable and secure message transmission tolerating mobile adversary

Arpita Patra, Ashish Choudhary, Chandrasekharan Pandu Rangan +2 more

We study the problem of perfectly reliable message transmission (PRMT) and perfectly secure message transmission (PSMT) in an undirected synchronous network tolerating an all powerful threshold mobile Byzantine adversary. Specifically, we show that the mobility of the threshold adversary does not affect the possibility and optimality of PRMT and PSMT protocols. We also characterise PSMT in directed networks tolerating mobile adversary. All existing PRMT and PSMT protocols abstract the paths between the sender and the receiver as wires, neglecting the intermediate nodes in the paths, thus causing significant over estimation in the communication and round complexity of protocols. Here, we consider the underlying paths as a whole instead of abstracting them as wires and derive a tight bound on the number of rounds required to achieve reliable communication tolerating a threshold mobile adversary with arbitrary roaming speed. Finally, we briefly study PRMT and PSMT protocols in the presence of non-threshold mobile Byzantine adversary. Even though the characterisation for PRMT/PSMT is shown to be same against both threshold static and threshold mobile adversary (in this article), we show that the characterisation for PRMT/PSMT against non-threshold static and non-threshold mobile adversary are not same.

International Journal of Applied Cryptography•Jan 1, 2009•3 citations

Efficient Protocols for Perfectly Secure Message Transmission With Applications to Secure Network Coding

Gabriele Spini, Gilles Zémor

In the model that has become known as “Perfectly Secure Message Transmission” (PSMT), a sender Alice is connected to a receiver Bob through n parallel two-way channels. A computationally unbounded adversary Eve controls t of these channels, meaning she can acquire and alter any data that is transmitted over these channels. The sender Alice wishes to communicate a secret message to Bob privately and reliably, i.e. in such a way that Eve gains no information about the message while Bob is able to recover it completely. We focus on PSMT protocols that work in two transmission rounds for n = 2t + 1. We break from previous work by following a conceptually simpler blueprint. This has two consequences: first, we obtain improved efficiency, namely, we reduce the previously best-known communication complexity, i.e. the number of transmitted bits necessary to communicate a 1-bit secret, from O(n3log n) to O(n2log n). Our solution also reaches optimal transmission rate for a secret of size O(n log n), thus answering the hitherto open question of attaining a threshold below O(n2log n) bits. Second, our construction can be adapted to more general scenarios relevant to Network Coding, where the adversary is given more power.

IEEE Transactions on Information Theory•May 13, 2020•4 citations

Two-Round Perfectly Secure Message Transmission with Optimal Transmission Rate

Nicolas Resch, Chen Yuan

In the model of Perfectly Secure Message Transmission (PSMT), a sender Alice is connected to a receiver Bob via n parallel two-way channels, and Alice holds an 𝓁 symbol secret that she wishes to communicate to Bob. There is an unbounded adversary Eve that controls t of the channels, where n = 2t+1. Eve is able to corrupt any symbol sent through the channels she controls, and furthermore may attempt to infer Alice’s secret by observing the symbols sent through the channels she controls. The transmission is required to be (a) reliable, i.e., Bob must always be able to recover Alice’s secret, regardless of Eve’s corruptions; and (b) private, i.e., Eve may not learn anything about Alice’s secret. We focus on the two-round model, where Bob is permitted to first transmit to Alice, and then Alice responds to Bob. In this work we provide upper and lower bounds for the PSMT model when the length of the communicated secret 𝓁 is asymptotically large. Specifically, we first construct a protocol that allows Alice to communicate an 𝓁 symbol secret to Bob by transmitting at most 2(1+o_{𝓁→∞}(1))n𝓁 symbols. Under a reasonable assumption (which is satisfied by all known efficient two-round PSMT protocols), we complement this with a lower bound showing that 2n𝓁 symbols are necessary for Alice to privately and reliably communicate her secret. This provides strong evidence that our construction is optimal (even up to the leading constant).

Leibniz international proceedings in informatics•Jan 1, 2023•1 citation

On perfectly secret message transmission in digraphs tolerating dual failures

Ravi Kishore, Chiranjeevi Vanarasa, Tushant Jha +1 more

Consider a synchronous distributed network which is partly controlled by an adversary. In a Perfectly Secret Message Transmission(PSMT) protocol, the sender S wishes to transmit a message to the receiver R such that the adversary learns nothing about the message. We characterize the set of directed graphs that admit PSMT protocols tolerating a dual failure model where up to tp nodes are passively corrupted and further up to any tf nodes may fail.

International Conference on Distributed Computing and Networking (ICDCN)•Jan 4, 2016•4 citations
In a network ofnnnnodes (modeled as a digraph), the goal of a perfectly secret message transmission (PSMT) protocol is to replicate sender’s messagemmmat the receiver’s end without revealing any information aboutmmmto a computationally unbounded adversary that eavesdrops on anytttnodes. The adversary may be mobile too that is, it may eavesdrop on a different set oftttnodes in different rounds. We prove a necessary and sufficient condition on the synchronous network for the existence ofrrr-roundPSMTprotocols, for any givenr>0r > 0r>0; further, we show that round-optimality is achieved without trading-off the communication complexity; specifically, our protocols have an overall communication complexity ofO(n)O(n)O(n)elements of a finite field to perfectly transmit one field element. Apart from optimality/scalability, two interesting implications of our results are: 1)adversarial mobility does not affect its tolerability:PSMTtolerating a staticttt-adversary is possibleif and only ifPSMTtolerating mobilettt-adversary is possible; and 2)mobility does not affect the round optimality:the fastestPSMTprotocol tolerating a staticttt-adversary isnot fasterthan the one tolerating a mobilettt-adversary.
In a network of nnn nodes (modeled as a digraph), the goal of a perfectly secret message transmission ( PSMT ) protocol is to replicate sender’s message mmm at the receiver’s end without revealing any information about mmm to a computationally unbounded adversary that eavesdrops on any ttt nodes. The adversary may be mobile too that is, it may eavesdrop on a different set of ttt nodes in different rounds. We prove a necessary and sufficient condition on the synchronous network for the existence of rrr -round PSMT protocols, for any given r>0r > 0r>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)O(n)O(n) elements of a finite field to perfectly transmit one field element. Apart from optimality/scalability, two interesting implications of our results are: 1) adversarial mobility does not affect its tolerability: PSMT tolerating a static ttt -adversary is possible if and only if PSMT tolerating mobile ttt -adversary is possible; and 2) mobility does not affect the round optimality: the fastest PSMT protocol tolerating a static ttt -adversary is not faster than the one tolerating a mobile ttt -adversary.
In the model that has become known as "Perfectly Secure Message Transmission"(PSMT), a sender Alice is connected to a receiver Bob through n parallel two-way channels. A computationally unbounded adversary Eve controls t of these channels, meaning she can acquire and alter any data that is transmitted over these channels. The sender Alice wishes to communicate a secret message to Bob privately and reliably, i.e. in such a way that Eve will not get any information about the message while Bob will be able to recover it completely. In this paper, we focus on protocols that work in two transmission rounds for n= 2t+1. We break from previous work by following a conceptually simpler blueprint for achieving a PSMT protocol. We reduce the previously best-known communication complexity, i.e. the number of transmitted bits necessary to communicate a 1-bit secret, from O(n^3 log n) to O(n^2 log n). Our protocol also answers a question raised by Kurosawa and Suzuki and hitherto left open: their protocol reaches optimal transmission rate for a secret of size O(n^2 log n) bits, and the authors raised the problem of lowering this threshold. The present solution does this for a secret of O(n log n) bits. Additionally, we show how our protocol can be adapted to a Network Coding context.
We study the problem of perfectly reliable message transmission (PRMT) and perfectly secure message transmission (PSMT) in an undirected synchronous network tolerating an all powerful threshold mobile Byzantine adversary. Specifically, we show that the mobility of the threshold adversary does not affect the possibility and optimality of PRMT and PSMT protocols. We also characterise PSMT in directed networks tolerating mobile adversary. All existing PRMT and PSMT protocols abstract the paths between the sender and the receiver as wires, neglecting the intermediate nodes in the paths, thus causing significant over estimation in the communication and round complexity of protocols. Here, we consider the underlying paths as a whole instead of abstracting them as wires and derive a tight bound on the number of rounds required to achieve reliable communication tolerating a threshold mobile adversary with arbitrary roaming speed. Finally, we briefly study PRMT and PSMT protocols in the presence of non-threshold mobile Byzantine adversary. Even though the characterisation for PRMT/PSMT is shown to be same against both threshold static and threshold mobile adversary (in this article), we show that the characterisation for PRMT/PSMT against non-threshold static and non-threshold mobile adversary are not same.
In the model that has become known as “Perfectly Secure Message Transmission” (PSMT), a sender Alice is connected to a receiver Bob through n parallel two-way channels. A computationally unbounded adversary Eve controls t of these channels, meaning she can acquire and alter any data that is transmitted over these channels. The sender Alice wishes to communicate a secret message to Bob privately and reliably, i.e. in such a way that Eve gains no information about the message while Bob is able to recover it completely. We focus on PSMT protocols that work in two transmission rounds for n = 2t + 1. We break from previous work by following a conceptually simpler blueprint. This has two consequences: first, we obtain improved efficiency, namely, we reduce the previously best-known communication complexity, i.e. the number of transmitted bits necessary to communicate a 1-bit secret, from O(n3log n) to O(n2log n). Our solution also reaches optimal transmission rate for a secret of size O(n log n), thus answering the hitherto open question of attaining a threshold below O(n2log n) bits. Second, our construction can be adapted to more general scenarios relevant to Network Coding, where the adversary is given more power.
In the model of Perfectly Secure Message Transmission (PSMT), a sender Alice is connected to a receiver Bob via n parallel two-way channels, and Alice holds an 𝓁 symbol secret that she wishes to communicate to Bob. There is an unbounded adversary Eve that controls t of the channels, where n = 2t+1. Eve is able to corrupt any symbol sent through the channels she controls, and furthermore may attempt to infer Alice’s secret by observing the symbols sent through the channels she controls. The transmission is required to be (a) reliable, i.e., Bob must always be able to recover Alice’s secret, regardless of Eve’s corruptions; and (b) private, i.e., Eve may not learn anything about Alice’s secret. We focus on the two-round model, where Bob is permitted to first transmit to Alice, and then Alice responds to Bob. In this work we provide upper and lower bounds for the PSMT model when the length of the communicated secret 𝓁 is asymptotically large. Specifically, we first construct a protocol that allows Alice to communicate an 𝓁 symbol secret to Bob by transmitting at most 2(1+o_{𝓁→∞}(1))n𝓁 symbols. Under a reasonable assumption (which is satisfied by all known efficient two-round PSMT protocols), we complement this with a lower bound showing that 2n𝓁 symbols are necessary for Alice to privately and reliably communicate her secret. This provides strong evidence that our construction is optimal (even up to the leading constant).