一種高效的基于分治鄰接表的動態完整性審計方案*

符慶曉, 陳蘭香, 李繼國, 姚志強

福建師范大學 計算機與網絡空間安全學院 福建省網絡安全與密碼技術重點實驗室, 福州350117

1 引言

隨著云計算與云存儲的廣泛應用, 越來越多的單位及企業選擇將其數據外包至云服務器. 源于云計算的規模經濟效應, 可以為用戶提供更加專業的數據存儲與管理服務, 同時極大地節約經濟成本與社會能源.當用戶將數據存儲到遠程服務器, 便失去了對數據的物理控制權, 而云服務器往往并不完全可信. 數據外包特性及頻繁爆發的數據安全事件, 使得用戶對云存儲服務的信心不足[1]. 因此需要一種數據完整性審計技術, 讓用戶可以隨時隨地驗證其數據是否完整與可用. 由于數據擁有者無法存儲外包數據的本地副本,所以傳統的完整性驗證在云計算中并不適用[2]. 為了解決云計算中外包數據的完整性審計問題, 研究者提出了遠程數據完整性審計技術[3,4], 但現有的數據完整性驗證方法需要頻繁地進行審計和傳輸, 這樣給審計者造成很大的計算和通信開銷. 在支持外包數據動態更新方面, 現有的遠程數據完整性審計方法采用不同的數據結構以支持數據動態更新, 比如二叉樹、動態Hash 表等, 來證明外包數據的完整性, 但對于大文件中的少量數據塊更新, 基于這些數據結構的驗證算法需要重新平衡大量數據塊, 會帶來較大的計算開銷[5]. 因此, 針對一些需要頻繁更新的數據, 需要設計專門的數據完整性審計方法.

近年來, 針對云存儲環境下的數據完整性審計已經取得了豐碩的研究成果, 也有大量針對數據動態性的研究方案, 但仍然存在諸如安全與效率的平衡、數據的隱私保護以及實用性等幾方面的問題, 下面本文將介紹相關的研究工作.

2 相關工作

2007 年, Ateniese 等[6]最早提出可證明數據持有(provable data possession, PDP) 方案, 該方案使用同態標簽來驗證外包數據完整性. 隨著云計算與云存儲技術的廣泛應用, 驗證外包數據完整性得到研究者的廣泛關注并取得了一系列的研究成果. 鑒于用戶將數據存儲到遠程云存儲服務器后, 通常有數據更新的需求, 因此, 研究者們提出了支持數據動態更新的完整性審計方案.

為了支持外包數據動態更新, 2008 年, Ateniese 等[7]提出了外包數據動態審計方案, 該方案在數據更新時, 讓數據擁有者重新計算塊標簽, 因此會造成較大的計算開銷. 2009 年, Erway 等[8]首次提出基于跳表的動態外包數據審計方案, 但是該方案不支持單個數據塊的完整性驗證, 而且數據塊對應的驗證路徑較長. 2011 年, Wang 等[9]提出基于雙線性聚合簽名與Merkle 哈希樹的動態審計方案, 該方案實現隱私保護公共審計和多用戶環境下的批量驗證. 然而, 該方案會造成外包數據審計時的數據泄露, 而對于云存儲中大型外包數據文件也會帶來較高的計算開銷. 2015 年, 文獻[10] 提出基于雙線性對與Merkle 哈希樹的云存儲動態數據完整性審計方案, 該方案通過將數據塊分割成長度更小的數據塊, 使得Merkle 哈希樹的每個葉子節點對應多個數據塊, 從而有效降低Merkle 哈希樹的高度, 但是該方案在數據初始化階段的計算開銷較大.

為了減少審計過程中的計算開銷, 文獻[11] 提出基于代數簽名(algebraic signature) 的數據完整性驗證方案, 可以顯著降低外包數據審計過程中數據擁有者和云服務器的計算開銷. 然而該方案無法支持外包數據的動態更新. 為支持動態數據更新,文獻[12]提出基于Merkle 哈希樹的云存儲數據審計方案,但是因為Merkle 哈希樹在數據更新時需要重新平衡二叉樹, 造成較大的計算開銷. 而且該方案在審計過程中, 數據擁有者需要對云存儲中的外包數據進行完整性驗證, 而不是授權給第三方審計者(third party auditor,TPA), 從而在外包數據審計過程中, 極大地增加了數據擁有者和云存儲服務器的計算開銷.

2014 年, 文獻[13] 提出一個基于代數簽名的云存儲動態數據審計方案, 該方案引入了第三方審計者TPA, 減輕了審計過程中數據擁有者的計算開銷, 并且提出索引表數據結構以支持數據動態更新, 但是該方案在數據更新時的效率比較低. 不久, 文獻[14] 提出一個結合代數簽名和分治表的動態數據審計方案,該方案使用代數簽名對外包數據進行完整性審計, 同時提出分治表數據結構來支持數據的動態更新, 使得動態數據更新計算開銷得到顯著降低. 然而該方案使云存儲服務器在不訪問外包數據的情況下可以生成有效的證明, 從而容易造成審計過程中的數據隱私泄露并且容易受到重放攻擊. 2018 年, 文獻[15] 也提出一個結合代數簽名和分治表的動態數據審計方案, 與文獻[14] 不同的是, 該方案首先對數據塊的索引號加密, 然后再生成塊的校驗值和塊標記, 這樣可以有效抵抗審計過程中的重放攻擊和數據泄露問題. 然而該方案在審計過程中的初始化階段會給數據擁有者造成過大的計算開銷. 因此, 文獻[16] 提出一個基于代數簽名的數據完整性驗證方案, 為了減少數據審計過程中數據擁有者的計算開銷, 該方案引入第三方審計者, 將外包數據完整性審計授權給第三方審計者. 為了保護外包數據并防止審計過程中的數據隱私泄露問題, 他們還提出了異或同態函數(XOR-homomorphic function) , 可以一定程度上保護外包數據審計時所造成的隱私泄露問題. 最近, 韓靜等[17]提出一種輕量級的支持用戶可動態撤銷及存儲數據可動態更新的云審計方案, 利用多重單向代理重簽名技術實現動態撤銷, 引入虛擬索引實現實時動態更新. 文獻[18] 利用Fisher-Yates Shuffles 算法構造異或同態函數, 使得算法的時間開銷比較大, 時間復雜度為O(n2). 在支持外包數據更新方面, 他們設計了記錄表(record table, RTable)數據結構以支持外包數據動態更新, 但刪除或者插入數據塊(i), 必須移動(n ?1) 個數據塊, 因此造成嚴重的計算負載.

為了解決數據動態更新過程中計算開銷太大的問題, 本文設計一種新的分治鄰接表(divide and conquer adjacency table, D&CAT) 數據結構實現高效的動態更新操作. 數據的基本審計方案基于代數簽名, 為了保護審計過程中的數據隱私, 使用Knuth-Durstenfeld Shuffle 算法構造異或同態函數, 相比算法Fisher-Yates Shuffles 的O(n2), 根據文獻[19] 洗牌算法證明, 該算法的時間復雜度O(n), 從而可以相應減少異或同態函數的時間開銷. 分治鄰接表結構在外包數據更新操作時, 當刪除或者插入數據塊(i)時, 只需要修改對應數據塊的鏈表指針, 從而可以有效提高外包數據更新操作的效率.

下文結構組織如下: 第3 節介紹相關預備知識, 包括系統模型、代數簽名與異或同態函數; 第4 節詳細介紹本文提出的完整性審計方案; 第5 節對本方案的安全性與性能進行分析; 第6 節總結全文并指出下一步的研究工作.

3 預備知識

本節介紹系統模型、代數簽名和異或同態函數的相關知識.

3.1 系統模型

本文提出方案的系統模型包括3 個實體: 數據擁有者, 云存儲服務器, 第三方審計者. 其系統模型如圖1 所示.

圖1 外包數據審計流程Figure 1 System model

(1) 數據擁有者(data owner, DO): 指將數據存儲在云存儲服務器中的企業或個人, 他們擁有修改、插入、刪除權限來更新外包數據.

(2) 云存儲服務提供者(cloud storage provider, CSP): 負責存儲數據擁有者的數據并生成驗證證據作為對用戶挑戰的響應.

(3) 第三方審計者(third party auditor, TPA): 審計外包數據并進行完整性驗證.

3.2 代數簽名

代數簽名(algebraic signature) 是一種具有同態性的哈希函數, 用于為文件塊生成同態標簽. 代數簽名的代數性質是指數據塊的代數簽名之和與相應數據塊之和的代數簽名相同. 由n個數據塊(F[1],F[2],··· ,F[n]) 組成的文件F的代數簽名計算如下:

其中,γ為有限域的本原元素, 代數簽名有以下3 個性質:

性質1: 長度為r的數據塊F[I] 和F[j] 相連接的代數簽名計算公式為

性質2: 文件F的所有數據塊之和的代數簽名與每個數據塊代數簽名之和相等:

性質3: 文件F與文件G之和的代數簽名與各個代數簽名之和相等:

3.3 異或同態函數

異或同態函數(XOR-homomorphic function) 是指具有異或同態特性的偽隨機函數, 它可以增強對數據的隱私保護. 異或同態函數f有以下相應的性質:

性質4: 對輸入x1,x2的異或運算等于函數f對每個輸入的異或運算:

性質5: 對于置換密鑰(k1,k2), 則:

3.4 威脅模型

當DO 將數據外包到云存儲中, 并將數據委托給CSP 時, 數據的完整性可能面臨以下風險:

(1) 由于硬件或管理錯誤, 以及各種內部或外部攻擊, CSP 有可能隱藏外包數據丟失或受損情況.

(2) 為了節省資源, CSP 可能會忽略執行數據所有者要求的數據更新操作. 例如, 在挑戰驗證階段, 不誠實的CSP 可能利用以前的合法響應或其他信息生成證明, 而不需要檢索實際外包數據, 以欺騙TPA 通過驗證(重放攻擊) .

針對以上問題, 本文提出一種通過驗證外包數據的完整性來檢測CSP 不當行為的方法.

4 方案詳細設計

本節首先對方案的幾個算法進行形式化描述, 然后對每個算法進行詳細介紹.

4.1 算法形式化描述

本文提出的動態數據完整性審計方案包括兩個部分: 基本的完整性審計方案與動態數據更新方案. 基本的完整性審計方案分為4 個階段: 初始化階段、挑戰階段、回應階段與驗證階段, 包括5 個多項式時間算法; 動態數據更新方案包括4 個多項式時間算法. 算法的形式化定義如下.

? Setup (1λ)→(params,sk) : DO 使用Setup 算法以安全參數λ為輸入, 隨機輸出公共參數params 和密鑰sk.

? TagGen(params,sk,F)→(T) : DO 使用TagGen 算法, 以公共參數params、密鑰sk、文件F為輸入, 輸出每個數據塊的標簽Ti.

? Challenge (c)→(chal) : TPA 使用Challenge 算法隨機輸出挑戰消息chal.

? Response(params,F,Ti,chal)→(proof): CSP 使用Response 算法, 以公共參數params、外包文件F、挑戰消息chal 以及對應挑戰塊的標簽為輸入, 輸出回應消息proof.

? Verify(params,sk,chal,proof)→(1,0): TPA 使用Verify 算法, 以公共參params、密鑰sk 和回應消息proof 作為輸入, 輸出結果1 或0.

動態數據更新方案的4 個多項式時間算法的形式化定義如下.

4.2 算法詳細設計

上節對本方案的算法進行了形式化描述, 下面將對以上算法的詳細過程進行描述.4.2.1 基本的完整性審計

基本的完整性審計方案分為4 個階段: 初始化階段、挑戰階段、回應階段與驗證階段, 包括5 個多項式時間算法, 分別詳述如下, 其流程如圖2 所示.

圖2 外包數據審計流程Figure 2 Audit processs

(1) 初始化算法Setup(1λ)→(params,sk) 的執行過程如下.

(1.1) 數據擁有者DO 首先通過數據分片技術將文件F分為n個數據塊F[1],F[2],··· ,F[n].

云存儲服務器CSP 接收到TPA 的挑戰消息chal 后執行以下計算:

(5) 驗證算法Verify(params,sk,chal,Proof)→(1,0) 的執行過程如下.

當TPA 接收到CSP 發送的Proof 消息時, TPA 首先計算TCi=fskt(τi ⊕vi), 然后計算ωi=μi ⊕TCi, 此后TPA 可以通過以下等式驗證外包數據塊的完整性:

其正確性證明如下:

4.2.2 基于分治鄰接表的動態數據更新

動態數據更新是數據完整性審計中的一個非常重要的特征, 實現不用下載數據情況下的外包數據的更新. 盡管文獻[16] 提出的RTable 數據結構可以支持動態數據更新. 但插入一個數據塊需要完成(n ?1)次數據塊移動. 為了更好地支持動態數據更新, 本文提出分治鄰接表數據結構, 在刪除或者插入數據塊(i) 時, 只需要修改對應數據塊的鏈表指針, 不需要移動之后的數據塊, 同時, 根據表頭結點的LMIN 與LMAX 可以快速定位結點, 從而可以較好地提高外包數據更新操作的效率.

分治鄰接表主要由兩個數據結構組成: 表頭數組與鏈表. 表頭數組的每個結點由四個部分構成:LMIN 表示對應鏈表最小的數據塊的索引號, LMAX 表示為對應鏈表最大的數據塊的索引號, FIRST表示對應鏈表的頭指針, REAR 表示對應鏈表最后一個結點指針. 鏈表則由三個部分構成: LN 表示數據塊的索引號, TIME 表示數據塊最后更新的時間, NEXT 表示下一個結點的指針. 同時為了表述方便, 使用MAX 表示文件最大的邏輯索引號.

數據擁有者DO 在上傳外包數據到CSP 之前, 為每個文件生成對應的D&CAT 數據結構. 為了實現數據的動態更新, 我們設計了數據修改Modify、數據插入Insert、數據附加Add 與數據刪除Delete 等4個數據更新算法.

假設DO 需要修數據塊F[2], 則修改前的分治鄰接表如圖3 所示.

圖3 數據修改前的分治鄰接表Figure 3 D&CAT before modification

當修改完成后, 分治鄰接表如圖4 所示.

圖4 數據修改后的分治鄰接表Figure 4 D&CAT after modification

假設DO 需要在數據塊F[2] 后插入一個新的數據塊, 設新數據塊插入前的分治鄰接表如圖4 所示. 而當新數據塊插入完成后, 其分治鄰接表如圖5 所示.

圖5 插入數據塊后的分治鄰接表Figure 5 D&CAT after inserting

(3) 數據附加算法Add(F[n+1])→(Tn+1,DCn+1,Noden+1) 的執行過程如下.假設DO 需要將新的數據塊F[n+1] 附加到文件F后面, 則DO 將會執行以下操作:

(3.1) 找到表頭結點的最后一個結點.

(3.2) 創建一個新的鏈表結點Noden+1, 即LN=MAX,TIME=TIMEn+1, 其中TIMEn+1為當前時間, NEXT=∧.

(3.3) 修改表頭結點的LMAX = LMAX+1, 將對應鏈表最后一個結點域NEXTrear指向新創建的鏈表結點, 然后將REAR 指向新建的結點Noden+1.

(3.4) 計算Cn+1=fsko⊕skc⊕skt(F[n+1]⊕rn+1) 和DCn+1=fsko(τn+1⊕rn+1), 其中τn+1=FID‖LN‖TIME, 然后計算Tn+1=Sγ(Cn+1‖τn+1‖rn+1).

(3.5) DO 將{F[n+1],Tn+1,DCn+1}發送給CSP.

假設DO 在文件F附加一個新的數據塊, 設新數據塊附加前的分治鄰接表如圖5 所示. 而新數據塊附加完成后, 其分治鄰接表如圖6 所示.

圖6 附加新數據塊后的分治鄰接表Figure 6 D&CAT after adding

(4) 數據刪除算法Delete(i)→(1,0) 的執行過程如下.

假設DO 需要將數據塊F[i] 刪除, 則DO 將會執行以下操作:

(4.1) 根據F[i] 查找表頭數組, 若滿足LMIN

(4.2) 若第i個數據塊對應結點為鏈表第一個結點, 則將表頭結點域FIRST = NEXTi. 若第i個數據塊對應結點為鏈表最后結點, 則直接將表頭結點域REAR 指向第i ?1 個結點. 若第i個數據塊既不是鏈表對應第一個結點和最后結點, 則將第i ?1 對應的結點中NEXTi?1=NEXTi, 相應表頭結點LMAX 以及隨后表頭結點中LMIN 和LMAX 均減1.

(4.3) CSP 刪除對應數據塊, 刪除完成后, CSP 返回1, 否則返回0.

假設DO 需要刪除數據塊F[2], 設刪除數據塊前的分治鄰接表如圖6 所示. 在刪除數據塊完成后,其鄰接表如圖7 所示.

圖7 刪除數據塊后的分治鄰接表Figure 7 D&CAT after deleting

5 安全性與性能分析

本節對方案的安全性與性能進行分析.

5.1 安全性分析

本方案的核心是對存儲在云服務器上的數據執行完整性審計, 而且由可信第三方審計者TPA 代替數據擁有者進行不定期審計. 關于數據的機密性與訪問控制不在本文的討論范圍, 而且在實際系統中, 數據可以加密存儲, 本方案仍然適用于作加密數據的完整性驗證. 在系統模型三方之間的相互認證可以使用已有的認證機制, 相互的通信可以使用保密信道, 比如SSL/TLS.

這里的安全性分析主要考慮的是數據完整性審計方案及動態更新過程中的安全問題, 包括代數簽名的魯棒性與異或同態函數的安全性, 本方案中代數簽名可取足夠長的簽名長度, 碰撞概率是非常低的, 甚至可以忽略不計. 一個128 bits 的簽名可能發生的碰撞概率為2?128, 一個256 bits 的代數簽名可能發生的碰撞概率則為2?256, 同時代數簽名的計算效率非常高. 在保護數據隱私泄露方面, 方案使用Knuth-Durstenfeld Shuffle 算法構造異或同態函數生成隨機校驗值, 使得TPA 將無法在審計外包數據時獲取任何關于用戶的信息, 卻可以審計外包數據完整性.

同時, 因為本方案支持外包數據動態更新, 所以當更新數據塊時, 也需要相應更新對應的數據塊的標簽. 然而, 不誠實CSP 有可能不響應DO 更新外包數據請求. 所以CSP 可能利用過期的版本的外包數據塊和標簽欺騙TPA. 為此, 為了抵抗重放攻擊方面, 假設DO 請求CSP 更新外包數據, 如果CSP 忽略外包數據更新請求, 并在TPA 審計數據時發送舊的數據標簽, 這時TPA 可以檢測到CSP 的行為. 這是因為分治鄰接表數據結構中的參數TIME 記錄每個數據塊相應更新時間, 并嵌入對應數據塊標簽中即是τi=FID‖LN‖TIME,Ti=Sγ(Ci‖τi), 所以重放的標簽不能以一個不可忽略的概率通過TPA 的驗證.

本文方案相比于文獻[16], 一方面是使用分治鄰接表數據結構替代記錄表數據結構來實現更加高效的數據更新. 另一方面利用Knuth-Durstenfeld Shuffle 算法[18]構造異或同態函數, 實現時間復雜度從Fisher-Yates Shuffles 算法的O(n2) 下降至O(n). 關于本文方案的形式化安全性證明可以參考文獻[16].

5.2 篡改概率分析

本方案的外包數據驗證采用隨機抽樣策略, 外包數據篡改檢測的概率是基于數據塊抽樣. 即將文件F分為n個數據塊, 并隨機選擇c個數據塊作為一個質詢檢測, 下面對外包數據篡改檢測概率進行分析.

所以可得外包數據篡改檢測的概率范圍為:

假設DO 將1 GB 文件劃分為125 000 個數據塊, 則每個數據塊為8 KB, 然后將數據上傳至CSP,若PX= 0.9 以及PX= 0.999 99 的概率檢測到外包數據篡改時, 不同數量的篡改數據塊與挑戰數據塊的關系如圖8 所示.

由圖8 可知, 若要TPA 檢測概率達到PX= 0.9, 當CSP 篡改數據塊比例為10% 時, 則至少需要挑戰質詢的數據塊個數為22 塊; 若要TPA 檢測概率達到PX=0.95, 且在CSP 篡改數據塊比例為10% 條件下, 則需要挑戰質詢的數據塊個數為30 塊; 若要TPA 檢測概率達到PX=0.97 在同樣條件下, 則至少需要挑戰的數據塊個數為35 塊; 若要TPA 檢測概率達到PX= 0.999 99, 則至少需要質詢的數據塊個數為110 塊.

5.3 性能分析

關于外包數據完整性審計方案的存儲開銷與通信開銷, 大部分方案都是相似的, 因此本文主要從計算開銷, 即方案的計算效率方面進行分析.

實驗利用一臺配置為Intel Core i5-8250U CPU @ 1.6 GHz CPU 以及8 GB RAM 的PC 機, 采用Eclipse 集成開發工具并使用Java 語言實現本文方案與文獻[9,16] 方案中的數據審計與動態更新算法.

本方案的性能分析主要包括兩個方面:

(1) 基本審計方案的時間開銷: 包括初始化階段, DO 用于生成文件塊標簽的計算開銷; 響應階段CSP 生成證據的計算開銷; 驗證階段, TPA 驗證外包數據塊完整性的計算開銷.

(2) 動態更新方案的時間開銷: DO 對外包數據執行修改、插入、附加和刪除更新操作所需計算開銷.

為了分析基本審計方案中代數簽名長度和數據塊大小對初始化階段時間開銷的影響, 我們選取5 GB的文件, 分別將外包文件的數據塊分為8 KB、16 KB、32 KB、64 KB, 并依次選取代數簽名長度為64、128、256 及512 bits, 分析實驗中初始化階段的時間開銷, 實驗的結果取10 次測試結果的平均值, 其時間開銷如圖9 所示.

圖9 初始化階段時間開銷Figure 9 Time overhead of setup phase

由圖9 可知, 在代數簽名長度相同的情況下, 隨著數據分塊大小的增加, 初始化階段計算開銷減少. 在數據塊大小相同情況下, 隨著代數簽名長度的增加, 初始化階段時間開銷也相應減少. 實驗結果表明, 隨著代數簽名長度和數據分塊增加, 初始化階段的開銷相應減少, 其原因是簽名長度長, 分塊粒度大, 減少分塊數量, 從而減少計算時間.

我們設定將外包文件的數據塊分為8 KB, 挑戰外包數據塊數為5000, 并依次選取代數簽名長度為依次選取代數簽名長度為128、256 及512 bits, 分析實驗中回應階段和驗證階段的時間開銷, 實驗的結果取10 次測試結果的平均值, 時間開銷如圖10 所示.

圖10 回應階段和驗證階段時間開銷Figure 10 Time overhead of response and verification phase

由圖10 所示可知, 在數據分塊大小為8 KB 情況下, 隨著代數簽名長度的增加, 回應階段時間開銷也相應減少. 然而, 即使代數簽名長度增加, 驗證階段的時間開銷始終大約在25 ms 左右. 實驗結果表明, 隨著代數簽名的增加, 響應階段的時間開銷降低.

為了測試動態更新方案的時間開銷, 我們將本文所提方案與文獻[9,16] 提出的方案從數據修改、插入、附加與刪除操作進行比較. 選取5 GB 的文件, 設分塊大小為8 KB, 代數簽名長度為512 bits, 更新數據塊數量從1000 到10 000 遞增, 每次更新數據塊隨機抽取. 數據修改操作的實驗結果如圖11 所示.

圖11 不同數據塊數的修改時間開銷Figure 11 Modification time overhead of different number of blocks

與文獻[16] 相比, 當修改數據塊數小于5000 時, 兩方案的時間開銷是相似的, 但當修改數據塊數繼續增加時, 本方案的時間開銷高于文獻[16] 方案的開銷. 由于文獻[16] 方案采用RTable 數據結構, 在查找數據塊時速度比較快, 所以在修改數據塊時優于本文所提方案. 與文獻[9] 相比, 本文方案與文獻[16] 方案的數據修改效率均較高.

數據插入操作的時間開銷如圖12 所示, 文獻[9] 提出的動態數據插入操作需要重新調整Merkle 樹,所以會造成較大的計算開銷. 文獻[16] 提出的動態數據插入方案在插入數據塊F[i] 時, 需要(n ?i) 次數據塊移動操作, 因此會造成較大的時間開銷. 而在本文所提方案中, 插入數據塊F[i] 只需要修改對應的指針, 即只需移動1 次, 從而可以極大地降低插入操作的時間開銷. 實驗結果表明本文所提出方案可以顯著降低插入數據的計算開銷.

圖12 不同數據塊數的插入時間開銷Figure 12 Inserting time overhead of different number of blocks

數據附加操作的時間開銷如圖13 所示, 文獻[9] 提出的動態數據附加方案需要重新調整Merkle 樹,因此有較高的計算開銷. 在文獻[16] 提出的動態數據附加方案中, 當附加數據塊F[n+ 1] 時, 需要將RTable 表的長度由n增加為n+1, 此操作的時間開銷較大. 而在本文所提方案中, 附加數據塊F[n+1]只需將rear 指針指向新的附加數據塊, 因此本文方案的附加操作可以顯著降低計算開銷.

圖13 附加不同數據塊數的時間開銷Figure 13 Addition time overhead of different number of blocks

數據刪除操作的時間開銷如圖14 所示, 刪除操作與插入操作正好相反, 即刪除數據塊F[i] 時, 文獻[16] 提出的動態數據刪除操作需要移動(n ?i) 次數據塊; 文獻[9] 刪除數據塊時與動態插入數據一樣,需要動態調整Merkle 樹, 因此它們的計算開銷均較大. 本文所提方案只需更改對應的指針, 即只需移動1次, 所以本文所提出方案刪除操作可以顯著地降低計算開銷.

圖14 刪除不同數據塊數的時間開銷Figure 14 Deleting time overhead of different number of blocks

表1 主要分析文獻[9,16] 與本方案的外包數據更新的計算開銷對比, 其中n代表外包數據塊個數,c代表更新的外包數據塊個數.

表1 不同方案的數據更新操作對比Table 1 Comparison of data updating of different schemes

因此, 四種數據更新操作中, 文獻[16] 只有修改操作的時間開銷略低于本文方案, 其余三種更新操作,包括插入、附加與刪除操作的時間開銷都比本文方案高, 文獻[9] 的四種更新操作的時間開銷均是最大.總地來說, 本文方案的計算是最高效的.

6 結論與未來研究

本文提出一種高效的外包數據完整性驗證方案, 采用代數簽名驗證外包數據的完整性, 為了防止審計時造成數據隱私泄露問題, 引入了異或同態函數. 同時為了更好地支持外包數據的動態更新操作, 我們設計出一種分治鄰接表數據結構提供更加高效的數據更新. 實驗結果表明本文方案的可行性和高效性. 下一步工作中, 我們將在此基礎上通過運用輕量級加密技術, 實現更加有效防止外包數據泄露的方法, 同時希望將本方案進一步擴展, 用于分布式云存儲系統.