Abstract
Secure message transmission (SMT) is a two-party protocol between a sender and a receiver over a network in which the sender and the receiver are connected by n disjoint channels and t out of n channels can be controlled by an adaptive adversary with unlimited computational resources. If a public discussion channel is available to the sender and the receiver to communicate with each other then a secure and reliable communication is possible even when n ≥ t + 1. The round complexity is one of the important measures for the efficiency for SMT. In this paper, we revisit the optimality and the impossibility for SMT with public discussion and discuss the limitation of SMT with the “unidirectional” public channel, where either the sender or the receiver can invoke the public channel, and show that the “bidirectional” public channel is necessary for SMT.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Araki, T.: Almost secure 1-round message transmission scheme with polynomial-time message decryption. In: Safavi-Naini, R. (ed.) ICITS 2008. LNCS, vol. 5155, pp. 2–13. Springer, Heidelberg (2008)
Agarwal, S., Cramer, R., de Haan, R.: Asymptotically optimal two-round perfectly secure message transmission. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 394–408. Springer, Heidelberg (2006)
Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation. In: Proc. 20th Annual ACM Symposium on Theory of Computing, pp. 1–10 (1988)
Berman, P., Garay, J.A.: Fast consensus in networks of bounded degree. Distributed Computing 2(7), 62–73 (1993)
Chandran, N., Garay, J.A., Ostrovsky, R.: Improved fault tolerance and secure computation on sparse networks. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010 (Part 2). LNCS, vol. 6199, pp. 249–260. Springer, Heidelberg (2010)
Chaum, D., Crépeau, C., Damgård, I.: Multiparty unconditionally secure protocols. In: Proc. 20th Annual ACM Symposium on Theory of Computing, pp. 11–19 (1988)
Dolev, D., Dwork, C., Waarts, O., Yung, M.: Perfectly secure message transmission. J. ACM 40(1), 17–47 (1993)
Dwork, C., Peleg, D., Pippenger, N., Upfal, E.: Fault tolerance in networks of bounded degree. SIAM J. Comput. 17(5), 975–988 (1988)
Desmedt, Y., Wang, Y.: Perfectly secure message transmission revisited. IEEE Trans. Information Theory 54(6), 2582–2595 (2008)
Fitzi, M., Franklin, M.K., Garay, J.A., Simhadri, H.V.: Towards optimal and efficient perfectly message transmission. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 311–322. Springer, Heidelberg (2007)
Franklin, M.K., Wright, R.N.: Secure communication in minimal connectivity models. J. Cryptology 13(1), 9–30 (2000)
Garay, J.A., Ostrovsky, R.: Almost-everywhere secure computation. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 307–323. Springer, Heidelberg (2008)
Garay, J.A., Givens, C., Ostrovsky, R.: Secure message transmission with small public discussion. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 177–196. Springer, Heidelberg (2010)
Kurosawa, K., Suzuki, K.: Truly efficient 2-round perfectly secure message transmission scheme. IEEE Transactions on Information Theory 55(11), 5223–5232 (2009)
Kurosawa, K., Suzuki, K.: Almost secure (1-round, n-channel) message transmission scheme. IEICE Trans. Fundamentals of Electronics Communications and Computer Sciences E92-A(1), 105–112 (2009)
Rabin, T., Ben-Or, M.: Verifiable secrete sharing and multiparty protocols with honest majority. In: Proc. 21st Annual ACM Symposium on Theory of Computing, pp. 73–85 (1989)
Sayeed, H., Abu-Amara, H.: Efficient perfectly secure message transmission in synchronous networks. Information and Computation 126(1), 53–61 (1996)
Shi, H., Jiang, S., Safavi-Naini, R., Tuhin, M.A.: Optimal secure message transmission by public discussion. In: Proc. IEEE International Symposium on Information Theory 2009, pp. 1313–1317 (2009)
Srinathan, K., Narayanan, A., Rangan, C.P.: Optimal perfectly secure message transmission. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 545–561. Springer, Heidelberg (2004)
Srinathan, K., Patra, A., Choudhary, A., Rangan, C.P.: Probabilistic perfectly reliable and secure message transmission — possibility, feasibility and optimality. In: Srinathan, K., Rangan, C.P., Yung, M. (eds.) INDOCRYPT 2007. LNCS, vol. 4859, pp. 101–122. Springer, Heidelberg (2007)
Upfal, E.: Tolerating a linear number of faults in networks of bounded degree. Information and Computation 115(2), 312–320 (1994)
Wegman, M., Carter, J.: New hash functions and their use in authentication and set equality. J. Computer and System Sciences 22(2), 265–279 (1981)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Koshiba, T., Sawada, S. (2011). Public Discussion Must Be Back and Forth in Secure Message Transmission. In: Rhee, KH., Nyang, D. (eds) Information Security and Cryptology - ICISC 2010. ICISC 2010. Lecture Notes in Computer Science, vol 6829. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-24209-0_22
Download citation
DOI: https://doi.org/10.1007/978-3-642-24209-0_22
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-24208-3
Online ISBN: 978-3-642-24209-0
eBook Packages: Computer ScienceComputer Science (R0)