高可靠度網路資料傳輸與驗證

Reliable Network Data Transmission and Verification

古秉禾(Bying-He Ku)

指導教授 ： 孫宏民

國立清華大學/電機資訊學院/資訊工程學系/博士(2010年)

https://doi.org/10.6843/NTHU.2010.00467

摘要

近年來糾刪碼Erasure code (將數據分為k 個碎片, 編碼為n 個,其中任意k 個編碼後數據可用來恢復原始數據) 因為有較佳的傳輸效率
而被大量使用在多點傳送(multicast) 網路資料傳輸應用上，但是如
果在傳輸過程中，或是發送者蓄意傳輸錯誤的資料，則接收端必須
要等到累積足夠資料要解回原始資料時才能發現有接收到錯誤資
料。這篇論文想利用秘密分享(secret sharing scheme) 的編碼特性，加以改良，使得資料傳輸時加上驗證機制，讓接收端在接收到部份資料時就能馬上驗證其正確性，若發現該資料無法過驗證則馬上捨
棄，直接接收下一份資料。這個方法的驗證安全性是基於橢圓曲線
離散對數問題(ECDLP) 的困難性上，透過利用橢圓曲線運算，可以
降低運算量又可達到公開金鑰的訴求。另外，我將提供一種分配資
料的演算法，透過線性規劃與可存取結構(access structure) 的圖形化重組，可達到自動化地在多項式時間複雜度內決定分配策略，並配合本篇論文提出的編碼方法解決目前網路傳輸應用的更一般化的資
料分配傳輸問題。

關鍵字

糾刪碼 ； 秘密分享 ； 網路傳輸

並列摘要

In recent years, many multicast applications, such as audio, videoconferencing, one-to-many file transfer and Pay-TV, are emerging and provide us convenient daily life. Comparing with unicast, multicast can simultaneously transfer data to multiple receivers using fewer bandwidth. However, reliable multicast transmission should be guaranteed so that the data can be correctly and reliably transferred to multiple receivers. The factors of unreliability include, buffer overflow in the routers, user heterogeneity, user mobility, and other potential equipment malfunction, and etc. Although retransmission strategy by using ack-based protocols can be utilized to reach the goal of reliability in unicast communication, it does not scale well in multicast applications, where heterogeneous receivers may have different lost data blocks.

To meet the requirement of reliability for multicast applications, a new class of Forward Error Correction (FEC), called Erasure codes, has been extensively studied and applied to multicast transmission. Erasure code allows
the receiver to correct erasure without retransmission and is especially useful for those circumstances, where retransmission is impossible, such as multicast networks, wireless networks, and satellite communication, and etc. Recently, erasure code has been extensively applied to multicast net work transmission due to its higher transmission efficiency. However, many open issues are still needed to be addressed. Using conventional erasure code, the receivers are unable to verify the correctness of the receiving data packets on-the-fly, unless all data packets have been received and decoded by the receiver. In this thesis, we proposed a new erasure code to provide reliable multicast data distribution. The proposed codes
satisfy all requirements of erasure codes, and are inspired by secret sharing technology and Elliptic Curve Discrete Logarithm Problem (ECDLP). More importantly, the receivers can verify its receiving data on-the-fly by using the codes. The analysis also shows the security and feasibility of the proposed scheme.

並列關鍵字

Erasure code ； secret sharing scheme ； multicast

參考文獻

[1] L. Rizzo, “Effective erasure codes for reliable computer communication protocols,”ACM SIGCOMM Computer Communication Review, vol. 27, no. 2, pp. 24--36, Apr. 1997.

[5] H.-M. Sun, S.-Y. Chang, and H.-T. Chiao, “Polynomial Interpolation codes for reliable multicast data distribution,” TENCON 2009 - 2009 IEEE Region 10 Conference, pp.1--6, Nov. 2009.

[6] Z. Liu, X. Li, and Z. Dong, “Direct Fingerprinting on Multicasting Compressed Video,”Electrical Engineering, 2005.

[7] J. Byers, J. Considine, M. Mitzenmacher, and S. Rost, “Informed content delivery across adaptive overlay networks,” IEEE/ACM Transactions on, pp. 767--780, 2004.

[9] S. Agrawal and D. Boneh, “Homomorphic MACs: MAC-Based Integrity for Network Coding,” Network, pp. 292--305, 2009.