Cryptology ePrint Archive: Report 2008/232

Perfectly Secure Message Transmission Tolerating Mixed Adversary

Arpita Patra and Ashish Choudhury and Ashwinkumar B. V and 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.

Category / Keywords: Information Theoretic Security, Static and Mobile Mixed Adversary, Undirected Graphs, Synchronous Networks

Publication Info: A preliminary version of this paper got accepted in ICITS 2008.

Date: received 22 May 2008, last revised 19 Apr 2010

Contact author: arpitapatra_10 at yahoo co in

Available format(s): PDF | BibTeX Citation

Version: 20100420:043053 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]