网络编码签名算法
|
摘要
大量研究证明,网络编码能广泛应用于无线传感器网络,传统计算机网络,P2P及P4P网络中,并能提供各方面好处,例如增加网络带宽利用率,减少网络拥塞,增强网络健壮性,降低能量消耗等。然而,网络编码极易遭受污染攻击的破坏。近年来,国内外众多学者针对网络编码中的污染攻击提出了许多防御方法,其中基于密码学的签名算法在抵御污染攻击方面具有更高的安全性,能抵御任意数量攻击者的污染攻击,因此拥有更为广泛的应用前景。
本文在大量研究网络编码现有签名算法的前提下,针对现有签名算法中的某些缺陷,提出了三种网络编码签名算法,每种算法都有不同的特点与优势,可以为不同性质的网络传输系统提供性能更优越的签名算法的选择。同时,本文分别利用分析的方法和随机预言模型的方法对所提出的算法进行了安全性的证明：
-一次一密网络编码签名算法：现有的许多基于密码学的网络编码签名算法在传输一个新的文件时需要重新选择私钥,并更换公钥,这极大增大了网络传输负载。本算法针对这种缺陷,采用一次一密的无条件签名方法,在不改变公钥的情况下,对每一代新消息都使用不同私钥进行签名,这样既增强了签名安全性,同时也降低了网络传输负载；
-快速网络编码签名算法：当前,网络编码签名算法都基于复杂的计算操作,这使中间结点在验证消息是产生大量时延,特别是在许多无线传感器网络中,由于结点计算能力低下,使用这种复杂的验证算法会极大降低网络传输效率。本算法通过采用基于线性计算的同态哈希函数为消息计算哈希值,可以极大提高结点的验证速度。实验表明,本算法验证过程的时间复杂度远小于其它已发表的文献；
-多源网络编码短签名算法：几乎所有现有网络编码签名算法都只能用于单源网络编码,而对于拥有广泛应用的多源网络编码则无法适用,这极大的缩小了网络编码的应用领域。本算法设计了一种新的同态签名函数,可以对基于线性编码的多源网络编码的消息的完整性进行全面的安全保护,并且具有较短的尺寸和高安全性。
It has been proven that network coding can be widely applied in wireless sensor networks, traditional networks, peer to peer and peer for peer systems, and provide significant benefits to networks, such as improved throughput, reduced congestion, increased reliability, reduced power consumption, and so on. However, network coding is very vulnerable to pollution attacks. In recent years, many authentication schemes have been proposed to defend against this kind of attacks, those schemes based on cryptographic approaches have higher security, and can defend against attacks from any amount of adversaries, therefore, this kind of schemes have more promising future.
This paper proposed three signature schemes for network coding aims at kinds of disadvantages in published signature schemes, which will make network coding be used in various network systems. What's more, we have proved the security of the three signature schemes by using analysis and random oracle model:
-One time signature scheme for network coding:Some signature schemes require to update the public keys when transmitting a new file, which will greatly increase the overload in the network. This proposed signature scheme uses one time secrete key based on homomorphic public cryptograpgy to sign the messages, and updating the secrete key when transmit a new file without changing the public key, it will not only reduce the overload in network, but also enhance the security of the scheme;
-Fast signature scheme for network coding:Most of these prblished schemes are based on expensive computations, these schemes are inefficient for verifying messages, and are not suitable for scenarios with low computing capability, such as mobile Ad hoc networks and wireless sensor networks. This scheme proposed a novel signature scheme for network coding based on a linear homomorphic public cryptography, and using fast computation which greatly improved the efficiency of authentication when counteracting pollution attack for network coding. Experiment shows that the time complexity of verification in this signature scheme is much less than those in the existing algorithms.
-Short signatures for multi-source network coding:All of these published schemes cannot be used in multi-source network coding, which has a broader application background than single-source network coding. In this signature schem, we proposed a novel homomorphic signature scheme based on bilinear pairings to stand against pollution attacks for multi-source network coding. The signatures in this scheme are publicly verifiable and the public keys are independent of the files so that this scheme can be used to authenticate multiple files without having to update public keys. The signature length in this scheme is as short as the shortest signatures of a single-source network, and the verification speed is faster than those signature schemes based on elliptic curves in the single-source network.
本文在大量研究网络编码现有签名算法的前提下,针对现有签名算法中的某些缺陷,提出了三种网络编码签名算法,每种算法都有不同的特点与优势,可以为不同性质的网络传输系统提供性能更优越的签名算法的选择。同时,本文分别利用分析的方法和随机预言模型的方法对所提出的算法进行了安全性的证明：
-一次一密网络编码签名算法：现有的许多基于密码学的网络编码签名算法在传输一个新的文件时需要重新选择私钥,并更换公钥,这极大增大了网络传输负载。本算法针对这种缺陷,采用一次一密的无条件签名方法,在不改变公钥的情况下,对每一代新消息都使用不同私钥进行签名,这样既增强了签名安全性,同时也降低了网络传输负载；
-快速网络编码签名算法：当前,网络编码签名算法都基于复杂的计算操作,这使中间结点在验证消息是产生大量时延,特别是在许多无线传感器网络中,由于结点计算能力低下,使用这种复杂的验证算法会极大降低网络传输效率。本算法通过采用基于线性计算的同态哈希函数为消息计算哈希值,可以极大提高结点的验证速度。实验表明,本算法验证过程的时间复杂度远小于其它已发表的文献；
-多源网络编码短签名算法：几乎所有现有网络编码签名算法都只能用于单源网络编码,而对于拥有广泛应用的多源网络编码则无法适用,这极大的缩小了网络编码的应用领域。本算法设计了一种新的同态签名函数,可以对基于线性编码的多源网络编码的消息的完整性进行全面的安全保护,并且具有较短的尺寸和高安全性。
It has been proven that network coding can be widely applied in wireless sensor networks, traditional networks, peer to peer and peer for peer systems, and provide significant benefits to networks, such as improved throughput, reduced congestion, increased reliability, reduced power consumption, and so on. However, network coding is very vulnerable to pollution attacks. In recent years, many authentication schemes have been proposed to defend against this kind of attacks, those schemes based on cryptographic approaches have higher security, and can defend against attacks from any amount of adversaries, therefore, this kind of schemes have more promising future.
This paper proposed three signature schemes for network coding aims at kinds of disadvantages in published signature schemes, which will make network coding be used in various network systems. What's more, we have proved the security of the three signature schemes by using analysis and random oracle model:
-One time signature scheme for network coding:Some signature schemes require to update the public keys when transmitting a new file, which will greatly increase the overload in the network. This proposed signature scheme uses one time secrete key based on homomorphic public cryptograpgy to sign the messages, and updating the secrete key when transmit a new file without changing the public key, it will not only reduce the overload in network, but also enhance the security of the scheme;
-Fast signature scheme for network coding:Most of these prblished schemes are based on expensive computations, these schemes are inefficient for verifying messages, and are not suitable for scenarios with low computing capability, such as mobile Ad hoc networks and wireless sensor networks. This scheme proposed a novel signature scheme for network coding based on a linear homomorphic public cryptography, and using fast computation which greatly improved the efficiency of authentication when counteracting pollution attack for network coding. Experiment shows that the time complexity of verification in this signature scheme is much less than those in the existing algorithms.
-Short signatures for multi-source network coding:All of these published schemes cannot be used in multi-source network coding, which has a broader application background than single-source network coding. In this signature schem, we proposed a novel homomorphic signature scheme based on bilinear pairings to stand against pollution attacks for multi-source network coding. The signatures in this scheme are publicly verifiable and the public keys are independent of the files so that this scheme can be used to authenticate multiple files without having to update public keys. The signature length in this scheme is as short as the shortest signatures of a single-source network, and the verification speed is faster than those signature schemes based on elliptic curves in the single-source network.
引文
[1]D.Petrovic, K.Ramchandran, and J.Rabaey. Overcoming Untuned Radios in Wireless Networks with Network Coding. In IEEE Transactions on Information Theory, Vol 52, No.6, pp.2649-2657,2006.
[2]C. Gkantsidis and P. Rodriguez. Network Coding for Large Scale File Distribution. In Proc. IEEE INFOCOM,2005.
[3]Haiyong Xie, Arvind Krishnanmurthy, Yang Richard Yang, Avi Silberschatz. P4P:Proactive Provider Participation for P2P. YALEU/DCS/TR-1377. January 2007.
[4]R. Ahlswede, N. Cai, S. R. Li, and R. W. Yeung. Network information flow. IEEE Transactions on Information Theory, July 2000.
[5]M. J. Siavoshani, C. Fragouli, and S. Diggavi. On locating byzantine attackers. In Network Coding Workshop:Theory and Applications,2008.
[6]T. Ho, B. Leong, R. Koetter, M. M'edard, M. E□ros, and D. Karger. Byzantine modification detection in multicast networks using randomized network coding. In Proc. of International Symposium on Information Theory (ISIT) (2004),144-152.
[7]S. Jaggi. Design and Analysis of Network Codes. Ph.D. dissertation, California Institute of Technology (2006).
[8]S. Jaggi, M. Langberg, S. Katti, T. Ho, D. Katabi, M. M'edard, and M. E□ros. Resilient network coding in the presence of Byzantine adversaries. IEEE Trans.on Information Theory 54 (2008),2596-2603.
[9]M.N.Krohn, M.J.Freedman, and D.Mazi'eres, On-the-fly verification of rateless era-sure codes for efficient content distribution, IEEE Symp. Security and Privacy, Oak-land, CA, pp. 226-240, May 2004.
[10]Fang Zhao, Ton Kalker, M. M'edard, and Keesook J. Han, Signatures for content distribution with network coding, ISIT2007, Nice, France, June 24-June 29,2007.
[11]Jing Dong, Reza Curtmola, Cristina Nita-Rotaru, Practical Defenses Against Pollution Attacks in Intra-Flow Network Coding for Wireless Mesh Networks, Proc. of The Second ACM Conference on Wireless Network Security(WiSec 2009), Zurich, Switzerland, March 2009.
[12]Zhen Yu, YaWen Wei, Bhuvaneswari Ramkumar, and Yong Guan, An Efficient Signature-based Scheme for Securing Network Coding against Pollution Attacks. INFOCOM
2008. The 27th Conference on Computer Communications. IEEE, April 2008.
[13]D. Charles, K. Jian, and K. Lauter, Signature for Network Coding, Technique Report MSR-TR-2005-159, Microsoft,2005.
[14]Jonathan Katz, Brent Waters, Compact signatures for network coding, http://eprint.iacr.org/2008/316,2008.
[15]Yixin Jiang, Haojin Zhu, Minghui Shi, Xuemin Shen, Chuang Lin. An efficient dynamic-identity based signature scheme for secure network coding. Computer Networks. 2009.08.06.
[16]Silverman, J. (1986). The Arithmetic of Elliptic Curves, Graduate Texts in Math, Vol.106, Springer-Verlag.
[17]罗蛟,杨铭熙.安全多源网络编码环签名方案.中国科技论文在线(http://www.paper.edu.cn).2009年3月3日.
[18]Yuan Jun, Li Zongpeng, Yu Wei et al. A cross-layer optimization framework for multicast in multi-hop wireless networks. In:Proc. Of first International Conference of Wireless Internet(WICON),2005:47-54.
[19]Cai Ning, Yeung R W.Network coding and error correction. In Proc. Information Theory Workshop(ITW),2002:119-122.
[20]Cai Ning, Yeung R W.Secure network coding.IEEE Information Symposium on Information Theory,2002:323.
[21]Ore. O. Invitation to Number Theory. Washington, DC:The Mathematical Association of America,1976.
[22]Leveque, W. Elementary Theory of Numbers. New York:Dover,1990.
[23]W. Mao. Modern Cryptography:Theory & Practice. Prentice Hall PTR, Indianapolis, IN, USA,2003.
[24]W. Stallings. Cryptography and Network Security. Prentice Hall, NJ.,1999.
[25]Bith, T., Frisch, M., Simmons, G. Public-key Cryptography:State of the Art and Future Directions. New York:Springer-Verlag,1991.
[26]S. Li, R. Yeung, and N. Cai, Linear Network Coding, in IEEE Transactions on Information Theory, Vol.49, No.2, pp.37138,2003.
[27]Koetter R, Medard M. An Algebraic Approach to Network Coding. IEEE/ACM Transactions on Networking,2003,11(5):782-795.
[28]T. Ho, R. Koetter, M. M'edard, D. R. Karger, and M. Effros. The benefits of coding over routing in a randomized setting. In International Symposium on Information Theory (ISIT),
2003.
[29]T. Ho, M. M'edard, J. Shi, M. Effros and D. R. Karger, "On randomized network coding," In proc.41st Annual Allerton Conference on Communication Control and Computing, Oct. 2003.
[30]Bollobas B. Graph theory an introductory course [M]. New York; Springer-Verlag,1979.
[31]Christina Fragouli, Emina Soljanin. Network Coding Fundamentals. Foundations and Trends in Networking, Vol.2, No.1(2007)
[32]S. Jaggi, P. Sanders, P. A. Chou, et al. Polynomial time algorithms for multicast network code construction. IEEE Transactions on Information Theory, July,2003,51(2):1973-1982
[33]R. Johnson, D. Molnar, D. Song, and D. Wagner. Homomorphic Signature Schemes. RSA Conference - Cryptographers'Track,2002.
[34]Yongge Wang. Insecure "Provably Secure Network Coding" and Homomorphic Authentication Schemes for Network Coding, http://eprint.iacr.org/2010/060.
[35]A. Menezes, T. Okamoto, and S. Vanstone. Reducing Elliptic Curve Logorithms to Logorithms in a Finite Field. In IEEE Transactions on Information Theory, Vol.39, No.5, pp. 1639-1646,1993.
[36]V. Miller, Short Programs for Functions over Curve, unpublished manuscript,crypto.stanford.edu/miller,1986.
[37]杨铭熙，严文杰.一次一密的网络编码签名算法.武汉理工大学学报，vol.31, No.2,pp73-76,Feb.2009.
[38]Yang Mingxi, Yan Wenjie, Fang Huajing. Fast Signature Scheme for Network Coding. In The 8th International Symposium on Distributed Computing and Applications to Business, Engineering and Science (DCABES 2009*). DCABES 2009 Proceedings, pp 410-414, Oct. 2009.
[39]Bresson E, Catalano D, Pointcheval D. "A simple public key cryptosystem with a double trapdoor decryption mechanism and its applications," In:Laih CS, ed. Aciacrypt 2003. LNCS 2894, Berlin:Springer-Verlag,2003.37-54.
[40]SUN Zhong-Wei, FENG Deng-Guo, WU Chuan-Kun. An Anonymous Fingerprinting Scheme Based on Additively Homomorphic Public Key Cryptosystem. In Journal of Software:2005,vol.16, No.10,pp1816-1821.
[41]Wenjie Yan, Mingxi Yang, Layuan Li, Huajing Fang. Short Signatures for Multi-Source Network Coding. MINES, vol.1, pp.458-462,2009 International Conference on Multimedia Information Networking and Security,2009.
[42]C. Gkantsides and P. Rodriguez, Cooperative Security for Network Coding File Distribution, in proc. IEEE INFOCOM,2006.
[43]Raymond Yeung, S.-Y. R. Li, N. Cai and Z. Zhang. Network Coding Theory. Foundations and Trands in Comm. And Info. Theory.2005.
[44]Gangishetti, R., M.C. Gorantla, M.L.Das, A. Saxena and V.P. Gulati (2005). An efficient secure key issuing protocol in ID-based cryptosystems, In Proceedings of the International Conference on Information Technology:Coding and Computing (ITCC 2005), vol.1. IEEE Computer Society, pp.674-678.
[45]M. Bellare and P. Rogaway. Random Oracles are Practical:A Paradigm for Designing Efficient Protocols. In First ACM Conference on Computer and Communications Security, pages 62-73, New York,1993. ACM Press.
[2]C. Gkantsidis and P. Rodriguez. Network Coding for Large Scale File Distribution. In Proc. IEEE INFOCOM,2005.
[3]Haiyong Xie, Arvind Krishnanmurthy, Yang Richard Yang, Avi Silberschatz. P4P:Proactive Provider Participation for P2P. YALEU/DCS/TR-1377. January 2007.
[4]R. Ahlswede, N. Cai, S. R. Li, and R. W. Yeung. Network information flow. IEEE Transactions on Information Theory, July 2000.
[5]M. J. Siavoshani, C. Fragouli, and S. Diggavi. On locating byzantine attackers. In Network Coding Workshop:Theory and Applications,2008.
[6]T. Ho, B. Leong, R. Koetter, M. M'edard, M. E□ros, and D. Karger. Byzantine modification detection in multicast networks using randomized network coding. In Proc. of International Symposium on Information Theory (ISIT) (2004),144-152.
[7]S. Jaggi. Design and Analysis of Network Codes. Ph.D. dissertation, California Institute of Technology (2006).
[8]S. Jaggi, M. Langberg, S. Katti, T. Ho, D. Katabi, M. M'edard, and M. E□ros. Resilient network coding in the presence of Byzantine adversaries. IEEE Trans.on Information Theory 54 (2008),2596-2603.
[9]M.N.Krohn, M.J.Freedman, and D.Mazi'eres, On-the-fly verification of rateless era-sure codes for efficient content distribution, IEEE Symp. Security and Privacy, Oak-land, CA, pp. 226-240, May 2004.
[10]Fang Zhao, Ton Kalker, M. M'edard, and Keesook J. Han, Signatures for content distribution with network coding, ISIT2007, Nice, France, June 24-June 29,2007.
[11]Jing Dong, Reza Curtmola, Cristina Nita-Rotaru, Practical Defenses Against Pollution Attacks in Intra-Flow Network Coding for Wireless Mesh Networks, Proc. of The Second ACM Conference on Wireless Network Security(WiSec 2009), Zurich, Switzerland, March 2009.
[12]Zhen Yu, YaWen Wei, Bhuvaneswari Ramkumar, and Yong Guan, An Efficient Signature-based Scheme for Securing Network Coding against Pollution Attacks. INFOCOM
2008. The 27th Conference on Computer Communications. IEEE, April 2008.
[13]D. Charles, K. Jian, and K. Lauter, Signature for Network Coding, Technique Report MSR-TR-2005-159, Microsoft,2005.
[14]Jonathan Katz, Brent Waters, Compact signatures for network coding, http://eprint.iacr.org/2008/316,2008.
[15]Yixin Jiang, Haojin Zhu, Minghui Shi, Xuemin Shen, Chuang Lin. An efficient dynamic-identity based signature scheme for secure network coding. Computer Networks. 2009.08.06.
[16]Silverman, J. (1986). The Arithmetic of Elliptic Curves, Graduate Texts in Math, Vol.106, Springer-Verlag.
[17]罗蛟,杨铭熙.安全多源网络编码环签名方案.中国科技论文在线(http://www.paper.edu.cn).2009年3月3日.
[18]Yuan Jun, Li Zongpeng, Yu Wei et al. A cross-layer optimization framework for multicast in multi-hop wireless networks. In:Proc. Of first International Conference of Wireless Internet(WICON),2005:47-54.
[19]Cai Ning, Yeung R W.Network coding and error correction. In Proc. Information Theory Workshop(ITW),2002:119-122.
[20]Cai Ning, Yeung R W.Secure network coding.IEEE Information Symposium on Information Theory,2002:323.
[21]Ore. O. Invitation to Number Theory. Washington, DC:The Mathematical Association of America,1976.
[22]Leveque, W. Elementary Theory of Numbers. New York:Dover,1990.
[23]W. Mao. Modern Cryptography:Theory & Practice. Prentice Hall PTR, Indianapolis, IN, USA,2003.
[24]W. Stallings. Cryptography and Network Security. Prentice Hall, NJ.,1999.
[25]Bith, T., Frisch, M., Simmons, G. Public-key Cryptography:State of the Art and Future Directions. New York:Springer-Verlag,1991.
[26]S. Li, R. Yeung, and N. Cai, Linear Network Coding, in IEEE Transactions on Information Theory, Vol.49, No.2, pp.37138,2003.
[27]Koetter R, Medard M. An Algebraic Approach to Network Coding. IEEE/ACM Transactions on Networking,2003,11(5):782-795.
[28]T. Ho, R. Koetter, M. M'edard, D. R. Karger, and M. Effros. The benefits of coding over routing in a randomized setting. In International Symposium on Information Theory (ISIT),
2003.
[29]T. Ho, M. M'edard, J. Shi, M. Effros and D. R. Karger, "On randomized network coding," In proc.41st Annual Allerton Conference on Communication Control and Computing, Oct. 2003.
[30]Bollobas B. Graph theory an introductory course [M]. New York; Springer-Verlag,1979.
[31]Christina Fragouli, Emina Soljanin. Network Coding Fundamentals. Foundations and Trends in Networking, Vol.2, No.1(2007)
[32]S. Jaggi, P. Sanders, P. A. Chou, et al. Polynomial time algorithms for multicast network code construction. IEEE Transactions on Information Theory, July,2003,51(2):1973-1982
[33]R. Johnson, D. Molnar, D. Song, and D. Wagner. Homomorphic Signature Schemes. RSA Conference - Cryptographers'Track,2002.
[34]Yongge Wang. Insecure "Provably Secure Network Coding" and Homomorphic Authentication Schemes for Network Coding, http://eprint.iacr.org/2010/060.
[35]A. Menezes, T. Okamoto, and S. Vanstone. Reducing Elliptic Curve Logorithms to Logorithms in a Finite Field. In IEEE Transactions on Information Theory, Vol.39, No.5, pp. 1639-1646,1993.
[36]V. Miller, Short Programs for Functions over Curve, unpublished manuscript,crypto.stanford.edu/miller,1986.
[37]杨铭熙，严文杰.一次一密的网络编码签名算法.武汉理工大学学报，vol.31, No.2,pp73-76,Feb.2009.
[38]Yang Mingxi, Yan Wenjie, Fang Huajing. Fast Signature Scheme for Network Coding. In The 8th International Symposium on Distributed Computing and Applications to Business, Engineering and Science (DCABES 2009*). DCABES 2009 Proceedings, pp 410-414, Oct. 2009.
[39]Bresson E, Catalano D, Pointcheval D. "A simple public key cryptosystem with a double trapdoor decryption mechanism and its applications," In:Laih CS, ed. Aciacrypt 2003. LNCS 2894, Berlin:Springer-Verlag,2003.37-54.
[40]SUN Zhong-Wei, FENG Deng-Guo, WU Chuan-Kun. An Anonymous Fingerprinting Scheme Based on Additively Homomorphic Public Key Cryptosystem. In Journal of Software:2005,vol.16, No.10,pp1816-1821.
[41]Wenjie Yan, Mingxi Yang, Layuan Li, Huajing Fang. Short Signatures for Multi-Source Network Coding. MINES, vol.1, pp.458-462,2009 International Conference on Multimedia Information Networking and Security,2009.
[42]C. Gkantsides and P. Rodriguez, Cooperative Security for Network Coding File Distribution, in proc. IEEE INFOCOM,2006.
[43]Raymond Yeung, S.-Y. R. Li, N. Cai and Z. Zhang. Network Coding Theory. Foundations and Trands in Comm. And Info. Theory.2005.
[44]Gangishetti, R., M.C. Gorantla, M.L.Das, A. Saxena and V.P. Gulati (2005). An efficient secure key issuing protocol in ID-based cryptosystems, In Proceedings of the International Conference on Information Technology:Coding and Computing (ITCC 2005), vol.1. IEEE Computer Society, pp.674-678.
[45]M. Bellare and P. Rogaway. Random Oracles are Practical:A Paradigm for Designing Efficient Protocols. In First ACM Conference on Computer and Communications Security, pages 62-73, New York,1993. ACM Press.