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

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

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

1 引 言

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

1.1 相關(guān)工作

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

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

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

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

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

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

1.2 貢 獻(xiàn)

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

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

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

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

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

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

2 預(yù)備知識(shí)

2.1 雙線性對(duì)

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

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

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

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

2.2 CDH困難問(wèn)題

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

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

2.3 Merkle Hash Tree

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

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

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

3 定義與模型

3.1 系統(tǒng)模型與設(shè)計(jì)目標(biāo)

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

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

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

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

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

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

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

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

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

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

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

3.2 符號(hào)定義

方案中涉及到的符號(hào)含義由表1給出.

Table 1 Table of symbols and notions表1 符號(hào)表

3.3 方案框架

定義3.一個(gè)支持批處理和錯(cuò)誤定位的公開可驗(yàn)證的數(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,主密鑰對(duì)(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對(duì)每個(gè)塊計(jì)算數(shù)據(jù)標(biāo)簽σijk,并輸出數(shù)據(jù)標(biāo)簽集合{σijk},然后將{Mijk}和{σijk}存儲(chǔ)到相應(yīng)的服務(wù)器端.服務(wù)器收到數(shù)據(jù)塊和數(shù)據(jù)標(biāo)簽后校驗(yàn)其可用性.

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

5)Challenge({i,j,k})→(chal,{chalj}).以所有文件塊的索引集為輸入,TPA輸出總挑戰(zhàn)chal,并將chal按服務(wù)器劃分成若干分挑戰(zhàn){chalj},然后將每個(gè)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ù)標(biāo)簽集合{σijk}和CSj上所存儲(chǔ)的數(shù)據(jù)塊集合{Mijk}為輸入,計(jì)算證明Pj,并將Pj發(fā)送給校驗(yàn)者TPA.

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

3.4 安全定義

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 具體方案

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

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

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

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

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

DOi隨機(jī)選取,對(duì)自己的每個(gè)文件塊計(jì)算,并計(jì)算.令文件塊的數(shù)據(jù)標(biāo)簽為.

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

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

用戶DOi隨機(jī)選擇.

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

例如,用戶DO1在服務(wù)器CS1上共存放了 4 個(gè)數(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ù),針對(duì)CS1上的數(shù)據(jù)塊構(gòu)建的MHTTR11t

DOi令.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5.1 正確性證明

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

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

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

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

5.2 安全性分析

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

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

1A進(jìn)行交互得到gxy∈G1,模擬過(guò)程如下.

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

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

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

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

a)若bi=0,B隨機(jī)選擇一個(gè),計(jì)算;

b)若bi=1,B隨機(jī)選擇一個(gè),計(jì)算.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

B可得到:

B計(jì)算.

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

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

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

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

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

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

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

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

B計(jì)算.

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

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

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

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

5.3 性能分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5.4 仿真實(shí)驗(yàn)

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

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

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

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

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

Table 4 Error locating period of validity for different verification time interval表4 不同校驗(yàn)時(shí)間間隔下,支持錯(cuò)誤定位的有效期

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

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

服務(wù)器Prove-DataTag的計(jì)算開銷與TPA批量審計(jì)Verify的計(jì)算開銷均與TPA選取的挑戰(zhàn)塊數(shù)量有關(guān),所以我們?cè)谕瑯拥臈l件下對(duì)這兩個(gè)計(jì)算進(jìn)行了仿真.實(shí)驗(yàn)中,我們?cè)O(shè)置了10個(gè)用戶和10個(gè)服務(wù)器,每個(gè)用戶擁有10 000個(gè)數(shù)據(jù)塊,每個(gè)數(shù)據(jù)塊4KB,每個(gè)分區(qū)20B,每個(gè)用戶將其10 000個(gè)數(shù)據(jù)塊均勻地存儲(chǔ)到10個(gè)服務(wù)器上,這樣,每個(gè)服務(wù)器上存儲(chǔ)著10個(gè)用戶的10 000個(gè)數(shù)據(jù)塊.若云服務(wù)器的數(shù)據(jù)塊損毀率為1%,則TPA挑戰(zhàn)其上的300個(gè)(460個(gè))數(shù)據(jù)塊,就能以95%(99%)的概率檢測(cè)出該服務(wù)器的損毀數(shù)據(jù)行為[23].因此,在TPA隨機(jī)均勻選取10個(gè)服務(wù)器上的挑戰(zhàn)塊的情況下,我們對(duì)總挑戰(zhàn)塊數(shù)為3 000～4 600(相應(yīng)的每個(gè)服務(wù)器上被挑戰(zhàn)塊數(shù)為300～460),以步長(zhǎng)為200,進(jìn)行了實(shí)驗(yàn),結(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ù)增加時(shí),單個(gè)服務(wù)器Prove-DataTag和TPA Verify的計(jì)算開銷

從實(shí)驗(yàn)結(jié)果可以看出,服務(wù)器Prove-DataTag的計(jì)算開銷隨著其上被挑戰(zhàn)塊數(shù)量的增加而增長(zhǎng).這主要是因?yàn)楫?dāng)其上被挑戰(zhàn)塊數(shù)增加時(shí),服務(wù)器需要為增加的挑戰(zhàn)塊的數(shù)據(jù)標(biāo)簽做群上的指數(shù)運(yùn)算.隨著總挑戰(zhàn)塊數(shù)的增加,TPA批量校驗(yàn)數(shù)據(jù)標(biāo)簽證明 Verify的計(jì)算開銷增長(zhǎng)并不明顯.這是因?yàn)樵黾拥牟僮髦皇且恍﹤坞S機(jī)函數(shù)和普通加法運(yùn)算,實(shí)驗(yàn)結(jié)果與性能分析結(jié)果一致.進(jìn)一步觀察,當(dāng)總挑戰(zhàn)塊數(shù)為 3 000(4 600)個(gè)時(shí),服務(wù)器 Prove-DataTag的時(shí)間為2.7s(4.1s),TPA Verify的時(shí)間僅為53ms(54ms).

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

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

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

3.TPA定位錯(cuò)誤時(shí)間比較

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

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

Fig.7 Time comparison of location errors by TPA圖7 TPA定位錯(cuò)誤時(shí)間比較

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

6 總 結(jié)

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

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

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

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