On the equivalency of reliability and security metrics for wireline networks

Document Type : Article

Authors

Information Systems and Security Lab. (ISSL), Sharif University of Technology, Tehran, P.O. Box 11155-8639, Iran.

Abstract

In this paper, we consider a secure network coding problem in which some secret keys are shared among legitimate nodes, and there exists an eavesdropper which is able to hear a subset of links. We show the equivalency of secure network coding under weak and strong secrecy conditions. For linear network coding, we show a stronger result: equivalency of "perfect secrecy and zero-error constraints" to "weak secrecy and $\epsilon$-error constraints". This is a secure version of the result obtained by Langberg and Effros, on the equivalence of zero-error and $\epsilon$-error regions in the network coding problem with co-located sources. Jalali and Ho exploit extractor functions to prove the weak and strong rate region equivalency for this network; however, to prove this equivalency, we develop some tools in random binning and prove the equivalency in a slightly more general setting.

Keywords

Main Subjects


1. Shannon, C.E. The zero error capacity of a noisy channel", Information Theory, IRE Transactions on, 2(3), pp. 8-19 (1956). 2. Langberg, M. and E_ros, M. Network coding: Is zero error always possible?", In Communication, Control, and Computing (Allerton), 2011 49th Annual Allerton Conference on, pp. 1478-1485, IEEE (2011). 3. Chan, T. and Grant, A. On capacity regions of non-multicast networks", In 2010 IEEE International Symposium on Information Theory, pp. 2378-2382, IEEE (2010). 4. Maurer, U. and Wolf, S. Information-theoretic key agreement: From weak to strong secrecy for free", In Advances in Cryptology-EUROCRYPT 2000, pp. 351- 368, Springer (2000). 5. Jalali, S. and Ho, T. On capacity region of wiretap networks", arXiv preprint arXiv:1212.3859 (2012). 6. Mojahedian, M.M., Gohari, A., and Aref, M.R. Perfectly secure index coding", Information Theory, IEEE Transactions on, 63(11), pp. 7382-7395 (2017). 7. Cai, N. and Yeung, R.W. Secure network coding", In Information Theory, 2002. Proceedings. 2002 IEEE International Symposium on, p. 323, IEEE (2002). 8. Cheng, F. and Yeung, R.W. Performance bounds on a wiretap network with arbitrary wiretap sets", IEEE Transactions on Information Theory, 60(6), pp. 3345- 3358 (2014). 9. Cui, T., Ho, T., and Kliewer, J. Achievable strategies for general secure network coding", In Information Theory and Applications Workshop (ITA), 2010, pp. 1-6, IEEE (2010). 10. Cui, T., Ho, T., and Kliewer, J. On secure network coding with nonuniform or restricted wiretap sets", IEEE Transactions on Information Theory, 59(1), pp. 166-176 (2013). 11. Czap, L., Fragouli, C., Prabhakaran, V.M., and Diggavi, S. Secure network coding with erasures and feedback", IEEE Transactions on Information Theory, 61(4), pp. 1667-1686 (2015). 12. El Rouayheb, S., Soljanin, E., and Sprintson, A. Secure network coding for wiretap networks of type ii", IEEE Transactions on Information Theory, 58(3), pp. 1361-1371 (2012). 13. Feldman, J., Malkin, T., Stein, C., and Servedio, R.A. On the capacity of secure network coding", In Proc. 42nd Annual Allerton Conference on Communication, Control, and Computing, pp. 63-68 (2004). 14. Huang, W., Ho, T., Langberg, M., and Kliewer, J. On secure network coding with uniform wiretap sets", In 2013 International Symposium on Network Coding (NetCod), pp. 1-6, IEEE (2013). 15. Mishra, S., Fragouli, C., Prabhakaran, V., and Diggavi, S. Using feedback for secrecy over graphs", In Information Theory Proceedings (ISIT), 2013 IEEE International Symposium on, IEEE, pp. 2399-2403 (2013). 16. Silva, D. and Kschischang, F.R. Security for wiretap networks via rank-metric codes", In 2008 IEEE International Symposium on Information Theory, IEEE, pp. 176-180 (2008). 17. Fragouli, C. and Soljanin, E. (Secure) linear network coding multicast", Designs, Codes and Cryptography, 78(1), pp. 269-310 (2016). 18. Dau, S.H., Skachek, V., and Chee, Y.M. On secure index coding with side information", In Information Theory Proceedings (ISIT), 2011 IEEE International Symposium on, IEEE, pp. 983-987 (2011). 19. Yassaee, M.H., Aref, M.R., and Gohari, A. Achievability proof via output statistics of random binning", Information Theory, IEEE Transactions on, 60(11), pp. 6760-6786 (2014). 20. Csisz_ar, I. and Narayan, P. Secrecy capacities for multiple terminals", IEEE Transactions on Information Theory, 50(12), pp. 3047-3061 (2004). 21. Steinberg, Y. and Verdu, S. Channel simulation and coding with side information", IEEE Transactions on Information Theory, 40(3), pp. 634-646 (1994). 22. Csisz_ar, I. Linear codes for sources and source networks: Error exponents, universal coding", IEEE M.M. Mojahedian et al./Scientia Iranica, Transactions D: Computer Science & ... 26 (2019) 1749{1761 1761 Transactions on Information Theory, 28(4), pp. 585- 592 (1982). 23. Slepian, D. andWolf, J. Noiseless coding of correlated information sources", IEEE Transactions on information Theory, 19(4), pp. 471-480 (1973). 24. Blake, I.F. and Studholme, C. Properties of random matrices and applications", Unpublished report available at www.cs.toronto.edu/~cvs/coding/random report. pdf (2006). 25. Pardo Llorente, M.D.C. and Vajda, I. About distances of discrete distributions satisfying the data processing theorem of information theory", IEEE Transactions on Information Theory, 43(4), pp. 1288- 1293 (1997). 26. Shannon, C.E. Communication theory of secrecy systems", Bell System Technical Journal, 28(4), pp. 656-715 (1949). 27. Birk, Y. and Kol, T. Informed-source coding-ondemand (ISCOD) over broadcast channels", In INFOCOM' 98. Seventeenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings, IEEE, 3, pp. 1257-1264 (1998). 28. Lubetzky, E. and Stav, U. Nonlinear index coding outperforming the linear optimum", Information Theory, IEEE Transactions on, 55(8), pp. 3544-3551 (2009). 29. Alon, N., Lubetzky, E., Stav, U., Weinstein, A., and Hassidim, A. Broadcasting with side information", In Foundations of Computer Science, 2008. FOCS'08. IEEE 49th Annual IEEE Symposium on, pp. 823-832, IEEE (2008). 30. Bar-Yossef, Z., Birk, Y., Jayram, T., and Kol, T. Index coding with side information", Information Theory, IEEE Transactions on, 57(3), pp. 1479-1494 (2011). 31. Tehrani, A.S., Dimakis, A.G., and Neely, M.J. Bipartite index coding", In Information Theory Proceedings (ISIT), 2012 IEEE International Symposium on, pp. 2246-2250, IEEE (2012). 32. Blasiak, A., Kleinberg, R., and Lubetzky, E. Broadcasting with side information: Bounding and approximating the broadcast rate", Information Theory, IEEE Transactions on, 59(9), pp. 5811-5823 (2013). 33. Blasiak, A., Kleinberg, R., and Lubetzky, E. Index coding via linear programming", arXiv preprint arXiv:1004.1379 (2010). 34. Arbabjolfaei, F., Bandemer, B., Kim, Y.-H., Sasoglu, E., and Wang, L. On the capacity region for index coding", In Information Theory Proceedings (ISIT), 2013 IEEE International Symposium on, IEEE, pp. 962-966 (2013). 35. Shanmugam, K., Dimakis, A.G., and Langberg, M. Graph theory versus minimum rank for index coding", arXiv preprint arXiv:1402.3898 (2014). 36. Neely, M.J., Tehrani, A.S., and Zhang, Z. Dynamic index coding for wireless broadcast networks", In INFOCOM, 2012 Proceedings IEEE, pp. 316-324, (2012).