基于云存儲的動態組共享數據完整性驗證方案

李秀艷，劉明曦，史聞博，郝旭龍，董國芳+

(1.云南民族大學 電氣信息工程學院，云南 昆明 650500；2.東北大學 計算機科學與工程學院，遼寧 沈陽 110819；3.東北大學秦皇島分校 計算機與通信工程學院，河北 秦皇島 066004)

0 引 言

云存儲服務中最常見的客戶之一就是擁有大數據應用的企業用戶組[1,2]，它們常需要頻繁地訪問和更新外包數據，借助云存儲服務，企業允許他們的內部員工存儲和共享數據，以及企業間的數據共享。但云存儲在給企業用戶帶來便利的同時，也面臨著各種安全威脅。

首當其沖的是數據完整性問題，當組用戶(group user，GU)在云端進行數據共享時，失去了對數據的直接控制權，存儲在云端的數據可能會因為硬件故障或GU的錯誤行為而失效，GU無法直接知道數據在云存儲服務器(cloud service provider，CSP)中是否完整或正確執行[3]。為了實現用戶數據的完整性驗證，Yang等[4]提出一種高效的云存儲審計方案，同時還支持用戶的身份隱私和身份的追溯性，但在這個過程中，TPA可能會獲得一些數據的相關信息，TPA只是在代表用戶檢查數據完整性時是可信的，其不應了解任何數據內容的相關信息。雖然現已提出了許多基于不同簽名的完整性檢查方案[5]，但仍存在許多安全問題[6]。因此，如何確保存儲在云端共享數據的完整性成為一個亟待解決的熱點問題[7]。除了數據的完整性，數據的可用性和數據可驗證刪除問題也同樣面臨著各種安全挑戰[8]。特別是數據刪除問題，其作為外包數據生命周期的最后一個階段，直接決定了數據共享能否順利結束，這對數據安全和隱私保護有著重要的意義。現有的數據刪除方案有斷開鏈接、覆蓋和消除數據解密密鑰3種方式[9-11]。雖然現已可以實現數據刪除，但其無法實現數據刪除的公開可驗證性。此外對于云端數據不僅應該被訪問，還應被用戶端更新，如數據的插入、修改和刪除操作。為了支持數據動態操作，很多研究員提出了一些基于跳表、哈希表、二叉樹和Merkle樹等數據結構來支持GU數據實時更新的需求[12-14]。但動態的高效性仍然未得到滿足。為解決這些問題，本文提出一個基于云存儲的動態組共享數據完整性驗證方案。其貢獻總結如下：

(1)提出一種高效且安全的基于桶的紅黑樹(bucket-red black tree，B-RBT)動態數據結構，該結構用來支持GU共享數據的動態操作，其在常數時間內完成數據的更新及結構的更新再平衡，實現數據操作的高效性。

(2)提出一個GU共享云數據完整性驗證方案。方案基于計數布隆過濾器(counting Bloom filter，CBF)結構實現高效的公開可驗證數據刪除，其驗證過程可在O(1) 時間內完成。還支持批量審計驗證操作，不同用戶的多個審計任務可以同時進行處理。

(3)通過具體的安全分析，證明了所提方案的正確性和安全性，在實驗仿真中，與其它方案進行了對比分析，實驗結果表明，本方案是安全且高效的。

1 問題描述

1.1 系統模型

如圖1所示，本方案的系統模型由4個實體組成，包括GU、私鑰生成器(private key generator，PKG)、TPA和CSP。GU：主要由組管理者(group administrators，GA)和組成員(group members，GM)構成。GA負責管理組成員之間信息的變更情況，有一定的計算和存儲能力，負責為GM生成簽名。一個組中有多個組成員，合法的組成員是誠實的，其中每個組成員都可以通過云服務器與其它組成員共享數據；PKG：誠信的私鑰分發中心，據GU的身份信息，生成系統公共參數和組的身份密鑰；TPA：它負責代表GU執行云存儲審計，對數據存在誠實好奇性，審計中需要保護數據隱私。CSP：為半誠信實體，負責為GU提供巨大的存儲資源和計算資源。通過云存儲，企業用戶可以享受到數據共享服務。

圖1 系統模型

該系統模型主要包括GU共享數據審計模型和動態數據刪除可驗證模型。GU共享數據審計模型可描述如下：首先GU對共享數據文件進行分塊和盲處理，接著對盲數據塊進行簽名發送給TPA，在TPA收到簽名后對數據簽名進行存儲。當GU有審計需求時，TPA代表GU執行審計的挑戰響應過程來驗證數據存儲的完整性；動態數據刪除可驗證模型描述如下：首先是GU將動態請求和動態數據簽名發送給GU，GU更新特定的數據結構之后將動態請求和數據發送給CSP，CSP收到后在工作表中更新數據。當GU成員變更時，相應的在CSP中共享的數據也隨之變更，特別是當一些數據塊不需要時，CSP為GU刪除不需要的數據塊并返回驗證刪除結果。

1.2 威脅模型

我們考慮的安全挑戰如下：首先是數據隱私泄露，CSP是半誠信實體，一方面，CSP由于硬件或軟件錯誤或者外部攻擊而修改甚至刪除數據時，CSP會隱瞞數據被破壞的事實，向GU返回不正確或不完整的驗證結果。另一方面，CSP可能會將數據轉移給其它服務器，與其它企業共享數據，以實現經濟利益；其次是資源耗盡攻擊，外部攻擊者或過期的GU嘗試從驗證信息中獲取數據信息，通過發送頻繁的動態更新操作來消耗云端的存儲資源或將私有信息進行存儲，從而增大GU的支付開銷。

1.3 設計目標

(1)審計高效性：在GU請求動態操作、審計操作和刪除驗證期間，系統的通信開銷和計算開銷小，整個審計過程時延低，在發送請求后可以快速獲知操作結果。數據結構檢索和更新速度越快，審計效率高。

(2)數據刪除可公開驗證：為了保證CSP能永久的刪除用戶不需要的數據塊，應該賦予GU驗證刪除結果的能力。如果CSP惡意保留數據，沒有執行數據刪除命令并真實地生成刪除證據，那么GU會檢測到惡意的數據保留。

(3)批量審計：TPA單獨執行審計任務的效率很低。由于來自不同用戶的多個審計任務可能正在等待同時處理，由此可以引入批處理審計來提高審計效率。

(4)數據隱私：審計中TPA無法檢索出用戶身份信息或數據信息，為了保護外包數據的敏感信息，在將外包數據存儲到云服務器之前，需對其進行盲化，保護數據隱私安全。

2 預備知識

2.1 雙線性映射對

2.2 困難假設

離散對數問題[8]：對素數p階的乘法循環群， 給定其生成元g和Y=gx∈， 計算x∈p值是很困難的；計算Diffie-Hellman問題：對素數p階的乘法循環群， 隨機選取其中一個生成元g， 給定(g,ga,gb)∈， 在未知a,b∈p的情況下，計算值gab是很困難的。

2.3 布隆過濾器

布隆過濾器(Bloom filter，BF)是用于查詢集合D中是否包含指定的元素[15]。BF可看作是一個m位的數組，在初始階段數組中的每個位置都設為0，接著將集合D={d1,d2,…,dn} 元素di通過k個相互獨立的哈希函數H={h1,h2,…,hk} 映射到數組中，對每個元素di∈D， 把數組中相應元素哈希值的位置設置為1。

2.4 紅黑樹

紅黑樹是一個自平衡的二叉查找樹[16]，每個節點擁有一個附加的屬性表示其顏色，可以是紅色或者黑色。它通過對節點進行旋轉或者重新著色來保持樹的平衡。在動態操作過程中，它的插入和刪除操作時間復雜度都為O(1)，查找的時間復雜度最壞為O(logn)。紅黑樹的屬性使得一棵n個結點的RBT始終保持了logn的高度。

2.5 混 淆

3 所提動態數據結構B-RBT

3.1 符號說明

表1定義了方案中使用的符號定義。

表1 符號說明

3.2 B-RBT結構

在GU共享數據審計方案中，一方面，GU的變更會帶來龐大的數據量變動，另一方面，共享數據支持常規的數據動態更新也會帶來數據的存儲變更，這無疑對模型中參與的各實體都會帶來龐大的計算開銷和通信開銷。特別對于半誠信的CSP來說，數據的增加或刪除對其帶來的開銷是巨大的。我們解決這些問題的核心是提出一個高效的數據結構來支持組共享數據的動態更新和數據刪除的公共可驗證。

3.2.1 結構描述

B-RBT是一種平衡搜索樹，可以在最壞情況下以常數時間達到樹的再平衡狀態。具體來說，該結構不是在查找樹的葉子節點中存儲單個鍵組成，而是由每個葉子中存儲由多個鍵組成的有序列表的桶構成。本方案提出的B-RBT并不需要全局重建技術，對于樹中節點的刪除，不需要像傳統紅黑樹一樣進行全局重建。由此該結構所需要的空間和時間更少。B-RBT結構的規則如下：①每個結點都有顏色，紅色的為紅結點，黑色的為黑結點；②根節點是黑色的；③每個葉節點都是黑色的桶；④如果一個節點是紅色的，且父節點也是紅色的，那么它的子節點都是黑色的，即所有路徑上最多存在兩個連續的紅節點；⑤從任意節點開始到其葉節點的每條路徑上黑結點的數量最多相差1。

B-RBT結構如圖2所示，每個節點都有一個額外的比特位表示其顏色，每個節點都有由多個鍵構成的桶、左子指針、右子指針、父指針和顏色位這5個屬性值。該結構將元素插入到桶中而不是內部樹節點中，每個樹節點存儲一個路徑值，該值小于或等于存儲在其右子樹的桶中的鍵，而大于其左子樹中桶的鍵。并在單個桶增大到一定值時對桶進行分割，當相鄰的兩個桶減小到一定值時對桶進行合并。每個桶都包含一個頭部，它將桶連接到樹節點上，并存儲關于桶的其它信息，例如桶的大小。對于存儲桶的大小，我們的方案保存與Elmasry等[18]提出的桶閾值一致，即每個桶中的鍵數必須在0.5H～2H范圍內。分割操作可能會導致需要在樹中添加一個新的節點，并且可能會打破原來B-RBT的平衡狀態。我們的目的是維護在每個桶的頭中指向第一個、中間和最后一個列表節點的指針，讓每個更新操作都會調用一個修復過程，并在下一次分割或合并違反樹平衡狀態之前修復，保證在此之前對這些指針的正確設置。

圖2 B-RBT結構

由于BF只允許對元素進行插入和查詢操作。它的缺陷是不支持元素的刪除操作。為了實現動態更新和數據刪除可驗證問題，本文采用CBF。其使用一個計數器單元計數來替換BF中每個位的位置，它允許對CBF執行插入、修改和刪除操作。設定CBF由m個計數器組成，元素集合D′={d′1,d′2,…,d′n}?S， 對于每個元素d′i∈U, 使用k個相互獨立哈希函數H={h1,h2,…,hk} 將其映射到CBF的k個位置上，如圖3所示。當CBF執行插入或刪除操作時，對應的計數器將增1或減1。

圖3 CBF結構

3.2.2 動態更新

本方案的數據結構支持高效的數據更新，具體過程如下：

(1)數據插入：首先GU先向TPA發送插入數據請求，并附帶上盲數據塊及生成數據簽名，TPA收到后把要插入的數據塊簽名存儲在B-RBT數據結構中，操作如下：假如GU想插入的數據塊為BI={x,y}， 首先在指定桶B的指定位置插入新的列表節點，并調用桶B的修復過程。當桶超過最大閾值時，如果修復指針PK還未到達根節點R處，則重復調用B的修復過程，直到PK到達R。接著將桶B分成兩個桶 {B1,B2}， 將 {B1,B2} 新的父節點B12以紅色節點的形式添加到樹中。并使兩個新桶的指針指向新插入的節點。最后再為兩個桶中的一個調用修復過程。完成簽名存儲后，把請求發送給CSP，CSP選取k個相互獨立的哈希函數對需插入的數據塊進行散列到CBF中，CBF對數據信息進行更新，在散列結果相應位置增加1，即CBF[{h1(x),h2(x),…,hk(x)},{h1(y),h2(y),…,hk(y)}]=+1并在CSP中存儲這些數據記錄。

(2)數據刪除：其過程和插入操作相似，GU還需要對數據進行混淆生成混淆標簽，然后再生成數據簽名和動態請求。為了數據刪除的可驗證，我們對需刪除的數據塊先發送修改請求，對TPA和CSP中存儲的數據進行修改后，再相應的發送刪除請求。TPA將數據塊簽名從B-RBT中刪除具體操作如下：假如GU想刪除的數據塊為BD={a，b}， 首先從桶B的刪除所需列表節點，并調用兩次桶B的修復過程。當桶小于最小閾值時，若修復指針PK還未到達根節點R處，則重復調用B的修復過程，直到PK到達R。如果桶B的同級桶B′的大小超過最小閾值時，B將從B′中借用一個節點，并對B′調用兩次修復過程。若桶B的同級桶B′的大小不會超過最小閾值時，B和B′進行合并為一個新桶B″，合并時將右桶的鍵放到左桶的尾部，B″的父節點是原B或B′的祖父節點。若刪除的父桶為黑色，則將B″標記為雙黑色。在簽名刪除后，把請求發送給CSP，CBF在相應位置減1，即CBF[{h1(x),h2(x),…,hk(x)}，{h1(y),h2(y),…,hk(y)}]=-1， 并在CSP中更新這些數據記錄。

(3)數據修改：修改操作是將已存儲在CSP中的某些數據信息進行更正，具體操作和插入及刪除一致，可看成是先對原有數據進行刪除操作后，再把新的數據進行插入來完成。

3.2.3 數據刪除驗證

方案支持共享數據刪除的可公共驗證，驗證CSP端是否誠實按照GU的需求永久刪除不必要的數據塊。如果CSP沒有執行數據刪除命令并真實地生成證據，那么GU很可能會檢測到惡意的數據保留。方案的數據刪除采用數據覆蓋的思想，將覆蓋操作偽裝成數據更新操作，GU通過驗證數據刪除證據來檢查共享數據的刪除結果。具體操作如下：首先GU向CSP發送一個數據刪除驗證請求，CSP返回刪除的數據證明，GU通過驗證其是否有效來確定CBF的有效性。當驗證通過后GU接著驗證CBF中刪除的數據塊的哈希值對應的位置是否為0，若為0則說明刪除的數據塊已不在CBF中，GU終止驗證并返回成功。若驗證不成功，則GU接著驗證CSP中對應刪除請求的數據塊中是否有混淆標簽的標志，若存在混淆標志，則說明CSP沒有按照GU請求執行數據刪除操作，返回數據刪除驗證失敗，否則返回數據刪除驗證成功。

4 協議設計

4.1 完整性審計協議

我們將詳細描述GU數據共享審計方案協議，該協議由數據上傳、完整性驗證兩個階段構成。具體內容如下：

(1)KeyGen(sk,k,T1,T2,g)： PKG為GU生成公鑰和密鑰參數。首先，GA隨機選擇一個非對稱加密密鑰對 (ssk,pk) 和α,k∈P作為系統私鑰的一部分，系統密鑰為sk={α,ssk}。 PKG為GM和GA生成私鑰GMID和GAID， 即GUID={GMID,GAID}。 接著GA隨機選取g,μ∈1， 讓y=gα,α∈P，T1和T2為授權的開始時間和結束時間。最后GA生成系統全局參數PK={g,y,H,e,μ,pk}, 其中H{0,1}*→1為單向哈希函數。

(2)GUBlind(mi,k1,GUID,Fname)： 首先GA把名為Fname的文件F分成n塊，即F={m1,m2,…,mn}， 接著使用密鑰種子k1∈P計算盲數據塊m′i=(mi‖i)+BF,i∈[1,n]， 其中致盲因子BF=fk1(GUID‖Fname)。 最后將盲數據F′={m′1,m′2,…,m′n} 和盲因子BF發送給CSP。

(4)CSPStorage(F′,BF)： CSP收到盲數據F′后，存儲通過驗證的真實數據塊，即計算m={mi}1≤i≤n={m′i}1≤i≤n-BF， 若對于每個數據塊mi與數據塊序號i相對應，則CSP對數據塊mi進行存儲。

4.2 數據動態協議

我們詳細描述動態數據刪除方案的協議，主要由數據更新和數據可刪除驗證兩個階段構成，具體如下：

(1)DataInsertion(BI)： 假設GU想在文件F中的數據塊mi之后插入一個新的數據塊mj， 首先GU發送插入的數據塊信息BI={I,i,mj,T1,T2,GUID,δj} 給TPA，其中I代表操作類型為插入，i為插入數據塊的位置，δj=(H(j‖T1,T2)μmj)α為插入的數據塊簽名。接著TPA在B-RBT結構中插入數據簽名后，把 {I,i,mj,T1,T2,GUID} 發送給CSP，CSP驗證后在mi之后存儲該數據塊。

5 協議安全分析

本節利用博弈假設的方法，證明了所提出的方案滿足審計的可靠性、正確性、有效性和數據刪除的不可否認性。

定理1 審計可靠性：CSP只有真正存儲GU的完整數據，才能通過TPA驗證，否則不能通過驗證。

定理2 數據刪除的不可否認性：對GU不再需要的數據進行刪除時，具有對數據刪除的公開可驗證性。這意味著GU和CSP都無法成功否認自己的行為，相互誹謗。

定理3 審計正確性：只有CSP誠實地生成有效的標簽證明TGU和有效的數據證明DCSP才能通過TPA驗證，否則不能通過驗證。

證明：根據雙線性映射對的特點，推導驗證方程的正確性可證明如下

從推導可以看出只有標簽證據TGU和數據證據DCSP同時有效，才能通過TPA驗證。

定理4 數據隱私安全：TPA或CSP不能在獲得的數據中提取GU的原始數據。在數據上傳階段，CSP不能從盲數據中獲取GU的真實數據，在審計階段，TPA不能從數據簽名和動態請求中獲取GU的真實數據。

證明：數據隱私安全是指敵手在沒有相應的數據解密密鑰的情況下無法獲得任何原數據信息。首先在數據上傳階段，盲數據塊m′i和其中的致盲因子BF是由GU隨機選取密鑰種子生成的隨機函數，且各盲數據塊間是相互獨立生成的，CSP對其也是隨機接收的，由此CSP想從中提取出真實數據信息F可作為一個DL問題，而解決DL問題的概率可以忽略不計。其次在審計階段，可通過如下等式驗證

定理5 動態操作有效性：在動態操作過程中，半誠實的CSP必須按動態請求的要求來執行，失效的GU無法通過發送頻繁的動態更新操作來消耗CSP的存儲資源，無論是篡改或虛假執行動態請求操作都通過TPA的驗證。

6 性能分析

6.1 計算開銷

方案主要從審計過程和數據刪除驗證兩個方面來對計算成本進行詳細分析。首先在審計過程中，包括GU數據上傳審計驗證兩個階段。本方案與Zhang等[2]提出的基于身份的用戶撤銷共享審計方案(IURS Audit)、Zhang等[12]提出的支持匿名用戶撤銷的共享動態數據審計方案(URSD Audit)和Xue等[22]提出的基于身份的云存儲用戶公共審計方案(IBP Audit)在計算開銷上進行對比，開銷細節見表2。本方案在GU數據上傳階段有較明顯的優勢，在審計階段本方案比其它3個方案開銷都低，IURS Audit和IBP Audit需要計算額外的累加、冪操作和乘運算，URSD Audit需要額外計算配對、哈希和乘運算。其次在數據刪除驗證過程中，主要包括數據塊的刪除和數據塊刪除驗證兩個階段。本方案還與Yang等[19]提出的支持數據跟蹤的公開可驗證刪除方案(TVD Scheme)、Yang等[7]提出的可公開驗證的高效細粒度數據刪除方案(FGVD Scheme)和Hao等[23]提出在基于云的物聯網中的一種安全、細粒度的外包數據刪除方案(SFGD Scheme)進行對比分析，開銷細節見表3。本方案相比于TVD Scheme和FGVD Scheme在刪除和驗證階段具有顯著優勢，與SFGD Scheme相比本方案開銷略低，在刪除驗證階段本方案開銷略低，其它3個方案需要進行額外的哈希操作或者驗證操作。

6.2 通信開銷

對于通信開銷主要針對動態更新過程，由于各數據結構不同，以及存儲位置不同，則導致它們的通信開銷也不同。開銷細節見表4。本方案的通信成本比Liu等[24]提出的基于Merkle哈希樹多級索引結構的動態數據隱私保護云審計方案(MI-MHT Scheme)略低，與Yu等[20]提出的基于動態索引表的云存儲公共審計方案(DIT Scheme)和Qi等[21]提出的基于秩的Merkle AVL樹實現云存儲動態和批量更新擁有驗證方案(RB-MAT Scheme)相比有較明顯的優勢，此外數據結構存儲在TPA端，比起存儲在CSP端，需要更低的通信成本。

表2 審計過程開銷對比

表3 數據刪除驗證過程開銷對比

表4 動態更新通信開銷對比

6.3 實驗分析

在實驗中，對本文提出的動態組共享數據完整性驗證方案從審計驗證過程、動態更新操作和數據可驗證刪除的時間開銷進行性能評估。實驗在配置為Intel Core i5-9300H CPU，8 GB RAM的筆記本電腦上進行，并搭建Linux虛擬機，利用C語言進行編譯，算法是基于雙線性配對的密碼(PBC)庫和GNU多精度算法(GMP)，采用MNT d159橢圓曲線，p中的一個元素的大小為160位，安全參數設置為80位。選用SH3-keccak256作為安全哈希函數。實驗步驟如下：①審計階段時間開銷：首先是數據上傳階段，主要的開銷源于配對和求冪操作。在實驗中總的處理2000個數據塊，觀察數據塊從400增加至2000間隔為200的時間開銷，如圖4所示。圖4(a)看出時間成本隨數據塊大小線性增加，同時，本方案的時間開銷比IURS Audit、URSD Audit和IBP Audit方案的時間開銷都低；其次是證明驗證階段，審計階段的計算開銷可分為挑戰生成和證明驗證過程。其中數據挑戰的開銷可忽略不計，我們選取數據塊從900到3600間隔為300的時間開銷，圖4(b)顯示了審計驗證的時間開銷，本方案的時間開銷比方案IURS Audit和IBP Audit的時間開銷低，比IURS Audit的開銷略低；②數據更新階段時間開銷：圖5展示了對數據更新的插入和修改操作的時間開銷，我們選取數據塊從30到300間隔為30的時間開銷。本方案的B-RBT數據結構與DIT Scheme、RB-MAT Scheme和MI-MHT Scheme進行對比，本方案的時間開銷更低。其中B-RBT結構和DIT Scheme對數據塊的插入和修改時間復雜度均為O(1)， 但

圖4 審計階段時間開銷

圖5 更新階段時間開銷

圖6 驗證刪除階段時間開銷

DIT Scheme查找的時間復雜度均為O(logn)。 其次RB-MAT Scheme和MI-MHT Scheme的結構時間復雜度均為O(logn)， 其需要花費的時間開銷較大；③數據刪除驗證階段時間開銷：我們選取數據塊從30到300間隔為30的時間開銷，如圖6所示。本方案在數據刪除和刪除驗證兩個階段的開銷都比TVD Scheme的開銷低。在數據刪除階段，與FGVD Scheme和SFGD Scheme相比，本方案的時間開銷更低，FGVD Scheme需額外的哈希和生成簽名開銷，SFGD Scheme需額外的哈希和生成簽名開銷。在刪除驗證階段，本方案采用的CBF數據結構復雜度為O(1) 有更低的時間開銷。

7 結束語

本文提出一個基于云存儲的動態組共享數據完整性驗證方案，為企業組用戶提供高效的數據共享和完整性驗證支持。為了解決共享云數據完整性驗證中存在的數據隱私安全性、動態更新高效性和數據刪除的可驗證性問題，首先GU對共享數據進行盲處理操作保證其它實體無法獲取真實的數據信息，保證數據的隱私安全；其次為了實現動態高效性需求，提出B-RBT數據結構來支持數據的動態操作；接著為實現對GU不再需要的數據信息進行有效的數據刪除，提出CBF數據結構來高效支持GU數據刪除的可公共驗證性。根據實驗對比結果的表明，我們的共享數據審計方案是有效的，其具有更低的時間開銷。