李昊宇，張龍軍，李慶鵬

(武警工程大學(xué) 信息工程系，西安 710086) (*通信作者電子郵箱459941720@qq.com)

基于B+樹的動(dòng)態(tài)數(shù)據(jù)持有性證明方案

李昊宇*，張龍軍，李慶鵬

(武警工程大學(xué) 信息工程系，西安 710086) (*通信作者電子郵箱459941720@qq.com)

針對(duì)云存儲(chǔ)環(huán)境下的數(shù)據(jù)持有性證明(PDP)方案效率較低、不能很好支持全動(dòng)態(tài)更新的問題，設(shè)計(jì)了一種基于B+樹的動(dòng)態(tài)數(shù)據(jù)持有性證明方案。該方案引入雙線性對(duì)技術(shù)和數(shù)據(jù)版本表，支持用戶進(jìn)行數(shù)據(jù)塊級(jí)的細(xì)粒度動(dòng)態(tài)操作并能保護(hù)用戶的數(shù)據(jù)隱私。通過優(yōu)化系統(tǒng)模型并設(shè)計(jì)節(jié)點(diǎn)索引值，使第三方檢測(cè)機(jī)構(gòu)能識(shí)別錯(cuò)誤數(shù)據(jù)并進(jìn)行精確定位。理論分析及實(shí)驗(yàn)結(jié)果表明，與基于Merkel哈希樹(MHT)的方案相比，所提方案能夠顯著降低系統(tǒng)構(gòu)造認(rèn)證數(shù)據(jù)結(jié)構(gòu)的時(shí)間開銷，并且簡(jiǎn)化了動(dòng)態(tài)更新過程，提高了第三方檢測(cè)機(jī)構(gòu)的驗(yàn)證效率。

數(shù)據(jù)持有性證明；雙線性對(duì)；B+樹；云存儲(chǔ)；數(shù)據(jù)版本表

0 引言

隨著數(shù)據(jù)量的爆炸式增長，傳統(tǒng)的存儲(chǔ)服務(wù)已無法滿足用戶的日常需求。為節(jié)約成本，越來越多的公司和用戶選擇將數(shù)據(jù)外包給云服務(wù)商(Cloud Service Provider, CSP)進(jìn)行管理和存儲(chǔ)[1]。為使利益最大化，CSP可能不按照服務(wù)等級(jí)協(xié)議的約定存儲(chǔ)數(shù)據(jù)，使用戶數(shù)據(jù)面臨極大的風(fēng)險(xiǎn)[2]。為保證數(shù)據(jù)的高可用性，CSP通常將數(shù)據(jù)分成多個(gè)副本進(jìn)行存儲(chǔ)，所以用戶需要強(qiáng)有力的證據(jù)表明CSP完整無誤地存儲(chǔ)著所有數(shù)據(jù)且所有副本都與用戶最近一次修改保持一致[3]。

Ateniese等[4]最早提出可證明數(shù)據(jù)持有(Provable Data Possession，PDP)方案，該方案引入“挑戰(zhàn)—應(yīng)答”協(xié)議，支持公開審計(jì)但計(jì)算開銷較大。之后他們提出改進(jìn)的可擴(kuò)展數(shù)據(jù)持有性(Scalable Provable Data Possession， SPDP)證明方案[5]，增加了部分動(dòng)態(tài)更新功能，但方案驗(yàn)證次數(shù)有限。Erway等[6]基于跳表(Skip List)結(jié)構(gòu)提出支持全動(dòng)態(tài)更新的PDP方案。Juels等[7]首次提出可恢復(fù)性證明(Proofs Of Retrievability， POR)方案，該方案能恢復(fù)部分受損數(shù)據(jù)，但不支持公開驗(yàn)證和數(shù)據(jù)動(dòng)態(tài)更新。Schacham等[8]在隨后提出支持公開驗(yàn)證的POR機(jī)制，驗(yàn)證次數(shù)沒有限制但通信開銷較大且不支持動(dòng)態(tài)更新。Wang等[9]提出一種基于Merkel哈希樹(Merkel Hash Tree, MHT)的驗(yàn)證方案，該方案支持公開審計(jì)和數(shù)據(jù)動(dòng)態(tài)更新，但計(jì)算開銷較大。李勇等[10]提出一種基于多分支路徑樹的完整性驗(yàn)證方案，簡(jiǎn)化了動(dòng)態(tài)更新過程但產(chǎn)生輔助信息過多，導(dǎo)致通信開銷較大。Wang[11]引入第三方審計(jì)者(Third Party Auditor， TPA)協(xié)助用戶驗(yàn)證數(shù)據(jù)完整性，該方案減少了用戶負(fù)擔(dān)，但CSP計(jì)算開銷較大。Chen[12]提出一種基于代數(shù)簽名的驗(yàn)證方案，支持用戶無限次驗(yàn)證，但不支持動(dòng)態(tài)操作。

為解決現(xiàn)有方案計(jì)算開銷大、不能較好地支持全動(dòng)態(tài)更新的問題，本文提出一種基于B+樹的數(shù)據(jù)持有性證明方案，通過引入數(shù)據(jù)版本表以支持?jǐn)?shù)據(jù)塊級(jí)的全動(dòng)態(tài)更新；通過優(yōu)化系統(tǒng)模型并引入節(jié)點(diǎn)檢索值，能識(shí)別定位錯(cuò)誤數(shù)據(jù)并提高TPA的驗(yàn)證效率。

1 相關(guān)知識(shí)

1.1 系統(tǒng)模型

方案模型如圖1所示，由4類實(shí)體組成。

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

2)授權(quán)用戶。經(jīng)過數(shù)據(jù)擁有者授權(quán)的其他用戶，與數(shù)據(jù)擁有者共享數(shù)據(jù)解密密鑰，可以遠(yuǎn)程訪問數(shù)據(jù)并進(jìn)行更新操作。

3)CSP。包括一個(gè)主服務(wù)器Master和若干個(gè)存儲(chǔ)服務(wù)器Slaves。為提高驗(yàn)證效率，本方案設(shè)計(jì)由Master負(fù)責(zé)分配證據(jù)生成任務(wù)，并收集結(jié)果返回給TPA；Slave根據(jù)指令為被挑戰(zhàn)的數(shù)據(jù)生成證據(jù)，并返回給Master。

4)TPA。第三方審計(jì)者，擁有強(qiáng)大的計(jì)算能力，代替數(shù)據(jù)擁有者對(duì)CSP發(fā)起挑戰(zhàn)，并對(duì)返回的證據(jù)進(jìn)行驗(yàn)證，將最終結(jié)果通知數(shù)據(jù)擁有者。

圖1 系統(tǒng)模型

1.2 安全模型

用戶數(shù)據(jù)的完整性面臨以下威脅：

1)CSP為獲取最大利益并保持公司聲譽(yù)，可能隱瞞數(shù)據(jù)損壞、丟失的情況，還可能刪除用戶訪問頻率較低的數(shù)據(jù)以節(jié)省存儲(chǔ)空間。

2)CSP可能存儲(chǔ)比服務(wù)協(xié)議更少的副本數(shù)量，并欺騙用戶，讓用戶以為所有數(shù)據(jù)被正確完整地存儲(chǔ)。

3)為節(jié)省計(jì)算資源，CSP可能忽略用戶的更新請(qǐng)求，或只更新部分?jǐn)?shù)據(jù)，從而導(dǎo)致多個(gè)備份副本數(shù)據(jù)不一致。

1.3 B+樹和雙線性對(duì)

B+樹是一種n叉平衡樹，其每個(gè)非葉子節(jié)點(diǎn)可以擁有大量葉子節(jié)點(diǎn)。一棵深度為h、存儲(chǔ)索引值為b的n階B+樹應(yīng)滿足以下特性[13]。

1)一棵B+樹由三部分組成：根節(jié)點(diǎn)、內(nèi)部節(jié)點(diǎn)和葉子節(jié)點(diǎn)。

2)所有葉子節(jié)點(diǎn)的深度相同，數(shù)據(jù)索引值存儲(chǔ)在葉子節(jié)點(diǎn)中。

3)一棵B+樹中能夠存儲(chǔ)的最小數(shù)據(jù)量為：bmin=2?n/2」h，能夠存儲(chǔ)的最大數(shù)據(jù)量為：bmax=nh-nh-1。

4)進(jìn)行數(shù)據(jù)查找、插入和刪除數(shù)據(jù)的時(shí)間復(fù)雜度均為O(lognb)。

圖2為B+樹結(jié)構(gòu)的一種實(shí)例，其中每個(gè)葉子節(jié)點(diǎn)存儲(chǔ)一個(gè)數(shù)據(jù)塊索引Ii，根節(jié)點(diǎn)R的索引鏈接可表示為Hash函數(shù):H(R1‖R2‖…‖Rn)。葉子節(jié)點(diǎn)Ri的索引鏈接為:H(I1‖I2‖…‖In)。

雙線性對(duì) 假設(shè)G1和G2是階為素?cái)?shù)P的循環(huán)群。g1，g2是G1和G2的生成元。定義雙線性映射e:G1×G2→GT，滿足以下性質(zhì)[14]。

1)可計(jì)算性。存在有效算法能夠計(jì)算e。

2)雙線性性。對(duì)所有的u∈G1，v∈G2和a,b∈Zp，有e(ua,vb)=e(u,v)ab。

3)非退化性。e(g1,g2)≠1。

計(jì)算性Diffie-Hellman(CDH)問題 給定e(g1,g2)≠1，其中x,y∈Zp，計(jì)算gxy。

圖2 B+樹結(jié)構(gòu)

2 B+樹動(dòng)態(tài)數(shù)據(jù)持有性證明方案

2.1 數(shù)據(jù)版本表

本文方案支持對(duì)外包數(shù)據(jù)進(jìn)行動(dòng)態(tài)更新，由于CSP是不可信的，所以需要對(duì)已更新數(shù)據(jù)塊進(jìn)行驗(yàn)證，以確保所有數(shù)據(jù)與用戶最近一次修改相一致。此外，TPA應(yīng)該知道數(shù)據(jù)塊的索引值，以保證能夠驗(yàn)證CSP是否在用戶所請(qǐng)求的特定數(shù)據(jù)塊位置執(zhí)行相應(yīng)的操作。由此引入數(shù)據(jù)版本表(Data Version Table， DVT)，DVT是一種小型元數(shù)據(jù)信息，由3部分組成。

1)數(shù)據(jù)塊索引號(hào)(IN)。IN是數(shù)據(jù)塊的索引值，它存儲(chǔ)著數(shù)據(jù)塊的具體物理地址。

2)數(shù)據(jù)塊編號(hào)(BN)。BN是數(shù)據(jù)塊的邏輯編號(hào)，它存儲(chǔ)著數(shù)據(jù)塊的邏輯地址。

3)數(shù)據(jù)塊版本號(hào)(VN)。VN是當(dāng)前數(shù)據(jù)塊的版本號(hào)，初始設(shè)定值為1，每更新一次，VN值增加1。

2.2 方案步驟

為方便描述，符號(hào)定義如表1所示。

表1 符號(hào)定義

本文方案包含8個(gè)多項(xiàng)式時(shí)間算法，如下所示。

1)KeyGen→(pk,sk)。假設(shè)e:G1×G2→GT是一個(gè)雙線性映射，g是G2的生成元。用戶運(yùn)行該算法生成用戶私鑰sk∈Zp和公鑰pk=gx∈G2。

2)GenB+tree。該算法在用戶端構(gòu)造B+樹，每個(gè)葉子節(jié)點(diǎn)對(duì)應(yīng)一個(gè)數(shù)據(jù)塊檢索值，映射完成后對(duì)B+樹的根節(jié)點(diǎn)簽名得到SignB+tree(H(R))=H(R)x。簽名后和隨后生成的數(shù)據(jù)塊標(biāo)簽一起發(fā)送給CSP，CSP端由Master節(jié)點(diǎn)構(gòu)造與用戶相同的B+樹。

a)在DVT中更新版本號(hào)，VN=VN+1；

②數(shù)據(jù)塊插入。假設(shè)用戶需要在文件f的第i個(gè)數(shù)據(jù)塊后插入新的數(shù)據(jù)塊b′，構(gòu)造新的文件f=(b1,b2,…,bi,b′,…,bm+1)。由于本文方案的數(shù)據(jù)塊索引號(hào)不包含在數(shù)據(jù)塊標(biāo)簽中，故不必計(jì)算插入新塊后移位的數(shù)據(jù)塊的標(biāo)簽值。用戶執(zhí)行如下算法：

③數(shù)據(jù)塊刪除。分為兩種情況，刪除最后一塊和刪除其他位置的數(shù)據(jù)塊。這里主要討論第二種情況。假設(shè)用戶刪除第i塊，執(zhí)行算法如下：

a)用戶刪除DVT中的第i個(gè)表項(xiàng)，第i項(xiàng)后的所有表項(xiàng)IN減1，其余值不變；

圖3對(duì)動(dòng)態(tài)更新過程中DVT的變化進(jìn)行了舉例。假設(shè)初始文件f的DVT如圖3(a)所示，INi=BNi，VNi=1，1≤i≤n；當(dāng)修改第3塊時(shí)，VN3加1，其余值不變，如圖3(b)所示；如果在第3塊后插入新的數(shù)據(jù)塊，新塊的IN4=4，BN4=n+1,VN4=1，如圖3(c)所示；刪除第3塊，DVT變化如圖3(d)所示。

圖3 DVT在動(dòng)態(tài)操作時(shí)的變化

5)ExecUpdate。CSP收到更新請(qǐng)求后，執(zhí)行下列算法。

①數(shù)據(jù)塊修改。CSP收到數(shù)據(jù)塊修改請(qǐng)求后，執(zhí)行下列操作：

②數(shù)據(jù)塊插入。CSP收到數(shù)據(jù)塊插入請(qǐng)求后，執(zhí)行下列操作：

③數(shù)據(jù)塊刪除。CSP收到數(shù)據(jù)塊刪除請(qǐng)求，執(zhí)行下列操作：

a)刪除第i個(gè)數(shù)據(jù)塊，生成新的文件副本f′；

b)刪除數(shù)據(jù)標(biāo)簽δi，生成新的標(biāo)簽集合δ′。

6)Chal→(ω,πkey(k1),ψkey(k2))。TPA隨機(jī)抽取若干個(gè)數(shù)據(jù)塊進(jìn)行挑戰(zhàn)。需要生成ω，πkey(k1)，ψkey(k2)，ω代表需要挑戰(zhàn)的文件編號(hào)，πkey(k1)代表偽隨機(jī)置換，ψkey(k2)代表偽隨機(jī)函數(shù)。將其組合成挑戰(zhàn)信息Chal=(ω,πkey(k1),ψkey(k2))發(fā)送給CSP。

7)GenProof→(μ,δ)。CSP收到挑戰(zhàn)信息后，Master節(jié)點(diǎn)對(duì)任務(wù)進(jìn)行分配，每個(gè)Slave節(jié)點(diǎn)進(jìn)行下列計(jì)算：

(1)

(2)

(3)

TPA由DVT可得數(shù)據(jù)塊邏輯號(hào)和版本號(hào)并對(duì)證據(jù)進(jìn)行計(jì)算，如果等式成立，則輸出1，代表驗(yàn)證成功；否則為0。最終，TPA將檢測(cè)結(jié)果發(fā)送給用戶。

2.3 識(shí)別損壞副本

圖4 3階B+樹結(jié)構(gòu)

不同存儲(chǔ)服務(wù)器返回的證據(jù)不同說明用戶數(shù)據(jù)遭到破壞。假設(shè)TPA在驗(yàn)證時(shí)檢測(cè)出不同存儲(chǔ)服務(wù)器返回的同一數(shù)據(jù)塊的Hash值hI3不同，需要檢測(cè)i=3的葉子節(jié)點(diǎn)，判斷哪個(gè)存儲(chǔ)服務(wù)器出現(xiàn)問題，利用RV可快速識(shí)別定位錯(cuò)誤數(shù)據(jù)，具體算法如下：

1)比較i和RVA的值。如果RVA

2)比較x和RVB的值，如果X≤RVB，則對(duì)此節(jié)點(diǎn)的子節(jié)點(diǎn)進(jìn)行檢索。如果X>RVB，則令x=x-RVB，比較x和RVC的大小，如果X≤RVC，則從此節(jié)點(diǎn)向下檢索；否則繼續(xù)重復(fù)該步驟，直到確定繼續(xù)向下檢索的節(jié)點(diǎn)。本例中x=i=3，可確定繼續(xù)檢索第一個(gè)子樹。

3)加入當(dāng)前節(jié)點(diǎn)到該數(shù)據(jù)塊的認(rèn)證路徑中。

重復(fù)步驟2)～3)，直到x=1，檢索到對(duì)應(yīng)的葉子節(jié)點(diǎn)。在B+樹結(jié)構(gòu)中使用本算法能較快地檢索到出現(xiàn)問題的節(jié)點(diǎn)，減少TPA的驗(yàn)證開銷。

3 安全性分析

定理如果本文提出的B+tree簽名不可偽造，且CDH問題在雙線性群中是難解的，那么TPA在檢測(cè)數(shù)據(jù)完整性時(shí)，沒有攻擊者能夠欺騙TPA，除非返回的證據(jù)是正確的。

證畢。

4 性能分析

將本文方案與現(xiàn)有兩類方案進(jìn)行對(duì)比，結(jié)果如表2所示，其中n表示數(shù)據(jù)塊的數(shù)量。通過對(duì)比，可以看出本文方案的TPA驗(yàn)證開銷和通信開銷較小，具有實(shí)用性。

表2 3種方案性能對(duì)比

為更好地評(píng)估方案性能，將本文方案與基于MHT的方案[9]進(jìn)行對(duì)比。實(shí)驗(yàn)在Hadoop 2.7.3框架下的Spark平臺(tái)上使用Python語言編程實(shí)現(xiàn)，雙線性對(duì)運(yùn)算和哈希運(yùn)算分別在OpenSSL庫和PBC庫中實(shí)現(xiàn)。設(shè)群階的大小為160 bit，獲得80 bit的安全參數(shù)。隨機(jī)生成數(shù)據(jù)文件2 000個(gè)，分塊大小為64 KB，數(shù)據(jù)文件的大小為2 GB，DVT為1 MB，實(shí)驗(yàn)取10次結(jié)果的平均值。

首先，通過計(jì)算用戶和CSP構(gòu)建B+樹、MHT樹的時(shí)間，比較本文方案與文獻(xiàn)[9]方案的性能。MHT樹是二叉樹結(jié)構(gòu)，假設(shè)數(shù)據(jù)被分為n塊，則至少需要建立深度為1+lbn的二叉樹，樹的深度隨數(shù)據(jù)塊n呈線性增加。相較于B+樹結(jié)構(gòu)，構(gòu)造MHT的計(jì)算開銷較大。生成不同認(rèn)證樹結(jié)構(gòu)的時(shí)間如圖5所示，可以看到構(gòu)建B+樹的時(shí)間與構(gòu)建MHT樹的時(shí)間在樹的出度為2時(shí)相同，隨著出度的增加，構(gòu)建MHT樹的時(shí)間逐漸增加，而構(gòu)建B+樹的時(shí)間大大減少，說明本文方案能夠有效地降低構(gòu)建數(shù)據(jù)結(jié)構(gòu)的計(jì)算開銷。

圖5 不同出度樹的構(gòu)建時(shí)間對(duì)比

為進(jìn)一步分析方案性能，對(duì)CSP計(jì)算證據(jù)的時(shí)間開銷進(jìn)行分析。運(yùn)行程序后輸入不同的數(shù)據(jù)塊數(shù)量，得到計(jì)算證據(jù)的時(shí)間如圖6所示。可以看出隨著數(shù)據(jù)塊大小的增加，CSP計(jì)算證據(jù)的時(shí)間都會(huì)逐漸增加；每次驗(yàn)證的數(shù)據(jù)塊數(shù)量越多，CSP計(jì)算證據(jù)所花費(fèi)的時(shí)間也越多，CSP的計(jì)算開銷越大。

最后對(duì)TPA的驗(yàn)證時(shí)間開銷進(jìn)行分析。以數(shù)據(jù)塊大小作為輸入，程序最終輸出TPA相應(yīng)的驗(yàn)證時(shí)間。選取數(shù)據(jù)塊大小分別為64 KB和128 KB兩種情況，實(shí)驗(yàn)結(jié)果如圖7所示。通過實(shí)驗(yàn)對(duì)比，可以發(fā)現(xiàn)在數(shù)據(jù)塊大小均為64 KB時(shí)，兩種方案的TPA驗(yàn)證時(shí)間在數(shù)據(jù)塊數(shù)量較少時(shí)較為相近；但隨著抽取數(shù)據(jù)塊的數(shù)量不斷增加，本文方案的驗(yàn)證時(shí)間開銷明顯低于文獻(xiàn)[9]方案的時(shí)間開銷。當(dāng)設(shè)定本文方案數(shù)據(jù)塊大小為128 KB時(shí)，TPA驗(yàn)證時(shí)間與數(shù)據(jù)塊大小為64 KB的文獻(xiàn)[9]方案的時(shí)間相近。

圖6 CSP計(jì)算證據(jù)的時(shí)間開銷

圖7 TPA驗(yàn)證時(shí)間

通過上述實(shí)驗(yàn)可知，相比文獻(xiàn)[9]方案，本文方案使用B+樹認(rèn)證結(jié)構(gòu)能夠有效降低用戶和CSP構(gòu)建數(shù)據(jù)結(jié)構(gòu)的計(jì)算開銷，減少TPA的驗(yàn)證時(shí)間，提高數(shù)據(jù)完整性驗(yàn)證效率。

5 結(jié)語

為解決傳統(tǒng)數(shù)據(jù)持有性證明方案計(jì)算開銷大、驗(yàn)證時(shí)間較長等問題，提出基于B+樹的數(shù)據(jù)持有性證明方案。在B+樹認(rèn)證結(jié)構(gòu)中引入數(shù)據(jù)版本表和節(jié)點(diǎn)檢索值，有效支持?jǐn)?shù)據(jù)動(dòng)態(tài)更新和錯(cuò)誤數(shù)據(jù)識(shí)別。實(shí)驗(yàn)證明：本文方案能有效降低模型中各實(shí)體的計(jì)算開銷，提高TPA的驗(yàn)證效率。由于本文方案假設(shè)TPA是完全可信的，審計(jì)過程中用戶數(shù)據(jù)可能遭到TPA和CSP的共謀攻擊而泄露，下一步將對(duì)如何保護(hù)用戶數(shù)據(jù)隱私展開研究。

References)

[1] 俞能海,郝卓,徐甲甲,等.云安全研究進(jìn)展綜述[J].電子學(xué)報(bào),2013,41(2):371-381.(YU N H, HE Z, XU J J, et al. Review of cloud computing security [J]. Acta Electronica Sinica, 2013, 41(2): 371-381.)

[2] 李暉,孫文海,李鳳華,等.公共云存儲(chǔ)服務(wù)數(shù)據(jù)安全及隱私保護(hù)技術(shù)綜述[J].計(jì)算機(jī)研究與發(fā)展,2014,51(7): 1397-1409.(LI H, SUN W H, LI F H, et al. Secure and privacy-preserving data storage service in public cloud [J]. Journal of Computer Research and Development, 2014, 51(7): 1397-1409.)

[3] BARSOUM A F, HASAN M A. Provable multicopy dynamic data possession in cloud computing systems [J]. IEEE Transactions on Information Forensics & Security, 2015, 10(3): 485-497.

[4] ATENIESE G, BURNS R, CURTMOLA R, et al. Provable data possession at untrusted stores [C]// Proceedings of the 2007 ACM Conference on Computer and Communications Security. New York: ACM, 2007: 598-609.

[5] ATENIESE G, PIETRO R D, MANCINI L V, et al. Scalable and efficient provable data possession [C]// Proceedings of the 4th International Conference on Security and Privacy in Communication Networks. New York: ACM, 2008: Article No. 9.

[6] ERWAY C C, PAPAMANTHOU C, TAMASSIA R. Dynamic provable data possession [J]. ACM Transactions on Information & System Security, 2009, 17(4): 213-222.

[7] JUELS A, KALISKI B S. PORs: proofs of retrievability for large files [C]// Proceedings of the 2007 ACM Conference on Computer and Communications Security. New York: ACM, 2007: 584-597.

[8] SHACHAM H, WATERS B. Compact proofs of retrievability [C]// ASIACRYPT ’08: Proceedings of the 14th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology. Berlin: Springer, 2008: 90-107.

[9] WANG Q, WANG C, REN K, et al. Enabling public auditability and data dynamics for storage security in cloud computing [J]. IEEE Transactions on Parallel & Distributed Systems, 2011, 22(5): 847-859.

[10] 李勇,姚戈,雷麗楠,等.基于多分支路徑樹的云存儲(chǔ)數(shù)據(jù)完整性驗(yàn)證機(jī)制[J].清華大學(xué)學(xué)報(bào)(自然科學(xué)版),2016,56(5):504-510.(LI Y, YAO G, LEI L N, et al. LBT-based cloud data integrity verification scheme [J]. Journal of Tsinghua University (Science and Technology), 2016, 56(5): 504-510.)

[11] WANG H. Identity-based distributed provable data possession in multicloud Storage [J]. IEEE Transactions on Services Computing, 2015, 8(2): 328-340.

[12] CHEN L. Using algebraic signatures to check data possession in cloud storage [J]. Future Generation Computer Systems, 2013, 29(7): 1709-1715.

[13] JENSEN C S, LIN D, OOI B C. Query and update efficient B+-tree based indexing of moving objects [C]// Proceedings of the Thirtieth International Conference on Very Large Data Bases. Amsterdam: Elsevier, 2004: 768-779.

[14] VAPNIK V N. The Nature of Statistical Learning Theory [M]. Berlin: Springer, 2000: 988-999.

[15] WANG H, ZHANG Y. On the knowledge soundness of a cooperative provable data possession scheme in multicloud storage [J]. IEEE Transactions on Parallel & Distributed Systems, 2014, 25(1): 264-267.

[16] BARSOUM A F, HASAN M A. Provable multicopy dynamic data possession in cloud computing systems [J]. IEEE Transactions on Information Forensics & Security, 2015, 10(3): 485-497.

This work is partially supported by the National Natural Science Foundation of China (61402529), the Natural Science Foundation of Shaanxi Province (2015JQ6266).

LIHaoyu, born in 1993, M. S. candidate. His research interests include cloud computing security, cryptology.

ZHANGLongjun, born in 1964, Ph. D., professor. His research interests include information and network security, cryptology.

LIQingpeng, born in 1992, M. S. candidate. His research interests include data mining, privacy protection.

DynamicprovabledatapossessionschemebasedonB+tree

LI Haoyu*, ZHANG Longjun, LI Qingpeng

(DepartmentofInformationEngineering,EngineeringUniversityofChinesePeople’sArmedPoliceForce,Xi’anShaanxi710086,China)

Concerning the problem that the existing schemes of provable data possession are inefficient and can not support full dynamic update, a novel dynamic provable data possession scheme based on B+tree was proposed. Bilinear pairing techniques and data version table were introduced to support fine-grained dynamic operations at the block level and to protect user’s data privacy in the proposed scheme. The third party auditor could identify the wrong data and locate it accurately by optimizing the system model and designing the retrieved value of data node. In comparison with the scheme based on the Merkel Hash Tree (MHT), theoretical analysis and experimental results show that the proposed scheme can significantly reduce the cost of constructing the authentication data structure, simplify the dynamic update process, and improve the verification efficiency of the third party auditor.

Provable Data Possession (PDP); bilinear pairing; B+tree; cloud storage; data version table

TP309.2

:A

2016- 12- 22;

:2017- 02- 15。

國家自然科學(xué)基金資助項(xiàng)目(61402529)；陜西省自然科學(xué)基金資助項(xiàng)目(2015JQ6266)。

李昊宇(1993—)，男，陜西富平人，碩士研究生，CCF會(huì)員，主要研究方向：云計(jì)算安全、密碼學(xué)； 張龍軍(1964—)，男，陜西扶風(fēng)人，教授，博士生導(dǎo)師，博士，主要研究方向：信息與網(wǎng)絡(luò)安全、密碼學(xué)； 李慶鵬(1992—)，男，山東莒縣人，碩士研究生，主要研究方向：數(shù)據(jù)挖掘、隱私保護(hù)。

1001- 9081(2017)07- 1931- 05

10.11772/j.issn.1001- 9081.2017.07.1931