基于WSN的全同態(tài)數(shù)據(jù)加密聚合方案

王彩芬,成玉丹,劉 超

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

0 概述

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network,WSN)的基本結(jié)構(gòu)有樹形和簇形,均由若干個(gè)傳感器節(jié)點(diǎn)和一個(gè)基站(Base Station,BS)組成,通信方式是無線鏈路通信,并且能夠?qū)崟r(shí)監(jiān)測、感知和收集網(wǎng)絡(luò)覆蓋范圍內(nèi)的各種環(huán)境信息[1]。傳感器能量受限,存儲(chǔ)和計(jì)算能力較小,但基站有固定的能量來源,是整個(gè)網(wǎng)絡(luò)的核心,存儲(chǔ)空間大,計(jì)算能力強(qiáng)。

目前,國內(nèi)外學(xué)者針對(duì)WSN中數(shù)據(jù)的安全傳輸問題進(jìn)行了一定研究。早期采用基于對(duì)稱加密機(jī)制的點(diǎn)到點(diǎn)數(shù)據(jù)聚合算法[2],該算法的優(yōu)點(diǎn)是容易實(shí)現(xiàn)且方便快捷,但其會(huì)造成密鑰和明文的泄露。為得到較好的安全性能,文獻(xiàn)[3]提出2-DNF非對(duì)稱密碼系統(tǒng),通過同態(tài)的加乘運(yùn)算實(shí)現(xiàn)數(shù)據(jù)的聚合,但其在數(shù)據(jù)驗(yàn)證和防止抵賴等方面仍存在局限性。此后,又出現(xiàn)了多個(gè)針對(duì)該方案的改進(jìn)方法。文獻(xiàn)[4]提出能夠抵御內(nèi)部攻擊的數(shù)據(jù)聚合方案。文獻(xiàn)[5]提出在WSN中基于同態(tài)原語的數(shù)據(jù)聚合方案。文獻(xiàn)[6]在數(shù)據(jù)的機(jī)密性和完整性上進(jìn)行改進(jìn),提出基于同態(tài)加密的WSN數(shù)據(jù)融合的機(jī)密性和完整性方案。文獻(xiàn)[7]提出基于同態(tài)加密的可驗(yàn)證隱私數(shù)據(jù)聚合方案。文獻(xiàn)[5-7]對(duì)2-DNF非對(duì)稱密碼系統(tǒng)的計(jì)算效率和安全性能均做了改進(jìn),但仍有不足之處:文獻(xiàn)[5]需要一個(gè)額外的可信第三方來分發(fā)保密干擾因子,而且方案的構(gòu)造方式復(fù)雜;文獻(xiàn)[6]在抵御內(nèi)部攻擊上存在局限性;文獻(xiàn)[7]通過聚合器本身對(duì)每一個(gè)傳感器節(jié)點(diǎn)分配干擾因子,計(jì)算復(fù)雜度高,并且其采用ElGamal方案加密隱私數(shù)據(jù),僅滿足了乘法同態(tài)性,并不滿足全同態(tài)性。

針對(duì)上述方法的不足,本文在文獻(xiàn)[7]的基礎(chǔ)上,基于簇的網(wǎng)絡(luò)結(jié)構(gòu)提出WSN中全同態(tài)的數(shù)據(jù)加密聚合方案。采用具有全同態(tài)性的DGHV[8]方案加密隱私數(shù)據(jù),同時(shí)將包含節(jié)點(diǎn)身份信息的簽名嵌入到密文中,通過簽名驗(yàn)證其正確性,使方案具有抵抗數(shù)據(jù)被篡改、追查并糾正錯(cuò)誤數(shù)據(jù)的能力。本文方案以簇為單位,通過聚合器為簇內(nèi)的傳感器節(jié)點(diǎn)分發(fā)保密干擾因子,以避免由第三方帶來的安全問題。

1 預(yù)備知識(shí)

1.1 符號(hào)和參數(shù)定義

給定安全參數(shù)λ,參數(shù)的設(shè)置為:ρ表示噪音長度,η表示私鑰長度,γ表示公鑰長度,τ表示公鑰中整數(shù)的個(gè)數(shù)。為滿足該方案的安全性,上述參數(shù)需滿足如下條件:

1)ρ=ω(lbλ),使方案能夠抵抗噪音的蠻力攻擊。

2)η≥ρΘ(λlb2λ),使方案能夠支持足夠深的電路同態(tài)評(píng)估。

3)γ=ω(η2lbλ),使方案能阻止各種基于格的攻擊,比如近似的最大公因子(Greatest Common Divisor,GCD)問題。

4)τ≥γ+(ωlbλ),使方案能夠在GCD中使用剩余的哈希引理。

1.2 雙線性映射

1)雙線性:對(duì)任意的u,v∈G1,滿足e(ua,vb)=e(u,v)ab。

2)非退化性:e(u,v)≠1G2,其中,1G2為G2中的單位元。

3)可計(jì)算性:對(duì)任意u,v∈G1,存在有效算法能夠計(jì)算e(u,v)。

1.3 困難問題假設(shè)

定義3(GCD問題)[8]參數(shù)為ρ、η、γ,p為一個(gè)隨機(jī)的ηbit的素?cái)?shù),x0=pq0,q0∈Z∩[0,2γ/p)。

求p的過程就是GCD問題。

1.4 全同態(tài)加密

定義4(全同態(tài)加密)[10]同態(tài)加密指在不解密密文的情況下,通過對(duì)密文執(zhí)行操作來實(shí)現(xiàn)對(duì)明文的加密,且其結(jié)果一致,這里的全同態(tài)是指同時(shí)滿足加法同態(tài)和乘法同態(tài)。全同態(tài)加密方案中包含4個(gè)函數(shù):KeyGen(λ),Encrypt(pk,m),Decrypt(sk,c)和Evaluate(pk,C,c)。其具體操作如下:

1)KeyGen(λ):根據(jù)安全參數(shù)λ產(chǎn)生公私鑰對(duì)(pk,sk)。

2)Encrypt(pk,m):在公鑰pk下把明文m加密成密文c。

3)Decrypt(sk,c):用私鑰sk解密密文c,得到明文m。

4)Evaluate(pk,C,c):輸入一個(gè)公鑰pk、電路C和一個(gè)密文元組c=〈c1,c2,…,ct〉,輸出另一個(gè)密文元組c。

1.5 DGHV方案

文獻(xiàn)[8]在Gentry方案的基礎(chǔ)上提出基于整數(shù)的全同態(tài)加密方案DGHV。其中各函數(shù)具體操作如下:

3)Decrypt(sk,c):輸出明文m←[[c]p]2。在解密過程中,首先通過密文模私鑰p,再模2即可得到1 bit的明文。

4)Evaluate(pk,C,c1,c2,…,ct):輸入公鑰pk、電路C和t個(gè)密文c1,c2,…,ct,其中,ci=Encrypt(pk,mi),i=1,2,…,t。輸出c*=Evaluate(pk,C,c1,c2,…,ct)且滿足Decrypt(sk,c*)=C(m1,m2,…,mt)。該算法集中體現(xiàn)了全同態(tài)加密的技術(shù)優(yōu)勢(shì),其通過門電路或者函數(shù)對(duì)密文進(jìn)行任意操作后再解密,結(jié)果和操作明文的結(jié)果一致。

2 WSN中全同態(tài)數(shù)據(jù)加密方案

WSN的構(gòu)建方式有多種,同時(shí)也產(chǎn)生了很多標(biāo)準(zhǔn)協(xié)議,如文獻(xiàn)[11]提出的標(biāo)準(zhǔn)聚合協(xié)議和文獻(xiàn)[12]中的網(wǎng)絡(luò)構(gòu)建方式。假定本文方案中的聚合器擁有足夠的計(jì)算能力且是誠實(shí)但好奇的,即其可能會(huì)自主地做出一些錯(cuò)誤的舉動(dòng),但不會(huì)與其他實(shí)體實(shí)施共謀攻擊[13]。同時(shí),它能夠有效地完成方案中涉及的簽名驗(yàn)證和解密操作。

目前提出的基于WSN的同態(tài)加密聚合方案僅僅實(shí)現(xiàn)了加法同態(tài)或乘法同態(tài),文獻(xiàn)[7]以簇為單位分發(fā)干擾因子,但是每一個(gè)傳感器擁有獨(dú)立的干擾因子在很大程度上增加了方案的計(jì)算復(fù)雜度。由干擾因子的作用可知,它不涉及隱私信息,所以對(duì)它的改進(jìn)主要是提高運(yùn)算效率,降低計(jì)算復(fù)雜度。因此,本文在文獻(xiàn)[7]的基礎(chǔ)上,以簇為網(wǎng)絡(luò)結(jié)構(gòu),提出基于WSN的全同態(tài)數(shù)據(jù)加密聚合算法,實(shí)現(xiàn)隱私數(shù)據(jù)的加法和乘法同態(tài)。在干擾因子的分發(fā)過程中,每一個(gè)簇內(nèi)的傳感器節(jié)點(diǎn)擁有相同的干擾因子,這樣既保證了方案能夠抵抗內(nèi)部攻擊,又在很大程度上降低了計(jì)算復(fù)雜度。

2.1 網(wǎng)絡(luò)模型

本文采用的網(wǎng)絡(luò)模型是基于簇的網(wǎng)絡(luò)結(jié)構(gòu)[14],如圖1所示。該結(jié)構(gòu)的優(yōu)點(diǎn)是將簇內(nèi)節(jié)點(diǎn)的信息收集起來,統(tǒng)一向上一級(jí)節(jié)點(diǎn)傳送,能夠節(jié)省通信開銷,增強(qiáng)擴(kuò)展性。網(wǎng)絡(luò)模型結(jié)構(gòu)包含3類角色:基站BS,聚合器Agg和傳感器節(jié)點(diǎn)。整個(gè)網(wǎng)絡(luò)由多個(gè)非重疊的簇組成,每個(gè)簇中包含一個(gè)聚合器(簇頭)和n個(gè)傳感器節(jié)點(diǎn)。簇頭的功能是給簇內(nèi)的每一個(gè)傳感器節(jié)點(diǎn)分發(fā)干擾因子π和身份標(biāo)識(shí)ID,π只分發(fā)一次,即每一個(gè)傳感器節(jié)點(diǎn)具有相同的干擾因子,同時(shí)從傳感器節(jié)點(diǎn)接收加密的數(shù)據(jù),將其聚合驗(yàn)證后傳給BS;每一個(gè)傳感器節(jié)點(diǎn)將接收到的數(shù)據(jù)采用帶有干擾因子的DGHV方案加密,用自己的身份標(biāo)識(shí)簽名,然后將密文發(fā)送給聚合器。

圖1 基于簇的網(wǎng)絡(luò)拓?fù)?/p>

2.2 方案設(shè)計(jì)

在基于簇的WSN構(gòu)建完成后,加密聚合方案主要包括3個(gè)基本過程:系統(tǒng)建立階段,加密簽名階段和驗(yàn)證聚合階段。在系統(tǒng)建立階段,聚合器作為整個(gè)簇的核心,為每一個(gè)傳感器節(jié)點(diǎn)分配身份標(biāo)識(shí)ID、公私鑰和干擾因子π;在加密簽名階段,傳感器節(jié)點(diǎn)收集信息,利用公私鑰和π對(duì)消息加密,用ID對(duì)消息簽名;在驗(yàn)證聚合階段,聚合器發(fā)出消息聚合的命令,每一個(gè)傳感器節(jié)點(diǎn)將加密的消息發(fā)送給聚合器,聚合器完成數(shù)據(jù)的聚合并進(jìn)行驗(yàn)證,若驗(yàn)證成功,則進(jìn)行相應(yīng)操作得到消息,若驗(yàn)證失敗,則檢測每一個(gè)節(jié)點(diǎn)的數(shù)據(jù),并要求數(shù)據(jù)傳輸錯(cuò)誤的節(jié)點(diǎn)重新傳輸數(shù)據(jù)。

2.2.1 系統(tǒng)建立階段

設(shè)在每一個(gè)簇內(nèi)由一個(gè)聚合器控制著n個(gè)傳感器節(jié)點(diǎn)Ui(i=0,1,…,n-1)。聚合器作為密鑰生成中心,通過DGHV[8]方案和DF[15]方案為簇內(nèi)的每一個(gè)節(jié)點(diǎn)分配公私鑰和干擾因子。該階段的2個(gè)基本操作如下:

1)密鑰生成階段:

(1)聚合器對(duì)控制的每一個(gè)傳感器節(jié)點(diǎn)分配身份標(biāo)識(shí)IDi(i=0,1,…,n-1)。

(2)設(shè)置安全參數(shù)λ。

(4)生成N階乘法循環(huán)群G。

(5)在G中取生成元g。

(6)發(fā)布公鑰PK={pk,g},私鑰SK=p。

2)分配保密干擾因子πk(k=0,1,…,n-1,表示聚合器的個(gè)數(shù))。

保密干擾因子的生成和分發(fā)過程是保密的,由于它不涉及核心消息mi,因此對(duì)它的保密要求比較低,而對(duì)其效率的要求較高。本文采用與DF[15]方案相同的分配方式,若聚合器為每一個(gè)傳感器都分配保密干擾因子,會(huì)增加計(jì)算復(fù)雜度。為降低計(jì)算復(fù)雜度,本文采用基于簇的傳感器網(wǎng)絡(luò)。假設(shè)以n個(gè)傳感器節(jié)點(diǎn)為一個(gè)簇,每一個(gè)簇分配一個(gè)保密干擾因子,即n個(gè)節(jié)點(diǎn)具有相同的干擾因子。聚合器(簇頭)的具體分配過程如下:

2.2.2 加密簽名階段

當(dāng)傳感器節(jié)點(diǎn)Ui(i=0,1,…,n-1)收到聚合器發(fā)布的數(shù)據(jù)聚合的命令時(shí),進(jìn)行數(shù)據(jù)加密簽名的操作,在此過程中,傳感器節(jié)點(diǎn)可以對(duì)多次加密的數(shù)據(jù)實(shí)現(xiàn)全同態(tài)操作,再用身份標(biāo)識(shí)IDi簽名,然后上傳給聚合器。具體過程如下:

4)計(jì)算簽名σi=H(ci‖IDi)p及yi=gp。

5)將{ci,yi,σi}(i=0,1,…,n-1)發(fā)送至聚合器。

2.2.3 驗(yàn)證聚合階段

在驗(yàn)證聚合階段,聚合器首先對(duì)上傳的數(shù)據(jù)進(jìn)行聚合,然后利用雙線性映射驗(yàn)證其正確性,若驗(yàn)證正確,則可以計(jì)算得到聚合的消息,具體操作如下:

1)聚合器接收所有傳感器節(jié)點(diǎn)Ui傳來的數(shù)據(jù){ci,yi,σi}(i=0,1,…,n-1)。

2.3 方案的正確性分析

本文方案的正確性分析具體如下:

1)簽名驗(yàn)證的正確性:

2)聚合解密的正確性:

3 方案性能分析

3.1 全同態(tài)性分析

由于本文方案的加密算法運(yùn)用了基于整數(shù)的全同態(tài)加密方案DGHV,因此其全同態(tài)性的詳細(xì)證明過程可參考文獻(xiàn)[8]。

3.2 保密干擾因子的安全性分析

在本文方案中,保密干擾因子πk(k=0,1,…,n-1表示聚合器的個(gè)數(shù))是以簇為單位分配的,作用是在保證安全的基礎(chǔ)上提高方案的效率,其分配方式根據(jù)DF[15]方案構(gòu)造,故本文方案中保密干擾因子安全性的詳細(xì)證明過程可參考文獻(xiàn)[15]。

3.3 基于AGCD問題的安全性證明

本文方案的安全性基于近似公因子(AGCD)難題和計(jì)算版本的Co-Diffie-Hellman問題。Co-Diffie-Hellman問題作為一些密碼系統(tǒng)困難問題的基礎(chǔ),已經(jīng)得到了證明和廣泛應(yīng)用。本文對(duì)基于AGCD問題的安全性進(jìn)行證明,主要證明思路是使用攻擊算法A來構(gòu)造求解困難問題的算法B,該過程包括4個(gè)步驟:1)利用困難問題產(chǎn)生方案的公鑰;2)利用A構(gòu)造求解p的商的最小比特位;3)執(zhí)行Binary-GCD算法;4)恢復(fù)p。

定理1在第2.1節(jié)的方案中,固定參數(shù)(ρ,η,γ,τ)與安全系數(shù)λ。任意的攻擊者A以優(yōu)勢(shì)ε攻擊加密方案,都可以轉(zhuǎn)化成求解器B以至少ε/2優(yōu)勢(shì)求解參數(shù)為(ρ,η,γ)的近似AGCD問題。B的運(yùn)行時(shí)間是tA、λ和1/ε的多項(xiàng)式,其中,tA是A的運(yùn)行時(shí)間。

證明攻擊者A以ε的優(yōu)勢(shì)攻擊本文方案,即A以ε的優(yōu)勢(shì)輸入公鑰和密文(由本文方案的算法獲得公鑰和密文),正確輸出明文的概率至少是1/2+ε。

在參數(shù)為ρ、η、γ時(shí),構(gòu)造求解近似AGCD困難問題的求解器B,對(duì)于隨機(jī)選取的ηbit的奇整數(shù)p,求解器B需要從Dr,ρ(p)分布中獲得多個(gè)樣本來求解目標(biāo)p。步驟如下:

步驟1創(chuàng)建公鑰。首先,求解器B為方案創(chuàng)建一個(gè)公鑰pk=〈x0,x1,…,xτ〉。

步驟2利用最低有效位(Least Significant Bit,LSB)子程序求解p的近似倍數(shù)的最小比特位。B調(diào)用以下子程序:

子程序Learn-LSB(z,pk)

輸入z∈[0,2γ),|rp(z)|<2ρ,公鑰pk=〈x0,x1,…,xτ〉

輸出qp(z)的最低有效位

1.For i=1 to poly(λ)/ε do://ε是A的整體優(yōu)勢(shì);

4.調(diào)用A訪問隨機(jī)預(yù)言機(jī)得到ai←A(pk,ci);

5.設(shè)置bi←ai⊕parity(z)⊕mi;

步驟3運(yùn)用Binary-GCD算法[8]計(jì)算p。給定任意的2個(gè)整數(shù)z1=qp(z1)·p+rp(z1)和z2=qp(z2)·p+rp(z2)(rp(zi)<

綜上,若隨機(jī)預(yù)言機(jī)能計(jì)算出[qp(z)]2(z的噪聲遠(yuǎn)小于p),則B就可以恢復(fù)p。接下來分析在隨機(jī)預(yù)言機(jī)模型下B成功的概率。

由步驟1可得,求解器B產(chǎn)生公鑰的分布與本文方案產(chǎn)生的正確分布相同,如文獻(xiàn)[8]所述:如果A猜測成功的可能性為ε,則敵方猜測成功的可能性至少為ε/2。如果固定p,在對(duì)應(yīng)的公鑰pk下A猜測成功的可能性至少是ε/4,敵方猜測成功的可能性至少為ε/4。在子程序Learn-LSB(z,pk)的步驟4中,A猜測成功的可能性至少是ε/4-negl,對(duì)于該子程序而言,返回正確值的可能性很大,B有很大概率恢復(fù)出p。對(duì)于這樣的p,公鑰pk下的概率ε/4-negl也成立,則求解器B在運(yùn)行中恢復(fù)p的概率至少是1/2(ε/4-negl),B重復(fù)調(diào)用算法(8/ε)ω(lbλ)次,此時(shí)B的時(shí)間復(fù)雜度是poly(λ,1/ε),因此,求解器B成功恢復(fù)p的概率至少是ε/2。至此,定理1證明完畢,本文方案是IND-CPA安全的。

3.4 網(wǎng)絡(luò)內(nèi)部攻擊分析

網(wǎng)絡(luò)內(nèi)部的攻擊者可以在數(shù)據(jù)聚合前后的2個(gè)階段獲得數(shù)據(jù)。從這2個(gè)方面進(jìn)行如下分析:

1)在聚合前,內(nèi)部攻擊者要獲得明文消息mi,在得到傳感器的加密私鑰p的同時(shí),也要得到干擾因子πk。由于本文方案以簇為單位分配干擾因子,因此簇內(nèi)每一個(gè)節(jié)點(diǎn)的干擾因子都相同。為獲知內(nèi)部攻擊者是否會(huì)進(jìn)行重復(fù)性攻擊,作如下證明:在一個(gè)簇內(nèi)隨機(jī)選取一個(gè)節(jié)點(diǎn)的2個(gè)消息m1、m2,加密之后的密文為c1、c2。

(1)

(2)

式(1)、式(2)相減并化簡可得:

(3)

對(duì)于式(3),分2種情況討論:

(1)m1-m2的值未知,則不能得到干擾因子πk。

(2)假設(shè)m1-m2的值已知,在N階乘法循環(huán)群內(nèi)求解πk屬于離散對(duì)數(shù)困難問題,故也不能得到干擾因子πk。因此,πk的獲取是困難的。

由以上分析可得,本文方案可有效抵御來自網(wǎng)絡(luò)內(nèi)部的攻擊。

4 不同方案性能對(duì)比

表1所示為文獻(xiàn)[4,7,14]中的經(jīng)典方案和本文方案的主要性能對(duì)比。其中,同態(tài)性指方案是否能實(shí)現(xiàn)全同態(tài)性。

表1 4種方案性能比較

由表1可以看出,與文獻(xiàn)[4]方案相比,本文方案無需可信第三方并且滿足全同態(tài)性;與文獻(xiàn)[7]方案相比,本文方案時(shí)間復(fù)雜度更低且能夠進(jìn)行全同態(tài)運(yùn)算;與文獻(xiàn)[14]方案相比,本文方案能夠抵御內(nèi)部網(wǎng)絡(luò)攻擊。因此,與已有方案相比,本文方案在無需可信第三方的情況下,時(shí)間復(fù)雜度較低且滿足全同態(tài)性。

5 結(jié)束語

為改善WSN中的數(shù)據(jù)聚合效果,本文提出一種基于全同態(tài)加密的數(shù)據(jù)聚合方案,該方案具有如下優(yōu)點(diǎn):1)采用全同態(tài)加密方案,聚合器無需對(duì)密文解密就可以進(jìn)行全同態(tài)運(yùn)算;2)聚合器沒有解密密鑰,每個(gè)簇內(nèi)的傳感器都有保密因子,并且不需要可信第三方來分配,因此,該方案既可以抵御內(nèi)部攻擊也能節(jié)約存儲(chǔ)空間;3)以簇為單位分配保密干擾因子,將計(jì)算復(fù)雜度降低到O(1)。實(shí)驗(yàn)結(jié)果驗(yàn)證了該方案的性能優(yōu)越性。下一步考慮改進(jìn)公鑰產(chǎn)生算法并縮短公鑰的長度,以減少本文算法的運(yùn)行時(shí)間,提高運(yùn)算效率。