格上基于同態(tài)加密的數(shù)據(jù)完整性驗證方案

牛淑芬, ,,

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

0 概述

隨著云計算的快速發(fā)展,越來越多的企業(yè)和個人選擇將數(shù)據(jù)的存儲和處理外包給云端的服務(wù)器,此舉不僅可以減少個人或組織的存儲和計算負(fù)擔(dān),而且可以隨時隨地地訪問存儲在云端的數(shù)據(jù)。但是,云存儲服務(wù)提供商(Cloud Server Provider,CSP)被認(rèn)為是半可信的,它有可能篡改或丟失用戶儲存的數(shù)據(jù),由此帶來的數(shù)據(jù)保密和隱私問題引起了業(yè)界的廣泛關(guān)注。為保證數(shù)據(jù)的完整性和準(zhǔn)確性,有研究者提出了驗證CSP上數(shù)據(jù)完整性的有效方法。

文獻(xiàn)[1-2]提出2個可證明安全性的數(shù)據(jù)持有性(Provable Data Possession,PDP)方案,但是這2個方案僅用于數(shù)據(jù)完整性驗證,沒有考慮到分布式存儲系統(tǒng)與動態(tài)數(shù)據(jù)更新,且由于方案是基于RSA密碼技術(shù),算法中存在大量模指數(shù)的運(yùn)算,因此方案中都存在極大的計算開銷。文獻(xiàn)[3-4]為實現(xiàn)數(shù)據(jù)更新操作提出改進(jìn)方案,允許用戶執(zhí)行有限的數(shù)據(jù)塊更新,但是在數(shù)據(jù)更新過程中,用戶需要重新生成已保留的挑戰(zhàn),這不適用于大文件的情況。文獻(xiàn)[5]改進(jìn)PDP方案,用基于等級的認(rèn)證跳表進(jìn)行數(shù)據(jù)塊的動態(tài)更新,但該方案不能滿足獨(dú)立數(shù)據(jù)塊的完整性驗證。文獻(xiàn)[6]定義可恢復(fù)性證明(Proof of Retrievability,POR)的概念,提出可恢復(fù)性證明方案,該方案能保證數(shù)據(jù)的可恢復(fù)性與完整性,但是其支持的驗證次數(shù)有限。文獻(xiàn)[7]利用BLS簽名提出一個POR方案,該方案雖然能滿足公開審計,但是會泄漏用戶隱私。文獻(xiàn)[8]為減少用戶的計算量,提出基于代數(shù)簽名的完整性驗證方案,該方案具有代數(shù)的性質(zhì)且計算量較小。

上述數(shù)據(jù)完整性驗證方案多數(shù)基于大整數(shù)分解和有限域上的離散對數(shù)等問題,運(yùn)算速度較慢,且不能抵御量子攻擊和亞指數(shù)攻擊。格密碼作為典型的后量子密碼的代表,具有可抵抗量子攻擊、運(yùn)用小向量的線性運(yùn)算、計算復(fù)雜度低、安全性基于格困難問題等優(yōu)點(diǎn)。因此,本文提出一種格上基于同態(tài)加密的數(shù)據(jù)完整性驗證方案,并通過性質(zhì)與效率分析驗證其性能。

1 相關(guān)知識

1.1 格

(1)

1.2 高斯分布

(2)

其中,ρσ,c(Λ)為正則化因子,c=0時,其簡寫為DΛ,σ。

1.3 格困難問題

LWE(Learning With Errors)問題是學(xué)習(xí)部分和錯誤問題的一個概括,具體定義如下。

以上描述的表達(dá)式中As+e可以簡記為As,χ,相對應(yīng)的LWE問題可以表示為LWEq,χ。量子規(guī)約算法證實了(平均情況下的)LWE問題的困難性等同于(最差情況下的)任意n維格上的SVP問題和SIVP問題[13]。

定義5一個多項式時間概率算法D的優(yōu)勢定義如下:

(4)

1.4 公鑰同態(tài)加密

定義6(公鑰同態(tài)加密方案) 方案由以下4個多項式時間算法組成:

1)ParamGen(1λ,h)→pp:λ是安全參數(shù),h是一個密文安全更新的最大值。

2)KeyGen(1λ)→(pk,sk):pk是公鑰,sk是私鑰。

3)Enc(pk,m)→c:加密算法返回密文c。

4)Dec(sk,c)→m:解密算法返回消息m。

定義7[14]對于一個公鑰同態(tài)加密方案,在敵手A和挑戰(zhàn)者C之間有如下游戲:

1)系統(tǒng)建立,挑戰(zhàn)者C產(chǎn)生pp和密鑰對(pk,sk),將pp和pk發(fā)給敵手A。

2)挑戰(zhàn),敵手A選擇2個相同長度的明文m0和m1提交給挑戰(zhàn)者C,挑戰(zhàn)者C隨機(jī)返回b∈{0,1}并計算C*=Enc(pk,mb)。挑戰(zhàn)密文C*被返回給敵手A,然后A生成一個比特b′。

2 系統(tǒng)模型

公鑰同態(tài)加密方案的云存儲體系結(jié)構(gòu)如圖1所示,其由用戶、CSP和第三方審計(Third Party Auditor,TPA)3個部分組成[15]。用戶擁有大量數(shù)據(jù),需要保存在CSP中;CSP具有較強(qiáng)的存儲空間和計算能力,為用戶提供數(shù)據(jù)儲存或計算服務(wù);TPA被認(rèn)為是可信的,可以代替用戶對其存儲在云中的數(shù)據(jù)執(zhí)行完整性驗證任務(wù),且被認(rèn)為沒有與CSP或用戶勾結(jié)的動機(jī)。

圖1 公鑰同態(tài)加密方案云存儲體系結(jié)構(gòu)

3 安全模型

為保證云存儲中數(shù)據(jù)的完整性和準(zhǔn)確性,驗證者必須不定期地對存儲在云服務(wù)器中的數(shù)據(jù)進(jìn)行完整性驗證。已有研究定義格上的數(shù)據(jù)完整性驗證方案的安全模型為:在驗證數(shù)據(jù)完整性時,不可能存在一個多項式敵手讓驗證者以不可忽略的概率接收所生成的證據(jù)。

本文將格上的同態(tài)加密數(shù)據(jù)完整性驗證方案的安全模型描述為:敵手A扮演證明者角色,挑戰(zhàn)者C扮演驗證者角色,游戲基于如下假定,如果敵手A能在多項式時間范圍內(nèi)以不可忽略的概率產(chǎn)生一組證據(jù)p*且證據(jù)通過了驗證,則挑戰(zhàn)者C在敵手A的幫助下解決了LWE困難問題。

4 數(shù)據(jù)完整性驗證方案

4.1 方案步驟

將文件F劃分成n個數(shù)據(jù)塊:f[1],f[2],…,f[n],用戶將數(shù)據(jù)存儲在云上,通常情況下認(rèn)為云端是半可信的實體。數(shù)據(jù)完整性驗證通常由用戶、CSP和可信的TPA組成。驗證方案包括以下4個階段。

1)初始化設(shè)計階段

用戶首先通過執(zhí)行KeyGen算法生成公私鑰對(pk,sk),公鑰pk用于生成數(shù)據(jù)塊的驗證標(biāo)簽,私鑰sk用于驗證數(shù)字標(biāo)簽的合法性。具體步驟如下:

然后,計算每個數(shù)據(jù)塊的唯一標(biāo)簽T[i],具體步驟如下:

(1)計算加密數(shù)據(jù)塊c[i]:

c1[i]=e1A+pe2,c2[i]=e1P+pe3+f[i]

c[i]=(c1[i],c2[i])

(2)計算加密屬性塊B[i]:

B1[i]=e1A+pe2

B2[i]=e1P+pe3+IDF‖i‖Vi

B[i]=(B1[i],B2[i])

(3)生成數(shù)據(jù)塊標(biāo)簽T[i]:

T[i]=c[i]‖B[i]

(5)

2)挑戰(zhàn)階段

進(jìn)行數(shù)據(jù)檢測時,當(dāng)TPA收到用戶發(fā)給它的一個標(biāo)簽請求后,它將所需的標(biāo)簽返回,用戶用私鑰sk驗證標(biāo)簽的合法性。然后,TPA從(1,2,…,n)中隨機(jī)選取c(1≤c≤n)個數(shù),依次放入集合csi*中,chal={csi*,g}(g=qs,i*=1,2,…,c)作為一個挑戰(zhàn)信息,被發(fā)送給CSP。

3)證據(jù)生成階段

就業(yè)內(nèi)人士的分析來看，兩家企業(yè)融合發(fā)展在解決磷肥企業(yè)綠色發(fā)展的問題上仍存在一定的困難，涉及資金、市場、政策等方面。但不管怎樣說，開磷集團(tuán)和甕福集團(tuán)的融合發(fā)展已經(jīng)在路上，從綠色發(fā)展中要效益的大方向不會改變，我們也希望雙方的融合能夠開創(chuàng)一個生態(tài)環(huán)境、企業(yè)效益與農(nóng)業(yè)發(fā)展共贏的良好局面。

CSP收到挑戰(zhàn)信息后,根據(jù)獲得的數(shù)據(jù)并利用式(6)計算認(rèn)證標(biāo)簽u和σ。然后,CSP將證據(jù)P*=(u,σ)發(fā)送給TPA。

4)驗證階段

TPA接收到證據(jù)后,首先運(yùn)用公鑰pk和證據(jù)σ計算Enc(pk,σ),然后驗證式(7)是否成立。若成立,證明數(shù)據(jù)完整性沒有被破壞;否則,證明數(shù)據(jù)完整性遭到破壞。

qs·Enc(pk,σ)=u

(7)

在本文方案中,用戶也可以進(jìn)行數(shù)據(jù)完整性驗證,具體過程為:

1)用戶隨機(jī)選取chal={csi*}(i*=1,2,…,c)作為一個挑戰(zhàn)信息,發(fā)送給CSP。

3)用戶接收到(u*,σ*)后,計算Dec(sk,u*)。

4)驗證等式Dec(sk,u*)=σ*是否成立,若等式成立,表明存儲的數(shù)據(jù)完整;否則,表明數(shù)據(jù)遭到破壞。

4.2 算法的正確性與安全性

為驗證用戶存儲數(shù)據(jù)的完整性,需要根據(jù)接收到的挑戰(zhàn)信息chal={csi*,g}和CSP生成的證據(jù)P*=(u,σ)來驗證qs·Enc(pk,σ)=u等式是否成立。運(yùn)用格上的加密算法計算如下:

c1=e1A+pe2

(8)

(e1A+pe2,e1P+pe3+f[cs1])+

(e1A+pe2,e1P+pe3+f[cs2])+…+

可見,qs·Enc(pk,σ)=u等式成立,即可以證明數(shù)據(jù)的完整性。

2)用戶驗證的正確性

用戶計算Dec(sk,u*):

c1[i]S+c2[i]=(e1A+pe2)S+e1P+pe3+u*=

(13)

可見,Dec(sk,u*)=σ*等式成立,即可以證明數(shù)據(jù)的完整性。

3)安全性分析

5 算法性質(zhì)與效率分析

5.1 同態(tài)操作

在本文方案的驗證階段,運(yùn)用格上的加密算法對數(shù)據(jù)塊的和進(jìn)行整體加密后,判斷生成的證據(jù)u(u是對每個數(shù)據(jù)塊分別加密再求和)是否與qs·Enc(pk,σ)相等。若相等,證明數(shù)據(jù)完整性沒有遭到破壞;否則,證明數(shù)據(jù)完整性遭到破壞。同態(tài)加密過程如下。

1)用戶對2個數(shù)據(jù)塊f[1]和f[2]及屬性塊分別進(jìn)行加密:

c1[1]=e1A+pe2,c2[1]=e1P+pe3+f[1]

c[1]=(c1[1],c2[1])

c1[2]=e1A+pe2,c2[2]=e1P+pe3+f[2]

c[2]=(c1[2],c2[2])

B1[1]=e1A+pe2,B2[1]=e1P+pe3+IDF‖1‖V1

B[1]=(B1[1],B2[1])

B1[2]=e1A+pe2,B2[2]=e1P+pe3+IDF‖2‖V2

B[2]=(B1[2],B2[2])

然后生成如下的數(shù)據(jù)塊標(biāo)簽并發(fā)送給CSP:

T[1]=c[1]‖B[1],T[2]=c[2]‖B[2]

2)CSP先把加密后的2個數(shù)據(jù)塊標(biāo)簽相加,然后計算認(rèn)證標(biāo)簽u和σ并發(fā)送給TPA:

σ=f[1]+f[2]

(16)

3)TPA對2個數(shù)據(jù)塊的和σ進(jìn)行整體加密:

c1[σ]=e1A+pe2

c2[σ]=e1P+pe3+σ

c[σ]=(c1[σ],c2[σ])=c[1]+c[2]

最后得到qs·c[σ]=qs·(c[1]+c[2])=g(c[1]+c[2])=u。

通過這種同態(tài)加密算法,可以減少用戶、CSP和TPA間的通信開銷以及客戶端的計算代價。

5.2 動態(tài)操作

為滿足各方面的需求,用戶會不定期地對儲存在云服務(wù)器中的數(shù)據(jù)進(jìn)行更新,因此,必須對數(shù)據(jù)塊進(jìn)行動態(tài)操作。該過程由CSP計算,包括刪除、修改和插入3個步驟。

1)刪除:在f[1],f[2],…,f[n]中刪除一個數(shù)據(jù)塊后,后面所有的數(shù)據(jù)塊索引向前移動一位。若要刪除位置j上的數(shù)據(jù)塊,則用戶向CSP發(fā)送一個刪除詢問,當(dāng)CSP接收到刪除詢問后,在指針j處刪除數(shù)據(jù)塊以及該數(shù)據(jù)塊在CSP上相應(yīng)的標(biāo)簽。

2)修改:在f[1],f[2],…,f[n]上修改一個數(shù)據(jù)塊后,其余所有數(shù)據(jù)塊的索引不變。如果用戶需要修改位置j上的數(shù)據(jù)塊,則他向CSP發(fā)送一個修改詢問,當(dāng)CSP接收到修改詢問后,修改指針j的數(shù)據(jù)塊以及該數(shù)據(jù)塊相應(yīng)的標(biāo)簽。

3)插入:在f[1],f[2],…,f[n]的j位置插入一個數(shù)據(jù)塊前,后面數(shù)據(jù)塊的指針依次往后移動一位,數(shù)據(jù)塊數(shù)目變?yōu)閚+1后插入一個新數(shù)據(jù)塊。當(dāng)CSP接收到用戶發(fā)出的插入詢問后,在指針j處插入數(shù)據(jù)塊以及該數(shù)據(jù)塊在CSP上相應(yīng)的標(biāo)簽。

5.3 批處理

批處理可以實現(xiàn)對多個用戶的數(shù)據(jù)同時進(jìn)行完整性驗證,提高了完整性驗證的效率。TPA驗證CSP中來自K個不同用戶的數(shù)據(jù)文件Fk(1≤k≤K)的具體步驟如下:

2)在挑戰(zhàn)階段,假定每個數(shù)據(jù)文件都分成n個數(shù)據(jù)塊,當(dāng) TPA收到用戶發(fā)給它的一個標(biāo)簽請求后,它將所需的標(biāo)簽返回,用戶用私鑰sk驗證數(shù)字標(biāo)簽的合法性。TPA隨機(jī)選取chal={csi*,g}(g=qs,i*=1,2,…,c)作為一個挑戰(zhàn)信息,將其發(fā)送給CSP。

3)在證據(jù)生成階段,CSP收到挑戰(zhàn)信息后,根據(jù)獲得的數(shù)據(jù)并運(yùn)用以下公式計算認(rèn)證標(biāo)簽uk和σk。

然后,CSP返回k個證據(jù)Pk*=(uk,σk)給TPA。

qs·Enc(pk,σ)=u

(19)

5.4 效率分析

對本文方案和其他文獻(xiàn)方案進(jìn)行性能對比分析,結(jié)果如表1所示。其中,Pro.表示概率性驗證,Det.表示確定性驗證,n是所有塊的數(shù)量,c是取樣塊的數(shù)量,s是在一個塊中區(qū)間的數(shù)量。由表1可以看出,相比其他方案,本文方案可以實現(xiàn)公開驗證、批處理、動態(tài)操作、同態(tài)操作,具有可行性和高效性。

表1 不同方案性能對比

6 結(jié)束語

本文提出一種格上基于同態(tài)加密的數(shù)據(jù)完整性驗證方案。方案的高效性體現(xiàn)在其主要運(yùn)用的是線性運(yùn)算,無需模指數(shù)運(yùn)算與對運(yùn)算,可以大幅減少運(yùn)算量、提高算法效率;安全性體現(xiàn)在它是基于LWE困難問題的;抗量子攻擊性體現(xiàn)在其運(yùn)用格上小向量的線性運(yùn)算加密,計算復(fù)雜度低、效率高。但該方案中用戶的計算量較大,且其密鑰長度比基于雙線性對的方案長,因此,減少方案的用戶計算量并盡可能地縮短密鑰長度是下一步的研究方向。