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

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

Arpita Patra, Ashish Choudhary, Chandrasekharan Pandu Rangan

Published Jan 1, 2009• 4 citations
OpenAlex

Abstract

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 ℓ

Related papers

Efficient Perfectly Reliable and Secure Communication Tolerating Mobile Adversary.

Arpita Patra, Ashish Choudhary, Madhu Gayatri +1 more

We study the problem of Perfectly Reliable Message Transmission (PRMT) and Perfectly Secure Message Transmission (PSMT) between two nodes S and R in an undirected synchronous network, a part of which is under the influence of an all powerful mobile Byzantine adversary. In ACISP’2007 Srinathan et. al. has proved that the connectivity requirement for PSMT protocols is same for both static and mobile adversary thus showing that mobility of the adversary has no effect on the possibility of PSMT (also PRMT) protocols. Similarly in CRYPTO 2004, Srinathan et. al. has shown that the lower bound on the communication complexity of any multiphase PSMT protocol is same for static and mobile adversary. The authors have also designed a O(t) phase1 protocol satisfying this bound where t is the maximum number of nodes corrupted by the Byzantine adversary. In this work, we design a three phase bit optimal PSMT protocol using a novel technique, whose communication complexity matches the lower bound proved in CRYPTO 2004 and thus significantly reducing the number of phases from O(t) to three. Further using our novel technique, we design a three phase bit optimal PRMT protocol which achieves

•Jan 1, 2008•3 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

On the Optimal Communication Complexity of Multiphase Protocols for Perfect Communication

Kannan Srinathan, Neeli Rashmi Prasad, Chandrasekharan Pandu Rangan

In the perfectly secure message transmission (PSMT) problem, two synchronized non-faulty players (or processors), the Sender S and the Receiver R are connected by n wires (each of which facilitates 2-way communication); S has a message, represented by a sequence oft elements from a finite field, that he wishes to send to R; after exchanging messages in phases R should correctly obtain S 's message, while an adversary listening on and actively controlling any set of t (or less) wires should have no information about S 's message. Similarly, in the problem of perfect reliable message transmission (PRMT), the receiver R should correctly obtain S's message, in spite of the adversary actively controlling any set oft (or less) wires.

IEEE Symposium on Security and Privacy (S&P)•May 1, 2007•19 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

Secure Message Transmission In Asynchronous Directed Networks.

Shashank Agrawal, Abhinav Mehta, Kannan Srinathan

We study the problem of information-theoretically secure message transmission (SMT) in asynchronous directed networks. In line with the literature, the distrust and failures of the network is captured via a computationally unbounded Byzantine adversary that may corrupt some subset of nodes. We give a characterization of networks over which SMT from sender S to receiver R is possible in both the well-known settings, namely perfect SMT (PSMT) and unconditional SMT (USMT). We distinguish between two variants of USMT: one in which R can output an incorrect message (with small probability) and another in which R never outputs a wrong message, but may choose to abort (with small probability). We also provide efficient protocols for an important class of networks.

•Jan 1, 2011•0 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
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 ℓ
We study the problem of Perfectly Reliable Message Transmission (PRMT) and Perfectly Secure Message Transmission (PSMT) between two nodes S and R in an undirected synchronous network, a part of which is under the influence of an all powerful mobile Byzantine adversary. In ACISP’2007 Srinathan et. al. has proved that the connectivity requirement for PSMT protocols is same for both static and mobile adversary thus showing that mobility of the adversary has no effect on the possibility of PSMT (also PRMT) protocols. Similarly in CRYPTO 2004, Srinathan et. al. has shown that the lower bound on the communication complexity of any multiphase PSMT protocol is same for static and mobile adversary. The authors have also designed a O(t) phase1 protocol satisfying this bound where t is the maximum number of nodes corrupted by the Byzantine adversary. In this work, we design a three phase bit optimal PSMT protocol using a novel technique, whose communication complexity matches the lower bound proved in CRYPTO 2004 and thus significantly reducing the number of phases from O(t) to three. Further using our novel technique, we design a three phase bit optimal PRMT protocol which achieves
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 perfectly secure message transmission (PSMT) problem, two synchronized non-faulty players (or processors), the Sender S and the Receiver R are connected by n wires (each of which facilitates 2-way communication); S has a message, represented by a sequence oft elements from a finite field, that he wishes to send to R; after exchanging messages in phases R should correctly obtain S 's message, while an adversary listening on and actively controlling any set of t (or less) wires should have no information about S 's message. Similarly, in the problem of perfect reliable message transmission (PRMT), the receiver R should correctly obtain S's message, in spite of the adversary actively controlling any set oft (or less) wires.
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
We study the problem of information-theoretically secure message transmission (SMT) in asynchronous directed networks. In line with the literature, the distrust and failures of the network is captured via a computationally unbounded Byzantine adversary that may corrupt some subset of nodes. We give a characterization of networks over which SMT from sender S to receiver R is possible in both the well-known settings, namely perfect SMT (PSMT) and unconditional SMT (USMT). We distinguish between two variants of USMT: one in which R can output an incorrect message (with small probability) and another in which R never outputs a wrong message, but may choose to abort (with small probability). We also provide efficient protocols for an important class of networks.
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.