一種云存儲完整性的格簽名驗證方法

常 亮， 王冠棋， 楊雪欣

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

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

1 基本原理

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

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

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

1.2 格和格難題

1.3 LWE問題

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

1.4 同態(tài)簽名

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

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

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

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

公鑰同態(tài)加密方案，一般由3個多項式時間算法構(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)，可以花費較短的開銷進行數(shù)據(jù)驗證，其被廣泛應用于云存儲、P2P、比特幣等需要進行快速驗證的領域[5]。其葉子節(jié)點存儲各個數(shù)據(jù)子塊的哈希值，非葉子節(jié)點存儲其子節(jié)點值之和的哈希值[6]。

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

2 系統(tǒng)模型

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

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

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

2.2 基本算法

基本算法主要由5個多項式時間算法組成，如圖3所示。

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

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

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

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

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

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

3 驗證方案

3.1 驗證步驟

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

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

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

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

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

3.2 正確性與安全性

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

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

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

3.3 效率分析

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

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

4 結(jié)束語

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