常 亮， 王冠棋， 楊雪欣

(黑龍江科技大學(xué) 計(jì)算機(jī)與信息工程學(xué)院， 哈爾濱 150022)

云存儲系統(tǒng)可以使用戶以低廉的價(jià)格獲取海量的存儲能力，但數(shù)據(jù)的高度集中同樣使其面臨著嚴(yán)峻的安全挑戰(zhàn)。當(dāng)用戶選擇云存儲模式時(shí)，用戶一般并不會在本地保存數(shù)據(jù)副本。換言之，用戶可能失去了對這些數(shù)據(jù)的物理控制。這些存儲在云端的數(shù)據(jù)不僅可能會遭受來自其他用戶的惡意攻擊，甚至還可能遭到不可靠云服務(wù)提供商(Cloud storage service provider,CSP)的濫用，如窺視用戶隱私、挖掘用戶隱私、數(shù)據(jù)丟失瞞報(bào)、數(shù)據(jù)惡意篡改等。隨著量子計(jì)算技術(shù)的發(fā)展，大素?cái)?shù)因子分解難題和有限域上離散對數(shù)問題將變得不再困難，基于傳統(tǒng)難題的RSA、DSA、ECDSA等簽名方案也面臨失去安全的風(fēng)險(xiǎn)。大數(shù)據(jù)時(shí)代為保證用戶數(shù)據(jù)的安全性和完整性，迫切需要對傳統(tǒng)數(shù)據(jù)完整性驗(yàn)證方案加以多方面更加安全的改進(jìn)。為此，筆者提出了一種基于格的云存儲完整性驗(yàn)證方法，通過效率分析和安全分析來驗(yàn)證其性能。

1 基本原理

1.1 PDP數(shù)據(jù)完整性驗(yàn)證方案

數(shù)據(jù)持有性證明方案(Provable data possession,PDP)采用隨機(jī)抽樣的策略，概率性的進(jìn)行數(shù)據(jù)完整性驗(yàn)證。這是一個(gè)靜態(tài)的基于RSA簽名同態(tài)特性的概率性策略，進(jìn)而開創(chuàng)了在不可信存儲器上的數(shù)據(jù)完整性驗(yàn)證方案。典型PDP方案的邏輯架構(gòu)如圖1所示。

圖1 PDP方案的基本架構(gòu)Fig. 1 Basics PDP scheme architecture

1.2 格和格難題

1.3 LWE問題

容錯(cuò)學(xué)習(xí)(Learning with errors，LWE)是格密碼學(xué)的基礎(chǔ)問題，其困難性可以歸約成格的SVP和SIVP問題。LWE問題包括CLWE(LWE搜索)問題和DLWE(LWE判定)問題。

1.4 同態(tài)簽名

設(shè)簽名者所持有的公鑰為pk，私鑰為sk，對數(shù)據(jù)塊m而言，分別對其任意數(shù)據(jù)子塊m1、m2做對應(yīng)的簽名得σ1、σ2。若簽名方案滿足以下性質(zhì)：

不可偽造性。只有持有密鑰對(pk,sk)的簽名者才能生成簽名σ。

驗(yàn)證簡化性。已知簽名σ1、σ2，任取隨機(jī)數(shù)k1、k2對數(shù)據(jù)塊m′=k1m1+k2m2而言，驗(yàn)證者可以在不知道m(xù)1、m2的情況下，通過σ1、σ2和k1、k2計(jì)算并對數(shù)據(jù)塊m′進(jìn)行驗(yàn)證。

非擴(kuò)展性。已知簽名σ1、σ2，任取隨機(jī)數(shù)k1、k2，對應(yīng)的數(shù)據(jù)塊m′=k1m1+k2m2而言，驗(yàn)證者在不持有私鑰sk的前提下，無法通過線性結(jié)合的方式生成新的滿足驗(yàn)證條件的簽名σ′，則稱該簽名方案為一個(gè)同態(tài)簽名方案，該簽名為同態(tài)簽名[3-4]。

公鑰同態(tài)加密方案，一般由3個(gè)多項(xiàng)式時(shí)間算法構(gòu)成。

(1)密鑰生成KeyGen(1λ)→(pk,sk)：輸入安全參數(shù)λ、輸出公鑰pk、私鑰sk。

(2)明文加密Enc(m,pk)→c：輸入明文m、公鑰pk、輸出密文c。

(3)密文解密Dec(c,sk)→m：輸入密文c、私鑰sk、輸出明文m。

1.5 Merkel散列樹

Merkle散列樹(Merkle hash tree, MHT)是一種樹形數(shù)據(jù)結(jié)構(gòu)，可以花費(fèi)較短的開銷進(jìn)行數(shù)據(jù)驗(yàn)證，其被廣泛應(yīng)用于云存儲、P2P、比特幣等需要進(jìn)行快速驗(yàn)證的領(lǐng)域[5]。其葉子節(jié)點(diǎn)存儲各個(gè)數(shù)據(jù)子塊的哈希值，非葉子節(jié)點(diǎn)存儲其子節(jié)點(diǎn)值之和的哈希值[6]。

當(dāng)用戶端對服務(wù)器端數(shù)據(jù)某個(gè)數(shù)據(jù)子塊進(jìn)行完整性驗(yàn)證時(shí)，服務(wù)器端返回Merkel樹上對應(yīng)數(shù)據(jù)子塊的葉子節(jié)點(diǎn)存儲的哈希值和相對的直至Merkel樹根節(jié)點(diǎn)的輔助路徑上的哈希值[7]。用戶端只需對所返回葉子節(jié)點(diǎn)存儲的哈希值和所返回輔助路徑上的哈希值進(jìn)行簡單計(jì)算，并與用戶端所持有的原數(shù)據(jù)塊的哈希值進(jìn)行對比，即可判定原數(shù)據(jù)塊和對應(yīng)數(shù)據(jù)子塊的完整性[8]。

2 系統(tǒng)模型

2.1 基本結(jié)構(gòu)

云存儲數(shù)據(jù)完整性驗(yàn)證模型由三方組成：用戶、云服務(wù)器提供商和第三方審計(jì)者[3]，如圖2所示。

在上述三方架構(gòu)模型中，用戶首先對第三方審計(jì)者發(fā)起委托驗(yàn)證請求[9]。第三方審計(jì)者收到用戶的委托驗(yàn)證請求，根據(jù)用戶的委托驗(yàn)證請求生成相應(yīng)的挑戰(zhàn)信息，對云服務(wù)提供商發(fā)起相應(yīng)的挑戰(zhàn)-應(yīng)答游戲請求,然后云服務(wù)提供商響應(yīng)第三方審計(jì)者所發(fā)起的挑戰(zhàn)，進(jìn)行數(shù)輪挑戰(zhàn)-應(yīng)答游戲[10]。最后第三方審計(jì)者根據(jù)數(shù)輪挑戰(zhàn)-應(yīng)答游戲的結(jié)果，得到對應(yīng)的用戶數(shù)據(jù)完整性證明結(jié)果，并將該完整性證明返回給用戶。

2.2 基本算法

基本算法主要由5個(gè)多項(xiàng)式時(shí)間算法組成，如圖3所示。

圖3 基本算法流程Fig. 3 Basic algorithm model

(1)生成參數(shù)算法KeyGen，由用戶執(zhí)行，算法輸入隨機(jī)長度{0,1}串，輸出公私鑰對(pk,sk) 。

(2)生成標(biāo)簽算法Encode，由用戶執(zhí)行。算法輸入公私鑰對(pk,sk)和數(shù)據(jù)子塊m，輸出對應(yīng)標(biāo)簽對Tm。

(3)生成挑戰(zhàn)算法Challenge，由第三方審計(jì)者執(zhí)行。算法輸入待檢測數(shù)據(jù)子塊集合I(由TPA隨機(jī)產(chǎn)生)，輸出對應(yīng)挑戰(zhàn)信息chal。

(4)生成證據(jù)算法Prove，由云服務(wù)提供商執(zhí)行。算法輸入挑戰(zhàn)信息chal，輸出對應(yīng)證明信息proof。

(5)檢驗(yàn)證據(jù)算法Verify，由第三方審計(jì)者執(zhí)行。算法輸入證明信息proof，輸出證明結(jié)果{0,1}。當(dāng)證明信息有效時(shí)，即用戶數(shù)據(jù)完整性得到證明時(shí)，輸出1。反之，輸出0。

3 驗(yàn)證方案

3.1 驗(yàn)證步驟

(1)初始化階段。用戶執(zhí)行密鑰生成算法KenGen，生成公鑰pk、私鑰sk。用戶將所持有原數(shù)據(jù)塊F分成若干個(gè)數(shù)據(jù)子塊f，并執(zhí)行明文加密算法Enc，對每個(gè)數(shù)據(jù)子塊f用公鑰pk加密，生成每個(gè)數(shù)據(jù)子塊的驗(yàn)證標(biāo)簽。用戶保存私鑰sk，以執(zhí)行密文解密算法Dec，對每個(gè)由數(shù)據(jù)子塊生成的驗(yàn)證標(biāo)簽加以驗(yàn)證。根據(jù)各個(gè)數(shù)據(jù)子塊f[i]所對應(yīng)的數(shù)據(jù)子塊簽名σ[i]，自底至頂建立Merkel樹，最終求得根節(jié)點(diǎn)的哈希值hr。隨后，用戶將各個(gè)數(shù)據(jù)子塊f[i]和其對應(yīng)的數(shù)據(jù)塊簽名σ[i]發(fā)送至CSP，并刪除本地?cái)?shù)據(jù)。

密文解密算法Dec,密文解密者對所接收密文C=(c1,c2)和所持有私鑰sk=s，計(jì)算M′=c2-c1⊙sk=r⊙(A⊙s+e)+msg-(r⊙A)⊙s，以及M=M′mod2。由于隨機(jī)誤差項(xiàng)矩陣e是由服從離散高斯分布的偶數(shù)元素所構(gòu)成，故模2操作后得到最終解密后的明文M=msg。

(2)挑戰(zhàn)階段。用戶委托TPA周期性的對CSP發(fā)起完整性驗(yàn)證挑戰(zhàn)。當(dāng)用戶委托TPA對CSP發(fā)起完整性驗(yàn)證挑戰(zhàn)時(shí)，用戶將欲校驗(yàn)數(shù)據(jù)完整性的數(shù)據(jù)子塊的唯一標(biāo)識符id和其對應(yīng)簽名Sig(id)作為審計(jì)請求發(fā)送至TPA。當(dāng)TPA接收到用戶發(fā)送的審計(jì)請求時(shí)，通過驗(yàn)證簽名的方式來判斷該請求是否來自合法用戶。當(dāng)確認(rèn)用戶合法后，TPA發(fā)起挑戰(zhàn)。TPA隨機(jī)抽取c個(gè)元素構(gòu)造數(shù)據(jù)塊索引集合I={s1,s2,…,sc}并將其發(fā)送至CSP，其中c∈[1,n]。

(3)應(yīng)答階段。當(dāng)CSP接收到TPA發(fā)送的挑戰(zhàn)信息后，自底置頂建立Merkel樹。CSP根據(jù)數(shù)據(jù)塊索引集合I={s1,s2,…,sc}尋找數(shù)據(jù)塊所對應(yīng)的葉子節(jié)點(diǎn)，并尋訪該葉子節(jié)點(diǎn)至Merkel哈希樹根節(jié)點(diǎn)的路徑上所有兄弟節(jié)點(diǎn)，將其記錄為對應(yīng)的輔助路徑集合{Ωi}，其中i∈{s1,s2,…,sc}。最后，CSP將數(shù)據(jù)塊所對應(yīng)的葉子節(jié)點(diǎn)簽名Sig(ci)和輔助路徑集合{Ωi}作為證據(jù)σ={Sig(ci),Ωi}返回給TPA。

(4)驗(yàn)證應(yīng)答階段。當(dāng)TPA接收到CSP返回的驗(yàn)證證據(jù)σ={Sig(ci),Ωi}，i∈{s1,s2,…,sc}時(shí)，利用葉子節(jié)點(diǎn)簽名Sig(ci)和輔助路徑集合{Ωi}，計(jì)算對應(yīng)的Merkel樹根節(jié)點(diǎn)值。如果用戶簽名Sig(ci)通過公鑰pk驗(yàn)證成功，并能通過葉子節(jié)點(diǎn)簽名和輔助路徑集合生成Merkel樹根節(jié)點(diǎn)值，則證明用戶數(shù)據(jù)完整性未被破壞。反之，則證明用戶數(shù)據(jù)完整性遭到破壞。

3.2 正確性與安全性

當(dāng)驗(yàn)證者持有私鑰sk=s時(shí)，有c′=c2-c1⊙sk=c2-c1⊙s=r⊙(A⊙s+e)+msg-(r⊙A)⊙s，因⊙是環(huán)R上的同態(tài)運(yùn)算，其滿足結(jié)合律，故有c′=r⊙A⊙s+r⊙e+msg-r⊙A⊙s=r⊙e+msg。

因隨機(jī)誤差項(xiàng)e是n×t個(gè)偶數(shù)元素，加密消息msg是{0,1}的消息串，故做模2操作后，可得r⊙e=0，即c′=0+msg=msg，等式c′=msg成立，簽名正確性得證。

(3)挑戰(zhàn)應(yīng)答正確性。當(dāng)用戶數(shù)據(jù)塊m=(m1,m2,…,mn)中任一數(shù)據(jù)子塊mi遭到破壞時(shí)，其對應(yīng)簽名Sig(mi)也遭到破壞。因哈希函數(shù)具有單向性和抗碰撞性，故而CSP自底置頂建立的Merkel哈希樹的根節(jié)點(diǎn)值root′與TPA所持有的哈希樹根節(jié)點(diǎn)值root不可能一致。root′≠root不成立，挑戰(zhàn)應(yīng)答正確性可證。

3.3 效率分析

針對所提出的基于格的數(shù)據(jù)完整性驗(yàn)證方法進(jìn)行仿真效率分析，選擇數(shù)據(jù)子塊大小為4 kB，數(shù)據(jù)子塊總數(shù)n=100 000，選取基于BLS簽名方案和ECDSA簽名方案的數(shù)據(jù)完整性驗(yàn)證方案，作為參照對比。重復(fù)進(jìn)行50次仿真實(shí)驗(yàn)，將結(jié)果取平均值，效率對比結(jié)果如表1所示,其中，參數(shù)生成開銷為tc，簽名開銷為tq, 挑戰(zhàn)-應(yīng)答開銷為tt。

表1 數(shù)據(jù)完整性驗(yàn)證方案開銷對比Table 1 Parameters of experimental cost for different data integrity verification

4 結(jié)束語

結(jié)合格簽名和Merkel樹的數(shù)據(jù)完整性驗(yàn)證方法，其具有相對效率優(yōu)勢。該方法的高效性體現(xiàn)在格簽名計(jì)算基于線性運(yùn)算，優(yōu)于基于BLS短簽名和基于ECDSA橢圓曲線簽名的模指數(shù)運(yùn)算和對數(shù)運(yùn)算，減少了簽名的運(yùn)算量，在參數(shù)生成開銷和簽名生成開銷方面具有一定優(yōu)勢。該方法的安全性體現(xiàn)在格簽名基于LWE困難問題，同時(shí)具有一定的抗量子攻擊性，但較其他方案而言，仍存在密鑰復(fù)雜時(shí)計(jì)算困難等問題，優(yōu)化密鑰長度和改進(jìn)環(huán)R上同態(tài)運(yùn)算還需要進(jìn)一步研究完善。