(Secure) Linear network coding multicast

详细信息    查看全文

• 作者：Christina Fragouli ; Emina Soljanin
• 关键词：Network coding ; Multicast ; Eavesdropping ; MDS codes ; Deterministic networks ; 00 ; 02 ; 11T71 ; 68P30 ; 94B05 ; 94B99
• 刊名：Designs, Codes and Cryptography
• 出版年：2016
• 出版时间：January 2016
• 年：2016
• 卷：78
• 期：1
• 页码：269-310
• 全文大小：1,093 KB
• 参考文献：1.Ahlswede R., Cai N., Li S.-Y.R., Yeung R.W.: Network information flow. IEEE Trans. Inf. Theory 46, 1204–1216 (2000).
  2.Amaudruz A., Fragouli C.: Combinatorial algorithms for wireless information flow. In: SODA (2009).
  3.Avestimehr A.S., Diggavi S.N., Tse D.N.C.: Wireless network information flow: a deterministic approach. IEEE Trans. Inf. Theory 57(4), 1872–1905 (2011).
  4.Bellovin S.M.: Frank Miller: inventor of the one-time pad. Cryptologia 35(3), 203–222 (2011).
  5.Bondy J.A., Murty U.S.R.: Graph theory with applications. North-Holland, Amsterdam (1979).
  6.Cai N., Yeung R.W.: Secure network coding. In: Proceedings of 2002 IEEE International Symposium on Information Theory (ISIT’02) (2002).
  7.Cheng F., Yeung R.W.: Performance bounds on a wiretap network with arbitrary wiretap sets. IEEE Trans. Inf. Theory 60(6), 3345–3358 (2014).
  8.Csiszár I., Narayan P.: Secrecy capacities for multi terminal channel models. IEEE Trans. Inf. Theory 54(6), 2437–2452 (2008).
  9.Cui T.: Coding for wireless broadcast and network secrecy. PhD Thesis, California Institute of Technology (2010).
  10.Cui T., Ho T., Kliewer J.: Achievable strategies for general secure network coding. In: Proceedings of Information Theory and Applications Workshop (ITA), pp. 1–6 (2010).
  11.Cui T., Ho T., Kliewer J.: On secure network coding with unequal link capacities and restricted wiretapping sets. In: Proceedings of IEEE Information Theory Workshop (ITW) (2010).
  12.Cui T., Ho T., Kliewer J.: On secure network coding with nonuniform or restricted wiretap sets. IEEE Trans. Inf. Theory 59(1), 166–176 (2013).
  13.Czap L., Prabhakaran V.M., Fragouli C., Diggavi S.: Secret message capacity of erasure broadcast channels with feedback. In: Proceedings of Information Theory Workshop (ITW), pp. 65–69 (2011).
  14.Czap L., Prabhakaran V.M., Diggavi S., Fragouli C.: Broadcasting private messages securely. In: Proceedings of International Symposium on Information Theory (ISIT), pp. 428–432. IEEE (2012).
  15.Czap L., Prabhakaran V.M., Diggavi S., Fragouli C.: Exploiting common randomness: a resource for network secrecy. In: Proceedings of Information Theory Workshop (ITW), pp. 1–5 (2013).
  16.Czap L., Prabhakaran V.M., Diggavi S., Fragouli C.: Secure network coding with erasures and feedback. In: Proceedings of Annual Allerton Conference on Communication, Control, and Computing (2013).
  17.Czap L., Prabhakaran V.M., Diggavi S., Fragouli C.: Triangle network secrecy. In: Proceedings of International Symposium on Information Theory (ISIT), pp. 781–785 (2014).
  18.Czap L., Fragouli C., Prabhakaran V., Diggavi S.: Secure network coding with erasures and feedback. IEEE Trans. Inf. Theory 61(4), 1667–1686 (2015)
  19.Dau S.H., Song W., Yuen C.: On the existence of MDS codes over small fields with constrained generator matrices. In: IEEE International Symposium on Information Theory (ISIT), 2014, pp. 1787–1791 (2014).
  20.Diggavi S.N., Avestimehr S., Tse D.N.C.: A deterministic approach to wireless relay networks. In: Proceedings of Allerton Conference on Communication, Control, and Computing (2007).
  21.Diggavi S.N., Avestimehr S., Tse D.N.C.: Wireless network information flow. In: Proceedings of Allerton Conference on Communication, Control, and Computing (2007).
  22.Diggavi S.N., Avestimehr S., Tse D.N.C.: Approximate capacity of gaussian relay networks. In: IEEE International Symposium on Information Theory (ISIT) (2008).
  23.Ebrahimi J., Fragouli C.: Multicasting algorithms for deterministic networks. In: Information Theory Workshop (ITW) (2010).
  24.Ebrahimi J., Fragouli C.: On the benefits of vector network coding. In: IEEE Allerton Conference on Communications, Control and Computing (2010).
  25.Ebrahimi J., Fragouli C.: Vector network coding. In: IEEE International Symposium on Information Theory (ISIT) (2010).
  26.Ebrahimi J., Fragouli C.: Algebraic algorithms for vector network coding. IEEE Trans. Inf. Theory, 57(2), pp. 1046–1066 (2011).
  27.Ebrahimi J., Fragouli C.: Combinatorial algorithms for wireless information flow. ACM Trans. Algorithms. doi:10.​1137/​1.​9781611973068.​61
  28.Ebrahimi J., Fragouli C.: Properties of network polynomials. In: IEEE International Symposium on Information Theory (ISIT), 2014 (2012).
  29.El Rouayheb S., Soljanin E.: On wiretap networks II. In: Proceedings of International Symposium on Information Theory (ISIT) (2007).
  30.El Rouayheb S., Soljanin E., Sprintson A.: Secure network coding for wiretap networks of type II. IEEE Trans. Inf. Theory 58(3), 1361–1371 (2012).
  31.Feldman J., Malkin T., Stein C., Servedio R.A.: On the capacity of secure network coding. In: Proceedings of 42nd Annual Allerton Conference on Communication, Control, and Computing (2004).
  32.Fragouli C., Soljanin E.: Information flow decomposition for network coding. IEEE Trans. Inf. Theory 52(3), 829–848 (2006).
  33.Gessel I.M., Viennot X.: Determinants, paths and plane partitions (1989) (preprint). http://​pfeinsil.​math.​siu.​edu/​MATH/​MatrixTree/​gesseldeterminan​ts_​paths_​and_​plane_​partitions.​pdf
  34.Halbawi W., Ho T., Hongyi Y., Duursma I.: Distributed Reed–Solomon codes for simple multiple access networks. In: Proceedings of IEEE International Symposium on Information Theory (ISIT’14), pp. 651–655 (2014).
  35.Huang W., Ho T., Langberg M., Kliewer J.: On secure network coding with uniform wiretap sets. In: Proceedings of IEEE International Symposium on Network Coding (NetCod) (2013).
  36.Iwata S., Goemans M., Zenklusen R.: An algorithmic framework for wireless information flow. Allerton, New York (2009).
  37.Jafari Siavoshani, M., Diggavi, S., Fragouli, C., Kiran Pulleti, U., Argyraki, K.: Group secret key generation over broadcast erasure channels. In: Proceedings of Asilomar Conference on Signals, Systems, and Computers, pp. 719–723 (2010).
  38.Jaggi S., Cassuto Y., Effros M.: Low complexity encoding for network codes. In: International Symposium on Information Theory (ISIT) (2006).
  39.Kim M., Medard M.: Algebraic network coding approach to deterministic wireless relay networks. arXiv:​1001.​4431 .
  40.Koetter R., Médard M.: An algebraic approach to network coding. IEEE/ACM Trans. Netw. 11(5), 782–795 (2003).
  41.Leung-Yan-Cheong S., Hellman M.E.: The Gaussian wire-tap channel. IEEE Trans. Inf. Theory 24(4), 451–456 (1978).
  42.Liang Y., Poor H.V., Shamai S.: Information theoretic security. Found. Trends Commun. Inf. Theory 5(4–5), 355–580 (2009).
  43.Maurer U.: Secret key agreement by public discussion from common information. IEEE Trans. Inf. Theory 39(3), 733–742 (1993).
  44.Maurer U., Wolf S.: Information-theoretic key agreement: from weak to strong secrecy for free. In: Proceedings of International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), pp. 351–368. Springer, Berlin (2000).
  45.Mishra S., Fragouli C., Prabhakaran V., Diggavi S.: Using feedback for secrecy over graphs. http://​arxiv.​org/​pdf/​1305.​3051.​pdf .
  46.Ozarow L.H., Wyner A.D.: The wire-tap channel II. Bell Syst. Tech. J. 63, 2135–2157 (1984).
  47.Papadopoulos A., Czap L., Fragouli C.: Secret message capacity of a line network. In: Annual Allerton Conference on Communication, Control and Computing (Allerton) (2014).
  48.Papadopoulos A., Czap L., Fragouli C.: Lp formulations for secrecy over erasure networks with feedback. In: International Symposium on Information Theory (ISIT) (2015).
  49.Shannon C.: Communication theory of secrecy systems. Bell Syst. Tech. J. 28, 656–715 (1949).
  50.Shi C., Ramamoorthy A.: Fast algorithms for finding unicast capacity of linear deterministic wireless relay networks. CoRR, abs/0909.5507 (2009).
  51.Silva D., Kschischang F.R.: Security for wiretap networks via rank-metric codes. In: Proceedings of IEEE International Symposium on Information Theory (ISIT), pp. 176–180 (2008).
  52.Silver D.S., Kovacs I., Williams S.G.: Determinants of commuting-block matrices. Am. Math. Mon. 106(10), 950–952 (1999).
  53.Sun Q., Yang X., Long K., Li Z.: Constructing multicast networks where vector linear coding outperforms scalar linear coding. In: International Symposium on Information Theory (ISIT) (2015).
  54.Tabatabaei Yazdi S., Savari S.: A combinatorial study of linear deterministic relay networks. arXiv:​0909.​5507v1 (2011).
  55.Wyner A.D.: The wire-tap channel. Bell Syst. Tech. J. 54(8), 1355–1387 (1975).
  56.Yan M., Sprintson A.: Algorithms for weakly secure data exchange. In: Proceedings of 2013 International Symposium on Network Coding (NetCod), pp. 1–6 (2013).
  57.Yan M., Sprintson A., Zelenko I.: Weakly secure data exchange with generalized reed solomon codes. In: Proceedings of 2014 IEEE International Symposium on Information Theory (ISIT), pp. 1366–1370 (2014).
  58.Yeung R.W., Cai N.: On the optimality of a construction of secure network codes. In: IEEE International Symposium on Information Theory (ISIT), pp. 166–170 (2008).
  
• 作者单位：Christina Fragouli (1)
  Emina Soljanin (2)
  
  1. UCLA, Los Angeles, CA, USA
  2. Bell Labs, Murray Hill, NJ, USA
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Coding and Information Theory
  Data Structures, Cryptology and Information Theory
  Data Encryption
  Discrete Mathematics in Computer Science
  Information, Communication and Circuits
  
• 出版者：Springer Netherlands
• ISSN：1573-7586

文摘

We introduce network coding in an elementary way, through a combinatorial/algebraic framework, and discuss connections with classical coding theory. We also present a selection of emerging areas and long-standing open problems. Keywords Network coding Multicast Eavesdropping MDS codes Deterministic networks