安全网络编码的研究
|
摘要
网络编码的出现打破了通信网所遵循的传统的基本操作规则——存储转发模式。它不仅仅让网络节点保留这个原始的功能,而且允许网络节点进行编码,极大地提高了网络的传输容量,从而达到了香农最大流最小割定理规定的上界,而传统路由器的存储转发模式根本不可能达到这个上界的。网络编码的理论创新具有普遍意义,应用前景十分广阔,因而近年来,网络编码的理论及应用在信息论、编码理论、网络交换、无线通信、计算机科学、信息安全、运筹学、矩阵理论以及许多其他学科领域,都受到人们的普遍关注。
虽然网络编码的初衷在于提高网络的吞吐量,然而随着进一步研究发现它也是一种构造安全网络传输的比较好方式。所以,随着网络编码的出现,在理论的研究上,网络编码越来越被人们应用于网络安全中。具体来说,网络编码在执行过程中伪装了数据,并且能有效地承载数据,所以实际上增强了信息的安全性,要比在网络上传输不可破译的算法流的传统加密技术更安全。比如有两个位组A和B,对两个位组执行异或操作,从得出的结果中,哪个位组的数据你都看不到。你可能知道其中的某些位的值,但你却不可能还原位组A的数据,除非你完全知道位组B的数据。
本论文首先对网络编码的基本理论进行详细地介绍,然后在充分掌握了网络编码的各种基本理论知识后,作者重点对安全网络编码进行深入地研究。
首先,以无延迟线性通信网络为基础,介绍网络窃听模型。其次,根据Kamal Jain提出的单信源单信宿网络的编码安全定理,设计了一种寻找安全路径的算法,并给出这种简单网络安全网络编码构造实例,同时提出窃听矩阵的概念。再次,详细分析单信源多信宿网络的安全网络编码的情况;通过一个反例,得出不能将单信源单信宿网络编码的安全条件单纯地直接“复制”到单信源多信宿网络中;但是如果窃听集中的边对应于网络路径类集F中的边不相交的路径数量小于网络的最大传输容量,那么网络就是安全的。由此,作者初步给出了单信源多信宿网络的编码条件较宽的安全定理,并加以证明。在证明过程中,作者引用了前面已定义的窃听矩阵的概念,最终得出一个条件更紧的单信源多信宿网络编码的安全定理,即如果窃听集对应的窃听矩阵的秩小于最大传输容量,经过合适的编码,就能够保证在网络中安全传输消息,而窃听者获得不了任何有用的信息;最后,比较了编码节点处使用纯随机数和伪随机函数的情况,得出在节点处使用伪随机函数更能增强网络的安全性和鲁棒性。
The advent of network coding broke the traditional basic operating regulation that was the pattern of storage and forwarding followed by communication network. Network coding not only reserved original function at network nodes, but also allowed coding at network nodes, which increased the transmitting capacity of the network greatly, and achieved the upper bound prescribed by the Shannon Max-Flow Min-Cut Theorem, while just used the traditional pattern of storage and forwarding at network codes reached this max-flow bound impossibly at all. Moreover, the theory innovation of network coding had pervasive significance, and its application foreground was extensive thoroughly, therefore, in recent years, network coding was a very attractive interdisciplinary study area that poses interesting questions across diverse areas such as information theory, coding theory, network switching, wireless communications, computer sciences, information security, operational research, matrix theory and so on.
The original intention of network coding was improving the throughput of the network; however, it was found that network coding was a better method for constructing secure network transmission in the further study. Thus, with the advent of network coding, network coding was applied network security increasingly in the academic study. Concretely, network coding can hide and bear the weight of data in the executed process, so it enhanced the information's security, which was safer than traditional encryption techniques used to encrypt the data in the network. For instance, there were two bit groups A and B, and the "exclusive or" operation was executed for A and B. From the results, those data of two bit groups can't be seen. Some bits of the data may be acquired, but the whole data of the bit group A can't be reverted, unless the data of the bit group B was completely captured.
The basic theory of network coding was introduced detailedly at beginning, and then after mastering various basic academic knowledge of network coding, the author made a deep research on secure network coding.
Firstly, based on the free delay linear communications network, the CSWN was introduced. Secondly, the security theorem of the single source and single sink network coding was displayed, which was mentioned by Kamal Jain. Based on this theorem, a kind of arithmetic that searching a security path was designed and an example was given, while a new concept that wiretap matrix was proposed by author. Thirdly, the author analyzed the situation of the secure coding of the single source and multi-sink network detailedly. After a counterexample was analyzed, the author found that the security condition of the single source and single sink network coding can't be directly "copy" to the single source and multi-sink network. However, if the number of edge disjoint paths in the collection of network path corresponding to all the edges in the wiretap set was less than the max-flow value, the network was safe. And a wider secure theorem of the single source and multi-sink network was proposed and proved. In the proof process, the wiretap matrix was quoted. And in the end, a tighter secure theorem of the single source and multi-sink network was elicited that if the rank of wiretap matrix was less than the max-flow value, the wire taper does not get any useful information about the message bit. Finally, the author compared the situation of using the pure random number on coding nodes with using the pseudo random function, and educed that it's better to use the pseudo random function to make the network safer and stronger.
虽然网络编码的初衷在于提高网络的吞吐量,然而随着进一步研究发现它也是一种构造安全网络传输的比较好方式。所以,随着网络编码的出现,在理论的研究上,网络编码越来越被人们应用于网络安全中。具体来说,网络编码在执行过程中伪装了数据,并且能有效地承载数据,所以实际上增强了信息的安全性,要比在网络上传输不可破译的算法流的传统加密技术更安全。比如有两个位组A和B,对两个位组执行异或操作,从得出的结果中,哪个位组的数据你都看不到。你可能知道其中的某些位的值,但你却不可能还原位组A的数据,除非你完全知道位组B的数据。
本论文首先对网络编码的基本理论进行详细地介绍,然后在充分掌握了网络编码的各种基本理论知识后,作者重点对安全网络编码进行深入地研究。
首先,以无延迟线性通信网络为基础,介绍网络窃听模型。其次,根据Kamal Jain提出的单信源单信宿网络的编码安全定理,设计了一种寻找安全路径的算法,并给出这种简单网络安全网络编码构造实例,同时提出窃听矩阵的概念。再次,详细分析单信源多信宿网络的安全网络编码的情况;通过一个反例,得出不能将单信源单信宿网络编码的安全条件单纯地直接“复制”到单信源多信宿网络中;但是如果窃听集中的边对应于网络路径类集F中的边不相交的路径数量小于网络的最大传输容量,那么网络就是安全的。由此,作者初步给出了单信源多信宿网络的编码条件较宽的安全定理,并加以证明。在证明过程中,作者引用了前面已定义的窃听矩阵的概念,最终得出一个条件更紧的单信源多信宿网络编码的安全定理,即如果窃听集对应的窃听矩阵的秩小于最大传输容量,经过合适的编码,就能够保证在网络中安全传输消息,而窃听者获得不了任何有用的信息;最后,比较了编码节点处使用纯随机数和伪随机函数的情况,得出在节点处使用伪随机函数更能增强网络的安全性和鲁棒性。
The advent of network coding broke the traditional basic operating regulation that was the pattern of storage and forwarding followed by communication network. Network coding not only reserved original function at network nodes, but also allowed coding at network nodes, which increased the transmitting capacity of the network greatly, and achieved the upper bound prescribed by the Shannon Max-Flow Min-Cut Theorem, while just used the traditional pattern of storage and forwarding at network codes reached this max-flow bound impossibly at all. Moreover, the theory innovation of network coding had pervasive significance, and its application foreground was extensive thoroughly, therefore, in recent years, network coding was a very attractive interdisciplinary study area that poses interesting questions across diverse areas such as information theory, coding theory, network switching, wireless communications, computer sciences, information security, operational research, matrix theory and so on.
The original intention of network coding was improving the throughput of the network; however, it was found that network coding was a better method for constructing secure network transmission in the further study. Thus, with the advent of network coding, network coding was applied network security increasingly in the academic study. Concretely, network coding can hide and bear the weight of data in the executed process, so it enhanced the information's security, which was safer than traditional encryption techniques used to encrypt the data in the network. For instance, there were two bit groups A and B, and the "exclusive or" operation was executed for A and B. From the results, those data of two bit groups can't be seen. Some bits of the data may be acquired, but the whole data of the bit group A can't be reverted, unless the data of the bit group B was completely captured.
The basic theory of network coding was introduced detailedly at beginning, and then after mastering various basic academic knowledge of network coding, the author made a deep research on secure network coding.
Firstly, based on the free delay linear communications network, the CSWN was introduced. Secondly, the security theorem of the single source and single sink network coding was displayed, which was mentioned by Kamal Jain. Based on this theorem, a kind of arithmetic that searching a security path was designed and an example was given, while a new concept that wiretap matrix was proposed by author. Thirdly, the author analyzed the situation of the secure coding of the single source and multi-sink network detailedly. After a counterexample was analyzed, the author found that the security condition of the single source and single sink network coding can't be directly "copy" to the single source and multi-sink network. However, if the number of edge disjoint paths in the collection of network path corresponding to all the edges in the wiretap set was less than the max-flow value, the network was safe. And a wider secure theorem of the single source and multi-sink network was proposed and proved. In the proof process, the wiretap matrix was quoted. And in the end, a tighter secure theorem of the single source and multi-sink network was elicited that if the rank of wiretap matrix was less than the max-flow value, the wire taper does not get any useful information about the message bit. Finally, the author compared the situation of using the pure random number on coding nodes with using the pseudo random function, and educed that it's better to use the pseudo random function to make the network safer and stronger.
引文
[1]殷剑宏,吴开亚,《图论及其算法》,中国科学技术大学出版社,2005年,P207-P225
[2]Ahlswede R.,Cai N.,Li S.-Y.R.,et al.,"Network information flow",IEEE Transactions on Information Theory,vol.46,no.4,August 2000,pp.1204-1216
[3]Koetter R.and Medard M.,"Beyond Routing:An algebraic Approach to network coding",in Proceedings of the 2002 TEEE Infocom,vol.1,November 2002,pp.122-130.
[4]Koetter R.and Medard M.,"An algebraic approach to network coding",IEEE/ACM Transactions on Networking,vol.11,no.5,October 2003,pp.782-795.
[5]Sanders P.,Egner S.,and Tolhuizen L.,"Polynomial time algorithms for network information flow",in 15~(th) ACM Symposium on Parallel Algorithms and Architectures(SPAA '03),San Diego,California,USA,June 2003,pp.286-294.
[6]Jaggi S.,Sander P.,Chou P.A.,et al.,"Polynomial time algorithms for network code construction",IEEE Transactions on Information Theory,vol.51,no.6,June 2005,pp.1973-1982
[7]Chou P.A.,Wu Y.,and Jain K.,"Practical network coding",in Proceedings of 41~(st) Annual Allerton Conference on Communication,Control,and Computing,October 2003.
[8]Ho Tracey,Karge D.r,Medard M.,et al..,"The benefits of coding over routing in a randomized setting",in IEEE International Symposium on Information Theory,June 2003,pp.442-447.
[9]Ho Tracey,Medard M.,Shi J.,et al.,"On Randomized Network Coding",in Proceedings of 41~(st) Annual Allerton Conference on Communication Control and Computing,October 2003.
[10]Li S.-Y.R.,Yueng R.W,and Cai N.,"Linear network coding",IEEE Transactions on Information Theory,vol.49,no.2,February.2003,pp.371-381.
[11]Effros M.,Medard M.,Ho Tracey,et al.,"Linear Network Codes:A Unified Framework for Source,Channel,and Network Coding",DIMACS(Series in Discrete Mathematics and Theoretical Computer Science),vol.66,Workshop on Network Information Theory,American Mathematical Society,2004,pp.197-216
[12]Dougherty R.,Freiling C.,and Zeger K.,"Linearity and Solvability in Multicast Networks",IEEE Transactions on Information Theory,vol.50,no.10,October 2004,pp.2243-2256
[13]S.Riis.,"Linear versus non-linear boolean functions in network flow[A]",in 38th Annual Conference on Information Science and Systems(CISS),Princeton,NJ,March 2004.
[14]Medard M.,Effros M.,Karger David,et al.,"On Coding for Non-multicast Networks",in Proceedings of 41~(st) Annual Allerton Conference on Communication Control and Computing,Monticello,Illinois,October 2003.
[15]Dougherty Randall,Freiling Chris,and Zeger Kenneth,"Insufficiency of Linear Coding in Network Information Flow",IEEE Transactions on Information Theory,vol.51,no.8,August 2005,pp.2745-2759.
[16]CAIN.and Yeung R.W.,"Secure network coding",in IEEE International Symposium on Information Theory,Lausanne,Switzerland,June 2002,pp.323.
[17]Jain K.,"Security based on network topology against the wiretapping attack",IEEE Wireless Communications,vol.11,no.1,February 2004,pp.68-71.
[18]Bhattad Kapil and Narayanan Krishna R.,"Weakly Secure Network Coding",in Proc.First Workshop on Network Coding Theory,and Applications(Netcod),Italy,April 2005.
[19]Ho Tracey,Leong Ben,Koetter Ralf,et al.,"Byzantine modification detection in multicast networks using randomized network coding",in International Symposium on Information Theory(ISIT),27 June-2 July 2004,pp.144-.
[20]Chou Philip A.and Wu Yunnan,"Network Coding for the Internet and Wireless Networks",Microsoft Research,TechReport,MSR-TR-2007-70,June 2007
[21]Petrovi(?),D.,Ramchandran,K.and Rabaey J.Riva,"Overcoming Untuned Radios in Wireless Networks with Network Coding",IEEE Transactions on Information Theory,vol.52,no.6,June 2006,pp.2649-2657
[22]Dimakis,A.G.,Prabhakaran,V.and Ramchandran,K.,"Decentralized Erasure Codes for Distributed Networked Storage",IEEE Transactions on Information Theory,vol.52,no.6,June 2006,pp.2809-2816.
[23]Yeung R.W.,Li S.-Y.R.,Cai Ning,et al.,"Network Coding Theory",now Publishers Inc.,USA,2006,pp.11-20
[24]Ho Tracey,Mrdard Muriel,Koetter Ralf,et al.,"A Random Linear Network Coding Approach to Multicast",IEEE Transactions On Information Theory,vol.52,no.10,October 2006,pp.4413-4430
[25]Castro M and Liskov B,"Practical byzantine fault tolerance",in Proceedings of 3rd USENIX Symposium on Operating Systems Design and Implementation (OSDI'99),New Orleans,LA,SA,February 1999
[26]Kihlstrom K.P.,Moser L.E.and Melliar-Smith P.M.,"The SecureRing protocols for securing group communication",in Proceedings of the 31st Annual Hawaii International Conference on System Sciences(HICSS'98),IEEE Computer Society Press,vol.3,1998,pp.317-326
[27]Cai Ning,Yeung R.W.,"A Security Condition for Multi-Source Linear Network Coding",in IEEE International Symposium on Information Theory,June 2007,pp.561-565
[28]Tan Jianlong,M(?)dard Muriel,"Secure Network Coding with a Cost Criterion"_in International Symposium on IEEE Modeling and Optimization in Mobile,Ad Hoc and Wireless Networks,April 2006,pp.1-6.
[29]Chan Terence and Grant A."Capacity Bounds for Secure Network Coding",IEEE Communications Theory Workshop,2008.AusCTW 2008,February 2008,pp.95-100
[30]Feldman Jon,Malkin Tal,Servedio Rocco A.,et al,"On the Capacity of Secure Network Coding",in 42nd Annual Allerton Conference on Communication,Control,and Computing,2004
[2]Ahlswede R.,Cai N.,Li S.-Y.R.,et al.,"Network information flow",IEEE Transactions on Information Theory,vol.46,no.4,August 2000,pp.1204-1216
[3]Koetter R.and Medard M.,"Beyond Routing:An algebraic Approach to network coding",in Proceedings of the 2002 TEEE Infocom,vol.1,November 2002,pp.122-130.
[4]Koetter R.and Medard M.,"An algebraic approach to network coding",IEEE/ACM Transactions on Networking,vol.11,no.5,October 2003,pp.782-795.
[5]Sanders P.,Egner S.,and Tolhuizen L.,"Polynomial time algorithms for network information flow",in 15~(th) ACM Symposium on Parallel Algorithms and Architectures(SPAA '03),San Diego,California,USA,June 2003,pp.286-294.
[6]Jaggi S.,Sander P.,Chou P.A.,et al.,"Polynomial time algorithms for network code construction",IEEE Transactions on Information Theory,vol.51,no.6,June 2005,pp.1973-1982
[7]Chou P.A.,Wu Y.,and Jain K.,"Practical network coding",in Proceedings of 41~(st) Annual Allerton Conference on Communication,Control,and Computing,October 2003.
[8]Ho Tracey,Karge D.r,Medard M.,et al..,"The benefits of coding over routing in a randomized setting",in IEEE International Symposium on Information Theory,June 2003,pp.442-447.
[9]Ho Tracey,Medard M.,Shi J.,et al.,"On Randomized Network Coding",in Proceedings of 41~(st) Annual Allerton Conference on Communication Control and Computing,October 2003.
[10]Li S.-Y.R.,Yueng R.W,and Cai N.,"Linear network coding",IEEE Transactions on Information Theory,vol.49,no.2,February.2003,pp.371-381.
[11]Effros M.,Medard M.,Ho Tracey,et al.,"Linear Network Codes:A Unified Framework for Source,Channel,and Network Coding",DIMACS(Series in Discrete Mathematics and Theoretical Computer Science),vol.66,Workshop on Network Information Theory,American Mathematical Society,2004,pp.197-216
[12]Dougherty R.,Freiling C.,and Zeger K.,"Linearity and Solvability in Multicast Networks",IEEE Transactions on Information Theory,vol.50,no.10,October 2004,pp.2243-2256
[13]S.Riis.,"Linear versus non-linear boolean functions in network flow[A]",in 38th Annual Conference on Information Science and Systems(CISS),Princeton,NJ,March 2004.
[14]Medard M.,Effros M.,Karger David,et al.,"On Coding for Non-multicast Networks",in Proceedings of 41~(st) Annual Allerton Conference on Communication Control and Computing,Monticello,Illinois,October 2003.
[15]Dougherty Randall,Freiling Chris,and Zeger Kenneth,"Insufficiency of Linear Coding in Network Information Flow",IEEE Transactions on Information Theory,vol.51,no.8,August 2005,pp.2745-2759.
[16]CAIN.and Yeung R.W.,"Secure network coding",in IEEE International Symposium on Information Theory,Lausanne,Switzerland,June 2002,pp.323.
[17]Jain K.,"Security based on network topology against the wiretapping attack",IEEE Wireless Communications,vol.11,no.1,February 2004,pp.68-71.
[18]Bhattad Kapil and Narayanan Krishna R.,"Weakly Secure Network Coding",in Proc.First Workshop on Network Coding Theory,and Applications(Netcod),Italy,April 2005.
[19]Ho Tracey,Leong Ben,Koetter Ralf,et al.,"Byzantine modification detection in multicast networks using randomized network coding",in International Symposium on Information Theory(ISIT),27 June-2 July 2004,pp.144-.
[20]Chou Philip A.and Wu Yunnan,"Network Coding for the Internet and Wireless Networks",Microsoft Research,TechReport,MSR-TR-2007-70,June 2007
[21]Petrovi(?),D.,Ramchandran,K.and Rabaey J.Riva,"Overcoming Untuned Radios in Wireless Networks with Network Coding",IEEE Transactions on Information Theory,vol.52,no.6,June 2006,pp.2649-2657
[22]Dimakis,A.G.,Prabhakaran,V.and Ramchandran,K.,"Decentralized Erasure Codes for Distributed Networked Storage",IEEE Transactions on Information Theory,vol.52,no.6,June 2006,pp.2809-2816.
[23]Yeung R.W.,Li S.-Y.R.,Cai Ning,et al.,"Network Coding Theory",now Publishers Inc.,USA,2006,pp.11-20
[24]Ho Tracey,Mrdard Muriel,Koetter Ralf,et al.,"A Random Linear Network Coding Approach to Multicast",IEEE Transactions On Information Theory,vol.52,no.10,October 2006,pp.4413-4430
[25]Castro M and Liskov B,"Practical byzantine fault tolerance",in Proceedings of 3rd USENIX Symposium on Operating Systems Design and Implementation (OSDI'99),New Orleans,LA,SA,February 1999
[26]Kihlstrom K.P.,Moser L.E.and Melliar-Smith P.M.,"The SecureRing protocols for securing group communication",in Proceedings of the 31st Annual Hawaii International Conference on System Sciences(HICSS'98),IEEE Computer Society Press,vol.3,1998,pp.317-326
[27]Cai Ning,Yeung R.W.,"A Security Condition for Multi-Source Linear Network Coding",in IEEE International Symposium on Information Theory,June 2007,pp.561-565
[28]Tan Jianlong,M(?)dard Muriel,"Secure Network Coding with a Cost Criterion"_in International Symposium on IEEE Modeling and Optimization in Mobile,Ad Hoc and Wireless Networks,April 2006,pp.1-6.
[29]Chan Terence and Grant A."Capacity Bounds for Secure Network Coding",IEEE Communications Theory Workshop,2008.AusCTW 2008,February 2008,pp.95-100
[30]Feldman Jon,Malkin Tal,Servedio Rocco A.,et al,"On the Capacity of Secure Network Coding",in 42nd Annual Allerton Conference on Communication,Control,and Computing,2004