增強型輕量級防竊聽安全網絡編碼算法

王 驍

（中國電子科技集團公司第20研究所，西安 710068）

0 引 言

網絡編碼［1］允許中間節點將各個入邊上的數據包進行混合后再發送到其出邊上，這與傳統的路由轉發模式不一樣。Li，Yeung和Cai表明，一個足夠大的有限域上的線性網絡編碼足以達到多播容量［2］。為了運算的方便和代數結構的簡明性，絕大多數研究都集中于線性網絡編碼。Ho等人提出一種在實際應用中容易實現的分布式網絡編碼方法［3］，即隨機網絡編碼（RLNC）。在RLNC中，中間節點在編碼域上獨立隨機選取編碼系數，對收到的數據包進行線性編碼，當編碼域的大小達到28或者216時，RLNC可以以接近于1的概率達到多播容量。網絡編碼在提高了吞吐量和可靠性的同時，也有著相應的安全問題，比如防竊聽安全問題。

針對防竊聽安全問題，文獻［4］首次研究了達到信息論意義安全的安全網絡編碼，假定竊聽者的竊聽能力受限，并給出安全網絡碼的構造方法。Feldman等人表明構造一個安全網絡碼等價于尋找一個有著廣義距離性質的線性碼，并指出通過犧牲少量的帶寬就能在相對小得多的有限域上構造安全網絡碼［5］。Ngai等人將廣義漢明重量擴展到線性網絡碼上［6-7］。Bhattad和 Narayanan則考慮了在實際應用中更一般的弱安全網絡編碼［8］，即竊聽者得不到源消息的任何有意義的信息。Harada和Yamamoto基于強安全斜坡秘密共享方法提出了強安全網絡編碼的概念，并表明弱安全事實上是強安全的一種特殊情況［9］。Silva和Kschischang基于秩測度碼提出一般化的安全網絡編碼［10］，可以用于任意網絡的源節點預編碼且不需要對網絡碼做任何改變。

在實際情況中，竊聽能力往往不受限制，而計算能力卻受到限制。此外，網絡容量和計算資源都是寶貴的資源。為解決這個問題，文獻［11］～［13］將密碼學方法和網絡編碼結合起來，提出了能夠防全局竊聽者的更為實用的方法，并且不用更改中間節點的隨機編碼方式。文獻［11］提出的最小開銷方法（MOS）安全性極佳，但是由于要加密整個消息，從而導致加密容量很高。文獻［12］提出的方法（P-coding）則利用置換函數來抵抗竊聽攻擊，且沒有空間開銷，但其加密容量同樣很高。文獻［13］提出了輕量級安全方法（SPOC），只需加密一個短小的額外的編碼向量，而不是整個消息，從而降低了加密容量，但增加了空間開銷。

文中提出一種更加高效的防全局竊聽者的方法，可以最小化空間開銷和加密容量。方法的主要思想在于利用一些映射值生成一個源節點上的預編碼矩陣，從而不需要額外的編碼向量，達到降低加密容量和最小化空間開銷的目的。

1 預備知識

用一個無環有向圖G＝（V，E）表示通信網絡，其中V和E分別代表節點集和邊集。每條邊能夠無差錯地傳送有限域Fq上的一個數據包，其中q為有限域的尺寸。源節點S希望將一個大的文件M發送給所有的接收節點，M被S分割為r個數據包。每個數據包用xi＝ （xi1，…，xin-1）∈Fn-1q表示，1≤i≤r，q＞r。

中間節點在Fq上為其收到的數據包隨機選取編碼系數，并將數據包的線性組合發送到每條出邊上。信宿節點在收到至少r個線性獨立數據包后，可以利用高斯消去法進行解碼，從而得到M。假定網絡中存在著一個全局竊聽者，他的竊聽能力不受限制，并且可以隨意選擇獨立邊，這也意味著被竊聽邊上的全局編碼向量是相互獨立的。

2 本文算法

2.1 源節點預編碼

那么，利用這r個映射值h（xi），1≤i≤r，構造出如下的預編碼矩陣P：

顯然，P是一個范德蒙矩陣，且是一個可逆矩陣，因此可以用于源數據包x1，…，xr的預編碼，預編碼方式如下：

預編碼后可得，然后源節點S將與相應的映射值h（xi）聯接，得到一個預編碼后的數據包

在這之后，S生成一個如下所示的擴展數據包：

經過上述預編碼步驟后，擴展數據包被發送到網絡當中，且中間節點采用隨機線性網絡編碼（RLNC）的編碼方式。

2.2 信宿節點解碼

當一個信宿節點接收到至少r個獨立的消息數據包后，它可以根據如下步驟進行解碼：

步驟2：對 ［xnew1，…，xnewr］T的最后一列解密，得到 ［x′1，…，x′r］T和h（xi）。

步驟3：利用h（xi），i＝1，…，r構造預編碼矩陣P。計算出逆矩陣P-1并將h（xi）從 ［x′1，…，x′r］T中移除，得到 ［1，…，］T。

步驟4：最后，通過計算 ［x1，…，xr］T＝P-1·［1，…，］T，得到原始數據。

2.3 安全性分析

假設竊聽者知道映射函數h（·）和矩陣P的構造特點，但是竊聽者的計算能力有限，也就是說，如果給定一個映射值b，是不可能通過計算找到輸入a使得h（a） ＝b。

式中：YW為W上傳輸的數據包。

因此，在不知道 （h（x1），…，h（xr））的情況下，竊聽者無法恢復（x1，…，xr），從而保證了原始數據包的安全性。

3 性能比較

考慮在尺寸為28的有限域上傳送數據，單個數據的最大尺寸為1 500字節，信源節點由此產生200個被編碼的數據包。1 500字節等價于F28上的1 500個符號。

3.1 空間開銷

SPOC算法用r個r長的全局編碼向量加密r個n-r長的原始數據包，這些全局編碼向量被加密后放在相應的預編碼數據包的包頭，并稱之為鎖定系數。而本文算法中共有r個n-1長的原始數據包，經過預編碼后得到n長的預編碼數據包，這表明每個數據包的空間開銷為1，預編碼數據包的最后一個字符用于構造鎖定系數，因此只需要加密這一個符號，也就是說空間開銷和加密容量獨立于數據包。

由于產生了200個被編碼數據包，那么在SPOC算法中，每個被編碼數據包上的鎖定系數所占用的空間為200字節。而依據本文算法，無論傳送多少個數據包，每個數據包上的鎖定系數占用空間只有1個字節。那么SPOC和本文算法的空間開銷比例分別為：

3.2 加密容量

加密容量Evol指的是應用算法傳送數據的過程中，需要被加密的數據的尺寸大小。

如果用k表示數據包個數，Fmax表示單個數據包的最大尺寸，L表示被傳送數據的總的尺寸大小，計算出有限域F28上，經典算法和文獻［11］、［12］、［13］以及本文算法的加密容量表達式分別為：

由此可得如圖1所示的加密容量對比圖。由圖可知文獻［12］的Pcoding算法產生的加密容量最大。而重合的2條曲線表明，文獻［11］的Adeli算法和經典算法所產生的加密容量幾乎相等。文獻［13］的SPOC算法產生的加密容量則呈階梯式增長。貼近x軸的曲線即為本文算法的結果，顯然本文算法中的加密容量相比于其他算法得到了顯著降低。

3.3 計算復雜度

圖1 加密容量對比

文獻［13］表明SPOC算法的計算復雜度為Ο（r3），其主要的計算代價集中在r×r維鎖定系數矩陣的求逆和乘積運算中。文獻［11］提出的算法的計算復雜度為Ο（r·n），計算代價集中在對每個數據包都要進行對應的Hash值的迭代計算。文獻［12］中算法的計算復雜度為Ο（r），其計算代價在于對每個數據包進行置換加密。

在一個n長的數據包情況下，表1給出了本文算法與其他算法在加密容量、空間開銷和計算復雜度之間的比較。從中可以看出本文算法所導致的空間開銷和加密容量都非常小；另外，本文算法的計算復雜度與SPOC一樣都是Ο（r3），計算代價主要由預編碼矩陣P的求逆和其他矩陣運算構成。總而言之，文中算法是一種高效率算法，所要求的空間開銷和加密容量都更小，并且計算復雜度也適中。

表1 算法的綜合性能比較

4 結束語

本文基于計算安全，結合傳統密碼學方法提出一種增強型輕量級防竊聽算法，算法的基本思想是利用與r個原始數據包對應的r個密鑰生成一個范德蒙矩陣作為預編碼矩陣用于隨機化原始數據包。密鑰加密后被放置在相應的預編碼后的數據包的尾端，從而得到一個新的被發送到網絡中的數據包。安全性能分析和數據對比表明，本文算法既達到了安全要求，同時也最小化了空間開銷和加密容量。

［1］ Ahlswede R，Cai N，Li S-Y R，Yeung R W.Network information flow ［J］.IEEE Transactions on Information Theory，2000，46（4）：1204-1216.

［2］ Li S-Y R，Yeung R W，Cai N.Linear network coding［J］.IEEE Transactions on Information Theory，2003，49（2）：371-381.

［3］ Ho T，Medard M，Koetter R，et al.A random linear network coding approach to multicast ［J］.IEEE Transactions on Information Theory，2006，52（10）：4413-4430.

［4］ Cai N，Yeung R W.Secure network coding［A］.IEEE ISIT，2002［C］.Lausanne，Switzerland，2002：323.

［5］ Feldman J，Malkin T，Stein C，et al.On the capacity of secure network coding［A］.42nd Annual Allerton Conference Communication，Control and Computer［C］，2004.

［6］ Ngai C K，Yeung R W，Zhang Z.Network generalized hamming weight［A］.Netcod 2009 ［C］.Lausanne，Switzerland，2009：48-53.

［7］ Wei V K.Generalized hamming weight for linear codes［J］.IEEE Transactions on Information Theory，1991，37（5）：1412-1418.

［8］ Bhattad K，Narayanan K R.Weakly secure network coding［A］.Netcod 2005 ［C］.Riva del Garda，Italy，2005.

［9］ Harada K，Yamamoto H.Strongly secure linear network coding ［J］.IEICE Transactions on Fundamentals，2008，E91-A（10）：2720-2728.

［10］Silva D，Kschischang F R.Universal secure network coding via rank-metric codes ［J］.IEEE Transactions on Information Theory，2011，57（2）：1124-1135.

［11］Adeli M，Liu H P.Secure network coding with minimum overhead based on hash functions ［J］.IEEE Communications Letter，2009，13（12）：956-958.

［12］Zhang P，Jiang Y X，Lin C.P-coding：secure network coding against eavesdropping attacks［A］.IEEE INFOCOM，2010［C］.San Diego，CA，USA，2010：1-9.

［13］Vilela J P，Lima L，Barros J.Lightweight security for network coding［A］.IEEE ICC，2008［C］.Beijing，China，2008：1750-1754.