Header menu link for other important links
Perfectly secure message transmission in directed networks tolerating threshold and non threshold adversary
Ashish Choudhary,
Published in Springer Verlag
Volume: 4856 LNCS
Pages: 80 - 101
In this paper we study Perfectly Secure Message Transmission (PSMT) between a sender S and a receiver R, connected in a directed synchronous network through multiple parallel edges (called wires), each of which are directed from S to R or vice-versa. The unreliability of the network is modeled by a Byzantine adversary with infinite computing power. We investigate the problem with two different adversarial settings: (i) threshold and (ii) non-threshold. In [1], the authors have characterized PSMT against a t-active threshold adversary in directed networks1. However, their PSMT protocol was exponential both in terms of number of phases2 and communication complexity. In addition, they also presented a polynomial phase PSMT protocol with n′ = max(3t-u+1, 2t+1) wires from S to R. In this paper, we significantly improve the exponential phase protocol and present an elegant and efficient three phase PSMT protocol with polynomial communication complexity (and computational complexity) with n = max(3t - 2u + 1, 2t + 1) wires from S to R. Also with n′ = max(3t - u + 1, 2t + 1) wires from S to R, we are able to further improve the communication complexity of our three phase PSMT protocol. Our second contribution in this paper is the first ever characterization for any two phase PSMT protocol.Finally, we also characterize PSMT protocol in directed networks tolerating nonthreshold adversary. In [3], the authors have given the characterization for PSMT against non-threshold adversary. However, in their characterization, they have only considered the paths from S to R, excluding the feedback paths (i.e paths from R to S) and hence their characterization holds good only for single phase protocols. We characterize multiphase PSMT considering feedback paths. © Springer-Verlag Berlin Heidelberg 2007.
About the journal
JournalData powered by TypesetLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherData powered by TypesetSpringer Verlag
Open AccessNo
Concepts (9)
  •  related image
    Computational complexity
  •  related image
  •  related image
    Network protocols
  •  related image
  •  related image
    Problem solving
  •  related image
    Security systems
  •  related image
  •  related image
  •  related image
    Message passing