多云存儲(chǔ)中保護(hù)隱私的數(shù)據(jù)完整性驗(yàn)證方案

任孟琦，龐曉瓊，王田琪，聶夢(mèng)飛

中北大學(xué) 大數(shù)據(jù)學(xué)院，太原 030051

1 引言

隨著云計(jì)算的蓬勃發(fā)展，為海量數(shù)據(jù)提供云服務(wù)的云存儲(chǔ)系統(tǒng)成為關(guān)注熱點(diǎn)。用戶將數(shù)據(jù)交由云服務(wù)提供商管理，能夠有效減輕本地存儲(chǔ)負(fù)擔(dān)。然而，云存儲(chǔ)[1]是一把雙刃劍，它在為用戶提供便利的同時(shí)也引發(fā)了安全性挑戰(zhàn)，不可信云服務(wù)提供商會(huì)為了自身利益而隱瞞用戶數(shù)據(jù)的丟失或損壞，造成數(shù)據(jù)的完整性破壞。因此，數(shù)據(jù)完整性驗(yàn)證技術(shù)成為云存儲(chǔ)中保證數(shù)據(jù)安全的重要手段。

早期，Ateniese等人[2]提出數(shù)據(jù)持有性（Provable Data Possess，PDP）模型來驗(yàn)證云存儲(chǔ)數(shù)據(jù)的完整性。模型中，用戶通過概率抽查的方式發(fā)起對(duì)遠(yuǎn)端服務(wù)器的挑戰(zhàn)，服務(wù)器返回與挑戰(zhàn)相關(guān)的文件塊和數(shù)據(jù)標(biāo)簽證明回應(yīng)挑戰(zhàn)，并由用戶根據(jù)回應(yīng)判斷數(shù)據(jù)的完整性。之后出現(xiàn)了很多在此模型上拓展應(yīng)用的數(shù)據(jù)完整性驗(yàn)證方案[3-5]，其中支持公開校驗(yàn)成為數(shù)據(jù)完整性驗(yàn)證的重要應(yīng)用拓展，解決了用戶作為審計(jì)個(gè)體計(jì)算能力有限的弊端。Wang等人[6]首次引入第三方審計(jì)（Third Party Auditor，TPA），提出支持公開審計(jì)的PDP方案。TPA的出現(xiàn)減輕了用戶的計(jì)算負(fù)擔(dān)，同時(shí)也帶來了新的安全風(fēng)險(xiǎn)。審計(jì)過程中，TPA出于好奇可能與服務(wù)器進(jìn)行多次交互從而獲得用戶數(shù)據(jù)的相關(guān)信息，造成用戶的數(shù)據(jù)隱私泄露[7-8]。Hao等人[9]首次提出“針對(duì)TPA隱私性”的概念，并給出了可證明安全的PDP方案。Yu等人[10]在Hao等人基礎(chǔ)上加強(qiáng)了方案的隱私性保護(hù)并進(jìn)行了安全證明。文獻(xiàn)[11]中Yu等人又提出了一種基于身份的支持完美隱私保護(hù)的數(shù)據(jù)完整性驗(yàn)證方案。目前，支持隱私保護(hù)的數(shù)據(jù)完整性驗(yàn)證方案已成為熱門研究課題。

然而，上述方案大多在單用戶單服務(wù)器環(huán)境下提出，如果簡單地在多用戶多服務(wù)器環(huán)境下拓展，則使方案效率十分低下。也曾有學(xué)者在多云服務(wù)器環(huán)境下針對(duì)方案的隱私性和效率進(jìn)行了研究，但方案被指出存在安全性攻擊。Zhu等人[12]提出多云協(xié)同存儲(chǔ)并支持隱私保護(hù)的PDP模型，但方案被指出存在惡意云服務(wù)器攻擊的威脅。He等人[13]構(gòu)造了一個(gè)多用戶多服務(wù)器環(huán)境下支持批量審計(jì)的PDP方案，但方案缺乏對(duì)服務(wù)器的安全性證明。Wang[14]提出基于身份的分布式存儲(chǔ)PDP方案，該方案也被指出存在惡意服務(wù)器方欺騙的安全性問題。

針對(duì)上述問題，本文提出一種在多用戶多服務(wù)器環(huán)境下支持批處理校驗(yàn)，同時(shí)保護(hù)用戶數(shù)據(jù)隱私且針對(duì)服務(wù)器安全的數(shù)據(jù)完整性驗(yàn)證方案IDB-RDIC。

本文的創(chuàng)新點(diǎn)：所提方案對(duì)多用戶多服務(wù)器環(huán)境下的數(shù)據(jù)支持高效的批處理校驗(yàn)，與可在多用戶多服務(wù)器環(huán)境下簡單拓展的方案[11]相比，降低了TPA和服務(wù)器端的通信開銷與計(jì)算開銷。同時(shí)本文方案還實(shí)現(xiàn)了針對(duì)TPA的隱私保護(hù)，并對(duì)服務(wù)器的安全性進(jìn)行了證明。

2 IDB-RDIC結(jié)構(gòu)模型和安全模型

2.1 結(jié)構(gòu)模型

單用戶單服務(wù)器環(huán)境下的數(shù)據(jù)完整性驗(yàn)證方案[11]可以簡單地在多用戶多服務(wù)器環(huán)境下拓展，拓展之后的結(jié)構(gòu)模型圖如圖1所示。模型由四類實(shí)體構(gòu)成，當(dāng)多個(gè)用戶向第三方TPA發(fā)送審計(jì)請(qǐng)求任務(wù)時(shí)，TPA只能為每位用戶逐一校驗(yàn)其數(shù)據(jù)的完整性，由此帶來極大的通信與計(jì)算開銷。

圖1 簡單的多用戶多云存儲(chǔ)模型圖

為了提高效率，本文方案支持對(duì)存儲(chǔ)在多個(gè)云服務(wù)器上的多用戶進(jìn)行批處理校驗(yàn)，所采用的結(jié)構(gòu)模型圖如圖2所示。模型由五類實(shí)體構(gòu)成，具體闡述如下。

圖2 IDB-RDIC結(jié)構(gòu)模型圖

用戶：需要在不同的服務(wù)器上存儲(chǔ)數(shù)據(jù)的多個(gè)用戶，用戶可以和云存儲(chǔ)服務(wù)器通信來傳輸數(shù)據(jù)。

第三方審計(jì)（即校驗(yàn)者TPA）：獲得用戶授權(quán)的半可信代理，代替用戶執(zhí)行遠(yuǎn)程服務(wù)器上數(shù)據(jù)完整性驗(yàn)證的任務(wù)，并將驗(yàn)證結(jié)果返回給相應(yīng)用戶。

云存儲(chǔ)服務(wù)器（CS）：由不同的云服務(wù)商CSP提供的服務(wù)器資源，具有強(qiáng)大的存儲(chǔ)空間和計(jì)算能力，可以存儲(chǔ)用戶的數(shù)據(jù)信息并在收到挑戰(zhàn)時(shí)計(jì)算擁有數(shù)據(jù)的證明。

服務(wù)器組織者（Organizer）：服務(wù)器CS和校驗(yàn)者TPA之間起連接作用的服務(wù)器，接受TPA的審計(jì)挑戰(zhàn)并為被挑戰(zhàn)的服務(wù)器分發(fā)挑戰(zhàn)，聚合服務(wù)器返回的多個(gè)用戶的數(shù)據(jù)塊及標(biāo)簽證明，然后計(jì)算并返回最終回應(yīng)給TPA。

秘鑰生成器（KGC）：根據(jù)用戶的身份計(jì)算用戶私鑰，然后通過一個(gè)安全的通道返回給相應(yīng)用戶。

2.2 安全模型

根據(jù)文獻(xiàn)[11]中定義，方案IDB-RDIC的合理性和完美隱私性的模型定義如下。

定義1合理性（即針對(duì)服務(wù)器的安全性）。

（1）Setup：挑戰(zhàn)者運(yùn)行Setup算法，得到公開參數(shù)param和主私鑰msk，將 param發(fā)送給敵手，私密保存msk。

（2）Queries：敵手對(duì)挑戰(zhàn)者做一些提取Extract詢問和標(biāo)簽TagGen詢問。

①Extract Queries：敵手詢問用戶IDi的私鑰。挑戰(zhàn)者運(yùn)行算法Extract得到私鑰ski，將其發(fā)送給敵手。

②TagGen Queries：敵手對(duì)用戶IDi詢問文件Fi的數(shù)據(jù)標(biāo)簽，挑戰(zhàn)者查詢Extract并運(yùn)行算法TagGen，生成文件Fi的標(biāo)簽集合，將其發(fā)送給敵手。

（3）ProofGen：敵手對(duì)文件Fi進(jìn)行TagGen查詢，并以用戶身份IDi運(yùn)行算法ProofGen。挑戰(zhàn)者扮演TPA的角色，與敵手扮演的證明者角色進(jìn)行交互，最后敵手得到挑戰(zhàn)者的輸出P。

則稱敵手贏得了游戲。

定義2針對(duì)TPA的完美隱私性。

完美隱私是指TPA在和服務(wù)器交互過程時(shí)沒有得到用戶數(shù)據(jù)的任何信息。下面通過模擬器S來定義。假設(shè)存在一個(gè)多項(xiàng)式時(shí)間內(nèi)的非交互模擬器S，對(duì)于公開輸入IDi、chal、Tagi和非公開輸入Fi，以下兩個(gè)變量是計(jì)算上不可區(qū)分的：

則稱方案針對(duì)欺騙性TPA?具有完美隱私性。

3 IDB-RDIC方案

3.1 基礎(chǔ)知識(shí)

（1）雙線性映射：設(shè)G1、G2為階為q（q是大素?cái)?shù)）的乘法循環(huán)群，g為G1的生成元，則雙線性映射e:G1×G1→G2滿足：

①雙線性：對(duì)于?u,v∈G1和x,y∈Zq,有e(ux,vy)=e(u,v)xy；

②非退化性：e(g,g)≠1G2，其中1G2為群G2中的單位元；

③可計(jì)算性：對(duì)于?u,v∈G1，存在有效的算法計(jì)算e(u,v)。

（2）離散對(duì)數(shù)的相等性：設(shè)G為階為q（q是大素?cái)?shù)）的乘法循環(huán)群，g1、g2均為G的生成元，如果P向V證明群元素Y1、Y2在生成元g1、g2上有相同的離散對(duì)數(shù)x，那么交互證明如下：

②V隨機(jī)選擇c∈{0 ,1}λ發(fā)送給P；

③P計(jì)算z=ρ-cx( )mod q，并返回z給V；

3.2 回顧ID-RDIC方案

ID-RDIC方案[11]在單用戶單服務(wù)器環(huán)境下提出，方案的具體細(xì)節(jié)描述如下。

（1）Setup：輸入安全參數(shù)k，KGC選取兩個(gè)階為q的乘法循環(huán)群G1、G2，構(gòu)建一個(gè)雙線性映射e:G1×G1→G2。KGC隨機(jī)選取作為主私鑰，主公鑰設(shè)置為mpk=gα。KGC選擇三個(gè)不同的哈希函數(shù)H1,H2:{0,1}*→G1和 H3:G2→{0,1}l。輸出系統(tǒng)參數(shù)(G1,G2,e,g,mpk,H1,H2,H3,l,q)。

（2）Extract：輸入主私鑰α和用戶身份ID∈{0,1}*,輸出用戶私鑰。

（3）TagGen：用戶將文件名為 fname的文件分成n個(gè)數(shù)據(jù)塊，mi∈Zq,i=1,2,…,n；然后隨機(jī)選取計(jì)算r=gη，并對(duì)每個(gè)數(shù)據(jù)塊計(jì)算數(shù)據(jù)標(biāo)簽；最后將存放于服務(wù)器上。

（4）Challenge：校驗(yàn)者選取c個(gè)元素的子集合I?[1 ,n],并對(duì) ?i∈I,選取令挑戰(zhàn)集合校驗(yàn)者隨機(jī)選取計(jì)算，生成證明，將挑戰(zhàn)發(fā)送給服務(wù)器。

3.3 IDB-RDIC協(xié)議設(shè)計(jì)

本文構(gòu)造了一個(gè)在多用戶多服務(wù)器環(huán)境下支持批量校驗(yàn)用戶數(shù)據(jù)的IDB-RDIC協(xié)議，協(xié)議由參數(shù)初始化(Setup)、密鑰生成(Extract)、標(biāo)簽生成(TagGen)、挑戰(zhàn)(Challenge)、證明(Prove)和批校驗(yàn)(BatchVerify)六個(gè)算法組成，并對(duì)挑戰(zhàn)、證明和批校驗(yàn)算法進(jìn)行了改進(jìn)。其中，Challenge、Prove算法拆分為兩個(gè)分算法執(zhí)行，Challenge1、Challenge2及 Prove1、Prove2，BatchVerify算法用來實(shí)現(xiàn)對(duì)多個(gè)用戶數(shù)據(jù)的批處理校驗(yàn)。圖3為IDB-RDIC協(xié)議的數(shù)據(jù)傳輸圖，算法詳細(xì)步驟描述如下。

圖3 IDB-RDIC數(shù)據(jù)傳輸圖

（1）Setup(1k)→(params,msk)。算法輸入安全參數(shù)k，KGC選取兩個(gè)階為q的乘法循環(huán)群G1、G2，構(gòu)建雙線性映射e:G1×G1→G2。令G1的生成元為g，KGC隨機(jī)選取并設(shè)置主私鑰msk=α,主公鑰mpk=gα。KGC選擇三個(gè)不同的哈希函數(shù)H1:{0,1}*→G1，H2:{0,1}*→G1和 H3:G2→{0,1}l。輸出系統(tǒng)公開參數(shù)params=(l,q,G1,G2,e,H1,H2,H3,g,mpk),將msk私密保存。

（2）Extract(params,msk,IDi)→(ski)。算法輸入主私鑰msk和用戶身份IDi∈{0,1}*及系統(tǒng)參數(shù) params，輸出用戶私鑰ski=H1(IDi)α，并安全地傳送給相應(yīng)用戶。

DOi將文件塊的索引集合表N={(i,j,k)}發(fā)送給服務(wù)器組織者Organizer，索引表包含用戶索引i∈O，文件塊索引和存放DOi第k個(gè)塊的服務(wù)器索引。另外，DOi將值ri及其身份簽名IDS(ri)也發(fā)送給Organizer。

（4）Challenge(params,{i,k},N)→(chal,chalj)。挑 戰(zhàn)階段的算法分兩步執(zhí)行，具體如下：

①Challenge1(params,{i,k})→(chal)。校驗(yàn)者TPA隨機(jī)選取c個(gè)元素的子集合I?[ ]1,n，并對(duì)每個(gè)k∈I，選取系數(shù)，令挑戰(zhàn)集合為Q={( )}k,vk。TPA隨機(jī)選取并計(jì)算c2=Zρ,生成知識(shí)證明TPA令總挑戰(zhàn)為chal=(Q,c1,c2,pf),將chal發(fā)送給Organizer。

②Challenge2(chal,N)→(chalj)。Organizer驗(yàn)證知識(shí)證明的有效性，若有效，則根據(jù)存儲(chǔ)的索引表N為被挑戰(zhàn)服務(wù)器分發(fā)若干個(gè)分挑戰(zhàn)chalj={ |(i,j,k),{vk}i∈Oj,j∈U,k∈Ij}。其中，U表示被挑戰(zhàn)的服務(wù)器索引集合，Ij表示第 j個(gè)服務(wù)器上被挑戰(zhàn)的數(shù)據(jù)塊索引集合，Oj表示第 j個(gè)服務(wù)器上被挑戰(zhàn)的云用戶索引集合。

（5）Prove(p arams,{mijk},{σijk},{IDi},chalj) → (Pj,P )。證明階段也由兩部分算法構(gòu)成：

（6）BatchVerify( )params,{IDi},chal,P →1/0。TPA

4 IDB-RDIC安全分析

4.1 正確性證明

定理1如果服務(wù)器利用其上存儲(chǔ)的數(shù)據(jù)塊誠實(shí)地按照協(xié)議計(jì)算并返回相應(yīng)的證明，那么該證明就可以通過TPA的校驗(yàn)，使等式（1）成立。

證明

證畢。

4.2 合理性證明

根據(jù)文獻(xiàn)[11]，對(duì)方案IDB-RDIC的合理性證明如下。

定理2在一般性群模型和隨機(jī)諭言機(jī)模型下，IDBRDIC方案是可證明安全的。

一般性群Gi表示為是兩個(gè)獨(dú)立的隨機(jī)編碼函數(shù)，p為素?cái)?shù)。一般性算法是指沒有利用群結(jié)構(gòu)的算法，因此除了元素編碼值以外，得不到其他任何信息。隨機(jī)諭言機(jī)Oi,i∈{1 ,2}模擬群G1、G2的操作，輸入元素，輸出表示Oi上元素相乘的結(jié)果，輸出表示相除的結(jié)果。另一個(gè)諭言機(jī)OE模擬雙線性操作，輸入G1中元素和，輸出作為兩個(gè)元素雙線性運(yùn)算的結(jié)果。

證明基于以上背景，下面證明本文方案在隨機(jī)諭言機(jī)模型下針對(duì)一般性算法是可證明安全的。其中，敵手A扮演不可信云服務(wù)器的角色，且存在PPT模擬器S在與A進(jìn)行||

I次交互后可提取出挑戰(zhàn)的全部文件塊值。

（1）Settings：S運(yùn)行 Settings，得到公共參數(shù) (l,q,，并將元素 g 的編碼值 ξ1和一次的常量多項(xiàng)式對(duì)應(yīng)，將元素mpk的編碼值ξα與多元多項(xiàng)式α對(duì)應(yīng)。

（2）Hash-Queries：A對(duì)用戶IDi查詢諭言機(jī)H1，S返回一個(gè)隨機(jī)比特串ξIi，并與多項(xiàng)式Ii對(duì)應(yīng)；A對(duì)文件塊索引k查詢諭言機(jī)H2,S返回一個(gè)隨機(jī)比特串ξk，并與多項(xiàng)式k對(duì)應(yīng)；A查詢諭言機(jī)H3,S返回一個(gè)隨機(jī)比特串值。

（3）Oracle-O1：A 將元素 ξF1、ξF2和兩個(gè)整數(shù) e1、e2發(fā)送給S，詢問隨機(jī)諭言機(jī)O1的結(jié)果，S查找是否有與元素ξF1和ξF2對(duì)應(yīng)的多項(xiàng)式F1和F2存在。

①若不存在，S拒絕執(zhí)行。

②若存在，S計(jì)算多項(xiàng)式F3=e1F1+e2F2并查找歷史是否存在元素ξ∈G1，其對(duì)應(yīng)的多項(xiàng)式為F3。若存在返回ξF3給A；若不存在，S隨機(jī)選擇一個(gè)比特串ξF3與多項(xiàng)式F3對(duì)應(yīng)，然后將ξF3返回給A。

（4）Oracle-O2：與隨機(jī)諭言機(jī)O1的操作相同。

（5）Oracle-OE：A將元素 ξF1、ξF2發(fā)送給S，詢問隨機(jī)諭言機(jī)OE的結(jié)果，S查找是否有與元素ξF1和ξF2對(duì)應(yīng)的多項(xiàng)式F1和F2存在。

①若不存在，S拒絕執(zhí)行。

②若存在，S計(jì)算多項(xiàng)式F3=F1?F2并查找歷史是否存在元素ξ∈G2，其對(duì)應(yīng)的多項(xiàng)式為F3。若存在返回ξF3給A，否則，S隨機(jī)選擇一個(gè)比特串ξF3與多項(xiàng)式F3對(duì)應(yīng)并將ξF3返回給A。

（6）Extract Query：A將IDi發(fā)送給S，詢問該用戶私鑰。S首先進(jìn)行H1查詢，得到與多項(xiàng)式Ii對(duì)應(yīng)的元素ξIi，然后查找歷史是否存在元素ξαIi，其對(duì)應(yīng)的多項(xiàng)式為αIi。若存在，S發(fā)送ξαIi給A，否則，S隨機(jī)選擇一個(gè)比特串ξαIi與多項(xiàng)式αIi對(duì)應(yīng)，并將ξαIi返回給 A。

（7）TagGen Query：A將身份IDi和文件塊集合Mi=發(fā)送給S，詢問文件塊的數(shù)據(jù)標(biāo)簽。S對(duì)IDi進(jìn)行Extract查詢，得到與多項(xiàng)式αIi對(duì)應(yīng)的元素ξαIi，并對(duì)文件塊索引k進(jìn)行H2查詢，得到與多項(xiàng)式k對(duì)應(yīng)的元素ξk，然后S隨機(jī)選取比特串ξηi與多項(xiàng)式ηi對(duì)應(yīng)并計(jì)算Fi,k=αIimik+kηi。S查找是否存在與元素ξFi,k對(duì)應(yīng)的多項(xiàng)式Fi,k，若存在，S發(fā)送ξFi,k給A，作為文件塊mik的標(biāo)簽，否則，S隨機(jī)選擇一個(gè)比特串ξFi,k與多項(xiàng)式Fi,k對(duì)應(yīng)，并將ξFi,k返回給A。另外，S把元素ξηi和用戶IDi的身份簽名IDS()ri也返回給A。

（8）Challenge：A對(duì)用戶IDi*及其文件塊集合Mi*=發(fā)起挑戰(zhàn)，要求敵手A之前未對(duì)IDi*進(jìn)行過Extract查詢。S隨機(jī)選取挑戰(zhàn)集合并對(duì)所有k∈I隨機(jī)選取vk。S隨機(jī)選取比特串ξc1與多項(xiàng)式ρ對(duì)應(yīng)，選取隨機(jī)比特串ξZ與多項(xiàng)式αIi*對(duì)應(yīng)，選取隨機(jī)比特串 ξc2與多項(xiàng)式 αIi*ρ 對(duì)應(yīng)，將 ξc1、ξc2及知識(shí)證明 pf發(fā)送給A。

（9）GenProof：A返回值m′，群元素ri*和對(duì)其簽名IDS(ri*)作為回應(yīng)證明。

返回證明m′之前，A需要進(jìn)行一些群操作的詢問，在挑戰(zhàn)階段之前A會(huì)對(duì)群G1中元素進(jìn)行詢問，詢問元素對(duì)應(yīng)的多項(xiàng)式形式為：

敵手A知道上式中所有系數(shù)。

A對(duì)已知的群G1中元素和元素值ρ查詢隨機(jī)諭言機(jī)OE并返回證明m′，其對(duì)應(yīng)的多項(xiàng)式形式為：

此時(shí)，A和S已知多項(xiàng)式F中所有系數(shù)。將多項(xiàng)式F與等式（1）右邊元素對(duì)應(yīng)的多項(xiàng)式聯(lián)立，即：

4.3 完美隱私性證明

根據(jù)文獻(xiàn)[11]，對(duì)方案IDB-RDIC的隱私性證明如下。

定理3 IDB-RDIC方案針對(duì)校驗(yàn)者TPA具有完美隱私保護(hù)性。

證明構(gòu)造一個(gè)模擬器S回應(yīng)校驗(yàn)者V的挑戰(zhàn)。首先，因?yàn)閞i和 IDS()ri不包含文件塊的任何信息，所以可將{ri,IDS(ri)| i∈O} 發(fā)送給模擬器S。其次，S在收 到V發(fā) 送 的 挑 戰(zhàn)chal=(c1,c2,Q,pf )后 ，解 析 pf:并從中提取值ρ。根據(jù)值ρ計(jì)算回應(yīng)最后輸出回應(yīng)(m ′,ri,IDS(ri))i∈O給V。輸出的回應(yīng)與V和真實(shí)服務(wù)器交互得到的輸出具有不可區(qū)分性，因此方案針對(duì)TPA實(shí)現(xiàn)了完美隱私。證畢。

5 IDB-RDIC性能及實(shí)驗(yàn)分析

5.1 性能分析

本文提出多用戶多云存儲(chǔ)環(huán)境下支持批處理校驗(yàn)的IDB-RDIC方案，并與文獻(xiàn)[11]在多用戶多服務(wù)器環(huán)境下可拓展的方案（簡稱為ID-RDIC方案）進(jìn)行了性能對(duì)比分析，ID-RDIC的結(jié)構(gòu)模型圖如圖1所示。本文分別從存儲(chǔ)復(fù)雜度、計(jì)算復(fù)雜度和通信復(fù)雜度上進(jìn)行對(duì)比，并假設(shè)m個(gè)用戶被挑戰(zhàn)，每個(gè)用戶的文件塊總數(shù)為n，每個(gè)用戶被挑戰(zhàn)的文件塊數(shù)量為c。

（1）存儲(chǔ)復(fù)雜度的比較

用戶將自己的文件塊及數(shù)據(jù)標(biāo)簽存儲(chǔ)在云服務(wù)器CSj上，存儲(chǔ)形式為：

本文方案IDB-RDIC增加了服務(wù)器Orgniser來執(zhí)行分發(fā)挑戰(zhàn)和聚合證明的任務(wù)，因此增加的存儲(chǔ)內(nèi)容為索引集合表N=(i ,j,k)和用戶的身份簽名ri||IDS(ri)，存儲(chǔ)形式為：

考慮到橢圓曲線上的簽名一般包含兩個(gè)點(diǎn)，因此本文方案增加的存儲(chǔ)復(fù)雜度為

（2）通信復(fù)雜度的比較

本文從挑戰(zhàn)和證明兩個(gè)階段對(duì)比了本文方案IDBRDIC和ID-RDIC方案[11]的通信復(fù)雜度，如表1所示?，F(xiàn)將對(duì)比結(jié)果分析如下：

挑戰(zhàn)階段，IDB-RDIC由兩部分構(gòu)成。在Challenge1中，TPA發(fā)送總挑戰(zhàn)chal=( )c1,c2,Q,pf 給Organizer,其中c1、c2是兩個(gè)群Zq中元素包含c個(gè)整數(shù)和c個(gè)Zq中元素，pf中包括2個(gè)Zq中元素，主要考慮群上元素的通信開銷，Challenge1階段的通信開銷用比特串的長度表示為；在Challenge2中，Organizer將分挑戰(zhàn)發(fā)送給CSj，包含c個(gè)群Zq中的元素，其通信開銷為綜上，IDB-RDIC方案挑戰(zhàn)階段的通訊復(fù)雜度為O(c)。在ID-RDIC方案中，需要分別為m個(gè)用戶分發(fā)挑戰(zhàn)，因此ID-RDIC挑戰(zhàn)階段的通信開銷為，總體的通信復(fù)雜度為

證明階段，IDB-RDIC也由兩部分構(gòu)成。在Prove1中，CSj向Organizer返回有關(guān)m個(gè)挑戰(zhàn)用戶的證明，其中 μ′j,i、σ′j,i為 Zq中元素，故Prove1的通信開銷用比特串長度表示為在 Prove2中，Organizer向TPA返回證明 P={m′,{ri,，其中m′的比特串長度為l，簽名的長度為320 bit，ri的比特串長度用表示，Pr ove2的通信開銷為。綜上，IDB-RDIC證明階段的通訊復(fù)雜度為O(2 m )。在ID-RDIC方案中，服務(wù)器分別返回m個(gè)被挑戰(zhàn)用戶的證明所需的通信開銷為，故其通信復(fù)雜度為O(m)。

表1 通信復(fù)雜度的比較

表2 計(jì)算復(fù)雜度的比較

綜上所述，本文方案在證明階段的通信復(fù)雜度略有增加，但在挑戰(zhàn)階段復(fù)雜度明顯降低，因此IDB-RDIC擁有更低的通信復(fù)雜度。

（3）計(jì)算復(fù)雜度的比較

令P表示單個(gè)雙線性對(duì)運(yùn)算的開銷，H表示單個(gè)哈希函數(shù)運(yùn)算的開銷，EG1、EG2分別表示群G1、G2上單個(gè)指數(shù)運(yùn)算的開銷，MG1、MG2分別表示群G1、G2上單個(gè)乘法運(yùn)算的開銷，MZp表示整數(shù)群Zp上單個(gè)乘法運(yùn)算的開銷，AZp表示整數(shù)群Zp上單個(gè)加法運(yùn)算的開銷，對(duì)比分析本文方案IDB-RDIC與ID-RDIC方案[11]的計(jì)算復(fù)雜度，如表2所示。

從表2中可看出，本文方案在用戶端的計(jì)算復(fù)雜度上沒有變，這是因?yàn)橛脩舳说挠?jì)算復(fù)雜度和文件塊的數(shù)量成正比。但在TPA驗(yàn)證端和云服務(wù)器端上比ID-RDIC[11]方案擁有更低的計(jì)算復(fù)雜度。這是因?yàn)镮DB-RDIC方案支持批處理校驗(yàn)，使得TPA驗(yàn)證端減少了兩大主要計(jì)算開銷，包括(m-1)次P運(yùn)算及c(m-1)次EG1運(yùn)算。服務(wù)器端也減少了(m-1)次P運(yùn)算、EG1運(yùn)算、EG2運(yùn)算這些主要運(yùn)算開銷。

5.2 模擬實(shí)驗(yàn)

模擬實(shí)驗(yàn)使用的軟硬件配置如下：

PC硬件配置：Ubuntu 16.04 LTS 32位操作系統(tǒng)，4 GB內(nèi)存，Intel Core2Duo處理器。

軟件配置：Miracl庫、PBC庫、GMP庫。

實(shí)驗(yàn)設(shè)置10個(gè)用戶的文件分散存儲(chǔ)在10個(gè)服務(wù)器上，每個(gè)用戶文件大小為2 MB，總挑戰(zhàn)塊數(shù)3 000～4 600（相應(yīng)的每個(gè)服務(wù)器上挑戰(zhàn)300～460），步長200，模擬對(duì)比IDB-RDIC方案和ID-RDIC方案[11]在云服務(wù)器端的計(jì)算復(fù)雜度，如圖4所示。圖5設(shè)置總挑戰(zhàn)塊數(shù)1 000～5 000，步長500，模擬TPA驗(yàn)證端的計(jì)算復(fù)雜度對(duì)比。

從圖4和圖5可得，IDB-RDIC方案顯著降低了TPA端的計(jì)算復(fù)雜度，也降低了服務(wù)器端計(jì)算復(fù)雜度，實(shí)驗(yàn)結(jié)果與性能分析結(jié)果一致。特別地，當(dāng)云服務(wù)器損毀數(shù)據(jù)塊率為1%時(shí)，TPA挑戰(zhàn)其上460個(gè)數(shù)據(jù)塊，就能以99%的概率檢測出服務(wù)器的損毀數(shù)據(jù)行為[15]。因此當(dāng)總挑戰(zhàn)塊數(shù)為4 600時(shí)，IDB-RDIC方案的服務(wù)器計(jì)算證明時(shí)間開銷為11.7 s，檢測出10個(gè)服務(wù)器損毀數(shù)據(jù)行為的時(shí)間開銷為1.18 s。

圖4 云服務(wù)器端計(jì)算復(fù)雜度對(duì)比

圖5 TPA驗(yàn)證端計(jì)算復(fù)雜度對(duì)比

6 結(jié)束語

本文提出一個(gè)多用戶多服務(wù)器環(huán)境下支持批處理校驗(yàn)的數(shù)據(jù)完整性驗(yàn)證方案，可實(shí)現(xiàn)針對(duì)TPA的隱私保護(hù)，并保證了服務(wù)器的安全性，性能分析和實(shí)驗(yàn)也表明本文方案是高效可行的。