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

Unconditionally Reliable Message Transmission in Directed Neighbour Networks.

Shashank Agrawal, Abhinav Mehta, Kannan Srinathan

Published Jan 1, 2011• 0 citations
OpenAlex

Abstract

The problem of unconditionally reliable message transmission (URMT) is to design a protocol which when run by players in a network enables a sender s to deliver a message to a receiver r with high probability, even when some players in the network are under the control of an unbounded adversary. Renault and Tomala [JoC2008] gave a characterization of undirected neighbour networks over which URMT tolerating Byzantine adversary is possible. In this paper, we generalize their result to the case of directed networks. 1

Related papers

Unconditionally reliable and secure message transmission in undirected synchronous networks: possibility, feasibility and optimality

Arpita Patra, Ashish Choudhury, Chandrasekharan Pandu Rangan +1 more

We study the interplay of network connectivity and the issues related to the 'possibility', 'feasibility' and 'optimality' for unconditionally reliable message transmission (URMT) and unconditionally secure message transmission (USMT) in an undirected synchronous network, under the influence of an adaptive mixed adversary having unbounded computing power, who can corrupt some of the nodes in the network in Byzantine, omission, fail-stop and passive fashion respectively. We consider two types of adversary, namely threshold and non-threshold. One of the important conclusions we arrive at from our study is that allowing a negligible error probability significantly helps in the 'possibility', 'feasibility' and 'optimality' of both reliable and secure message transmission protocols. To design our protocols, we propose several new techniques which are of independent interest.

International Journal of Applied Cryptography•Jan 1, 2010•40 citations

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

Unconditionally secure message transmission in arbitrary directed synchronous networks tolerating generalized mixed adversary

Kannan Srinathan, Arpita Patra, Ashish Choudhary +1 more

In this paper, we re-visit the problem of unconditionally secure message transmission (USMT) from a sender S to a receiver R, who are part of a distributed synchronous network, modeled as an arbitrary directed graph. Some of the intermediate nodes between S and R can be under the control of an adversary having unbounded computing power. Desmedt and Wang [4] have given the characterization of USMT in directed networks. However, in their model, the underlying network is abstracted as directed node disjoint paths (also called as wires/channels) between S and R, where the intermediate nodes are oblivious, message passing nodes and perform no other computation. In this work, we first show that the characterization of USMT given by Desmedt et.al [4] does not hold good for arbitrary directed networks, where the intermediate nodes can perform some computation, beside acting as message forwarding nodes. We then give the characterization of USMT in arbitrary directed networks, considering the entire network as a whole. As far our knowledge is concerned, this is the first ever characterization of USMT in arbitrary directed networks.

ACM Asia Conference on Computer and Communications Security (ASIA CCS)•Mar 10, 2009•11 citations

Statistically Reliable and Secure Message Transmission in Directed Networks.

Arpita Patra, Ashish Choudhury, Chandrasekharan Pandu Rangan

Consider the following problem: a sender S and a receiver R are part of a directed synchronous network and connected through intermediate nodes. Specifically, there exists n node disjoint paths, also called as wires, which are directed from S to R and u wires, which are directed from R to S. Moreover, the wires from S to R are disjoint from the wires directed from R to S. There exists a centralized, static adversary A static , who has unbounded computing power and who can control at most t wires between S and R in Byzantine fashion. S has a message m S , which we wants to send to R. The challenge is to design a protocol, such that after interacting in phases 5 as per the protocol, R should correctly output m R = m S , except with error probability 2 −(κ) , where κ is the error parameter. This problem is called as statistically reliable message transmission (SRMT). The problem of statistically secure message transmission (SSMT) has an additional requirement that at the end of the protocol, m S should be information theoretically secure from A static . Desmedt et.al [14, 55] have given the necessary and sufficientcondition for the existence of SRMT and SSMT protocols in the above settings. They also presented an SSMT protocol, satisfying their characterization. The authors in [14, 55] claimed that their protocol is efficientand has polynomial computational and communication complexity. However, we show that it is not so. That is, we specify an adversary strategy, which may cause the protocol to have exponential computational and communication complexity 6 . We then present

•Jan 1, 2008•1 citation

Minimal Connectivity for Unconditionally Secure Message Transmission in Synchronous Directed Networks.

Manan Nayak, Shashank Agrawal, Kannan Srinathan

Abstract. In this paper we give the minimal connectivity required in a synchronous directed network, which is under the influence of a computationally unbounded Byzantine adversary that can corrupt a subset of nodes, so that Secure Message Transmission is possible between sender S and receiver R. We also show that secure communication between a pair of nodes in a given synchronous directed network is possible in both directions if and only if reliable communication is possible between them. We assume that in a network, every node is capable of computation and we model the network along the lines of [14].

•Jan 1, 2011•0 citations

On The Communication Complexity of Perfectly Secure Message Transmission in Directed Networks.

Arpita Patra, Ashish Choudhary, Chandrasekharan Pandu Rangan

In this paper, we re-visit the problem of perfectly secure message transmission (PSMT) in a directed network under the presence of a threshold adaptive Byzantine adversary, having unbounded computing power. Desmedt et.al [5] have given the characterization for three or more phase PSMT protocols over directed networks. Recently, Patra et. al. [15] have given the characterization of two phase PSMT over directed networks. Even though the issue of tradeoff between phase complexity and communication complexity of PSMT protocols has been resolved in undirected networks, nothing is known in the literature regarding directed networks. In this paper, we completely settle down this issue. Specifically, we derive the lower bounds on communication complexity of (a) two phase PSMT protocols and (b) three or more phase PSMT protocols in directed networks. Moreover, we show that our lower bounds are asymptotically tight, by designing communication optimal PSMT protocols in directed networks, which are first of their kind. We re-visit the problem of perfectly reliable message transmission (PRMT) as well. Any PRMT protocol that sends a message containing ℓ field elements, has a trivial lower bound of Ω(ℓ) (field elements) on its communication complexity. Thus any PRMT protocol that sends a message of ℓ

•Jan 1, 2009•4 citations
The problem of unconditionally reliable message transmission (URMT) is to design a protocol which when run by players in a network enables a sender s to deliver a message to a receiver r with high probability, even when some players in the network are under the control of an unbounded adversary. Renault and Tomala [JoC2008] gave a characterization of undirected neighbour networks over which URMT tolerating Byzantine adversary is possible. In this paper, we generalize their result to the case of directed networks. 1
We study the interplay of network connectivity and the issues related to the 'possibility', 'feasibility' and 'optimality' for unconditionally reliable message transmission (URMT) and unconditionally secure message transmission (USMT) in an undirected synchronous network, under the influence of an adaptive mixed adversary having unbounded computing power, who can corrupt some of the nodes in the network in Byzantine, omission, fail-stop and passive fashion respectively. We consider two types of adversary, namely threshold and non-threshold. One of the important conclusions we arrive at from our study is that allowing a negligible error probability significantly helps in the 'possibility', 'feasibility' and 'optimality' of both reliable and secure message transmission protocols. To design our protocols, we propose several new techniques which are of independent interest.
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 this paper, we re-visit the problem of unconditionally secure message transmission (USMT) from a sender S to a receiver R, who are part of a distributed synchronous network, modeled as an arbitrary directed graph. Some of the intermediate nodes between S and R can be under the control of an adversary having unbounded computing power. Desmedt and Wang [4] have given the characterization of USMT in directed networks. However, in their model, the underlying network is abstracted as directed node disjoint paths (also called as wires/channels) between S and R, where the intermediate nodes are oblivious, message passing nodes and perform no other computation. In this work, we first show that the characterization of USMT given by Desmedt et.al [4] does not hold good for arbitrary directed networks, where the intermediate nodes can perform some computation, beside acting as message forwarding nodes. We then give the characterization of USMT in arbitrary directed networks, considering the entire network as a whole. As far our knowledge is concerned, this is the first ever characterization of USMT in arbitrary directed networks.
Consider the following problem: a sender S and a receiver R are part of a directed synchronous network and connected through intermediate nodes. Specifically, there exists n node disjoint paths, also called as wires, which are directed from S to R and u wires, which are directed from R to S. Moreover, the wires from S to R are disjoint from the wires directed from R to S. There exists a centralized, static adversary A static , who has unbounded computing power and who can control at most t wires between S and R in Byzantine fashion. S has a message m S , which we wants to send to R. The challenge is to design a protocol, such that after interacting in phases 5 as per the protocol, R should correctly output m R = m S , except with error probability 2 −(κ) , where κ is the error parameter. This problem is called as statistically reliable message transmission (SRMT). The problem of statistically secure message transmission (SSMT) has an additional requirement that at the end of the protocol, m S should be information theoretically secure from A static . Desmedt et.al [14, 55] have given the necessary and sufficientcondition for the existence of SRMT and SSMT protocols in the above settings. They also presented an SSMT protocol, satisfying their characterization. The authors in [14, 55] claimed that their protocol is efficientand has polynomial computational and communication complexity. However, we show that it is not so. That is, we specify an adversary strategy, which may cause the protocol to have exponential computational and communication complexity 6 . We then present
Abstract. In this paper we give the minimal connectivity required in a synchronous directed network, which is under the influence of a computationally unbounded Byzantine adversary that can corrupt a subset of nodes, so that Secure Message Transmission is possible between sender S and receiver R. We also show that secure communication between a pair of nodes in a given synchronous directed network is possible in both directions if and only if reliable communication is possible between them. We assume that in a network, every node is capable of computation and we model the network along the lines of [14].
In this paper, we re-visit the problem of perfectly secure message transmission (PSMT) in a directed network under the presence of a threshold adaptive Byzantine adversary, having unbounded computing power. Desmedt et.al [5] have given the characterization for three or more phase PSMT protocols over directed networks. Recently, Patra et. al. [15] have given the characterization of two phase PSMT over directed networks. Even though the issue of tradeoff between phase complexity and communication complexity of PSMT protocols has been resolved in undirected networks, nothing is known in the literature regarding directed networks. In this paper, we completely settle down this issue. Specifically, we derive the lower bounds on communication complexity of (a) two phase PSMT protocols and (b) three or more phase PSMT protocols in directed networks. Moreover, we show that our lower bounds are asymptotically tight, by designing communication optimal PSMT protocols in directed networks, which are first of their kind. We re-visit the problem of perfectly reliable message transmission (PRMT) as well. Any PRMT protocol that sends a message containing ℓ field elements, has a trivial lower bound of Ω(ℓ) (field elements) on its communication complexity. Thus any PRMT protocol that sends a message of ℓ