多源網(wǎng)絡(luò)編碼數(shù)據(jù)完整性驗(yàn)證方案

牛淑芬,王彩芬,張玉磊,曹素珍

(西北師范大學(xué)計算機(jī)科學(xué)與工程學(xué)院,蘭州730070)

多源網(wǎng)絡(luò)編碼數(shù)據(jù)完整性驗(yàn)證方案

牛淑芬,王彩芬,張玉磊,曹素珍

(西北師范大學(xué)計算機(jī)科學(xué)與工程學(xué)院,蘭州730070)

基于同態(tài)向量哈希函數(shù)和向量合并算法,提出一種能夠抵御污染攻擊的多源網(wǎng)絡(luò)編碼數(shù)據(jù)完整性驗(yàn)證方案。通過信源節(jié)點(diǎn)計算發(fā)送向量的哈希值,利用私鑰對該哈希值進(jìn)行簽名,并將消息向量、哈希值以及哈希值的簽名發(fā)送至中間節(jié)點(diǎn)。中間節(jié)點(diǎn)和信宿節(jié)點(diǎn)基于系統(tǒng)公鑰,驗(yàn)證來自不同信源節(jié)點(diǎn)的線性編碼消息的完整性。實(shí)驗(yàn)結(jié)果表明,當(dāng)信源節(jié)點(diǎn)數(shù)大于200時,該方案的計算效率優(yōu)于現(xiàn)有多源網(wǎng)絡(luò)編碼方案,更適用于大規(guī)模分布式網(wǎng)絡(luò)數(shù)據(jù)的安全驗(yàn)證。

多源網(wǎng)絡(luò)編碼;數(shù)據(jù)完整性;聚合簽名;同態(tài)哈希函數(shù);向量合并算法;離散對數(shù)問題

1 概述

Ahlswede和Cai等人［1］于2000年提出網(wǎng)絡(luò)編碼理論,網(wǎng)絡(luò)編碼允許網(wǎng)絡(luò)中間節(jié)點(diǎn)在傳統(tǒng)數(shù)據(jù)轉(zhuǎn)發(fā)的基礎(chǔ)上參與數(shù)據(jù)處理,已成為提高網(wǎng)絡(luò)吞吐量、魯棒性和安全性的有效方法,但網(wǎng)絡(luò)編碼易遭受系統(tǒng)污染攻擊,一旦網(wǎng)絡(luò)中的某個信息被某蓄意節(jié)點(diǎn)惡意篡改,或在傳輸過程中由于外界原因發(fā)生變異,該污染信息將在整個網(wǎng)絡(luò)中迅速繁殖,使目的節(jié)點(diǎn)無法恢復(fù)源信息,導(dǎo)致網(wǎng)絡(luò)傳輸失敗。在密碼學(xué)中,通常用基于同態(tài)哈希函數(shù)的簽名［2］和同態(tài)數(shù)字簽名技術(shù)［3］解決線性網(wǎng)絡(luò)編碼中的污染問題。利用簽名函數(shù)或者同態(tài)哈希函數(shù)的同態(tài)性,中間(信宿)節(jié)點(diǎn)用公鑰驗(yàn)證數(shù)據(jù)的真實(shí)性。文獻(xiàn)［4］系統(tǒng)地討論了線性網(wǎng)絡(luò)編碼的安全問題,提出一個層次式抵御污染攻擊的安全協(xié)議,該協(xié)議能夠?qū)崿F(xiàn)污染節(jié)點(diǎn)的具體定位。

然而,現(xiàn)有算法大多是針對單源網(wǎng)絡(luò)編碼設(shè)計,而在多源網(wǎng)絡(luò)編碼中,該問題就會變得復(fù)雜,主要原因在于:現(xiàn)有單源網(wǎng)絡(luò)編碼簽名算法只需一個私鑰對消息進(jìn)行簽名,而在多源網(wǎng)絡(luò)編碼中,這個唯一的私鑰顯然不能被多用戶共享,且用不同的私鑰簽名

會破壞現(xiàn)有某些算法中的簽名同態(tài)性。針對多源網(wǎng)絡(luò)編碼,學(xué)者們提出了一系列簽名算法。文獻(xiàn)［5］利用簽名函數(shù)同態(tài)性提出一個安全的簽名算法,該方案每個源節(jié)點(diǎn)用自己的私鑰簽名,中間節(jié)點(diǎn)用每個源節(jié)點(diǎn)的公鑰驗(yàn)證,該方案的缺點(diǎn)是每個信源節(jié)點(diǎn)要計算一組簽名,計算量相對大。文獻(xiàn)［6］提出一個安全高效的多源網(wǎng)絡(luò)編碼簽名算法來預(yù)防網(wǎng)絡(luò)中的污染攻擊,并討論了算法的安全性。文獻(xiàn)［7］提出一個有效抵抗污染攻擊的多源網(wǎng)絡(luò)編碼簽名算法,但不足之處在于僅能供信宿節(jié)點(diǎn)進(jìn)行驗(yàn)證。文獻(xiàn)［8］給出一個針對多源網(wǎng)絡(luò)編碼的數(shù)字簽名,對于來自不同信源節(jié)點(diǎn)(不同子空間)的向量,提出向量合并算法,設(shè)計一個多源網(wǎng)絡(luò)編碼的簽名體制,并給出算法安全模型定義。文獻(xiàn)［9］為多源網(wǎng)絡(luò)編碼構(gòu)建一個無條件安全的認(rèn)證碼技術(shù),保證消息的完整性。文獻(xiàn)［10］提出一個在標(biāo)準(zhǔn)模型下可證明安全的簽名算法。從以上文獻(xiàn)可以看出,雖然學(xué)者們對多源網(wǎng)絡(luò)編碼的簽名算法做了很多研究,但都存在較多的局限性。

本文基于文獻(xiàn)［8］提出的向量合并算法,利用文獻(xiàn)［11］的同態(tài)哈希函數(shù)構(gòu)建一個數(shù)據(jù)完整性驗(yàn)證方案。每個信源節(jié)點(diǎn)首先計算消息的向量哈希值,然后用BGL聚合簽名算法［12］對哈希值進(jìn)行簽名。中間(信宿)無需知道信源節(jié)點(diǎn)的私鑰即可驗(yàn)證收到消息的完整性。該方案的安全性取決于向量哈希函數(shù)和BGL聚合簽名的安全性。

2 相關(guān)知識

2.1 雙線性映射

設(shè)q是一個大素數(shù),G1,G2是2個有著相同素數(shù)階q的乘法循環(huán)群,g是G1的生成元。假設(shè)在群G1,G2中的離散對數(shù)問題是難解的。一個雙線性映射e:G1×G1→G2在G1上滿足下列性質(zhì):

(1)雙線性:對任意的a,b∈Zq、g,h∈G1,存在e(ga,hb)=e(g,h)ab。

(2)非退化性:存在a,b∈Zq,使得e(ga,gb)≠1。(3)可計算性:對所有的g,h∈G1,存在有效算法計算e(g,h)。

2.2 困難問題假設(shè)

定義2(Diffie-Hellman(DH)問題) 設(shè)G1是階為q的循環(huán)群,g是G1的生成元,已知g,gα,h∈G1,計算hα。

2.3 同態(tài)向量哈希函數(shù)

定義3(向量哈希函數(shù)) 設(shè)G是一個階為p的循環(huán)群,隨機(jī)選擇公共參數(shù)g1,g2,…,gd∈G,則向量v=(v1,v2,…,vd)∈Zp的哈希函數(shù)為:

容易證明,向量哈希函數(shù)滿足以下性質(zhì):

(1)同態(tài)性:對任意2個向量m1,m2和2個實(shí)數(shù)w1,w2,滿足H(w1m1+w2m2)=H(m1)w1H(m2)w2。

(2)免碰撞性:不存在一個多項(xiàng)式時間的攻擊者偽造一個向量m3,同時滿足m3≠w1m1+w2m2且H(m3)=H(m1)w1H(m2)w2。

定理1 同態(tài)向量哈希函數(shù)在離散對數(shù)問題是困難問題假設(shè)下是安全的［11］。

2.4 多源線性網(wǎng)絡(luò)編碼

隨機(jī)線性網(wǎng)絡(luò)編碼的隨機(jī)性體現(xiàn)在網(wǎng)絡(luò)編碼的局部編碼系數(shù)是有限域內(nèi)的隨機(jī)數(shù),線性表示網(wǎng)絡(luò)編碼節(jié)點(diǎn)的輸入和輸出之間的關(guān)系是線性的［13］。多源網(wǎng)絡(luò)用一個無環(huán)有向圖G=(V,E)來表示,其中,E為網(wǎng)絡(luò)中鏈路的集合;V為網(wǎng)絡(luò)中所有節(jié)點(diǎn)的集合［14］。網(wǎng)絡(luò)中有l(wèi)個信源節(jié)點(diǎn)S=(s1,s2,…,sl)?V向網(wǎng)絡(luò)中另一個節(jié)點(diǎn)集合T?V中的所有信宿節(jié)點(diǎn)傳輸消息,其中,每個源節(jié)點(diǎn)都獨(dú)立地傳輸消息,且不知道任何其他節(jié)點(diǎn)的傳輸行為［15］。信源節(jié)點(diǎn)在傳輸前對它要發(fā)送的信息進(jìn)行分塊處理,把要發(fā)送的文件分成m個分塊,每個分塊用一個n(n≥m)維的行向量來表示,行向量的元素為有限域內(nèi)的數(shù)據(jù),文件可以表示為向量v=(v1,v2,…,vn)。每個信源節(jié)點(diǎn)在發(fā)送消息前,先對消息進(jìn)行如下預(yù)處理:

3 多源網(wǎng)絡(luò)編碼的數(shù)據(jù)完整性驗(yàn)證

本文方案能夠組合來自不同信源節(jié)點(diǎn)的向量,同時也能夠利用公鑰對來自不同私鑰簽名的消息進(jìn)行驗(yàn)證,所以,在基于同態(tài)向量哈希函數(shù)的基礎(chǔ)上,本文方案利用聚合簽名和向量合并算法［8］。

計算出βij=yn+(i-1)m+j,即可以計算出組合的編碼系數(shù)。

在本文驗(yàn)證方案中有三方:信源節(jié)點(diǎn),中間節(jié)點(diǎn)和信宿節(jié)點(diǎn)。完整性驗(yàn)證技術(shù)由5個算法組成: Setup,KeyGen,Sign,Combine,Verifying。記NS= (Setup,KeyGen,Sign,Combine,Verifying),算法具體描述如下:

(1)Setup:給定安全參數(shù)1k:

1)產(chǎn)生一個四元對(G1,G2,GT,e),其中,G1,G2,GT是階為素數(shù)p的3個循環(huán)群,e:G1×G2→GT為一個有效的雙線性映射。隨機(jī)產(chǎn)生gi←G1{1} (i=1,2,…,n)和g←G2{1}。

2)H1:{0,1}?→G1是一個哈希函數(shù)。

(2)KeyGen:源節(jié)點(diǎn)Si隨機(jī)選擇xi∈Zp,計算pi=gxi。源節(jié)點(diǎn)的公私鑰對為(pi,xi)。

(5)Verify:給定消息向量,向量的哈希值hi以及向量的簽名σi,y∈Fp:

2)如果以下2式均成立:

則輸出0(接受),否則輸出1(拒絕)。

正確性證明:

(1)驗(yàn)證消息哈希值:

(2)驗(yàn)證數(shù)據(jù)完整性:

4 安全性分析

在本文算法中,無需一個安全通道來發(fā)送每個向量的哈希值,哈希值的正確性通過聚合簽名算法驗(yàn)證,而數(shù)據(jù)完整性通過向量哈希函數(shù)性質(zhì)來驗(yàn)證。

定理2數(shù)據(jù)完整性驗(yàn)證算法NS是安全的,假設(shè)哈希函數(shù)VH和聚合簽名算法BGL是安全的。特別地,假設(shè)存在一個多項(xiàng)式時間的攻擊者A攻破NS算法,則存在一個多項(xiàng)式時間攻擊者B對BGL算法偽造一個簽名以及存在一個多項(xiàng)式時間攻擊者C能攻破向量哈希算法VH,使得:

其中,NS_Adv［A,NS］是攻擊者A攻破算法NS的概率。

4.1 簽名偽造

數(shù)據(jù)完整性是通過同態(tài)哈希函數(shù)驗(yàn)證的,中間

4.2 哈希碰撞

攻擊者對給定的哈希值偽造一個消息使其通過驗(yàn)證,即攻擊者選定一個消息,攻擊想偽造一個哈希值h()使得對已知消息w≠及其哈希值h(w),有h(w)=h()。由定理1可知,對任何一個攻擊者來說,偽造一個消息向量使其通過驗(yàn)證相當(dāng)于求解離散對數(shù)問題。

由以上分析可知,在本文方案中,在計算性Diffie-Hellman困難問題假設(shè)下,攻擊者不可能偽造消息向量的哈希值;在離散對數(shù)困難問題假設(shè)下,攻擊者不可能偽造一個向量使其通過驗(yàn)證。

5 實(shí)驗(yàn)結(jié)果與分析

從理論上分析本文方案在驗(yàn)證階段計算開銷方面的優(yōu)勢,給出具體數(shù)值結(jié)果。在所有表及圖中:d表示信源節(jié)點(diǎn)的個數(shù);n表示消息向量的唯數(shù);c表示中間節(jié)點(diǎn)編碼的消息向量的個數(shù)。

5.1 計算開銷

本節(jié)比較本文方案與文獻(xiàn)［3,7］方案在計算開銷方面的執(zhí)行效率,Cme表示執(zhí)行一次指數(shù)運(yùn)算花費(fèi)的時間,Cpar表示執(zhí)行一次對運(yùn)算花費(fèi)的時間,Cmul表示執(zhí)行一次乘法運(yùn)算花費(fèi)的時間,MSP表示算法支持多源網(wǎng)絡(luò)編碼。為簡單起見忽略所有計算負(fù)擔(dān)輕的加法運(yùn)算。假設(shè)驗(yàn)證者收到c個來自不同源節(jié)點(diǎn)的消息向量,按照多源線性網(wǎng)絡(luò)編碼理論:n≥d,n≥candd≥c。

表1表明本文方案需要執(zhí)行對運(yùn)算時間與文獻(xiàn)［7］方案相同,但執(zhí)行乘法和指數(shù)運(yùn)算的時間優(yōu)于文獻(xiàn)［7］方案。

表1 驗(yàn)證階段的計算開銷

5.2 實(shí)驗(yàn)結(jié)果

表2 對參數(shù)的主要性質(zhì)

5.2.1 運(yùn)行效率

本文分別運(yùn)行了在不同對參數(shù)下信源節(jié)點(diǎn)簽名與中間或者信宿節(jié)點(diǎn)驗(yàn)證的時間。對每一個信源節(jié)點(diǎn)來說,簽名時間主要決定于消息向量的大小。在這種情況下,可信源節(jié)點(diǎn)個數(shù)為d=50,消息向量維數(shù)分別為n=10,50,150,200,在2種對參數(shù)Type a和Type e下分別運(yùn)行信源節(jié)點(diǎn)簽名與中間或者信宿節(jié)點(diǎn)驗(yàn)證的時間。對每一個驗(yàn)證節(jié)點(diǎn)(中間節(jié)點(diǎn)或者信宿節(jié)點(diǎn))來說,驗(yàn)證的計算效率主要取決于文件的個數(shù)和消息向量的大小。因此,本文假設(shè)消息向量的長度為3 200 Byte,同時消息向量的個數(shù)分別設(shè)為10,50,100,200,300。

算法簽名階段和驗(yàn)證階段的運(yùn)行時間分別如圖1、圖2所示,可以看出,對固定的對參數(shù),算法運(yùn)行時間隨著消息向量大小的增加而增加。在對參數(shù)Type a下,當(dāng)信源節(jié)點(diǎn)的個數(shù)為200時,算法運(yùn)行時間為1 500 ms。

圖1 驗(yàn)證時間比較

圖2 簽名時間比較

5.2.2 分析比較

從數(shù)據(jù)實(shí)驗(yàn)角度比較本文方案與文獻(xiàn)［7］方案在驗(yàn)證階段的計算效率。本文選擇對參數(shù)類型為Type a,向量維數(shù)為50。由表3可以看出,當(dāng)信源節(jié)點(diǎn)個數(shù)d＞200時,本文方案運(yùn)行時間優(yōu)于文獻(xiàn)［7］方案。

表3 算法運(yùn)行時間比較s

6 結(jié)束語

本文提出一個多源網(wǎng)絡(luò)編碼數(shù)據(jù)完整性驗(yàn)證方案,利用向量合并算法計算來自不同信源節(jié)點(diǎn)的向量的線性組合,其作用是能夠計算出線性編碼系數(shù)。方案的數(shù)據(jù)完整性由同態(tài)向量哈希函數(shù)驗(yàn)證,哈希函數(shù)的正確性通過聚合簽名算法進(jìn)行驗(yàn)證。通過理論分析和數(shù)據(jù)測試結(jié)果表明,本文方案是可行有效的,具有良好的擴(kuò)展性。隨著全同態(tài)密碼算法研究的深入,今后將設(shè)計基于全同態(tài)密碼函數(shù)的多源網(wǎng)絡(luò)編碼簽名算法,進(jìn)一步提高算法的安全性及數(shù)據(jù)完整性驗(yàn)證的效率。

［1]Ahlswede R,CaiN,LiSYR,etal.Network Information Flow［J］.IEEE Transactions on Information Theory,2000,46(4):1204-1216.

［2]Gkantsidis C,Rodriguez P.Cooperative Security for Network Coding File Distribution［C］//Proceedings of the 25th IEEE International Conference on Computer Communications.Washington D.C.,USA:IEEE Press, 2006:1-13.

［3]Boneh D,Freeman D,Katz J,et al.Signing a Linear Subspace:Signature Schemes for Network Coding［C］// Proceedingsof2009ConferenceonPublicKey Cryptography.Berlin,Germany:Springer,2009:68-87.

［4]Adeli M,Liu H.On the Inherent Security of Linear Network Coding［J］.Communications Letters,2013, 17(8):1668-1671.

［5]羅 蛟.安全多源網(wǎng)絡(luò)編碼環(huán)簽名方案［EB/OL］.(2012-04-12).http://www.paper.edu.cn.

［6]彭 勇,陳愈強(qiáng),嚴(yán)文杰.一種安全的多源網(wǎng)絡(luò)編碼簽名算法［J］.計算機(jī)工程與應(yīng)用,2012,48(30): 135-139.

［7]Vajda I.SignaturesforMulti-sourceNetwork Coding［EB/OL］.(2010-06-04).http://eprint.iacr.org/2010/328.

［8]Agrawal S,Boneh D,Boyen X,et al.Preventing Pollution AttacksinMulti-sourceNetworkCoding［C］// Proceedingsof2010ConferenceonPublicKey Cryptography.Berlin,Germany:Springer,2010:161-176.

［9]Yang H,Yang M.An Unconditionally Secure Authentication CodeForMulti-sourceNetworkCoding［J］.InternationalJournalofWirelessandMicrowave Technologies,2012,2(1):45-49.

［10]Shao Jun,Zhang Jinlin,Ling Yun,et al.Multiple Sources Network Coding Signature in the Standard Model［M］// Pathan M,Wei Guiyi,Fortino G.Internet and Distributed Computing Systems.Berlin,Germany:Springer,2013: 195-208.

［11]Krohn M N,Freedman M J,Mazieres D.On-the-fly Verification of Rateless Erasure Codes for Efficient ContentDistribution［C］//ProceedingsofIEEE Symposium on Security and Privacy.Oakland,USA: IEEE Press,2004:226-240.

［12]Boneh D,Gentry C,Lynn B,et al.Aggregate and VerifiablyEncryptedSignaturesfromBilinear Maps［C］//Proceedings of EUROCRYPT’03.Berlin, Germany:Springer-Verlag,2003:416-432.

［13]牛淑芬,王彩芬.多源線性網(wǎng)絡(luò)編碼的同態(tài)簽名算法［J］.計算機(jī)工程,2012,38(2):126-128.

［14]牛淑芬,王彩芬,劉雪艷.抵御污染攻擊的雙源網(wǎng)絡(luò)編碼簽名算法［J］.計算機(jī)應(yīng)用,2011,31(6):1512-1514.

［15]嚴(yán)文杰.網(wǎng)絡(luò)編碼簽名算法［D］.武漢:武漢理工大學(xué),2010.

［16]The Pairing-basedCryptographyLibrary［EB/OL］.(2010-07-15).http://crypto.stanford.edu/pbc/.

編輯 陸燕菲

Data Integrity Verification Scheme for Multi-source Network Coding

NIU Shufen,WANG Caifen,ZHANG Yulei,CAO Suzhen
(College of Computer Science and Engineering,Northwest Normal University,Lanzhou 730070,China)

Taking advantage of vector merging algorithm and homomorphic Hash function,this paper proposes a data integrity scheme for multi-source network coding against pollution attacks.Each source node computes raw massage’s Hash values and uses a secure mechanism to sign the Hash values,then appends the Hash values and its signatures to each message which sends to forward nodes and sink nodes.The forwarder can verify the integrity of network coded data from different source nodes without knowing the sources private keys and generating the Hash for the combined messages.Experimental results show that the computation efficiency of the proposed scheme is better than the existing multi-source network coding scheme,and it is more suitable for the large-scale distributed network data security verification.

multi-source network coding;data integrity;aggregate signature;homomorphic Hash function;vector merging algorithm;discrete logarithm problem

牛淑芬,王彩芬,張玉磊,等.多源網(wǎng)絡(luò)編碼數(shù)據(jù)完整性驗(yàn)證方案［J］.計算機(jī)工程,2015,41(3):21-25.

英文引用格式:Niu Shufen,Wang Caifen,Zhang Yulei,et al.Data Integrity Verification Scheme for Multi-source Network Coding［J］.Computer Engineering,2015,41(3):21-25.

1000-3428(2015)03-0021-05

:A

:TP309.7

10.3969/j.issn.1000-3428.2015.03.004

國家自然科學(xué)基金資助項(xiàng)目(61163038);西北師范大學(xué)青年教師科研提升計劃基金資助項(xiàng)目(NWNU-LKQN-13-12)。

牛淑芬(1976-),女,副教授、博士,主研方向:網(wǎng)絡(luò)編碼,云計算,無線傳感器網(wǎng)絡(luò);王彩芬,教授、博士生導(dǎo)師;張玉磊,副教授;曹素珍,副教授、碩士。

2014-04-01

:2014-06-03E-mail:sfniu76@nwnu.edu.cn