多云存儲中保護隱私的數據完整性驗證方案

任孟琦，龐曉瓊，王田琪，聶夢飛

中北大學 大數據學院，太原 030051

1 引言

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

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

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

針對上述問題，本文提出一種在多用戶多服務器環境下支持批處理校驗，同時保護用戶數據隱私且針對服務器安全的數據完整性驗證方案IDB-RDIC。

本文的創新點：所提方案對多用戶多服務器環境下的數據支持高效的批處理校驗，與可在多用戶多服務器環境下簡單拓展的方案[11]相比，降低了TPA和服務器端的通信開銷與計算開銷。同時本文方案還實現了針對TPA的隱私保護，并對服務器的安全性進行了證明。

2 IDB-RDIC結構模型和安全模型

2.1 結構模型

單用戶單服務器環境下的數據完整性驗證方案[11]可以簡單地在多用戶多服務器環境下拓展，拓展之后的結構模型圖如圖1所示。模型由四類實體構成，當多個用戶向第三方TPA發送審計請求任務時，TPA只能為每位用戶逐一校驗其數據的完整性，由此帶來極大的通信與計算開銷。

圖1 簡單的多用戶多云存儲模型圖

為了提高效率，本文方案支持對存儲在多個云服務器上的多用戶進行批處理校驗，所采用的結構模型圖如圖2所示。模型由五類實體構成，具體闡述如下。

圖2 IDB-RDIC結構模型圖

用戶：需要在不同的服務器上存儲數據的多個用戶，用戶可以和云存儲服務器通信來傳輸數據。

第三方審計（即校驗者TPA）：獲得用戶授權的半可信代理，代替用戶執行遠程服務器上數據完整性驗證的任務，并將驗證結果返回給相應用戶。

云存儲服務器（CS）：由不同的云服務商CSP提供的服務器資源，具有強大的存儲空間和計算能力，可以存儲用戶的數據信息并在收到挑戰時計算擁有數據的證明。

服務器組織者（Organizer）：服務器CS和校驗者TPA之間起連接作用的服務器，接受TPA的審計挑戰并為被挑戰的服務器分發挑戰，聚合服務器返回的多個用戶的數據塊及標簽證明，然后計算并返回最終回應給TPA。

秘鑰生成器（KGC）：根據用戶的身份計算用戶私鑰，然后通過一個安全的通道返回給相應用戶。

2.2 安全模型

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

定義1合理性（即針對服務器的安全性）。

（1）Setup：挑戰者運行Setup算法，得到公開參數param和主私鑰msk，將 param發送給敵手，私密保存msk。

（2）Queries：敵手對挑戰者做一些提取Extract詢問和標簽TagGen詢問。

①Extract Queries：敵手詢問用戶IDi的私鑰。挑戰者運行算法Extract得到私鑰ski，將其發送給敵手。

②TagGen Queries：敵手對用戶IDi詢問文件Fi的數據標簽，挑戰者查詢Extract并運行算法TagGen，生成文件Fi的標簽集合，將其發送給敵手。

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

則稱敵手贏得了游戲。

定義2針對TPA的完美隱私性。

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

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

3 IDB-RDIC方案

3.1 基礎知識

（1）雙線性映射：設G1、G2為階為q（q是大素數）的乘法循環群，g為G1的生成元，則雙線性映射e:G1×G1→G2滿足：

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

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

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

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

②V隨機選擇c∈{0 ,1}λ發送給P；

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

3.2 回顧ID-RDIC方案

ID-RDIC方案[11]在單用戶單服務器環境下提出，方案的具體細節描述如下。

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

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

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

（4）Challenge：校驗者選取c個元素的子集合I?[1 ,n],并對 ?i∈I,選取令挑戰集合校驗者隨機選取計算，生成證明，將挑戰發送給服務器。

3.3 IDB-RDIC協議設計

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

圖3 IDB-RDIC數據傳輸圖

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

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

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

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

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

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

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

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

4 IDB-RDIC安全分析

4.1 正確性證明

定理1如果服務器利用其上存儲的數據塊誠實地按照協議計算并返回相應的證明，那么該證明就可以通過TPA的校驗，使等式（1）成立。

證明

證畢。

4.2 合理性證明

根據文獻[11]，對方案IDB-RDIC的合理性證明如下。

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

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

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

I次交互后可提取出挑戰的全部文件塊值。

（1）Settings：S運行 Settings，得到公共參數 (l,q,，并將元素 g 的編碼值 ξ1和一次的常量多項式對應，將元素mpk的編碼值ξα與多元多項式α對應。

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

（3）Oracle-O1：A 將元素 ξF1、ξF2和兩個整數 e1、e2發送給S，詢問隨機諭言機O1的結果，S查找是否有與元素ξF1和ξF2對應的多項式F1和F2存在。

①若不存在，S拒絕執行。

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

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

（5）Oracle-OE：A將元素 ξF1、ξF2發送給S，詢問隨機諭言機OE的結果，S查找是否有與元素ξF1和ξF2對應的多項式F1和F2存在。

①若不存在，S拒絕執行。

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

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

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

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

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

返回證明m′之前，A需要進行一些群操作的詢問，在挑戰階段之前A會對群G1中元素進行詢問，詢問元素對應的多項式形式為：

敵手A知道上式中所有系數。

A對已知的群G1中元素和元素值ρ查詢隨機諭言機OE并返回證明m′，其對應的多項式形式為：

此時，A和S已知多項式F中所有系數。將多項式F與等式（1）右邊元素對應的多項式聯立，即：

4.3 完美隱私性證明

根據文獻[11]，對方案IDB-RDIC的隱私性證明如下。

定理3 IDB-RDIC方案針對校驗者TPA具有完美隱私保護性。

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

5 IDB-RDIC性能及實驗分析

5.1 性能分析

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

（1）存儲復雜度的比較

用戶將自己的文件塊及數據標簽存儲在云服務器CSj上，存儲形式為：

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

考慮到橢圓曲線上的簽名一般包含兩個點，因此本文方案增加的存儲復雜度為

（2）通信復雜度的比較

本文從挑戰和證明兩個階段對比了本文方案IDBRDIC和ID-RDIC方案[11]的通信復雜度，如表1所示。現將對比結果分析如下：

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

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

表1 通信復雜度的比較

表2 計算復雜度的比較

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

（3）計算復雜度的比較

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

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

5.2 模擬實驗

模擬實驗使用的軟硬件配置如下：

PC硬件配置：Ubuntu 16.04 LTS 32位操作系統，4 GB內存，Intel Core2Duo處理器。

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

實驗設置10個用戶的文件分散存儲在10個服務器上，每個用戶文件大小為2 MB，總挑戰塊數3 000～4 600（相應的每個服務器上挑戰300～460），步長200，模擬對比IDB-RDIC方案和ID-RDIC方案[11]在云服務器端的計算復雜度，如圖4所示。圖5設置總挑戰塊數1 000～5 000，步長500，模擬TPA驗證端的計算復雜度對比。

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

圖4 云服務器端計算復雜度對比

圖5 TPA驗證端計算復雜度對比

6 結束語

本文提出一個多用戶多服務器環境下支持批處理校驗的數據完整性驗證方案，可實現針對TPA的隱私保護，并保證了服務器的安全性，性能分析和實驗也表明本文方案是高效可行的。