Abstract
Consider an arbitrary network of n nodes, up to any t of which are eavesdropped on by an adversary. A sender S wishes to send a message m to a receiver R such that the adversary learns nothing about m (unless it eavesdrops on one among {S,R}). We prove a necessary and sufficient condition on the (synchronous) network for the existence of r-round protocols for perfect communication, for any given r > 0. Our results/protocols are easily adapted to asynchronous networks too and are shown to be optimal in asynchronous “rounds”. Further, we show that round-optimality is achieved without trading-off the communication complexity; specifically, our protocols have an overall message complexity of O(n) elements of a finite field to perfectly transmit one field element. Interestingly, optimality (of protocols) also implies: (a) when the shortest path between S and R has Ω(n) nodes, perfect secrecy is achieved for “free”, because any (insecure routing) protocol would also take O(n) rounds and send O(n) messages (one message along each edge in the shortest path) for transmission and (b) it is well-known that (t + 1) vertex disjoint paths from S to R are necessary for a protocol to exist; a consequent folklore is that the length of the (t + 1)th ranked (disjoint shortest) path would dictate the round complexity of protocols; we show that the folklore is false; round-optimal protocols can be substantially faster than the aforementioned length.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Franklin, M.K., Yung, M.: Secure hypergraphs: privacy from partial broadcast (extended abstract). In: Leighton, F.T., Borodin, A. (eds.) STOC, pp. 36–44. ACM (1995)
Hirt, M., Maurer, U.: Complete Characterization of Adversaries Tolerable in Secure Multi-party Computation. In: Proceedings of the 16th Symposium on Principles of Distributed Computing (PODC), pp. 25–34. ACM Press (August 1997)
Ostrovsky, R., Yung, M.: How to Withstand Mobile Virus Attacks. In: Proceedings of the 10th Symposium on Principles of Distributed Computing (PODC), pp. 51–61. ACM Press (1991)
Srinathan, K., Raghavendra, P., Chandrasekaran, P.R.: On proactive perfectly secure message transmission. In: Pieprzyk, J., Ghodosi, H., Dawson, E. (eds.) ACISP 2007. LNCS, vol. 4586, pp. 461–473. Springer, Heidelberg (2007)
Fitzi, M., Hirt, M., Maurer, U.M.: Trading Correctness for Privacy in Unconditional multi-party Computation. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 121–136. Springer, Heidelberg (1998)
Choudhary, A., Patra, A., Ashwinkumar, B.V., Srinathan, K., Rangan, C.P.: Perfectly reliable and secure communication tolerating static and mobile mixed adversary. In: Safavi-Naini, R. (ed.) ICITS 2008. LNCS, vol. 5155, pp. 137–155. Springer, Heidelberg (2008)
Sayeed, H., Abu-Amara, H.: Perfectly Secure Message Transmission in Asynchronous Networks. In: Seventh IEEE Symposium on Parallel and Distributed Processing (1995)
Dolev, D., Dwork, C., Waarts, O., Yung, M.: Perfectly Secure Message Transmission. Journal of the Association for Computing Machinery (JACM) 40(1), 17–47 (1993)
Nayak, M., Agrawal, S., Srinathan, K.: Minimal connectivity for unconditionally secure message transmission in synchronous directed networks. In: Fehr, S. (ed.) ICITS 2011. LNCS, vol. 6673, pp. 32–51. Springer, Heidelberg (2011)
Menger, K.: Zur allgemeinen kurventheorie. Fundamenta Mathematicae 10, 96–115 (1927)
Kurosawa, K., Suzuki, K.: Truly efficient 2-round perfectly secure message transmission scheme. IEEE Trans. Inf. Theor. 55(11), 5223–5232 (2009)
Badanidiyuru, A., Patra, A., Choudhury, A., Srinathan, K., Rangan, C.P.: On the trade-off between network connectivity, round complexity, and communication complexity of reliable message transmission. J. ACM 59(5), 22 (2012)
Fitzi, M., Franklin, M.K., Garay, J.A., Vardhan, S.H.: Towards optimal and efficient perfectly secure message transmission. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 311–322. Springer, Heidelberg (2007)
Renault, J., Renou, L., Tomala, T.: Secure message transmission on directed networks. Games and Economic Behavior 85, 1–18 (2014)
Kumar, M.V.N.A., Goundan, P.R., Srinathan, K., Pandu Rangan, C.: On perfectly secure communication over arbitrary networks. In: Proceedings of the 21st Symposium on Principles of Distributed Computing (PODC), Monterey, California, USA, pp. 193–202. ACM Press (July 2002)
Diffie, W., Hellman, M.E.: New Directions in Cryptography. IEEE Transactions on Information Theory IT-22, 644–654 (1976)
Desmedt, Y.G., Wang, Y.: Perfectly Secure Message Transmission Revisited. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 502–517. Springer, Heidelberg (2002)
Srinathan, K., Rangan, C.P.: Possibility and complexity of probabilistic reliable communications in directed networks. In: Proceedings of 25th ACM Symposium on Principles of Distributed Computing, PODC 2006 (2006)
Franklin, M.K., Yung, M.: Communication complexity of secure computation (extended abstract). In: Kosaraju, S.R., Fellows, M., Wigderson, A., Ellis, J.A. (eds.) Proceedings of the 24th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 4-6, pp. 699–710. ACM (1992)
Shamir, A.: How to Share a Secret. Communications of the ACM 22, 612–613 (1979)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press (2009)
Endre Tarjan, R.: Testing graph connectivity. In: Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, STOC 1974, pp. 185–193. ACM, New York (1974)
Goldberg, A.V., Tarjan, R.E.: A new approach to the maximum flow problem. Journal of the ACM 35, 921–940 (1988)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Kishore, R., Kumar, A., Vanarasa, C., Kannan, S. (2015). Round-Optimal Perfectly Secret Message Transmission with Linear Communication Complexity. In: Lehmann, A., Wolf, S. (eds) Information Theoretic Security. ICITS 2015. Lecture Notes in Computer Science(), vol 9063. Springer, Cham. https://doi.org/10.1007/978-3-319-17470-9_3
Download citation
DOI: https://doi.org/10.1007/978-3-319-17470-9_3
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-17469-3
Online ISBN: 978-3-319-17470-9
eBook Packages: Computer ScienceComputer Science (R0)