符慶曉

（福建師范大學(xué)數(shù)學(xué)與信息學(xué)院 福建省福州市 350117）

目前，隨著云存儲存儲普及，越來越多的公司以及機(jī)構(gòu)，為了減少本地?cái)?shù)據(jù)存儲和維護(hù)所帶來的經(jīng)濟(jì)負(fù)擔(dān)，都選擇將數(shù)據(jù)外包。然而，由于對數(shù)據(jù)的物理控制不足，云中的所外包的數(shù)據(jù)并不是可信的。為了解決云數(shù)據(jù)的安全問題，研究者專注于設(shè)計(jì)遠(yuǎn)程數(shù)據(jù)檢查(RDC)技術(shù)來減少云數(shù)據(jù)的安全威脅。但現(xiàn)有的RDC 方法使用不同的數(shù)據(jù)結(jié)構(gòu)(如二叉樹)來證明外包數(shù)據(jù)的完整性。但是這種數(shù)據(jù)結(jié)構(gòu)只能審計(jì)普通文件大小，因?yàn)楦麓笮臀募械纳倭繑?shù)據(jù)塊需要重新平衡大量數(shù)據(jù)塊，這會給審計(jì)人員帶來明顯的計(jì)算的開銷。另一方面，與需要極少更新操作的歸檔數(shù)據(jù)相反，一些特定應(yīng)用程序(如WhatApp)的大型數(shù)據(jù)，這些數(shù)據(jù)需要頻繁更新。所以使用傳統(tǒng)的數(shù)據(jù)結(jié)構(gòu)來支持這種頻繁更新操作，將會導(dǎo)致大量的計(jì)算成本。為了解決云存儲服務(wù)的動態(tài)數(shù)據(jù)完整性檢驗(yàn)方案存在的安全和效率問題，本文利用分治表和雙線性對技術(shù)，提出基于分治表的動態(tài)數(shù)據(jù)完整性審計(jì)方案。

1 相關(guān)工作

外包數(shù)據(jù)審計(jì)近年成為研究課題熱門。2007年Ateniese 等[1]年提出使用可證明數(shù)據(jù)方案來審計(jì)外包數(shù)據(jù)。其中主要為使用同態(tài)標(biāo)簽和塊標(biāo)簽生成單個標(biāo)簽。但該方案造成較大計(jì)算成本。Wang等[2]提出基于雙線性聚合簽名和Merkle 哈希樹的動態(tài)遠(yuǎn)程數(shù)據(jù)審計(jì)方案，其方案實(shí)現(xiàn)隱私保護(hù)公共審計(jì)和多用戶環(huán)境下的批量驗(yàn)證，然而造成數(shù)據(jù)擁有者較高計(jì)算成本。為了降低審計(jì)過程中開銷，文獻(xiàn)[3]提出基于代數(shù)簽名(Algebraic Signature)云存儲中數(shù)據(jù)完整性審計(jì)，該方案可以降低外包數(shù)據(jù)審計(jì)過程中的數(shù)據(jù)擁有者和云服務(wù)器的計(jì)算消耗。但該方案無法支持云存儲數(shù)據(jù)動態(tài)更新。文獻(xiàn)[4]提出基于代數(shù)簽名和Merkle 哈希樹的云存儲數(shù)據(jù)審計(jì)方案。由于更新需要重新平衡Merkle 哈希樹，會造成較大的計(jì)算成本開銷。

為此，文獻(xiàn)[5]中提出基于代數(shù)簽名數(shù)據(jù)完整性驗(yàn)證方案。為了減少數(shù)據(jù)審計(jì)過程中數(shù)據(jù)擁有者計(jì)算開銷，該方案采用將云存儲數(shù)據(jù)完整性審計(jì)工作授權(quán)第三方審計(jì)者完成。文獻(xiàn)[5]在支持?jǐn)?shù)據(jù)動態(tài)更新方面，提出Record Table(RTable)數(shù)據(jù)結(jié)構(gòu)以支持外包數(shù)據(jù)動態(tài)更新，然而刪除或者插入數(shù)據(jù)塊(i)，必須移動其余(n-i)，這樣會造成嚴(yán)重的計(jì)算負(fù)載。

為了更好支持云存儲數(shù)據(jù)動態(tài)更新問題，本文提出的外包數(shù)據(jù)審計(jì)方案是對文獻(xiàn)[5]提出方案進(jìn)行改進(jìn)，提出一種基于分治表的動態(tài)外包數(shù)據(jù)審計(jì)方案。

本方案提出一種Divide Conquer Table 數(shù)據(jù)結(jié)構(gòu)(DCT)以支持外包數(shù)據(jù)的動態(tài)更新。其中DCT 數(shù)據(jù)結(jié)構(gòu)在更新操作時，可以很好提高外包數(shù)據(jù)更新操作的效率，減少外包數(shù)據(jù)更新所帶來計(jì)算消耗。

2 預(yù)備知識

本節(jié)介紹系統(tǒng)模型以及安全模型和雙線性對的基本知識。

2.1 系統(tǒng)模型

系統(tǒng)模型包括3 個實(shí)體：用戶，數(shù)據(jù)擁有者(DO)，云存儲提供商(CSP)，第三方審核員(TPA)。

（1）數(shù)據(jù)所有者（DO）：指有存儲需求的用戶，與遠(yuǎn)程CSP建立通信，并將加密數(shù)據(jù)上傳至云存儲服務(wù)器中。

（2）云存儲提供商（CSP）：該實(shí)體負(fù)責(zé)備份用戶數(shù)據(jù)并生成證據(jù)作為收到的質(zhì)詢的響應(yīng)。

（3）第三方審核員（TPA）：審核外包數(shù)據(jù)及其驗(yàn)證由TPA完成。

2.2 雙線對基本知識

假設(shè)G1和GT是具有相同素?cái)?shù)階p 的2 個循環(huán)乘法群。令g 是群G1的一個生成員，那么雙線對映射:G1×G1→GT滿足以下性質(zhì)：

（1）雙線對性：任意g1,g2∈G1和任意a,b∈zp*，都有

（2）非退化性：存在g1,g2∈G1，使得

（3）可計(jì)算性：對所有g(shù)1,g2∈G1，存在一個高效的算法計(jì)算(g1,g2)。

3 云存儲數(shù)據(jù)完整性方案

3.1 基本操作

3.1.1 設(shè)置階段（1）KeyGen(1λ)→(sk,pk).用戶選擇2個隨機(jī)數(shù)sk∈zp* 和u∈G1,并且計(jì)算pk=gsk,那么私鑰為sk，公鑰為（pk，u)。

（2）TagGen(F,sk)→(FID,T).DO 為每 個F[l]數(shù)據(jù)塊構(gòu) 造向量vl=(h(ml1),h(ml2),…h(huán)(mln) ),其中，l∈{1,2,…,s}.然后，用戶為每個每個F[l]數(shù)據(jù)塊計(jì)算一個同態(tài)標(biāo)簽其中BN 表示數(shù)據(jù)塊邏輯索引，F(xiàn)ID 表示文件F 唯一的標(biāo)識。通過上述的計(jì)算，用戶生成一個同態(tài)標(biāo)識集合T={Tl|l∈{1,2,…s}}。

（3）用戶將{F,FID,T}發(fā)給CSP，并刪除該文件的本地備份。

3.1.2 質(zhì)詢階段

審計(jì)者選擇集合{1,2,…s}的一個子集I={s1,s2,…sc},并選擇一個隨機(jī)數(shù)k∈ZP*; 計(jì)算一個系數(shù)al=fk(l),其中f()是一個偽隨機(jī)函數(shù)。

3.1.3 回應(yīng)階段

3.1.4 驗(yàn)證階段

收到響應(yīng)消息后,審核員可以通過以下方法檢查外包塊的完整性：

3.2 動態(tài)數(shù)據(jù)分治表操作

云存儲數(shù)據(jù)更新是數(shù)據(jù)審計(jì)的一個重要的特征[6][7]，允許數(shù)據(jù)所有者(DO)在不需要下載數(shù)據(jù)的情況下，對外包數(shù)據(jù)進(jìn)行更新。本小節(jié)將描述提出的數(shù)據(jù)結(jié)構(gòu)DCT(分治表)，此數(shù)據(jù)結(jié)構(gòu)可以高效地進(jìn)行動態(tài)數(shù)據(jù)的更新操作。

方案中提出DCT(分治表)，DCT 由3 個部分組成:

（1）IN:IN 是數(shù)據(jù)塊的索引值,存儲數(shù)據(jù)塊的具體物理地址。

（2）BN:BN 是數(shù)據(jù)塊的邏輯編號，存儲數(shù)據(jù)塊的邏輯地址。

（3）TIME:TIME 為數(shù)據(jù)塊完成更新后相對系統(tǒng)的時間。

數(shù)據(jù)修改：

假設(shè)文件塊F[l]的需要修改為F^'' [l],則具體過程為：

（1）首先在DCT 中，通過比較l 和每個DCT 的范圍來查找數(shù)據(jù)[l]的位置[p]。

（2）修改,TIME=SYSTIME。

（3）更新vl''=(h(ml1''),h(ml2''),…h(huán)(mln''))。

（5）將(FID,l,F''[l],Tl'')發(fā)給CSP。

數(shù)據(jù)插入：

假設(shè)文件塊F*[l+1]插入在F[l]后面，則具體過程為：

（1）首先在DCT 中，通過比較l 和每個DCT 的范圍來查找數(shù)據(jù)塊[l]的位置[p]。

（2）在數(shù)據(jù)塊[l]的位置[p]后創(chuàng)建一行位置(IN*,BN*,TIME*),IN*=l+1,BN*=Max(LN)+1,TIME*=SYSTIME。

（5）將當(dāng)前DCT 的最大范圍，以及其后DCT 的最小和最大范圍均增加1。

（6）將(FID,l+1,F*[l+1],T*l+1)發(fā)給CSP。

數(shù)據(jù)附加：

假設(shè)需要增加新的文件塊F[s+1]到文件F 后面，則具體過程為：

（1）首先在最后一張DCTlast,在表尾增加新的一行(IN',BN',TIME')。

（2）IN'=s+1,BN'=Max(BN)+1,TIME'=SYSTIME。

（3）修改最后一張D&CTlast的上界UBlast=UBlast+1，既是最后一個DCT 的最大范圍增加1。

（4）vs+1=(h(m[s+1][1]),h(m[s+1][2]…) h(m[s+1][n]))。

（6）將(FID,s+1,F[s+1],Ts+1)。

數(shù)據(jù)刪除：

假設(shè)需要刪除文件塊F[l],具體的過程為：

（1）首先根據(jù)DCT 最小和最大范圍找到存儲的數(shù)據(jù)塊[l]，然后在DCT 中確定該塊的位置[p]。

（2）刪除該表的第[p]行，該表第[p]行后面的行需要向上移動。

（3）將當(dāng)前DCT 的最大范圍，以及其后DCT 的最小和最大范圍均減1。

4 算法正確性分析

本節(jié)對云存儲數(shù)據(jù)審計(jì)算法正確性進(jìn)行分析。當(dāng)云存儲供應(yīng)商(CSP)接收到質(zhì)詢消息時，會生成(μ,σ)作為一個證據(jù)消息，并發(fā)送給審計(jì)者。審計(jì)者能夠判定CSP 是否誠實(shí)地使用的數(shù)據(jù)塊和標(biāo)簽計(jì)算證據(jù)P.如果CSP 和審計(jì)者能夠誠實(shí)地按方案進(jìn)行計(jì)算，那么CSP 生成的證據(jù)P 就能夠通過審計(jì)者的數(shù)據(jù)完整性檢查。

證明：

私鑰為sk，公鑰為（pk，u)

證畢

5 實(shí)驗(yàn)分析

本方案的實(shí)驗(yàn)性能分析，主要分析包括：動態(tài)數(shù)據(jù)更新的計(jì)算成本：DO 對外包數(shù)據(jù)執(zhí)行修改、插入、附加和刪除更新操作所需的時間計(jì)算成本。實(shí)驗(yàn)配置為Intel Core i5-8250U CPU @ 1.6GHz以及8GB RAM 的PC，使用Eclipse 開發(fā)工具并使用JAVA 語言實(shí)現(xiàn)本方案的算法。

本文所提的方案算法與文獻(xiàn)[5]提出的外包數(shù)據(jù)動態(tài)更新算法進(jìn)行比較。實(shí)驗(yàn)中，DO 對外包文件F 大小為1GB 進(jìn)行動態(tài)更新，外包文件F 包含125000 個數(shù)據(jù)塊，每個數(shù)據(jù)塊8KB。實(shí)驗(yàn)中更新數(shù)據(jù)塊數(shù)從100 到1000 遞增，間隔為100，每次更新數(shù)據(jù)塊隨機(jī)抽取。實(shí)驗(yàn)結(jié)果如圖1 所示，可以看出本文提出的外包數(shù)據(jù)更新算法方案高效性。文獻(xiàn)[5]提出的動態(tài)數(shù)據(jù)更新方案，插入或者刪除數(shù)據(jù)塊F[i]，然后需要移動(n-i)次，這樣會造成更新操作極大的計(jì)算負(fù)載。而本文所提方案可以在更新操作中，插入或者刪除數(shù)據(jù)塊F[i]，只需更改移動1 次，從而可以很大程度上降低數(shù)據(jù)擁有者DO 計(jì)算負(fù)載。

圖1 顯示出在更新不同數(shù)據(jù)塊的計(jì)算成本，實(shí)驗(yàn)的結(jié)果表明本文所提出方案可以顯著降低更新數(shù)據(jù)的計(jì)算成本開銷。

圖1：更新外包數(shù)據(jù)塊時間成本

6 結(jié)論與未來研究

本文提出了一種用于云存儲數(shù)據(jù)的高效審計(jì)方案，提出的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)的分治表能夠地支持動態(tài)數(shù)據(jù)操作，例如附加、插入、修改和刪除等操作。然而本文在數(shù)據(jù)加密基礎(chǔ)沒有考慮數(shù)據(jù)冗余性，所以在接下來將研究外包數(shù)據(jù)在加密基礎(chǔ)上的去冗余性。