多級網絡編碼方案宋雪;周異輝;師軍;吳振強【摘要】目前安全網絡編碼的研究有信息論安全和密碼學安全兩種方法。信息論安全的編碼方案中，中繼節點編碼主要是使用隨機線性網絡編碼(RLNC)生成編碼矩陣，但是此方法并不能保證生成的矩陣一定滿秩，從而影響方案的解碼率。提出了一個多級網絡編碼(MLNC)方案，該方案通過在源端使用對角矩陣對消息進行編碼，以降低編碼復雜度；在中繼節點，讓入度大于等于2的節點作為編碼節點，使用多級的網絡編碼使混淆效果更好，編碼節點隨機生成滿秩的下三角矩陣和上三角矩陣，用它們的乘積作為編碼矩陣，這樣能保證編碼矩陣滿秩，接收節點可以成功解碼。Matlab仿真結果表明，MLNC編碼矩陣達到k-安全概率優于RLNC編碼矩陣，并證明MLNC方案滿足信息論安全。%Thecurrentsecurenetworkcodinghastwomethods.Theyareinformation-theoreticsecurityandcryptographysecurity.Amongtheencodingmethodsofinformation-theoreticsecurity,theencodingschemeoftherelaynodeusestheRandomLinearNetworkCoding(RLNC)togeneratetheencodingmatrix.Butthismethoddoesnotguaranteethattheresultingmatrixmustbefullrankandaffectsthedecodingrate.ThispaperproposesaMulti-LevelNetworkCoding(MLNC)scheme.Theschemeusesthetrianglematrixtoencodesourcemessage.Ontherelaynode,thenodewhosedegreeisgreaterthanorequalto2isusedascodingnode,usingmulti-levelnetworkcodingcanmakethemessageencodemixbetter.Theencodingnodesgeneratethefullranklowertriangularmatrixandthefullrankuppertriangularmatrixrandomly.Itusestheirproductasanencodingmatrix.Thisschemewillensureencodingmatrixmustbefullrank.Thereceivingnodecansuccessfullydecodethedata.TheresultoftheMatlabsimulationshowsthattheprobabilityofthecodingmatrixofMLNCsatisfyingk-securecanbebetterthanRLNC.AndtheschemeofMLNCsatisfiesthetheoreticsecurity.【期刊名稱】《計算機工程與應用》【年(卷)，期】2015(000)018【總頁數】5頁(P94-98)【關鍵詞】網絡編碼;對角矩陣;多級網絡編碼;k-安全【作者】宋雪;周異輝;師軍;吳振強【作者單位】陜西師范大學計算機科學學院，西安710062;陜西師范大學計算機科學學院，西安710062;陜西師范大學計算機科學學院，西安710062;陜西師范大學計算機科學學院，西安710062【正文語種】中文【中圖分類】TP3931概述網絡編碼理論是2000年由香港中文大學RudolfAhlswede[1]等基于網絡信息流的概念首次提出的。通過允許網絡節點進行編碼，指出網絡信息流可以被處理/壓縮，從而可進一步提升網絡吞吐量，實現網絡流量的最大化，即網絡資源利用的理論上限，而通過傳統的路由和復制并不能夠獲得該最大流限。2003年香港中文大學的李碩彥教授、楊偉豪教授、蔡寧教授等人在文獻［2］中指出線性網絡編碼可以達到多播方式下的網絡容量。近幾年，研究者們發現網絡編碼也可以實現網絡中信息的安全傳輸，文獻［3］論述了網絡編碼在安全方面的應用，為網絡編碼增加了新的應用領域，給出搭線竊聽的網絡通信模型。文獻［4］提出安全網絡編碼滿足以下兩個條件：(1)可解碼條件：伽為編碼函數，p,p'為隨機密鑰，對于所有用戶ueU和所有消息x,x,eX,x/x,,^u(x,p)/^u(x,/p,);(2)安全條件：對于竊聽子集weW,Yw為竊聽信道獲得的信息，X為源消息，H(X|Yw)=H(X)。文獻［5］給出了存在信道噪聲時網絡糾錯編碼的具體編譯碼算法。文獻［6］給出了具體的信息論安全的網絡編碼方法。網絡編碼具有一定的優勢，可以提升網絡有效性、可靠性、安全性和降低復雜度，但是需要中間節點進行編碼，相對于路由的存儲轉發，增加了因編譯碼帶來的計算和存儲方面的復雜度，與此同時，允許中間節點參與編譯碼，因而凸顯了安全問題。文獻［7］通過簡單網絡法降低編碼復雜度，將網絡轉變為節點入度和出度之和不超過3的簡單網絡，但簡單網絡的節點數比原網絡擴大了很多，即網絡編碼的節點數的代價被放大，簡單網絡法的最小代價不等于原網絡的最小代價。文獻［8］提出了一種基于稀疏矩陣理論的隨機線性網絡編碼的對等內容分發技術，其性能較傳統線性隨機編碼有所改善，但只降低了編碼的復雜度，沒有降低解碼的復雜度。文獻［9］提出一種基于稀疏矩陣的低復雜度安全網絡編碼算法，在源端對信息進行稀疏矩陣(對角矩陣)變換，然后在中繼節點進行隨機線性網絡編碼，但是不能保證匯點一定能解碼。通過對以上文獻的優缺點的比較，本文提出一種多級網絡編碼方案(MLNC),MLNC方案既可以降低編碼復雜度，又可以保證中繼節點生成的矩陣滿秩，并采用多級網絡編碼，在源端使用對角矩陣對源消息進行變換；中繼編碼節點隨機生成下三角矩陣和上三角矩陣，并用它們的乘積作為編碼矩陣對數據進行編碼，確保本方案在匯點能夠成功解碼，分析表明MLNC的編碼矩陣達到k-安全的概率高于RLNC編碼矩陣，并證明MLNC方案滿足信息論安全。2安全網絡編碼方案本文基于多播圖進行研究，該網絡拓撲圖如圖1所示。圖1拓撲圖通信網絡中用一有向無環圖G=(V，E)表示，其中V是節點的集合，E是邊的集合，令Fq為q階有限域，q為一個素數。對于任意節點vGV,uuV,若存在從v到u的有向信道，則用有向邊e=(v,u)表示此信道，u稱為e的頭節點，v稱為e的尾節點，即tail(e)。拓撲圖1中S為源節點，A、B、W為中繼編碼節點，Z1和Z2為接收節點。下面以圖1為例詳細介紹MLNC方案的實施過程。首先，在源端S點進行編碼，使用對角矩陣對源端消息進行變換。其次，將入度大于等于2的中繼節點A、B、W作為編碼節點，中繼編碼節點隨機生成滿秩的下三角矩陣和上三角矩陣，并用它們的乘積作為編碼矩陣對數據進行編碼。最后，通過全局編碼矩陣的逆和對角矩陣的逆對消息進行解碼，還原出源消息。算法1源端節點編碼算法在源節點S處進行如下的操作：輸入編碼數據信息輸出進行對角矩陣變換后的消息選取有限域中的一個隨機數t作為種子，通過隨機數生成器生成11,12，…，In，并排列成對角矩陣L;使用加密函數對種子t進行加密并放在數據包的頭部。(2)令X，=(X1,X2，…，Xn)L=(X1',X2',...,Xn')。(3)S=GX'為信源節點S最后要傳輸到網絡中的信息，G為全局編碼矩陣。算法2中繼節點編碼算法在中繼編碼節點進行如下操作：首先隨機生成一個滿秩的下三角矩陣C，和一個上三角矩陣D，矩陣C和D的乘積為M，作為系數矩陣，這樣生成的系數矩陣一定滿秩；對源消息進行編碼得S'=MS=G'X'。算法3信宿解碼算法在匯點Z1和Z2處進行解碼：(1)S'為信宿接收到的信息，信宿獲得全局編碼向量G',通過全局編碼矩陣的逆可求出信息X'=S'G'-1。(2)通過解密密鑰得t,以t為種子，通過隨機數生成器得到序列11,12，…，In,即可得L。(3)解碼出源信息X=X'L-1。算法4隨機數生成器算法3實例分析以圖1為例，假設源端發送兩個數據包X1和X2,令Y代表各個鏈路傳輸的數據包，S‘代表匯點接收的數據包，8代表編碼向量，具體的編碼過程如下：對于接收節點Z1,接收的矩陣為：假設數據包X1=[01],X2=[10],則源端消息X=[0110],所有的操作都是在有限域GF(23)上進行的，隨機選取種子3，在隨機數生成器上生成隨機數(1653),并構造對角矩陣：然后用對角矩陣對源消息進行操作得X'=XxL=[0650],分別構造矩陣：在中繼節點根據編碼算法生成矩陣：可得矩陣：從而得，因為：解碼可得，用解密密鑰獲得種子為3，然后根據隨機數生成器算法生成隨機數(1653),并形成對角矩陣。從而得：即可得源消息X=X'xL-1=[0110]。同理對于接收節點Z2接收信息也是如此，竊聽者所能竊聽到的消息都是變換了(編碼后)的消息，并且隨機數種子t是保密的，即使獲得中間節點編碼的消息，也無法獲得矩陣L,所以能保證消息的安全性。4仿真實驗與分析4.1復雜度分析本文所提出的安全網絡編碼方案是對信源進行了對角矩陣變換操作，在中間節點使用隨機生成下三角矩陣和上三角矩陣，并用它們的乘積作為編碼矩陣對數據進行編碼。所以從整個編碼過程來說，信源編碼的復雜度只是與矩陣的維數相關，矩陣的維數越高，復雜度就越高，因此算法的時間復雜度為O(n2)。4.2安全性分析根據預備知識定義的兩個條件進行以下證明。可解碼條件證明前提假設經過推導變換后得到的cr+1，cr+2，…，cn這n-r個數有不為0的數。對于源端消息x=[x1,x2,_/xn]和x'=[x1',x2',...,xn'],x玫，則k=xxL=[k1,k2，…，kn]和，假設對應的編碼矩陣分別為：對源消息分別進行編碼得：如果兩個消息編碼之后一樣則A=A‘，即A和A'中元素對應相等，可得方程組如下：此方程組為不定方程組，如果方程有解則證明編碼后的消息相等。根據文獻[10]轉換得：因為cr+1,cr+2，…，cn這n-r個數有不為0的數，所以方程組無解，因此本方案滿足可解碼條件。安全條件證明對于文中編碼方案，如果竊聽者能獲得鏈路所有的消息，它就能夠還原出源端發送的消息，但是源端編碼過程中p是保密的，所以竊聽者無法獲得源消息，即Yw和X是相互獨立的，滿足安全條件。通過證明可知，本文編碼方案滿足安全網絡編碼的兩個條件，因此本方案是安全的網絡編碼。4.3仿真分析在有限域Fq中，n階矩陣共有個，其中n階可逆矩陣共有個，所以在有限域Fq上任意取一n階矩陣，可逆的概率為。在有限域F（23）上，以3階矩陣為例，對于3階編碼矩陣和源消息［x1x2x3］，信宿接收到的消息為（z1，z2，z3），可得，求其滿足2-安全的概率p，即獲得任何兩條鏈路都獲得不到消息的概率。（1）MLNC編碼矩陣（滿秩）編碼矩陣中元素為非0元素，從有限域中1~7個數中選取，竊聽到兩條鏈路即可得兩個方程，能獲得消息（即有解）的概率為：MLNC方案是采用多級網絡編碼，如圖1所示，采用二級網絡編碼，使用一級網絡編碼時有解的概率為33.8%，則使用二級網絡編碼有解的概率p2=p1xp1必11.4%。則獲得不到任何消息的概率為：pMLNC=1-p2必88.6%（2）RLNC編碼矩陣在RLNC編碼矩陣，矩陣中元素是隨機選取的，不是完全可逆的，要使接收方能獲得源消息，編碼矩陣必須可逆。編碼矩陣中元素為非0元素，從有限域中1~7個數中取，竊聽到兩條鏈路即可得兩個方程，不能獲得任何消息（即無解）的概率為：在Matlab中取1000組矩陣進行仿真，仿真編碼矩陣達到2-安全的個數。RLNC方案達到2-安全的概率為56.9%，則1000組矩陣達到2-安全的矩陣有569個；MLNC方案達到2-安全的概率為66.2%，則1000組矩陣達到2-安全的矩陣有662個。結果表明系數矩陣越安全，消息在網絡中傳輸就越安全。本文對MLNC方案和RLNC方案達到k-安全的編碼矩陣的個數進行比較，分析結果如表1所示。表1MLNC與RLNC方案比較2-安全232425262728MLNC886915948969980990RLNC761840896937960985圖23階矩陣圖2對安全網絡編碼方案進行分析，橫坐標是有限域的大小，縱坐標是滿足m-1(m階方陣中最高安全級別)安全的概率，可知使用的MLNC方案是更安全的，以有限域GF(23)為例，在圖2的3階矩陣中，MLNC達到2-安全的概率為88.6%，RLNC達到2-安全的概率為76.1%，MLNC高于RLNC12.5%。5結束語本文研究了網絡編碼的安全問題，在源端利用對角矩陣對消息進行變換、降低復雜度的同時，中繼節點使用多級的網絡編碼對消息進行編碼。理論分析和實驗結果表明，MLNC的編碼矩陣達到k-安全的概率高于RLNC編碼矩陣達到k-安全的概率，MLNC方案可以更好地提供數據保密，并滿足信息論安全。【相關文獻】AhlswedeR，CaiN，LiSYR,etal.Networkinformationflow[J].IEEETransactionsonInformationTheory,2000,46(4):1204-1216.LiSYR,YeungRW,CaiN.Linearnetworkcoding[J].IEEETransactionsonInformationTheory,2003,49(2):371-381.CaiN,YeungRW.Securenetworkcoding[C]//2002IEEEInternationalSymposiumonInformationTheory，