一個支持錯誤定位的批處理數(shù)據(jù)擁有性證明方案?

龐曉瓊,王田琪,陳文俊,2,任孟琦

1(中北大學(xué) 大數(shù)據(jù)學(xué)院,山西 太原 030051)

2(中國人民銀行 太原中心支行,山西 太原 030001)

1 引 言

數(shù)據(jù)擁有性證明(PDP)方案使得數(shù)據(jù)擁有者(或校驗者)在沒有本地備份的情況下,不需要下載數(shù)據(jù),就能以很高的概率遠程校驗用戶存儲在服務(wù)器上的數(shù)據(jù)是否完整.目前,大多數(shù)數(shù)據(jù)擁有性證明方案是針對單用戶存放在單服務(wù)器上的數(shù)據(jù)進行完整性校驗[1-11],但是現(xiàn)實的情境中,云存儲提供的服務(wù)是面向很多用戶的,同時,云服務(wù)提供商并不是單一的,每個云服務(wù)提供商所擁有的也不僅僅是單個服務(wù)器.為了更適應(yīng)現(xiàn)實,近幾年,多用戶單服務(wù)器[12,13]、單用戶多服務(wù)器[14,15]、多用戶多服務(wù)器[16-19]情景下的批處理 PDP方案陸續(xù)被提出來.在這些批處理方案中,服務(wù)器在計算證明階段將被挑戰(zhàn)數(shù)據(jù)塊的證明按用戶或服務(wù)器進行聚合計算后,再將聚合證明發(fā)送給TPA(third party auditor)校驗,極大地降低了通信開銷,且有效地減少了TPA校驗的計算開銷.但是只有當(dāng)所有用戶的數(shù)據(jù)都是正確存儲時,這樣的批量處理才能體現(xiàn)出其效率優(yōu)勢,一旦有數(shù)據(jù)被損毀,批處理校驗將不通過,此時定位錯誤數(shù)據(jù)所在服務(wù)器和所屬用戶就成為一個亟需解決的問題.最直接的定位錯誤方法就是對被挑戰(zhàn)服務(wù)器返回的證明逐一校驗,但是這種方法的效率顯然不高,并且由于服務(wù)器通常返回的是聚合證明,故而目前多用戶多服務(wù)器環(huán)境下的批處理PDP方案中,即使采用逐一校驗法,TPA也只能定位錯誤數(shù)據(jù)所屬用戶或所在服務(wù)器,無法進行同時定位.因此需要一種有效的方法,在多用戶多服務(wù)器環(huán)境下實現(xiàn)批處理遠程數(shù)據(jù)完整性校驗的同時,還能在校驗不通過情況下高效地對錯誤數(shù)據(jù)定位,即找到錯誤數(shù)據(jù)屬于哪個用戶,且存放在哪個服務(wù)器上.

1.1 相關(guān)工作

2007年,Ateniese等人[1]首次提出了PDP的定義,并給出了一個支持公開校驗的PDP方案.2008年,Ateniese等人[2]提出了一個支持動態(tài)數(shù)據(jù)更新的 PDP方案,但是該方案只支持對文件塊的修改、刪除和附加操作,并不支持插入,且只能進行有限次校驗.2009年,Wang等人[3]利用Merkle哈希樹提出了一個全面支持數(shù)據(jù)動態(tài)更新的方案,同時引入了 TPA代替用戶驗證數(shù)據(jù)的完整性,但該方案沒有考慮用戶數(shù)據(jù)隱私會泄露給 TPA的問題.2010年,Wang等人[4]提出一個保護隱私的PDP方案,解決用戶隱私泄露給TPA的問題,但該方案不支持數(shù)據(jù)動態(tài)更新.2011年,Hao等人[5]提出了“針對第三方校驗者的隱私性”的安全性定義,并構(gòu)造了一個在此安全性定義下可證明安全的PDP方案.2015年～2016年,Yu等人[6-9]重點研究了提高PDP方案安全性的問題.2016年～2017年,Yu等人[10,11]提出兩種基于身份的PDP方案,消除了PKI龐大的證書管理開銷.以上工作都是針對單用戶單服務(wù)器環(huán)境下的PDP方案.

在多用戶單服務(wù)器環(huán)境下,2013年,Wang等人[12]利用BLS短簽名構(gòu)造同態(tài)驗證標簽,提出了一個保護隱私的批處理PDP方案.2014年,Ren等人[13]使用橢圓曲線上的Co-GDH簽名構(gòu)造同態(tài)驗證標簽,提出一個支持數(shù)據(jù)動態(tài)更新的批處理PDP方案.在文獻[12,13]中,服務(wù)器將被挑戰(zhàn)塊的證明按用戶聚合之后發(fā)送給TPA,TPA對所有證明聚合計算后進行批量校驗.不同的是,文獻[12]在批校驗不通過時,TPA會利用二分查找判斷哪個用戶的數(shù)據(jù)出錯;而文獻[13]并未考慮定位錯誤數(shù)據(jù)所屬用戶的問題.

在單用戶多服務(wù)器環(huán)境下,2015年,Wang[14]提出了一個基于身份的分布式批處理PDP方案.2016年,Mao等人[15]利用BLS短簽名提出了一個批處理PDP方案.這兩個方案中,被挑戰(zhàn)服務(wù)器將其上所有被挑戰(zhàn)數(shù)據(jù)塊的證明聚合計算后發(fā)送給 organizer,organizer將所有被挑戰(zhàn)服務(wù)器發(fā)來的聚合證明再次聚合成一個值,并發(fā)送給TPA進行校驗.文獻[14,15]這種交由 organizer統(tǒng)一聚合證明的方式極大地減輕了 TPA的計算開銷,但也使得TPA無法定位錯誤數(shù)據(jù)所在服務(wù)器.

在多用戶多服務(wù)器環(huán)境下,2014年,Liu等人[16]利用雙線性對提出一個批處理 PDP方案,并且使用有序的Merkle Hash Tree來抵抗置換攻擊.該方案中,被挑戰(zhàn)服務(wù)器將其上所有被挑戰(zhàn)塊的證明聚合后發(fā)給 organizer,organizer將所有被挑戰(zhàn)服務(wù)器返回的聚合證明再次聚合并發(fā)送給TPA審計,這種交由organizer聚合,再由TPA審計的方式在一次挑戰(zhàn)響應(yīng)中無法實現(xiàn)錯誤數(shù)據(jù)定位.2016年,Zhou等人[17]基于CDH假設(shè),利用雙線性對提出了一種基于身份的批處理 PDP方案.該方案中,被挑戰(zhàn)服務(wù)器將其上所有被挑戰(zhàn)塊的證明聚合后發(fā)送給 TPA,TPA將所有被挑戰(zhàn)服務(wù)器返回的證明再次聚合后進行批量校驗.雖然文獻[17]并未考慮錯誤數(shù)據(jù)定位問題,但是在批量審計不通過的情況下,TPA可以采用最直接的逐一校驗方式定位錯誤數(shù)據(jù)所在服務(wù)器,但無法定位錯誤數(shù)據(jù)所屬用戶.

在多用戶多服務(wù)器環(huán)境下的批處理PDP方案中,也曾有學(xué)者提出錯誤數(shù)據(jù)定位的想法.2013年,He等人[18]提出了一個僅能定位出錯數(shù)據(jù)所屬用戶的批量審計 PDP方案.該方案中,TPA批處理校驗不通過后,逐一校驗organizer服務(wù)器返回的按用戶聚合的證明以實現(xiàn)定位.2015年,Shin等人[19]提出了一個僅能定位出錯數(shù)據(jù)所在服務(wù)器的批量審計PDP方案,并且只能在單個服務(wù)器出錯的情境下進行定位.該方案中,被挑戰(zhàn)服務(wù)器為其上屬于不同用戶的被挑戰(zhàn)塊計算一個聚合證明,并發(fā)送給 TPA批量審計和錯誤定位.文獻[18,19]不能同時支持定位錯誤數(shù)據(jù)所屬用戶和所在服務(wù)器的原因在于:TPA收到的證明都是經(jīng)過聚合計算之后得到的聚合值,這種“先聚合再審計”的策略使得TPA在審計時無法同時區(qū)分這些聚合證明中涉及的數(shù)據(jù)塊所在的服務(wù)器和所屬的用戶,故而在定位錯誤時只能定位錯誤數(shù)據(jù)所屬用戶或所在服務(wù)器.

本文中,我們提出利用定位標簽輔助TPA快速定位錯誤的方法,并在Zhou等人[17]方案的基礎(chǔ)上,在多用戶多服務(wù)器環(huán)境下給出了一個具體實現(xiàn).方案在支持批處理校驗的同時,可以在審計到數(shù)據(jù)出錯后,僅通過比較操作實現(xiàn)錯誤快速定位,同時找到出錯數(shù)據(jù)的擁有者與其所處的服務(wù)器.

1.2 貢 獻

(1)提出了利用定位標簽輔助第三方審計員快速定位錯誤的方法,并給出一個多用戶多服務(wù)器環(huán)境下支持批處理校驗和錯誤數(shù)據(jù)定位的數(shù)據(jù)擁有性證明方案框架.云用戶對自己的每個文件塊計算相應(yīng)的數(shù)據(jù)標簽,將其和文件塊存儲在服務(wù)器中,同時對存儲在不同服務(wù)器上的數(shù)據(jù)計算定位標簽并發(fā)送給TPA;TPA接收到多個云用戶的審計請求后,可同時對這些用戶存儲在多個云服務(wù)器上的數(shù)據(jù)進行挑戰(zhàn);在收到被挑戰(zhàn)云服務(wù)器返回的證明后,TPA基于發(fā)送的挑戰(zhàn)和服務(wù)器返回的證明進行有效性批量驗證,若驗證不通過,則利用定位標簽,確定出錯數(shù)據(jù)的所屬用戶和存儲位置.

(2)給出了一個具體實現(xiàn).我們的方案是在 Zhou等人[17]基于身份的批處理 PDP方案基礎(chǔ)上增加了定位標簽生成算法,云用戶利用MHT為其數(shù)據(jù)塊構(gòu)建定位索引表,并將定位索引表發(fā)送給TPA.在審計階段,如果批處理校驗不通過,TPA則利用服務(wù)器重構(gòu)的 MHT樹根查找定位索引表以定位錯誤數(shù)據(jù)所屬用戶和所在服務(wù)器.我們的方案能夠?qū)崿F(xiàn)僅通過一次比較操作,即可判斷出特定用戶存放在特定服務(wù)器上的數(shù)據(jù)是否遭到破壞.

(3)為了防止服務(wù)器在某次審計成功后直接存儲用戶數(shù)據(jù)的MHT樹根,并利用其在以后的挑戰(zhàn)中構(gòu)造證明欺騙TPA,本方案中,每個用戶對其存儲在不同服務(wù)器上的數(shù)據(jù)分別用不同的參數(shù)值構(gòu)建λ棵MHT,即對相同數(shù)據(jù)計算λ個不同的定位標簽,在每次挑戰(zhàn)時,選用不同的 MHT參數(shù)值,要求服務(wù)器計算相應(yīng)的MHT樹根.由于服務(wù)器無法提前得知每次挑戰(zhàn)指定的MHT參數(shù),則其成功欺騙TPA的概率是可忽略的.

(4)方案在隨機諭言機模型下是可證明安全的.相對于逐一校驗定位錯誤的方式,我們的方案在實現(xiàn)錯誤數(shù)據(jù)定位的能力和效率方面均有優(yōu)勢.另一方面,除了可以一次性完成的額外計算外,因定位功能而在審計階段增加的計算和通信開銷都是可以接受的.

1.3 組織結(jié)構(gòu)

本文第 2節(jié)介紹一些相關(guān)知識和工具.第 3節(jié)介紹系統(tǒng)模型和本文中所使用的符號,并且提出方案框架和安全性定義.第4節(jié)是具體方案的構(gòu)造細節(jié).第5節(jié)對方案進行安全性分析和性能分析,并提供實驗結(jié)果.第6節(jié)進行總結(jié).

2 預(yù)備知識

2.1 雙線性對

設(shè)q是一個大素數(shù),群G1和G2是兩個階為q的乘法循環(huán)群,設(shè)G1的生成元為g,則群G1到G2的一個雙線性映射e:G1×G1→G2,滿足下面的性質(zhì).

(1)雙線性:對于任意的u,v∈G1和a,b∈Zq,有e(ua,vb)=e(u,v)ab.

(2)非退化性:e(g,g)的值不等于群G2中的單位元.

(3)可計算性:對任意的u,v∈G1,存在一個有效的算法可以計算e(u,v).

2.2 CDH困難問題

定義1(CDH問題).設(shè)q是一個大素數(shù),群G1是一個q階乘法循環(huán)群,G1的生成元為g,CDH問題指的是當(dāng)a,b未知,三元組已知時,計算gab∈G1.設(shè)一個概率多項式時間(PPT)算法A解決群G1上的CDH問題的概率為ε=Pr[gab←A(g,ga,gb)].

定義2.若對于任意PPT算法A,其解決以上CDH問題的概率ε是可忽略的,則稱群G1上的CDH問題是困難的.

2.3 Merkle Hash Tree

Merkle Hash Tree(MHT)是一種二叉樹,常被用來進行數(shù)據(jù)驗證.數(shù)據(jù)值做Hash計算后得到的值作為其葉子節(jié)點,每個父親節(jié)點的值是由兩個子節(jié)點的連接值做 Hash計算后得到的.當(dāng)一個父親節(jié)點只有 1個子節(jié)點時,父親節(jié)點的值為單個子節(jié)點值做Hash計算后得到的值.

一般來說,一棵MHT的構(gòu)造方法如圖1所示.

Fig.1 Construction diagram of MHT圖1 MHT構(gòu)造示意圖

3 定義與模型

3.1 系統(tǒng)模型與設(shè)計目標

一個支持批處理和錯誤定位的數(shù)據(jù)完整性驗證系統(tǒng)(error locating batch provable data possession,簡稱ELBPDP)包含3類實體:數(shù)據(jù)擁有者(即用戶,DO)、云服務(wù)器(CS)、第三方審計員(即校驗者,TPA).

· 數(shù)據(jù)擁有者:在支持批處理和錯誤定位的數(shù)據(jù)完整性驗證系統(tǒng)中,有多個數(shù)據(jù)擁有者.每個數(shù)據(jù)擁有者擁有各自的文檔數(shù)據(jù),他們將文檔數(shù)據(jù)預(yù)處理后對所有數(shù)據(jù)塊計算數(shù)據(jù)標簽,將數(shù)據(jù)塊和數(shù)據(jù)標簽外包給云服務(wù)提供商;對存儲在各個服務(wù)器上的數(shù)據(jù)計算定位標簽,并發(fā)送給第三方審計員.

· 云服務(wù)器:在本系統(tǒng)中,云服務(wù)器的數(shù)量也有多個.每個云服務(wù)器存儲著數(shù)據(jù)擁有者們提交的文件塊及其數(shù)據(jù)標簽.在接收到第三方審計員發(fā)送的校驗挑戰(zhàn)后,云服務(wù)器計算并返回證明.

· 第三方審計員:收到數(shù)據(jù)擁有者的審計請求后,第三方審計員給各個云服務(wù)器發(fā)送挑戰(zhàn),并對被挑戰(zhàn)服務(wù)器返回的證明進行批處理校驗.如果校驗未通過,則根據(jù)定位標簽繼續(xù)確定錯誤數(shù)據(jù)塊所屬的用戶和所在服務(wù)器,最后將校驗結(jié)果發(fā)送給相應(yīng)用戶.

支持批處理和錯誤定位的數(shù)據(jù)完整性驗證系統(tǒng)的結(jié)構(gòu)如圖2所示.

Fig.2 System model diagram圖2 系統(tǒng)模型圖

支持錯誤定位的批處理PDP方案,應(yīng)滿足如下要求.

(1)支持批處理校驗:校驗者可以一次性批量校驗多個用戶存儲在多個服務(wù)器上的數(shù)據(jù)是否完整.

(2)支持錯誤定位:在批處理校驗失敗后,校驗者可以同時找出錯誤數(shù)據(jù)所屬用戶與所存儲的服務(wù)器.

(3)公開審計性:允許第三方審計員驗證存儲在云服務(wù)器上的用戶數(shù)據(jù)的完整性,但是不需要從云服務(wù)器上下載全部的數(shù)據(jù).

(4)存儲完整性:確保云服務(wù)器只有真實存儲用戶的完整數(shù)據(jù)才能通過校驗者的驗證.

3.2 符號定義

方案中涉及到的符號含義由表1給出.

Table 1 Table of symbols and notions表1 符號表

3.3 方案框架

定義3.一個支持批處理和錯誤定位的公開可驗證的數(shù)據(jù)擁有性證明方案ELBPDP=(SetUp,Extract,TagGen,PosTagGen,Challenge,Prove,Verify)包括以下7種算法.

1)Setup(1k)→(params,mpk,msk).以安全參數(shù)k為輸入,PKG(private key generator)輸出公共參數(shù)params,主密鑰對(mpk,msk),msk僅為PKG所知.

2)Extract(params,msk,IDi)→(ski,pki).以公共參數(shù)params、主私鑰msk和用戶身份IDi為輸入,PKG輸出用戶相應(yīng)的私鑰ski和公鑰pki.

3)TagGen(params,IDi,ski,mpk,{Mijk})→({σijk}).以公共參數(shù)params、用戶身份IDi和私鑰ski、主公鑰mpk、文件數(shù)據(jù)塊的集合{Mijk}為輸入,用戶DOi對每個塊計算數(shù)據(jù)標簽σijk,并輸出數(shù)據(jù)標簽集合{σijk},然后將{Mijk}和{σijk}存儲到相應(yīng)的服務(wù)器端.服務(wù)器收到數(shù)據(jù)塊和數(shù)據(jù)標簽后校驗其可用性.

4)PosTagGen(params,mpk,{Mijk})→{chrij}.以公共參數(shù)params、主公鑰mpk、文件數(shù)據(jù)塊的集合{Mijk}為輸入,用戶DOi對其存儲在服務(wù)器CSj上的數(shù)據(jù)塊計算定位標簽chrij,并將所有的定位標簽{chrij}發(fā)送給校驗者TPA.

5)Challenge({i,j,k})→(chal,{chalj}).以所有文件塊的索引集為輸入,TPA輸出總挑戰(zhàn)chal,并將chal按服務(wù)器劃分成若干分挑戰(zhàn){chalj},然后將每個chalj發(fā)送給相應(yīng)的服務(wù)器CSj.

6)Prove(params,chalj,{IDi},{σijk},{Mijk})→Pj.收到挑戰(zhàn)的服務(wù)器CSj以公共參數(shù)params、挑戰(zhàn)chalj、用戶身份集合{IDi}、數(shù)據(jù)標簽集合{σijk}和CSj上所存儲的數(shù)據(jù)塊集合{Mijk}為輸入,計算證明Pj,并將Pj發(fā)送給校驗者TPA.

7)Verify(params,chal,{IDi},{Pj},mpk,{chrijt})→{1,{(i,j)}}.以公共參數(shù)params、總挑戰(zhàn)chal、用戶身份集合{IDi}、所有被校驗的服務(wù)器返回的證明{Pj}、主公鑰mpk、定位標簽集{chrijt}為輸入,TPA批處理校驗證明集{Pj}的有效性,以確定各個被校驗服務(wù)器中的數(shù)據(jù)保存是否完整.若{Pj}有效,則輸出“1”;否則,定位所有出錯數(shù)據(jù)所屬用戶和所在服務(wù)器,并輸出其索引對{(i,j)}.

3.4 安全定義

敵手模型:在我們的方案中,考慮校驗者即 TPA是誠實且好奇的,它總會按照協(xié)議規(guī)定執(zhí)行,因為作為第三方審計,一旦被用戶得知會與服務(wù)器勾結(jié),對其聲譽有極大的損害,但 TPA也有可能對用戶的數(shù)據(jù)有一定好奇心.而云服務(wù)器為了更高的利益,可能會刪除用戶不常用的數(shù)據(jù),而且在丟失或損毀用戶數(shù)據(jù)后,會偽造數(shù)據(jù)標簽或者證明企圖通過校驗,欺騙校驗者和用戶.綜上,我們對敵手模型的設(shè)定有其合理性.

定義4.偽造數(shù)據(jù)標簽游戲Dtag-forgeA(k).

1.Setup:挑戰(zhàn)者C運行Setup(1k),得到(params,mpk,msk),將(params,mpk)發(fā)送給敵手A,msk秘密保存.

2.Query:敵手A適應(yīng)性的對C做ExtractQuery和TagGenQuery兩種詢問:

(1)ExtractQuery:敵手A詢問IDi的私鑰.C運行算法Extract(params,msk,IDi),得到私鑰ski,并將其發(fā)送給A.C設(shè)置一個集合S1={IDi},存放被查詢過的用戶身份.

(2)TagGenQuery:敵手A詢問文件塊Mijk的數(shù)據(jù)標簽,C運行算法TagGen(params,IDi,ski,mpk,{Mijk})得到數(shù)據(jù)標簽σijk,并將其發(fā)送給A.C設(shè)置一個集合I1={(i,j,k,Mijk)},存放被查詢過數(shù)據(jù)標簽的文件塊.

3.Forge:敵手A對一個身份為的用戶所擁有的文件塊,偽造出一個數(shù)據(jù)標簽,且

4.如果敵手A輸出的數(shù)據(jù)標簽是有效的,則游戲輸出為1;否則輸出為0.如果Dtag-forgeA(k)=1,則稱敵手A贏得了這次偽造數(shù)據(jù)標簽游戲.

定義5.對于任意一個PPT敵手A,如果在一個文件塊集上存在一個可忽略的函數(shù)negl,使得:則稱在這個文件塊集上的數(shù)據(jù)標簽是不可偽造的.

定義6.偽造數(shù)據(jù)標簽證明游戲DtagProof-forgeA(k).

1.Setup:與偽造數(shù)據(jù)標簽游戲的Setup階段相同.

2.Query1:與偽造數(shù)據(jù)標簽游戲的Query階段相同.

3.Challenge:挑戰(zhàn)者C生成一個包含c*組數(shù)據(jù)的挑戰(zhàn)chal*,其中至少有 1個,使得,且.挑戰(zhàn)者C將挑戰(zhàn)chal*發(fā)送給A.

4.Query2:與偽造數(shù)據(jù)標簽游戲的Query階段相似,設(shè)置一個集合S2={IDi}存放本階段被查詢過的用戶身份,設(shè)置一個集合I2={(i,j,k,Mijk)}存放本階段被查詢過數(shù)據(jù)標簽的文件塊.挑戰(zhàn)chal*中至少存在 1個,使得,且.

5.Forge:敵手A針對挑戰(zhàn)chal*,偽造出一個證明.

6.如果敵手A輸出的數(shù)據(jù)標簽證明是有效的,則游戲輸出為1;否則輸出為0.如果DtagProof-forgeA(k)=1,則稱敵手A贏得了這次偽造數(shù)據(jù)標簽證明游戲.

定義7.對于任意一個PPT敵手A,如果在一個文件塊集上存在一個可忽略的函數(shù)negl,使得:

則稱在這個文件塊集上的數(shù)據(jù)標簽證明是不可偽造的.

4 具體方案

方案的具體細節(jié)如下.

1)Setup(1k)→(params,mpk,msk):輸入一個安全參數(shù)k,PKG執(zhí)行以下操作.

PKG選擇兩個階為q的乘法循環(huán)群G1和G2,q是一個大素數(shù)且滿足q>2k,取G1的生成元為g,在群G1和G2上選擇一個雙線性映射e:G1×G1→G2.

PKG選擇4個密碼學(xué)Hash函數(shù)H1、H2、H3、H4和一個偽隨機函數(shù)f,其中,:(H1和H3、H2和H4分別是不同的Hash函數(shù)),.

3)TagGen(params,IDi,ski,mpk,{Mijk})→({σijk}):用戶DOi執(zhí)行以下操作.

DOi隨機選取,對自己的每個文件塊計算,并計算.令文件塊的數(shù)據(jù)標簽為.

DOi將其所有的文件塊{Mijk}和相應(yīng)的數(shù)據(jù)標簽{σijk}按服務(wù)器索引發(fā)送給相應(yīng)的服務(wù)器.每個服務(wù)器收到用戶發(fā)送的數(shù)據(jù)塊和數(shù)據(jù)標簽后,通過校驗下面的等式是否成立來確定數(shù)據(jù)標簽是否可用:

4)PosTagGen(params,mpk,{Mijk})→{ait,chrijt}.

用戶DOi隨機選擇.

設(shè)存儲DOi數(shù)據(jù)的服務(wù)器索引集合為Ji,且DOi在服務(wù)器CSj(j∈Ji)上存儲的文件塊塊數(shù)為Nij.用戶DOi對每一個服務(wù)器CSj(j∈Ji),分別以ait(1≤t≤λ)為 MHT參數(shù),對其存儲在CSj上的Nij個數(shù)據(jù)塊構(gòu)建λ棵 MHT.每棵樹用TRijt(1≤t≤λ)表示,TRijt的根節(jié)點用Rijt表示.

例如,用戶DO1在服務(wù)器CS1上共存放了 4 個數(shù)據(jù)塊M111、M112、M113、M114,使用a1t(1≤t≤λ)作為參數(shù),TR11t的構(gòu)建如圖3所示,樹的根為R11t.

Fig.3 MHTTR11tconstructed byDO1 with the data block stored inCS1 and parametera1t圖3DO1以a1t為參數(shù),針對CS1上的數(shù)據(jù)塊構(gòu)建的MHTTR11t

DOi令.

設(shè)服務(wù)器共有η個.DOi構(gòu)建一張定位索引表,其中,若不存在,即j?Ji,則令將定位索引表發(fā)送給校驗者.定位索引表見表2.

Table 2 Table of locating indexes constructed byDOi表2 用戶DOi構(gòu)建的定位索引表

校驗者接收用戶DOi發(fā)來的審計請求,請求為DOi所有數(shù)據(jù)塊的索引集{(i,j,k)},包括用戶索引i、存儲DOi數(shù)據(jù)的服務(wù)器CSj索引j∈Ji、存放在CSj上的塊索引k.收到多個云用戶的審計請求后,TPA將所有審計請求做并集,得到總的審計請求集合.

校驗者從總的審計請求集合Q中選出c個塊進行校驗,令表示被選中的c個塊,構(gòu)建索引集合I={(in,jn,kn)|n=1,…,c}.

校驗者令總挑戰(zhàn)chal=(I,K,α).

設(shè)被挑戰(zhàn)的數(shù)據(jù)塊所在服務(wù)器的索引集合{j}用U表示,校驗者將挑戰(zhàn)chal按被挑戰(zhàn)服務(wù)器的不同,劃分成|U|個分挑戰(zhàn){chalj},有.每個,其中,并且.

校驗者將chalj發(fā)送給服務(wù)器CSj.

Prove-DataTag:收到挑戰(zhàn)chalj的服務(wù)器CSj計算(此處{rn}表示服務(wù)器CSj對其收到挑戰(zhàn)chalj中所有塊分別計算的偽隨機函數(shù)值構(gòu)成的集合),對chalj中涉及的每一個用戶,計算,得到集合,其中,Oj表示Ij中包含的所有云用戶的索引集合.然后,CSj利用標簽計算.

Prove-PositionTag:服務(wù)器CSj針對每個被挑戰(zhàn)的用戶DOi(i∈Oj),對存儲在其上的所有數(shù)據(jù)塊Mijk,以αj中與DOi的數(shù)據(jù)塊索引對應(yīng)的aiτ為參數(shù),按照如圖3所示的方法重構(gòu)相應(yīng)的 MHT,表示為TRijτ,其樹根為Rijτ.所有Oj中云用戶的數(shù)據(jù)塊構(gòu)建的MHT樹根和與其對應(yīng)的用戶、服務(wù)器索引構(gòu)成集合{(i,j,Rijτ)|i∈Oj}.

7)Verify(params,chal,τ,{IDi},{Pj},mpk,{chrijt})→{1,{(i,j)}}.

設(shè)校驗者生成的總挑戰(zhàn)中所涉及的用戶DOi的索引集合{i}用O表示.校驗者收到所有被挑戰(zhàn)服務(wù)器發(fā)回的證明后,先計算(此處{rn}表示 TPA對總挑戰(zhàn)中所有被挑戰(zhàn)塊分別計算的偽隨機函數(shù)值構(gòu)成的集合),然后校驗等式(2)是否成立:

· 若等式(2)成立,則說明批處理校驗通過,即總挑戰(zhàn)中涉及的云用戶的數(shù)據(jù)審計結(jié)果為驗證通過,校驗者輸出1;

· 若等式(2)不成立,則對云服務(wù)器CSj(j∈U)返回的集合中的每個元素(i,j,Rijτ),TPA利用(i,j)和τ,查詢定位索引表Indexi中第τ行、第j+1列中的值并校驗等式(3)是否成立:

若不成立,則輸出相應(yīng)的(i,j).

5 正確性、安全性及性能分析

5.1 正確性證明

定理1.若校驗者和服務(wù)器都是誠實的,那么服務(wù)器返回的關(guān)于數(shù)據(jù)標簽的證明就可以通過TPA的批處理校驗.

證明:等式(2)的右邊可以進行如下變換:

則等式(2)的右邊就等于:

故等式(2)成立.證畢. □

5.2 安全性分析

定理2[17].如果CDH問題是困難的,則在隨機諭言機模型下,不存在一個PPT敵手能夠以不可忽略的概率贏得偽造數(shù)據(jù)標簽游戲.

證明:令B的輸入為(g,gx,gy)∈G3,其中,G1為q階乘法循環(huán)群,g為生成元.B作為挑戰(zhàn)者,想要通過與敵手

1A進行交互得到gxy∈G1,模擬過程如下.

1.Setup:B選擇一個q階乘法循環(huán)群G2,在群G1和G2上選擇一個雙線性映射e:G1×G1→G2,隨機選擇,設(shè)置mpk=gx,將(G1,G2,q,g,e,mpk,{vl})發(fā)送給敵手A.

2.H1-Query:A可以隨時查詢隨機諭言機H1,B需要構(gòu)建維護一張H1列表H1-list={(IDi,bi,ai,H1(IDi))}來存儲對A的回應(yīng).當(dāng)A對IDi查詢H1,B回應(yīng)方法如下:

1)若H1-list中有包含元素IDi的元組,則B讀取四元組(IDi,bi,ai,H1(IDi)),并將H1(IDi)發(fā)送給A.

2)若H1-list中沒有包含元素IDi的元組,則B根據(jù)bi的值對A進行回應(yīng),其中,bi由B通過二項分布Pr[bi=0]=δ,Pr[bi=1]=1-δ確定.

a)若bi=0,B隨機選擇一個,計算;

b)若bi=1,B隨機選擇一個,計算.

B將(IDi,bi,ai,H1(IDi))加入表H1-list中,并將H1(IDi)發(fā)送給A.

3.H2-Query:A可以隨時查詢隨機諭言機H2,B需要構(gòu)建維護一張H2列表H2-list={(IDi,H2(IDi))}來存儲對A的回應(yīng).當(dāng)A對IDi查詢H2,B回應(yīng)方法如下.

1)若H2-list中有包含元素IDi的元組,則B讀取二元組(IDi,H2(IDi)),并將H2(IDi)發(fā)送給A.

2)若H2-list中沒有包含元素IDi的元組,則B隨機選擇一個H2(IDi)發(fā)送給A,然后將二元組(IDi,H2(IDi))加入表H2-list中.

4.H3-Query:A可以隨時查詢隨機諭言機H3.B需要構(gòu)建維護一張H3列表H3-list={(mpki,zi,H3(mpki))}來存儲對A的回應(yīng).當(dāng)A對mpki查詢H3,B回應(yīng)方法如下.

1)若H3-list中有包含元素mpki的元組,則B讀取三元組(mpki,zi,H3(mpki)),并將H3(mpki)發(fā)送給A.

2)若H3-list中沒有包含元素mpki的元組,則B隨機選擇,計算,并將H3(mpki)發(fā)送給A.然后,B將三元組(mpki,zi,H3(mpki))加入表H3-list中.特別地,當(dāng)mpki=mpk時,B將相應(yīng)的元組記為(mpk,z,H3(mpk)=gz).

5.ExtractQuery:A可以隨時查詢隨機諭言機Extract.B需要構(gòu)建維護一張表Extract-list={(IDi,ski)}來存儲對A的回應(yīng).當(dāng)A對IDi查詢諭言機Extract,B回應(yīng)方法如下.

1)若Extract-list中有包含元素IDi的元組,則B讀取二元組(IDi,ski),并將ski發(fā)送給A。

2)若Extract-list中沒有包含元素IDi的元組,則B查找H1-list中是否有包含元素IDi的元組,若沒有,則B生成一個H1(IDi)的查詢,使得四元組(IDi,bi,ai,H1(IDi))存在.B根據(jù)bi的值對A進行回應(yīng).

a)若bi=0,則B計算,并將ski發(fā)送給A.然后,B將(IDi,ski)加入表Extract-list中;

b)若bi=1,則B報告失敗,并終止模擬.

6.TagGenQuery:A可以隨時查詢隨機諭言機TagGen.B需要構(gòu)建維護一張表TagGen-list={(i,j,k,Mijk,σijk)}來存儲對A的回應(yīng).當(dāng)A對(i,j,k,Mijk)查詢諭言機TagGen,B回應(yīng)方法如下.

1)若TagGen-list中有包含元素(i,j,k,Mijk)的元組,則B讀取五元組(i,j,k,Mijk,σijk),并將σijk發(fā)給A.

2)若TagGen-list中沒有包含元素(i,j,k,Mijk)的元組,則B查找H1-list中是否有包含元素IDi的元組,若沒有,則B生成一個H1(IDi)的查詢.然后,B查找H2-list中是否有包含元素IDi的元組,若沒有,則B生成一個H2(IDi)的查詢.然后,B查找H3-list中是否有包含元素mpk的元組,若沒有,則B生成一個H3(mpk)的查詢.B根據(jù)bi的值對A進行回應(yīng).

a)若bi=0,則B隨機選擇Sijk∈G1,計算:

并將σijk發(fā)送給A.然后,B將五元組(i,j,k,Mijk,σijk)加入表TagGen-list中.可以驗證,(i,j,k,Mijk,σijk)滿足等式(1),即σijk為數(shù)據(jù)塊(i,j,k,Mijk)的有效標簽.

b)若bi=1,則B報告失敗,并終止模擬.

7.Forge:敵手A對一個身份為的用戶所擁有的文件塊偽造數(shù)據(jù)標簽,要求敵手A之前并未對進行過ExtractQuery,且未對進行過TagGenQuery.B查找H1-list中是否有包含元素的元組,若沒有,則B生成一個的查詢.然后,B查找H2-list中是否有包含元素的元組,若沒有,則B生成一個的查詢.然后,B查找H3-list中是否有包含元素mpk的元組,若沒有,則B生成一個H3(mpk)的查詢.B根據(jù)bi的值做如下操作.

B可得到:

B計算.

令E表示事件B求解出gxy,經(jīng)過上面分析可知:在A進行nEQ次ExtractQuery和nTQ次TagGenQuery時模擬未終止,且A對數(shù)據(jù)塊成功地偽造出有效的數(shù)據(jù)標簽;同時,在對進行H1-Query時,若元組中,則事件E發(fā)生.若敵手A贏得偽造數(shù)據(jù)標簽游戲的概率ε不可忽略,則不可忽略,即B解決群G1上的CDH問題的概率不可忽略.當(dāng)δ=(nEQ+nTQ)/(nEQ+nTQ+1)時,取得最大值.證畢. □

定理3[17].如果CDH問題是困難的,則在隨機諭言機模型下,不存在一個PPT敵手能夠以不可忽略的概率贏得偽造數(shù)據(jù)標簽證明游戲.

證明:令B的輸入為,其中,G1為q階乘法循環(huán)群,g為生成元.B作為挑戰(zhàn)者,想要通過和敵手A進行交互得到gxy∈G1,模擬過程如下.

1.Setup:B選擇一個q階乘法循環(huán)群G2,在群G1和G2上選擇一個雙線性映射e:G1×G1→G2,隨機選擇,選取偽隨機函數(shù),設(shè)置mpk=gx.將(G1,G2,q,g,e,f,mpk,{vl})發(fā)送給敵手A.

2.B對H1-Query、H2-Query、H3-Query、第1階段Extract-1Query、TagGen-1Query的回應(yīng)方式與定理2證明中的回應(yīng)方式相同.

3.Challenge:令S1表示第 1階段被Extract-1Query過的用戶身份IDi的集合,集合I1存放第 1階段被TagGen-1Query的(i,j,k,Mijk).B生成挑戰(zhàn)chal*=(I*,K*,α*),其中,,,其中至少有1個,且對于相同的,至少有1個塊將挑戰(zhàn)chal*發(fā)送給A.

4.第2階段Extract-2Query,TagGen-2Query與定理2中ExtractQuery,TagGenQuery相同,并令S2表示第2階段被Extract-2Query過的用戶身份IDi的集合,集合I2存放第 2階段被TagGen-2Query過的(i,j,k,Mijk).需保證挑戰(zhàn)chal*中至少有1個,且對于相同的,至少有1個塊.

5.Forge:敵手A針對挑戰(zhàn)chal*,偽造證明.B在H1-list中查找,對于不存在列表中的,B對其做H1-Query.B在H2-list中查找,對于不存在列表中的,B對其做H2-Query.B在H3-list中查找是否有(mpk,z,gx),若沒有,則B對mpk進行H3-Query.B根據(jù)的值做如下操作.

B計算.

令E表示事件B求解出gxy,經(jīng)過上面的分析可知,在A進行nEQ次ExtractQuery和nTQ次TagGenQuery未終止,且A針對挑戰(zhàn)能夠成功偽造出可通過校驗的數(shù)據(jù)標簽證明;同時,對進行H1-Query時,其中至少有1個,則事件E發(fā)生.設(shè)敵手A贏得偽造數(shù)據(jù)標簽證明游戲的概率為ε,則B解決群G1上的CDH問題的概率為時,取得最大值.證畢. □

定理4.如果Hash函數(shù)是抗碰撞的,則不存在一個PPT敵手能夠以不可忽略的概率偽造出通過TPA校驗的定位標簽證明.

證明:被挑戰(zhàn)服務(wù)器在每次挑戰(zhàn)時都會收到TPA發(fā)來的重構(gòu)MHT的參數(shù).由于每次挑戰(zhàn)用于定位的MHT根標簽所使用的參數(shù)不同,使得服務(wù)器無法提前預(yù)知、計算并存儲葉子節(jié)點,所以收到挑戰(zhàn)的服務(wù)器都需要根據(jù)挑戰(zhàn)中MHT參數(shù)集{αj}重新計算相應(yīng)的MHT根值作為證明.在MHT中,葉子節(jié)點是參數(shù)與文件塊連接后做Hash運算得到的,而根值是由所有葉子節(jié)點經(jīng)過多層計算Hash值得到的,所以,若Hash函數(shù)是抗碰撞的,則要在不知道參數(shù)與文件塊值的情況下偽造出可通過校驗的根值的概率是可以忽略的.證畢. □

此外,要說明的是,為了實現(xiàn)錯誤定位,且使得用戶端不額外存儲多余的信息,有些信息,如用戶數(shù)據(jù)塊所存儲的服務(wù)器和所有用戶數(shù)據(jù)的定位索引表,TPA都是知道的.而定位索引表中的元素是每個用戶存儲在不同服務(wù)器上的數(shù)據(jù)所構(gòu)成的MHT樹根,若Hash函數(shù)是抗原象攻擊的,則TPA無法得知用戶原始數(shù)據(jù)塊值.

5.3 性能分析

在下面的分析中,n表示所有云用戶的文件塊總數(shù),c表示TPA選中的被挑戰(zhàn)塊的數(shù)量,n1表示c個被挑戰(zhàn)塊所屬用戶的數(shù)量,n2表示c個被挑戰(zhàn)塊所在的服務(wù)器的數(shù)量,η表示所有云服務(wù)器的數(shù)量,γ表示所有云用戶的數(shù)量,s表示每個數(shù)據(jù)塊的分區(qū)數(shù),λ表示每個用戶對其存放在一個服務(wù)器上的數(shù)據(jù)所構(gòu)建的 MHT數(shù)量.cj表示被挑戰(zhàn)服務(wù)器CSj上被挑戰(zhàn)的塊數(shù),有1≤cj≤cmax=c-n2+1.假設(shè)云用戶DOi總共將mi個文件塊存儲到多個服務(wù)器中,服務(wù)器CSj上共存儲了m′j個文件塊.

方案的通信輪數(shù)為1輪,在此一輪通信中既實現(xiàn)了批處理校驗,又能實現(xiàn)錯誤數(shù)據(jù)的定位功能.

1.關(guān)于通信復(fù)雜度

在初始階段,云用戶除了將文件塊{Mijk}和相應(yīng)的數(shù)據(jù)標簽{σijk}發(fā)送給服務(wù)器以外,為了實現(xiàn)對其錯誤數(shù)據(jù)進行定位,還需要將定位索引表發(fā)送給TPA,每個用戶的定位索引表中包含λ(η+1)個Zq中的元素.

在挑戰(zhàn)階段,TPA發(fā)送總挑戰(zhàn)chal=(I,K,α),其中,I中包括3c個整數(shù),K中包含c個Zq中的元素,α中也包含c個Zq中的元素.綜上,挑戰(zhàn)階段的通信復(fù)雜度為O(c).

2.關(guān)于存儲復(fù)雜度

服務(wù)器存儲著用戶的數(shù)據(jù)塊和相應(yīng)的數(shù)據(jù)標簽,與其他方案相似.TPA需要存儲所有用戶發(fā)來的數(shù)據(jù)塊定位標簽,共有γ張定位索引表,包含γλ(η+1)個Zq中的元素,存儲復(fù)雜度為O(γλη).

3.關(guān)于計算復(fù)雜度

云用戶:除了為每個數(shù)據(jù)塊計算相應(yīng)的數(shù)據(jù)標簽以外,為了實現(xiàn)錯誤定位,額外地,云用戶需要對其存儲在不同服務(wù)器上的數(shù)據(jù)塊分別構(gòu)建λ棵MHT.含有Nij個葉子節(jié)點的MHT最多需要做次Hash運算.擁有mi個數(shù)據(jù)塊的云用戶DOi最多計算次 Hash,因此,DOi計算定位標簽的時間復(fù)雜度為O(λmi),這項工作是一次性的.

被挑戰(zhàn)服務(wù)器:計算的證明包含兩部分:(1)用于批處理校驗的部分,需要做cj次偽隨機函數(shù)運算、2cj次指數(shù)運算、2(cj-1)次群中乘法運算、s·cj次普通乘法運算,最多s·(cj-1)次普通加法運算;(2)用于定位錯誤的部分,最多需要進行次Hash運算.

TPA:批處理校驗包括c次偽隨機函數(shù)運算、n1次指數(shù)運算和3次雙線性對運算,最多n1(s-1)·(n2-1)+c次普通加法運算、最多s·min(n1n2,c)次普通乘法運算、2(n2-1)+(n1-1)次群中乘法運算.若批處理校驗不通過,則再對服務(wù)器返回的樹根一一進行對比校驗,判斷某一用戶存放在某一服務(wù)器上的數(shù)據(jù)是否遭到損毀,只需一次比較操作.

下面將我們的方案與其他多用戶多服務(wù)器環(huán)境下支持批處理校驗的方案進行比較.從效率和是否支持錯誤定位方面,我們的方案與He等人[18]、Shin等人[19]和Zhou等人[17]的方案進行對比的結(jié)果見表3.

Table 3 Comparison of efficiency and location function表3 效率及定位功能比較

其中,Cexp表示群G1上單個指數(shù)運算的開銷,CH表示單個Hash函數(shù)運算的開銷,Cpar表示一個雙線性對運算的開銷,Cper表示一個偽隨機函數(shù)運算的開銷,CmG表示群上單個乘法運算的開銷,CdG表示群上單個除法運算的開銷,CmZ表示單個普通乘法運算的開銷,CaZ表示單個普通加法運算的開銷,Tcpr表示一次比較的時間開銷.因為文獻[18]中每個用戶的數(shù)據(jù)都會被挑戰(zhàn)且被挑戰(zhàn)的塊索引相同,令c′表示一個被挑戰(zhàn)用戶被挑戰(zhàn)的塊數(shù),即c=c′·n1.

4個方案中,審計階段都僅需1輪通信,我們的方案在1輪通信中不僅能夠?qū)崿F(xiàn)批處理校驗,還能在校驗不通過情況下定位錯誤數(shù)據(jù)所屬用戶和所屬服務(wù)器;而文獻[18]只支持定位錯誤數(shù)據(jù)的擁有者;文獻[19]只支持定位錯誤數(shù)據(jù)所在服務(wù)器,并且僅適用于只有 1個服務(wù)器的數(shù)據(jù)被損毀的情景.我們的方案是基于查找的方式定位錯誤數(shù)據(jù),判斷特定用戶存儲在特定服務(wù)器上的數(shù)據(jù)是否出錯僅需一次比較操作;而文獻[18,19]都是利用計算的方式來實現(xiàn)錯誤數(shù)據(jù)定位,文獻[18]判斷特定用戶的數(shù)據(jù)是否損毀需要O(c′)次指數(shù)運算,文獻[19]定位唯一的數(shù)據(jù)被損毀服務(wù)器需要次乘法運算.

在我們的方案中,為了計算定位標簽,用戶需要為其數(shù)據(jù)塊構(gòu)建 MHT,服務(wù)器在計算證明時需要重構(gòu) MHT,所以相對于其他方案,在用戶端和服務(wù)器端分別增加了2λmi和2mj′次Hash運算.由于Hash運算的速度很快,所以增加的計算對總體的計算開銷影響并不顯著.為了定位錯誤,相對于文獻[17-19],TPA需要額外存儲γ張定位索引表,總共γλ(η+1)個Zq中的元素,而TPA進行批處理校驗的計算量相對于文獻[17]來說并沒有增加.

5.4 仿真實驗

我們首先對云用戶、服務(wù)器和 TPA各自計算的時間開銷進行了仿真實驗,然后對兩種定位錯誤方式的定位效率進行了對比.PC硬件配置為Intel Core2Duo處理器、4G內(nèi)存,操作系統(tǒng)為Ubuntu 16.04 LTS 32位,利用PBC庫[20]、GMP庫[21]和Miracl庫[22],使用gcc編譯執(zhí)行.實驗中,使用PBC庫中a.param參數(shù)設(shè)置雙線性對,構(gòu)造MHT時采用SHA-256.

1.用戶計算數(shù)據(jù)標簽TagGen和定位標簽PosTagGen的計算開銷

用戶將文件分塊后,對每個數(shù)據(jù)塊計算相應(yīng)的數(shù)據(jù)標簽,然后對存儲在不同服務(wù)器上的數(shù)據(jù)塊計算定位標簽.在實驗中,我們設(shè)置每個數(shù)據(jù)塊4KB,每個分區(qū) 20B,通過設(shè)置不同的文件大小來觀察 TagGen和 PosTagGen的計算開銷.令用戶文件大小為5MB～40MB,相應(yīng)的數(shù)據(jù)塊數(shù)為1 250～10 000,設(shè)置步長5MB.TagGen的計算開銷與λ=64和λ=128時PosTagGen的計算開銷實驗結(jié)果如圖4所示.

Fig.4 Computational cost of TagGen &PosTagGen for increased size of files圖4 文件大小增加時TagGen和PosTagGen的計算開銷

從實驗結(jié)果可以看出,TagGen的時間隨著文件大小的增長(數(shù)據(jù)塊數(shù)增長)呈線性增長,與性能分析結(jié)果一致.特別地,當(dāng)文件大小為5MB(40MB)時,TagGen的時間為13.6s(121.7s).PosTagGen的計算開銷與文件大小(數(shù)據(jù)塊數(shù)量)和λ值是相關(guān)的:當(dāng)λ值固定時,PosTagGen的計算開銷隨著數(shù)據(jù)塊數(shù)量增加而增大,基本呈線性增長,實驗結(jié)果與性能分析相符合.進一步觀察,當(dāng)λ=64,文件大小為 5M(40M)時,PosTagGen的時間為 5.5s(66.5s).當(dāng)λ=128,文件大小為 5MB(40MB)時,PosTagGen的時間為 11.0s(133.0s).TagGen與 PosTagGen的計算開銷較大,耗費的時間顯著高于其他操作耗費的時間,但是對于一個文件來說都僅需計算 1次.表4為當(dāng)λ=64和λ=128時,TPA進行校驗的不同時間間隔所能支持的錯誤定位有效期.

Table 4 Error locating period of validity for different verification time interval表4 不同校驗時間間隔下,支持錯誤定位的有效期

2.服務(wù)器計算證明Prove-DataTag、Prove-PositionTag和TPA批量校驗數(shù)據(jù)標簽證明Verify的計算開銷

在挑戰(zhàn)響應(yīng)階段,收到挑戰(zhàn)的服務(wù)器需要計算數(shù)據(jù)標簽的證明 Prove-DataTag和定位標簽的證明 Prove-PositionTag,而TPA需對被挑戰(zhàn)服務(wù)器返回的數(shù)據(jù)標簽證明進行批量審計.

服務(wù)器Prove-DataTag的計算開銷與TPA批量審計Verify的計算開銷均與TPA選取的挑戰(zhàn)塊數(shù)量有關(guān),所以我們在同樣的條件下對這兩個計算進行了仿真.實驗中,我們設(shè)置了10個用戶和10個服務(wù)器,每個用戶擁有10 000個數(shù)據(jù)塊,每個數(shù)據(jù)塊4KB,每個分區(qū)20B,每個用戶將其10 000個數(shù)據(jù)塊均勻地存儲到10個服務(wù)器上,這樣,每個服務(wù)器上存儲著10個用戶的10 000個數(shù)據(jù)塊.若云服務(wù)器的數(shù)據(jù)塊損毀率為1%,則TPA挑戰(zhàn)其上的300個(460個)數(shù)據(jù)塊,就能以95%(99%)的概率檢測出該服務(wù)器的損毀數(shù)據(jù)行為[23].因此,在TPA隨機均勻選取10個服務(wù)器上的挑戰(zhàn)塊的情況下,我們對總挑戰(zhàn)塊數(shù)為3 000～4 600(相應(yīng)的每個服務(wù)器上被挑戰(zhàn)塊數(shù)為300～460),以步長為200,進行了實驗,結(jié)果如圖5所示.

Fig.5 Computational cost of Prove-DataTag by single server &Verify by TPA for increased number of total challenged blocks圖5 總挑戰(zhàn)塊數(shù)增加時,單個服務(wù)器Prove-DataTag和TPA Verify的計算開銷

從實驗結(jié)果可以看出,服務(wù)器Prove-DataTag的計算開銷隨著其上被挑戰(zhàn)塊數(shù)量的增加而增長.這主要是因為當(dāng)其上被挑戰(zhàn)塊數(shù)增加時,服務(wù)器需要為增加的挑戰(zhàn)塊的數(shù)據(jù)標簽做群上的指數(shù)運算.隨著總挑戰(zhàn)塊數(shù)的增加,TPA批量校驗數(shù)據(jù)標簽證明 Verify的計算開銷增長并不明顯.這是因為增加的操作只是一些偽隨機函數(shù)和普通加法運算,實驗結(jié)果與性能分析結(jié)果一致.進一步觀察,當(dāng)總挑戰(zhàn)塊數(shù)為 3 000(4 600)個時,服務(wù)器 Prove-DataTag的時間為2.7s(4.1s),TPA Verify的時間僅為53ms(54ms).

被挑戰(zhàn)服務(wù)器計算定位標簽證明Prove-PositionTag的計算開銷與該服務(wù)器上被挑戰(zhàn)用戶的所有數(shù)據(jù)塊數(shù)有關(guān).我們對其中最壞的情況進行了模擬,即數(shù)據(jù)存放于該服務(wù)器上的所有用戶均有數(shù)據(jù)塊被TPA挑戰(zhàn),所以被挑戰(zhàn)服務(wù)器需對其上存儲的所有數(shù)據(jù)塊進行重構(gòu)MHT的操作.我們令被挑戰(zhàn)服務(wù)器存儲的數(shù)據(jù)塊數(shù)為5 000～12 000,步長為1 000,對單個被挑戰(zhàn)服務(wù)器計算定位標簽證明Prove-PositionTag(即重構(gòu)MHT)的計算開銷進行測試,結(jié)果如圖6所示.

從實驗結(jié)果可以看出,服務(wù)器重構(gòu)MHT的計算開銷隨著該服務(wù)器上存儲的數(shù)據(jù)塊數(shù)增加而增長,且增長趨勢基本呈線性,與性能分析結(jié)果一致.由于Prove-PositionTag的計算是重構(gòu)MHT樹,所做的都是Hash操作,因此即使是在最壞情況下,重構(gòu)MHT的時間也是較快的.當(dāng)服務(wù)器上存有5 000(12 000)個數(shù)據(jù)塊,且所有其上用戶都有數(shù)據(jù)塊被挑戰(zhàn)時,服務(wù)器Prove-PositionTag的時間為0.42s(1.34s).

Fig.6 Computational cost of Prove-PositionTag by single server for its increased number of stored blocks圖6 存儲的數(shù)據(jù)塊數(shù)增加時,單個服務(wù)器Prove-PositionTag的計算開銷

3.TPA定位錯誤時間比較

在本節(jié)中,我們對兩種定位錯誤方式的定位效率進行對比:逐一校驗方式和利用定位標簽輔助定位的方式.為了使對比結(jié)果更合理,我們同樣是在 Zhou等人方案[17]的基礎(chǔ)上實現(xiàn)逐一校驗定位錯誤,并設(shè)置相同的環(huán)境參數(shù).但需要說明的是,逐一校驗方式使得Zhou等人的方案只能定位錯誤數(shù)據(jù)所在服務(wù)器.

在實驗中,我們設(shè)置10個用戶和100個服務(wù)器,每個用戶擁有100 000個數(shù)據(jù)塊,每個數(shù)據(jù)塊4KB,每個分區(qū)20B,每個用戶將其 100 000個數(shù)據(jù)塊均勻存儲到 100個服務(wù)器上,這樣,每個服務(wù)器上就存儲著 10個用戶的10 000個數(shù)據(jù)塊.在TPA隨機均勻選取每個被挑戰(zhàn)服務(wù)器上10個用戶的300個挑戰(zhàn)塊的情況下,令被挑戰(zhàn)服務(wù)器個數(shù)為10～100,模擬兩種定位錯誤方法的計算開銷,實驗結(jié)果如圖7所示.

Fig.7 Time comparison of location errors by TPA圖7 TPA定位錯誤時間比較

從實驗結(jié)果可以看出,隨著被挑戰(zhàn)服務(wù)器數(shù)量的增加,逐一校驗方式定位錯誤服務(wù)器的時間耗費呈線性增長趨勢,而利用定位標簽定位錯誤數(shù)據(jù)所屬用戶和所在服務(wù)器的計算開銷增長并不明顯.這是因為逐一校驗方式中,TPA針對每個被挑戰(zhàn)服務(wù)器返回的證明單獨校驗,每次校驗都需要做多個指數(shù)運算和雙線性對運算;而利用定位標簽的方式只涉及比較操作.在被挑戰(zhàn)服務(wù)器個數(shù)為 10(100)時,定位標簽方式僅需 0.059s(0.087s),而逐一校驗方式則需0.523s(4.652s).顯然,隨著被挑戰(zhàn)服務(wù)器個數(shù)的增加,使用定位標簽輔助錯誤定位的效率顯著優(yōu)于逐一校驗的方式.

6 總 結(jié)

本文主要研究了批處理 PDP方案在批量審計不通過情況下的錯誤數(shù)據(jù)定位問題.提出了利用定位標簽輔助第三方審計員快速定位錯誤的方法,并在多用戶多服務(wù)器環(huán)境下給出了一個具體實現(xiàn),在批處理校驗不通過的情況下,僅通過比較操作就能同時定位錯誤數(shù)據(jù)所屬用戶和所在服務(wù)器.我們對方案的正確性和安全性進行了證明,并對方案的性能進行了理論分析和仿真實驗.性能分析結(jié)果表明,我們的方案在定位錯誤數(shù)據(jù)的能力和效率方面均高于其他具有單一定位功能的方案.實驗結(jié)果也表明,利用定位標簽輔助錯誤定位的效率顯著優(yōu)于逐一校驗的方式,且實現(xiàn)錯誤定位功能的額外計算開銷是可接受的.

在本文方案中,預(yù)先設(shè)定的 MHT數(shù)量使得本方案不適合進行無限次的錯誤定位.為了緩解次數(shù)限制問題,有兩種可行的解決辦法.

(1)不要求每次校驗都返回樹的根值.僅當(dāng)批處理校驗發(fā)生錯誤后,校驗者給服務(wù)器再次發(fā)送挑戰(zhàn),要求服務(wù)器提供相應(yīng)樹的根值.

(2)對服務(wù)器建立分級制度,校驗者在挑戰(zhàn)時可設(shè)立一個狀態(tài)標識,若狀態(tài)為“1”,則要求返回根值;若為“0”則不要求.對信譽好的服務(wù)器,可以適當(dāng)減少其返回根值的次數(shù).