Paper 2008/232

Perfectly Secure Message Transmission Tolerating Mixed Adversary

Arpita Patra, Ashish Choudhury, Ashwinkumar B. V, Kannan Srinathan, and C. Pandu Rangan


In this paper, we study the issues related to the possibility, feasibility and optimality for perfectly secure message transmission (PSMT) in an undirected synchronous network, under the influence of a mixed adversary having unbounded computing power, who can corrupt some of the nodes in the network in Byzantine, fail-stop and passive fashion respectively. Specifically, we answer the following questions: (a) Possibility: Given a network and a mixed adversary, what are the necessary and sufficient conditions for the existence of any PSMT protocol over the network tolerating the adversary? (b) Feasibility: Once the existence of a protocol is ensured, then does there exist a polynomial time and efficient protocol on the given network? (c) Optimality: Given a message of specific length, what is the minimum communication complexity (lower bound) needed by any PSMT protocol to transmit the message and how to design a polynomial time protocol whose total communication complexity matches the lower bound on the communication complexity? We answer the above questions by considering two different types of mixed adversary, namely static mixed adversary and mobile mixed adversary. Intuitively, it is more difficult to tolerate a mobile mixed adversary (who can corrupt different set of nodes during different stages of the protocol) in comparison to its static counter part (who corrupts the same set of nodes throughout the protocol). However, surprisingly, we show that the connectivity requirement in the network and lower bound on communication complexity of PSMT protocols is same against both static and mobile mixed adversary. To design our protocols against static and mobile mixed adversary, we use several new techniques, which are of independent interest.

Available format(s)
Publication info
Published elsewhere. A preliminary version of this paper got accepted in ICITS 2008.
Information Theoretic SecurityStatic and Mobile Mixed AdversaryUndirected GraphsSynchronous Networks
Contact author(s)
arpitapatra_10 @ yahoo co in
2010-04-20: revised
2008-05-26: received
See all versions
Short URL
Creative Commons Attribution


      author = {Arpita Patra and Ashish Choudhury and Ashwinkumar B.  V and Kannan Srinathan and C.  Pandu Rangan},
      title = {Perfectly Secure Message Transmission Tolerating Mixed Adversary},
      howpublished = {Cryptology ePrint Archive, Paper 2008/232},
      year = {2008},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.