[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/3288599.3288612acmconferencesArticle/Chapter ViewAbstractPublication PagesicdcnConference Proceedingsconference-collections
research-article

Perfectly secure message transmission over partially synchronous networks

Published: 04 January 2019 Publication History

Abstract

In a distributed network, we consider two special nodes called the sender S and the receiver R that are connected by n node-disjoint (except for S and R) bi-directional wires. Out of these n wires, the adversary can control at most t wires (of its choice) in Byzantine fashion. In this setting, our goal is to design a message transmission protocol Π that assures the following two conditions hold: (1) by the end of the protocol Π, R gets the correct message m transmitted by S without any error (perfect reliability), and (2) the adversary learns no information about m, whatsoever, in information theoretic sense (perfect secrecy). Protocols that satisfy these two conditions are known as the Perfectly Secure Message Transmission (PSMT) protocols.
However, out of the n wires that exist, if some number of wires say ns, fortunately, happen to be synchronous (serendipitous synchrony) then we ask under what conditions do PSMT protocols tolerating t-Byzantine faults exist. In the literature, it is known that, if either ns > 2t or n > 3t then PSMT protocols trivially exist. Therefore, we consider the case where we have at most 2t synchronous wires (i.e., ns ≤ 2t) and at most 3t wires overall (i.e., n ≤ 3t). Interestingly, we prove that in this case, no PSMT protocol exists. This concludes that, in designing PSMT protocols (tolerating the given fixed number of faults), either (serendipitous) synchronous wires alone are sufficient or we get absolutely no extra advantage of a wire being synchronous over asynchronous.

References

[1]
Ashwinkumar Badanidiyuru, Arpita Patra, Ashish Choudhury, Kannan Srinathan, and C. Pandu Rangan. 2012. On the trade-off between network connectivity, round complexity, and communication complexity of reliable message transmission. J. ACM 59, 5 (2012), pp. 22.
[2]
Ashish Choudhary, Arpita Patra, B. V. Ashwinkumar, Kannan Srinathan, and C. Pandu Rangan. 2009. On Minimal Connectivity Requirement for Secure Message Transmission in Asynchronous Networks. In Distributed Computing and Networking, 10th International Conference, ICDCN 2009, Hyderabad, India, January 3--6. Proceedings. 148--162.
[3]
Ashish Choudhury, Arpita Patra, B. V. Ashwinkumar, Kannan Srinathan, and C. Pandu Rangan. 2011. Secure message transmission in asynchronous networks. J. Parallel Distrib. Comput. 71, 8 (2011), pp. 1067--1074.
[4]
Danny Dolev, Cynthia Dwork, Orli Waarts, and Moti Yung. 1993. Perfectly Secure Message Transmission. J. ACM 40, 1 (1993), pp. 17--47.
[5]
Matthias Fitzi, Matthew K. Franklin, Juan A. Garay, and Harsha Vardhan Simhadri. 2007. Towards Optimal and Efficient Perfectly Secure Message Transmission. In Theory of Cryptography, 4th Theory of Cryptography Conference, TCC 2007, Amsterdam, The Netherlands, February 21--24, Proceedings. 311--322.
[6]
Matthew K. Franklin and Rebecca N. Wright. 2000. Secure Communication in Minimal Connectivity Models. J. Cryptology 13, 1 (2000), pp. 9--30.
[7]
Ravi Kishore, Ashutosh Kumar, Chiranjeevi Vanarasa, and Kannan Srinathan. 2018. On the Price of Proactivizing Round-Optimal Perfectly Secret Message Transmission. IEEE Trans. Information Theory 64, 2 (2018), 1404--1422.
[8]
Ravi Kishore, Chiranjeevi Vanarasa, Tushant Jha, and Kannan Srinathan. 2016. On perfectly secret message transmission in digraphs tolerating dual failures. In Proceedings of the 17th International Conference on Distributed Computing and Networking, Singapore, January 4--7. 29:1--29:10.
[9]
Ravi Kishore, Chiranjeevi Vanarasa, and Kannan Srinathan. 2018. On minimal connectivity requirements for secure message transmission in directed networks. Inf. Process. Lett. 131 (2018), 1--6.
[10]
M. V. N. Ashwin Kumar, Pranava R. Goundan, K. Srinathan, and C. Pandu Rangan. 2002. On perfectly secure communication over arbitrary networks. In Proceedings of the Twenty-First Annual ACM Symposium on Principles of Distributed Computing, PODC 2002, Monterey, California, USA, July 21--24. 193--202.
[11]
Nancy A. Lynch. 1996. Distributed Algorithms. Morgan Kaufmann.
[12]
Abhinav Mehta, Shashank Agrawal, and Kannan Srinathan. 2013. Interplay between (im)perfectness, synchrony and connectivity: The case of reliable message transmission. Theor. Comput. Sci. 496 (2013), pp. 2--16.
[13]
Arpita Patra, Ashish Choudhary, and Chandrasekaran Pandu Rangan. 2007. Constant phase efficient protocols for secure message transmission in directed networks. In Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing, PODC 2007, Portland, Oregon, USA, August 12--15. 322--323.
[14]
Arpita Patra, Ashish Choudhury, C. Pandu Rangan, and Kannan Srinathan. 2010. Unconditionally reliable and secure message transmission in undirected synchronous networks: possibility, feasibility and optimality. IJACT 2, 2 (2010), pp. 159--197.
[15]
Hasan Md. Sayeed and Hosame Abu-Amara. 1995. Perfectly secure message transmission in asynchronous networks. In Proceedings of the Seventh IEEE Symposium on Parallel and Distributed Processing, SPDP 1995, San Antonio, Texas, USA, October 25--28. 100--105.
[16]
K. Srinathan, M. V. N. Ashwin Kumar, and C. Pandu Rangan. 2002. Asynchronous Secure Communication Tolerating Mixed Adversaries. In Advances in Cryptology - ASIACRYPT 2002, 8th International Conference on the Theory and Application of Cryptology and Information Security, Queenstown, New Zealand, December 1--5, Proceedings. 224--242.
[17]
K. Srinathan, Arvind Narayanan, and C. Pandu Rangan. 2004. Optimal Perfectly Secure Message Transmission. In Advances in Cryptology - CRYPTO 2004, 24th Annual International CryptologyConference, Santa Barbara, California, USA, August 15--19, Proceedings. 545--561.
[18]
Yongge Wang and Yvo Desmedt. 2008. Perfectly Secure Message Transmission Revisited. IEEE Transactions on Information Theory 54, 6 (2008), pp. 2582--2595.

Cited By

View all
  • (2023)Synchronous Perfectly Secure Message Transmission with Optimal Asynchronous Fallback GuaranteesFinancial Cryptography and Data Security10.1007/978-3-031-47754-6_5(77-93)Online publication date: 1-May-2023

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
ICDCN '19: Proceedings of the 20th International Conference on Distributed Computing and Networking
January 2019
535 pages
ISBN:9781450360944
DOI:10.1145/3288599
  • General Chairs:
  • R. C. Hansdah,
  • Dilip Krishnaswamy,
  • Nitin Vaidya
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

In-Cooperation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 January 2019

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. asynchronous communication
  2. information theoretic security
  3. perfect security
  4. reliable and secure message transmission

Qualifiers

  • Research-article

Conference

ICDCN '19
Sponsor:
  • SIGOPS
  • Indian Institute of Science

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)6
  • Downloads (Last 6 weeks)0
Reflects downloads up to 20 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2023)Synchronous Perfectly Secure Message Transmission with Optimal Asynchronous Fallback GuaranteesFinancial Cryptography and Data Security10.1007/978-3-031-47754-6_5(77-93)Online publication date: 1-May-2023

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media