Paper 2008/232

Perfectly Secure Message Transmission Tolerating Mixed Adversary

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

Abstract

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.

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

BibTeX

@misc{cryptoeprint:2008/232,
      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},
      url = {https://eprint.iacr.org/2008/232}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.