田苗苗，高闖，陳潔

（1. 安徽大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 合肥 230601；2. 華東師范大學(xué)計算機(jī)科學(xué)與軟件工程學(xué)院，上海 200062）

1 引言

云存儲是當(dāng)前應(yīng)用最廣泛的云計算服務(wù)之一。用戶通過云存儲服務(wù)將其數(shù)據(jù)外包給云服務(wù)器，之后可以在任何地方通過網(wǎng)絡(luò)訪問其外包數(shù)據(jù)，從而節(jié)省了本地存儲開銷，提高了使用數(shù)據(jù)的靈活性。隨著越來越多的用戶使用云存儲服務(wù)，云存儲安全風(fēng)險越加凸顯[1]，例如硬件故障、軟件錯誤、操作失誤、惡意破壞等都可能使云端數(shù)據(jù)出現(xiàn)損壞或缺失。由于一些商業(yè)原因，云存儲發(fā)生數(shù)據(jù)損壞后用戶通常不能及時獲悉，因此用戶必須主動檢查存儲在云服務(wù)器中數(shù)據(jù)的完整性。

由于云端外包數(shù)據(jù)的規(guī)模通常非常龐大，所以下載全部云端數(shù)據(jù)至本地進(jìn)行完整性檢測的方法是不切實際的。為此，研究人員提出了一些高效的云端數(shù)據(jù)完整性檢測方法，本文統(tǒng)稱為云存儲完整性檢測方案。云存儲完整性檢測方案通過交互式手段，無需下載全部數(shù)據(jù)即可驗證云端外包數(shù)據(jù)的完整性。具體地，用戶在上傳數(shù)據(jù)時會對數(shù)據(jù)進(jìn)行分塊處理并計算每塊的標(biāo)簽，然后將數(shù)據(jù)和標(biāo)簽一同上傳到云服務(wù)器。當(dāng)驗證云端數(shù)據(jù)的完整性時，驗證者將發(fā)送一個隨機(jī)挑戰(zhàn)給云服務(wù)器，根據(jù)塊標(biāo)簽的線性同態(tài)特性，云服務(wù)器能夠計算出對應(yīng)該挑戰(zhàn)的一個較短證明。最后，驗證者只需驗證該證明是否正確，即可判定云端外包數(shù)據(jù)是否完整。

首個高效的云存儲完整性檢測方案在 2007年由Ateniese等[2]和Juels等[3]分別提出，其中Ateniese等的方案支持公開驗證，即允許任意的第三方驗證者檢測數(shù)據(jù)的完整性，并支持無限次的挑戰(zhàn)詢問；而 Juels等的方案僅支持秘密驗證，即只允許數(shù)據(jù)所有者對數(shù)據(jù)完整性進(jìn)行檢測，并且僅支持有限次的挑戰(zhàn)詢問。此后，新的云存儲完整性檢測方案[4-7]被相繼提出，其中大多數(shù)方案都支持公開驗證和無限次挑戰(zhàn)詢問。然而這些公開驗證方案大都依賴公鑰基礎(chǔ)設(shè)施(PKI, public key infrastructure)，即需要使用數(shù)字證書來保證用戶公鑰和身份的對應(yīng)關(guān)系，所以存在復(fù)雜的證書管理問題。

為了消除證書管理問題，一些基于身份的云存儲完整性檢測方案[8-10]被相繼提出。在基于身份的密碼方案中，用戶的身份即為其公鑰，對應(yīng)的私鑰由私鑰生成中心(KGC，key generation center)生成[11]。上述方案的安全性都依賴于離散對數(shù)等傳統(tǒng)數(shù)學(xué)問題的困難性，而這些數(shù)學(xué)問題都難以抵抗量子計算機(jī)的攻擊[12]。由于格上困難問題具有安全性高、量子算法難以破解等優(yōu)勢[13]，使基于格的密碼方案受到研究人員的廣泛關(guān)注。

為了提高云存儲完整性檢測方案的安全性，近年來一些基于格問題的設(shè)計方案相繼涌現(xiàn)。2012年，Xu等[14]利用小整數(shù)解（SIS, small integer solution）問題[15]設(shè)計了首個基于格的云存儲完整性檢測方案。2014年，Liu等[16]設(shè)計了一種格上支持公開驗證的云存儲完整性檢測方案，但沒有給出嚴(yán)格的安全性證明。隨后，Zhang等[17]指出該方案存在安全漏洞，惡意云服務(wù)器可以欺騙驗證者通過完整性檢測。2017年，Liu等[18]在文獻(xiàn)[17]的基礎(chǔ)上提出了一種格上基于身份的云存儲完整性檢測方案，但是由于該方案的塊標(biāo)簽涉及云服務(wù)器的公鑰，云服務(wù)器可以利用其私鑰偽造數(shù)據(jù)，所以該方案實際上也不能抵抗惡意云服務(wù)器的攻擊。

本文提出了一種新的格上基于身份的云存儲完整性檢測方案，并在隨機(jī)預(yù)言模型下證明了該方案的安全性。與現(xiàn)有同類方案[18]相比，本文方案的系統(tǒng)參數(shù)和用戶私鑰都更短，計算效率也更高。本文的主要貢獻(xiàn)如下。

1) 新的標(biāo)簽生成算法。受文獻(xiàn)[19]的同態(tài)簽名算法啟發(fā)，本文設(shè)計了一種新的塊標(biāo)簽生成算法。令公鑰為和輔助向量文件標(biāo)識符為τ，則第i塊數(shù)據(jù)zi的標(biāo)簽xi是一個小向量，滿足其中是一個安全的散列函數(shù)。與文獻(xiàn)[19]每次僅處理1 bit數(shù)據(jù)相比，本算法允許計算較大的數(shù)據(jù)塊，因而能夠減少文件的塊標(biāo)簽總數(shù)，提高標(biāo)簽生成的效率。

2) 高效的私鑰提取算法?，F(xiàn)有同類方案的私鑰提取算法較為復(fù)雜，需要較大的計算和存儲開銷。本文根據(jù)文獻(xiàn)[20]提出的新陷門算法及相關(guān)算法，設(shè)計了一種高效的私鑰提取算法。對于身份為id的用戶Uid，令其中，a是私鑰生成中心的公鑰，(?)是一個安全的散列函數(shù)。利用文獻(xiàn)[20]中的相關(guān)算法，私鑰生成中心可以容易地為用戶Uid生成較小的Rid作為其私鑰，其中Rid滿足是一個公開向量。利用函數(shù)的高效求逆性和關(guān)系用戶Uid可以容易地計算任意文件塊的標(biāo)簽。

4) 嚴(yán)格的安全性證明。本文方案在隨機(jī)預(yù)言模型下對云服務(wù)器的適應(yīng)性選擇身份攻擊是安全的，其安全性可以規(guī)約到環(huán)上的小整數(shù)解問題[22-23]（Ring-SIS，ring small integer solution），該問題與理想格上最壞情況下的經(jīng)典問題一樣困難[22]。

2 預(yù)備知識

2.1 符號說明

本文的安全參數(shù)為n；實數(shù)域和整數(shù)域分別記為R和Z。向量默認(rèn)為行向量，用黑體小寫字母表示；向量a的轉(zhuǎn)置表示為aT。矩陣用黑體大寫字母表示。向量的歐幾里得范數(shù)為矩陣R的范數(shù)其中，riT為R的第i個列向量。矩陣R∈ Rm×w的最大奇異值，記為其中x為 Rw中的單位向量。矩陣R的Gram-Schmidt正交化記為矩陣的行連接記為矩陣的列連接記為[A,B]，即

2.2 格

定義 1 設(shè)B∈ Rm×m是由 一 組線性無 關(guān) 的向量所組成的矩陣，則由其生成的m維格定義為其中B被稱為格Λ的基。

對正整數(shù)m和q，矩陣定義如下格。

本文基于多項式環(huán)結(jié)構(gòu)的理想格[21]。多項式環(huán)可表示為其中，為n階分圓多項式，當(dāng)n為2的冪時，環(huán)R與是同構(gòu)的，環(huán)R中的每個元素都對應(yīng)于系數(shù)向量范數(shù)表示為相應(yīng)系數(shù)向量的范數(shù)。令整數(shù)q≥2，q模環(huán)表示為環(huán)中多項式的系數(shù)本文采用的多項式環(huán)為

2.3 離散高斯

離散高斯分布[15,24]是格密碼學(xué)中的一個重要概念，下面介紹離散高斯的定義和相關(guān)性質(zhì)。

定義2 令參數(shù)s＞0，中心c∈ Rm的連續(xù)高斯函數(shù)

其中，格Λ上的以s為參數(shù)，c為中心的離散高斯分布定義為其中，x∈Λ，

當(dāng)中心c=0時，將連續(xù)高斯分布和離散高斯分布分別簡寫為ρs(x)和DΛ,s(x)。

平滑參數(shù)[15]是格中另一個重要概念。以下引理給出了平滑參數(shù)大小的一個上界[25]。

引理1 設(shè)B∈ Rn×n是格Λ?Rn的任意一組基，實數(shù)ε＞0，則平滑參數(shù)ηε(Λ)滿足式(4)。

離散高斯分布有以下基本性質(zhì)[24]。

引理2 令格Λ?Rm，任意實數(shù)ε∈ ( 0 ,1)，向量c∈span(Λ)，如果高斯參數(shù)s≥ηε(Λ)，那么

從 Rm×k中按照離散高斯分布選擇的矩陣，其最大奇異值滿足以下條件[21]。

引理3 設(shè)實數(shù)s＞0，如果矩陣R←DRm×k,s，則以極大概率成立，其中隱含的常數(shù)因子約為

文獻(xiàn)[21]給出了以下的平滑引理。

引理 4 給定整數(shù)n≥4,q≥2和m≥實數(shù)和隨機(jī)向量如果統(tǒng)計接近于Rq上的均勻分布。

2.4 困難問題

本文方案的安全性基于Ring-SIS問題[22-23]，如定義3所示。

2.5 格陷門

格陷門是格密碼學(xué)的重要工具之一。傳統(tǒng)的格陷門是格的一組較短的基[25]。本節(jié)回顧文獻(xiàn)[20]提出的新格陷門的概念及相關(guān)算法。

文獻(xiàn)[20]提出了g-陷門的概念，如定義4所示。

文獻(xiàn)[20]給出了一種g-陷門生成算法。

根據(jù)引理 3可知，陷門R將以極大概率滿足

正式地，文獻(xiàn)[20]給出了原像采樣引理，如引理6所示。

利用上述采樣算法可得以下陷門委派算法[20]，如引理7所示。

為簡便起見，本文將標(biāo)簽h均設(shè)為1。

3 系統(tǒng)描述

3.1 系統(tǒng)模型

如圖1所示，基于身份的云存儲完整性檢測方案由4個實體組成，分別為用戶、私鑰生成中心、云服務(wù)器和審計者。用戶是數(shù)據(jù)所有者，通過云存儲服務(wù)將其數(shù)據(jù)外包給云服務(wù)器。私鑰生成中心根據(jù)用戶的身份為用戶分配私鑰。云服務(wù)器擁有巨大的存儲空間和計算資源，可以為用戶提供云存儲服務(wù)。審計者是一個專業(yè)實體，可以代表用戶對存儲在云服務(wù)器中的數(shù)據(jù)進(jìn)行完整性檢測，并及時將審計結(jié)果返回給用戶。

圖1 基于身份的云存儲完整性檢測方案模型

不失一般性，本文假定私鑰生成中心與用戶之間、用戶與云服務(wù)器之間，以及云服務(wù)器與審計者之間均有安全的傳輸通道。同時，假定每個用戶只有一個文件存儲在云端。

定義 5 基于身份的云存儲完整性檢測方案由6個概率多項式時間算法組成，分別為系統(tǒng)建立（setup）算法，私鑰提取（extract）算法、標(biāo)簽生成（taggen）算法、審計（audit）算法，證據(jù)生成（prove）算法和證據(jù)驗證（verify）算法。

setup算法：該算法輸入為安全參數(shù)n，輸出為系統(tǒng)公鑰mpk和主私鑰msk。

extract算法：該算法由私鑰生成中心執(zhí)行。輸入系統(tǒng)公鑰mpk，主私鑰msk和用戶的身份id，輸出對應(yīng)的用戶私鑰skid。

taggen算法：該算法由用戶執(zhí)行。輸入為系統(tǒng)公鑰mpk，用戶的私鑰skid和文件Fid，輸出為文件的標(biāo)識符τid，總塊數(shù)Lid和塊標(biāo)簽集合idΦ。最后，用戶將上傳到云服務(wù)器，將發(fā)送給審計者，然后刪除本地副本。

audit算法：該算法由審計者執(zhí)行。審計者根據(jù)用戶身份 id，文件的唯一標(biāo)識符τid和文件總塊數(shù)Lid，輸出為一個隨機(jī)挑戰(zhàn)chal。

prove算法：該算法由云服務(wù)器執(zhí)行。輸入挑戰(zhàn)chal，文件Fid及其塊標(biāo)簽集合Φid，輸出證據(jù)P。

verify算法：該算法由審計者執(zhí)行。輸入系統(tǒng)公鑰mpk，用戶的身份id，審計挑戰(zhàn)chal及對應(yīng)的證據(jù)P，輸出“0”或“1”。輸出“0”表示云服務(wù)器中的文件是不完整的，輸出“1”則表示文件是完整的。

顯然，對于一個正確的基于身份的云存儲完整性檢測方案來說，如果方案的所有參與方都誠實，那么算法verify應(yīng)該以極大概率輸出“1”。

3.2 安全模型

本文假設(shè)私鑰生成中心、用戶和審計者均是可信的，而云服務(wù)器是半可信的，即在數(shù)據(jù)已損壞的情況下，云服務(wù)器可能通過給出有效的證據(jù)來極力隱藏數(shù)據(jù)損壞的事實。根據(jù)文獻(xiàn)[4]的結(jié)論，本文僅需考慮方案的頑健性，它是指云服務(wù)器應(yīng)難以給出一個與誠實證據(jù)不同且能通過審計者檢查的證據(jù)。

本文考慮適應(yīng)性選擇身份攻擊下的頑健性，如定義6所述，其中挑戰(zhàn)者C模擬私鑰生成中心、用戶和審計者，而敵手A模擬云服務(wù)器。

定義6 如果不存在多項式時間的敵手A能夠以不可忽略的概率贏得以下游戲，則稱該基于身份的云存儲完整性檢測方案滿足適應(yīng)性選擇身份攻擊下的頑健性。游戲由4個階段組成，分別為建立階段、詢問階段、審計階段和偽造階段。

1) 建立階段。在該階段，挑戰(zhàn)者 C扮演私鑰生成中心的角色。挑戰(zhàn)者C執(zhí)行setup算法生成系統(tǒng)公鑰mpk和主私鑰msk，并將mpk發(fā)送給敵手A。

2) 詢問階段。在該階段，挑戰(zhàn)者 C扮演私鑰生成中心和用戶的角色。敵手A可以適應(yīng)性地向挑戰(zhàn)者C進(jìn)行提取詢問和標(biāo)簽詢問。

① 提取詢問。敵手A詢問身份id對應(yīng)的私鑰。挑戰(zhàn)者C執(zhí)行算法extract獲得私鑰skid，并將其發(fā)送給敵手A。

② 標(biāo)簽詢問。敵手A詢問身份為id的用戶Uid對文件Fid的標(biāo)簽。挑戰(zhàn)者C執(zhí)行算法taggen生成對應(yīng)的塊標(biāo)簽集合Φid，并將其發(fā)送給敵手A。

3) 審計階段。在該階段，挑戰(zhàn)者 C扮演審計者的角色。對于已經(jīng)執(zhí)行過標(biāo)簽詢問的文件，挑戰(zhàn)者C執(zhí)行audit算法生成一個隨機(jī)挑戰(zhàn)chal，并發(fā)送給敵手A。然后敵手A執(zhí)行prove算法生成相應(yīng)的證據(jù)P，并將其發(fā)送給挑戰(zhàn)者C。

4) 偽造階段。挑戰(zhàn)者C提交關(guān)于身份id*的挑戰(zhàn)詢問chal*敵手，敵手A輸出一個相應(yīng)的證據(jù)P*。如果P*與誠實的證據(jù)不同，A未對id*進(jìn)行過提取詢問且則敵手A 贏得游戲。

4 方案描述

4.1 具體構(gòu)造

本文提出的格上基于身份的云存儲完整性檢測方案如下。

1) 系統(tǒng)建立算法

setup：輸入安全參數(shù)n，選取整數(shù)q、p≥2，高斯參數(shù)，以及2個安全的散列函數(shù)執(zhí)行下列操作。

① 運(yùn)行算法GenTrap(1,σ) → (a,R)。

③ 輸出系統(tǒng)公鑰 m pk=(a,u)和主私鑰msk=R。

2) 私鑰提取算法

extract：輸入系統(tǒng)公鑰mpk、主私鑰msk和身份 id ∈ {0 ,1}*，執(zhí)行下列步驟。

① 計算hid=H1(id)。

③ 運(yùn)行算法 D elTrap(aid,R,s)→Rid。

④ 輸出用戶私鑰 s kid=Rid。

3) 標(biāo)簽生成算法

taggen：輸入系統(tǒng)公鑰 mpk、用戶私鑰skid和文件Fid，用戶執(zhí)行下列步驟。

② 將文件Fid分為Lid塊，其中每塊均屬于Rpd，即

③ 計算αi= H2(τid,i)，其中，i= 1 ,2,…,Lid。

④ 計算每塊的標(biāo)簽，其中第i塊zi的標(biāo)簽

⑤ 輸出標(biāo)簽集合Φid={x1,x2,… ,xLid}。

⑥ 將{i d ,τid,Lid}和{i d ,τid,Φid,Fid}分別發(fā)送給審計者和云服務(wù)器，然后刪除本地副本。

4) 審計算法

② 發(fā)送 c hal = (i d ,τid,{i,vi}i∈I)給云服務(wù)器。

5) 證據(jù)生成算法

prove：當(dāng)收到來自審計者的挑戰(zhàn)chal = (i d ,τid,{i,vi}i∈I)后，云服務(wù)器找到對應(yīng)的文件Fid及標(biāo)簽集合Φid，計算然后將證據(jù)P= (x,z)返回。

6) 證據(jù)驗證算法

verify：輸入系統(tǒng)公鑰mpk，隨機(jī)挑戰(zhàn)chal和證據(jù)P，審計者執(zhí)行下列步驟。

① 解析 c hal=(i d ,τid,{i,vi}i∈I)和P=(x,z)。

④ 計算B= ? (p- 1 )2+1。

⑤ 判斷下列條件是否均成立。

若是，則返回“1”；否則，返回“0”。

4.2 參數(shù)設(shè)置

本文的安全參數(shù)n設(shè)為2的冪次。根據(jù)引理1，設(shè)函數(shù)

根據(jù)引理 5，GenTrap算法的高斯參數(shù)設(shè)為，則系統(tǒng)公鑰統(tǒng)計接近于上的均勻分布，主私鑰因此根據(jù)引理以極大概率成立，其中隱含的常數(shù)因子約為

5 方案分析

5.1 正確性

定理 2 如果本文方案中的用戶、私鑰生成中心、云服務(wù)器和審計者都是誠實的，那么verify算法將以極大概率輸出“1”。

證明 給定用戶的身份id和文件Fid，令文件標(biāo)識符為τid。對第i個數(shù)據(jù)塊zi，計算執(zhí)行算法根據(jù)引理2及引理6，標(biāo)簽xi將以極大概率滿足

因此，verify算法中的條件b)也成立。

5.2 頑健性

定理3 如果Ring-SIS問題是困難的，那么在隨機(jī)預(yù)言模型下任何多項式時間的敵手都不能以不可忽略的概率破解本文方案的頑健性。

證明 根據(jù)定義 6，假設(shè)存在一個多項式時間的敵手A能夠以不可忽略的概率ε破解本文方案的頑健性，則下面證明，存在一個多項式時間的算法B，能以不低于的概率破解Ring-SIS問題，其中，QH是H1詢問的最大次數(shù)，QE是提取詢問的最大次數(shù)。具體過程如下。

1) 建立階段。給定安全參數(shù)n，令?≥1為單次審計挑戰(zhàn)選擇的元素總個數(shù)，算法B選擇隨機(jī)整數(shù)公開向量高斯參數(shù)以及2個作為隨機(jī)預(yù)言機(jī)的散列函數(shù)輸入隨機(jī)向量作為Ring-SIS實例，令實數(shù)則算法B試圖尋找一個非零向量使得且算法B最后將系統(tǒng)公鑰發(fā)送給敵手A。

2） 詢問階段。敵手A可以適應(yīng)性地向算法B進(jìn)行一系列詢問，包括散列詢問、提取詢問和標(biāo)簽詢問。在這個階段，算法B將建立并維持多個表，其中表L1用于記錄H1詢問，表L2用于記錄H2詢問，表Lt用于記錄標(biāo)簽詢問。

①H1詢問。敵手A可以適應(yīng)性地對身份進(jìn)行H1詢問。不失一般性，假設(shè)H1詢問在其他類型詢問之前且敵手每次提交H1詢問的身份都不同。算法C隨機(jī)選取j∈ { 1 , …,QH}。對敵手A的第i次H1詢問，如果i=j，則算法B將(id,b,⊥)存于表L1中，并將b返回給敵手A。如果i≠j，則算法B按照分布選取k個隨機(jī)的列向量構(gòu)成計算若hid已在表L1中，則重新選取Rid。最后，算法B將存于表L1中，并將hid返回給敵手 A。根據(jù)引理4，hid統(tǒng)計接近于均勻分布。

② 提取詢問。敵手A 向算法B適應(yīng)性地進(jìn)行提取詢問，以獲取身份id對應(yīng)的私鑰。此時，算法B檢索表L1找到匹配項。若匹配項為(i d ,hid,Rid)，則返回Rid；若匹配項為(id,b,⊥)，則終止。

③ H2詢問。算法B建立并維護(hù)一個表L2用于響應(yīng)敵手A的H2詢問。一般地，對敵手A的一個H2詢問，算法B首先查找表L2，如果找到匹配項則直接將結(jié)果返回，否則選擇一個隨機(jī)的α∈Rq并返回。如果A的H2詢問形如(τid,i)，則算法B將以一種特殊方式進(jìn)行響應(yīng)，具體過程見標(biāo)簽詢問。

④ 標(biāo)簽詢問。敵手A適應(yīng)性地進(jìn)行標(biāo)簽詢問，以獲得身份為id的用戶Uid關(guān)于文件Fid的標(biāo)簽。此時，算法B首先查找表Lt，如果找到匹配項(i d ,τid,Φid,Fid)，則直接將其返回給敵手A。否則算法B執(zhí)行下列步驟：首先選取隨機(jī)的作為文件Fid的標(biāo)識符，并將文件Fid拆分為Lid塊其中，每塊然后計算標(biāo)簽集合其中，xi∈Rm是數(shù)據(jù)塊zi的標(biāo)簽；最后將(i d ,τid,Φid,Fid)存于表Lt中，并將其返回給敵手A。為了計算每個塊標(biāo)簽，算法B按照離散高斯分布Dm隨機(jī)選取xi，計算存于表L2中，并令H2(τid,i) =αi。根據(jù)引理4，αi統(tǒng)計接近于均勻分布。

3) 審計階段。算法B可以對已執(zhí)行過標(biāo)簽詢問的文件進(jìn)行審計詢問。假設(shè)算法B希望檢測外包文件Fid的完整性。輸入文件所有者的身份id，標(biāo)識符τid，總塊數(shù)Lid，算法B執(zhí)行算法 audit( id,τid,Lid)，生成挑戰(zhàn) c hal = (i d ,τid,{i,vi}i∈I)并將其發(fā)送給敵手A。敵手A收到挑戰(zhàn)后，找到匹配的Fid和Φid，執(zhí)行算法 p ro v e( chal,Fid,Φid)，生成相應(yīng)的證據(jù)并返回。

4) 偽造階段。敵手 A 以概率ε輸出對應(yīng)挑戰(zhàn)的一個與誠實證據(jù)不同的有效證據(jù)P?= (x?,z?)。

如果身份 id*不滿足H1(id?)=b，則終止。否則，算法B查詢表Lt，找到匹配項假設(shè)第i塊數(shù)據(jù)為zi，相應(yīng)的標(biāo)簽為xi，則由上述構(gòu)造過程和引理 2可知，且以極大概率成立，其中算法B輸出誠實證據(jù)P= (x,z)，其中

由 于 證 據(jù)P?= (x?,z?)也 滿 足 驗 證 條 件 ， 即

式(12)與式(11)相減，可得

式(13)等價于

由于以上兩證據(jù)是不同的，所以y≠0。

又由于z和z*均屬于 R因此

即算法B破解了Ring-SIS問題。

現(xiàn)在計算算法B成功的概率。

算法B成功意味著身份 id*在私鑰提取階段未被詢問且H1(id?)=b。由于身份 id*在私鑰提取階段未被詢問的概率不低于而身份 id*滿足H1(id*)=b的概率不低于所以算法B成功的概率不低于證畢。

6 性能評估

將本文方案分別與文獻(xiàn)[18]和文獻(xiàn)[9]中的方案進(jìn)行實驗比較來進(jìn)行性能評估，其中，文獻(xiàn)[18]中的IBRDICL(identity based remote data integrity checking from lattices)方案是基于格的同類方案，而文獻(xiàn)[9]中的 IBPDP(identity based provable data possession)方案是基于傳統(tǒng) CDH(computational Diffie-Hellman)假設(shè)的方案。這 3種方案的主要特征如表1所示。

表1 3種云存儲完整性檢測方案的特征比較

性能評估包括方案的存儲開銷，通信開銷和計算開銷3個方面。實驗代碼用C++ 11編寫，通過g++ 5.4.0編譯。實驗由配置了Intel Core i5-4590處理器，8 GB內(nèi)存和Ubuntu 16.04 LTS操作系統(tǒng)的PC機(jī)運(yùn)行。所有實驗結(jié)果均是10次實驗的平均值。

本文方案的實現(xiàn)使用了 NFLlib函數(shù)庫[26]，該函數(shù)庫提供了多項式環(huán)上任意操作的快速實現(xiàn)；SampleD算法利用了文獻(xiàn)[27]任意模下格Λ⊥(g)的采樣算法，該算法將文獻(xiàn)[20]任意模下格Λ⊥(g)采樣算法的計算開銷從O(nl og2q)降低到O(nl ogq)；散列函數(shù)使用SHA-256實現(xiàn)，并通過偽隨機(jī)數(shù)生成器生成隨機(jī)數(shù)進(jìn)行填充。

根據(jù)Ateniese等[2]的結(jié)論，當(dāng)文件的塊損壞比例為1%時，如果挑戰(zhàn)請求包含的元素個數(shù)?=460，則審計者能以不低于 99%的概率檢測出損壞。因此，本節(jié)所有算法均選擇?=460。

6.1 對比同類方案

首先將本文方案與 IBRDICL方案進(jìn)行對比。IBRDICL方案是一種一般格上基于身份的云存儲完整性檢測方案，該方案所采用的私鑰提取算法和原像采樣算法效率都較低，實驗中將使用與本文方案相同的算法代替；此外，由于本文方案未涉及保護(hù)隱私，因此實驗移除了 IBRDICL方案中隱私保護(hù)所需的計算，主要包括證據(jù)生成階段的一次原像采樣運(yùn)算和證據(jù)驗證階段的一次散列運(yùn)算。

本實驗中，2種方案的安全參數(shù)n均設(shè)為128，其他相關(guān)參數(shù)如表2所示。特別地，IBRDICL方案中塊標(biāo)簽向量的元素個數(shù)為nm，單個數(shù)據(jù)塊的元素個數(shù)為nd，因此2種方案每個數(shù)據(jù)塊的大小均為2 KB。根據(jù)文獻(xiàn)[28]可知，2種方案在此參數(shù)下具有相近的安全級別。

表2 實驗參數(shù)設(shè)置（n=128時）

1) 存儲開銷

存儲開銷主要比較系統(tǒng)公鑰長度、用戶私鑰長度和塊標(biāo)簽長度。具體的存儲開銷比較如表3所示。

表3 與IBRDICL方案的存儲開銷比較

由表3可知，IBRDICL方案的系統(tǒng)公鑰長度和用戶私鑰長度都遠(yuǎn)大于本文方案，而塊標(biāo)簽長度比本文方案略小。因此，本文方案的用戶存儲開銷和審計者存儲開銷都更低，云服務(wù)器的存儲開銷稍高。

2) 通信開銷

通信開銷主要比較挑戰(zhàn)長度和證據(jù)長度，具體的通信開銷比較如表4所示。

表4 與IBRDICL方案的通信開銷比較

由表4可知，本文方案與IBRDICL方案的通信開銷相近，僅在證據(jù)長度上略大。

3) 計算開銷

計算開銷包括各算法的運(yùn)算時間，其中標(biāo)簽生成算法分為離線階段和在線階段，離線階段不依賴于數(shù)據(jù)，僅計算SampleD算法所需的擾動向量p及apT，因此可以預(yù)先執(zhí)行并將結(jié)果保存在本地。標(biāo)簽生成算法的計算開銷比較如圖2所示，其他算法的具體計算開銷如表5所示。

圖2中，文件數(shù)據(jù)塊總數(shù)的范圍是1 000～10 000塊，每個數(shù)據(jù)塊的大小為2 KB。由圖2可知，2種方案離線階段所需的計算開銷都大于在線階段的計算開銷；相比較而言，本文方案離線階段的計算開銷與 IBRDICL方案比略低；但本文方案在線階段的計算效率比 IBRDICL方案提高了約93.74%。

表5 與IBRDICL方案的計算開銷對比

根據(jù)表5，本文方案的系統(tǒng)建立算法和私鑰提取算法的計算開銷與IBRDICL方案相比都更小。雖然與IBRDICL方案相比，本文方案證據(jù)生成算法的計算效率較低，但證據(jù)驗證算法的計算效率提高了98.81%且總的絕對數(shù)值遠(yuǎn)小于IBRDICL方案。因此，本文方案降低了私鑰生成中心、用戶和審計者的計算開銷。

圖2 與IBRDICL方案標(biāo)簽生成算法計算開銷對比

綜上，相對于 IBRDICL方案中的方案，本文方案降低了用戶的存儲開銷，提高了系統(tǒng)建立、私鑰提取、標(biāo)簽生成和證據(jù)驗證等算法的計算效率，并且數(shù)據(jù)審計過程的總體計算開銷也更低。

6.2 對比傳統(tǒng)方案

將本文方案與 IBPDP方案進(jìn)行對比。IBPDP方案是利用雙線映射構(gòu)造的一種基于身份的云存儲完整性檢測方案。本實驗使用 PBC庫（版本為0.5.14）實現(xiàn)IBPDP方案，其中實驗參數(shù)選自PBC庫的參數(shù)文件a.param（安全級別約為80 bit），扇區(qū)數(shù)設(shè)為205個（單個數(shù)據(jù)塊長度約為4 KB）。為了達(dá)到相近的安全級別和數(shù)據(jù)塊大小，根據(jù)文獻(xiàn)[28]，本文方案的安全參數(shù)n設(shè)為512，其他相關(guān)參數(shù)如表6所示。

表6 實驗參數(shù)設(shè)置（n=512時）

1) 存儲開銷

存儲開銷仍然比較系統(tǒng)公鑰長度，用戶私鑰長度和塊標(biāo)簽長度。具體的存儲開銷比較如表7所示。

表7 與IBPDP方案的存儲開銷比較

由表7可知，IBPDP方案的存儲開銷與本文方案相比都更小。

2) 通信開銷

通信開銷也主要比較挑戰(zhàn)長度和證據(jù)長度。具體的通信開銷比較如表8所示。

表8 與IBPDP方案的通信開銷比較

由表8可知，本文方案與IBPDP方案相比，僅挑戰(zhàn)長度較小，總通信開銷仍然較大。

3) 計算開銷

本文方案與 IBPDP方案在不同數(shù)據(jù)塊情況下標(biāo)簽生成算法的計算開銷如圖3所示，其他算法的計算開銷比較如表9所示。

表9 與IBPDP方案的計算開銷對比

圖3 與IBPDP方案的標(biāo)簽生成算法計算開銷對比

由于本文方案的標(biāo)簽生成算法分離線和在線兩階段，且離線階段與數(shù)據(jù)無關(guān)，所以圖3僅列出本文方案標(biāo)簽生成算法在線階段的計算開銷，并通過隨機(jī)替換方法生成擾動向量p。

由圖3可知，相比于IBPDP方案中，本文方案標(biāo)簽生成算法在線階段的計算效率提高了約88.32%。由表9可知，本文方案的系統(tǒng)建立算法和私鑰提取算法的計算開銷相對較大，但審計算法、證據(jù)生成和驗證算法的計算效率與 IBPDP方案相比分別提高了99.98%、76.56%和99.73%。由于這些算法執(zhí)行較為頻繁，因此本文方案大大降低了用戶、云服務(wù)器和審計者的計算開銷。

綜上，相比于IBPDP方案，本文方案提高了用戶、云服務(wù)器和審計者的計算效率。

7 結(jié)束語

本文基于理想格上的困難問題構(gòu)造了一種基于身份的云存儲完整性檢測方案。在隨機(jī)預(yù)言模型下該方案可以抵抗云服務(wù)器的適應(yīng)性選擇身份攻擊。實驗結(jié)果表明：與同類方案相比，本文方案整體更優(yōu)，更適合實際應(yīng)用；與傳統(tǒng)方案相比，本文方案數(shù)據(jù)審計過程的計算開銷也更低。