Repository logo
  • English
  • Català
  • Čeština
  • Deutsch
  • Español
  • Français
  • Gàidhlig
  • Italiano
  • Latviešu
  • Magyar
  • Nederlands
  • Polski
  • Português
  • Português do Brasil
  • Suomi
  • Svenska
  • Türkçe
  • Қазақ
  • বাংলা
  • हिंदी
  • Ελληνικά
  • Yкраї́нська
  • Log In
    or
    New user? Click here to register.Have you forgotten your password?
Repository logo
  • Communities & Collections
  • Research Outputs
  • Fundings & Projects
  • People
  • Statistics
  • English
  • Català
  • Čeština
  • Deutsch
  • Español
  • Français
  • Gàidhlig
  • Italiano
  • Latviešu
  • Magyar
  • Nederlands
  • Polski
  • Português
  • Português do Brasil
  • Suomi
  • Svenska
  • Türkçe
  • Қазақ
  • বাংলা
  • हिंदी
  • Ελληνικά
  • Yкраї́нська
  • Log In
    or
    New user? Click here to register.Have you forgotten your password?
  1. Home
  2. Indian Institute of Technology Madras
  3. Publication8
  4. Secure message transmission in asynchronous networks
 
  • Details
Options

Secure message transmission in asynchronous networks

Date Issued
01-08-2011
Author(s)
Choudhury, Ashish
Patra, Arpita
Ashwinkumar, B. V.
Srinathan, Kannan
C Pandu Rangan 
Indian Institute of Technology, Madras
DOI
10.1016/j.jpdc.2011.03.004
Abstract
In the Perfectly Secure Message Transmission (PSMT) problem, a sender S and a receiver R are part of a distributed network and connected through n node disjoint paths, also called as wires, among which at most t wires are controlled by a static, Byzantine adversary Atstatic, having unbounded computing power. S has a message m, which S intends to send to R. The challenge is to design a protocol, such that at the end of the protocol, R should correctly output m without any error (perfect reliability) and A tstatic should not get any information about m, whatsoever, in information theoretic sense (perfect security). The problem of Statistically Secure Message Transmission (SSMT) is same as PSMT, except that R should correctly output m with very high probability. Sayeed and Abu-Amara (1995) [37] have given a PSMT protocol in an asynchronous network tolerating Atstatic, where S and R are connected by n=2t+1 wires. However, we show that their protocol does not provide perfect security. We then prove that in an asynchronous network, if all the n wires are directed from S to R, then any PSMT protocol tolerating Atstatic is possible iff n>3t. Surprisingly, we also prove that even if all the n wires are bi-directional, then any PSMT protocol in asynchronous network tolerating A tstatic is possible iff n>3t. This is quite surprising because for synchronous networks, by the results of Dolev et al. (1993) [16], if all the wires are unidirectional (directed from S to R), then PSMT tolerating Atstatic is possible iff n>3t, where as if all the wires are bi-directional then PSMT tolerating Atstatic is possible iff n>2t. This shows that asynchrony of the network demands higher connectivity of the network for the existence of PSMT protocols. Interestingly, we further show that n>2t wires are necessary and sufficient for the existence of any SSMT protocol in asynchronous network tolerating A tstatic , irrespective of whether the n wires are unidirectional from S to R or the n wires are bi-directional. By the results of Franklin and Wright (2000) [18] and Kurosawa and Suzuki (2009) [22], n>2t wires are necessary and sufficient for the existence of SSMT in synchronous networks, irrespective of whether the n wires are unidirectional from S to R or the n wires are bi-directional. This shows that asynchrony of the network does not demand higher connectivity of the network for SSMT protocols. © 2011 Elsevier Inc. All rights reserved.
Volume
71
Subjects
  • Asynchronous networks...

  • Error probability

  • Information theoretic...

  • Optimality

Indian Institute of Technology Madras Knowledge Repository developed and maintained by the Library

Built with DSpace-CRIS software - Extension maintained and optimized by 4Science

  • Cookie settings
  • Privacy policy
  • End User Agreement
  • Send Feedback