抗密鑰泄露的支持密態數據去重的完整性審計方案

張襄松，李晨，劉振華

（1. 西安工業大學理學院，陜西 西安 710021；2. 西安電子科技大學數學與統計學院，陜西 西安 710071）

1 引言

云平臺具有強大的計算能力和存儲能力，個人或企業可以將各種復雜的任務外包給云平臺進行處理[1]，而不再需要花費高昂的代價購置和維護軟硬件。例如大數據云存儲服務，用戶將數據上傳給云存儲服務提供商（CSP, cloud service provider）存儲管理，這大大減輕了用戶的存儲負擔，方便用戶隨時隨地訪問云端數據[2]。但是，由于用戶失去對云端數據的絕對控制權，不可避免地帶來了一系列數據安全問題[3]，如數據完整性、重復性、密鑰泄露等。

為了自身經濟利益，CSP可能故意刪除用戶的一部分數據。即使 CSP能夠誠實地存儲用戶的數據，也不可避免地存在因軟硬件故障而導致的數據損壞。當上述問題發生時，CSP可能瞞報，聲稱數據仍完整正確地存儲在云服務器上，因此，需要定期地對云端數據完整性進行審計檢查。如果需要將數據下載到本地再進行驗證，這顯然是低效的，甚至在數據量較大時是不可行的。為此，Ateniese等[4]結合隨機采樣技術和隨機化數字簽名中的同態認證標簽，提出了數據持有性證明（PDP, provable data possession）概念——在不進行數據取回的前提下,云服務器向用戶證明云端存儲數據的完整性。進而，Juels等[5]采用檢查點和糾錯碼的方法，提出了數據可恢復性證明（PoR, proof of retrievability）概念，不僅可以進行完整性審計，而且還能實現損壞數據的恢復。

相同的數據文件可能被不同用戶上傳到云服務器進行存儲，產生多個文件副本，這不僅占用了云存儲服務商的存儲空間，也浪費了用戶的帶寬資源，因此需要解決數據重復存儲的問題。通過數據去重來消除冗余的數據，相同文件只保存一個副本，可以大大減少用戶上傳帶寬及服務器存儲空間。熊金波等[6]綜述了數據去重的研究進展。

在云存儲環境中同時實現數據的完整性驗證和去重功能[7-10]是十分有意義的，但是機械地將去重功能和完整性驗證組合起來不可避免地會導致上傳者的身份混淆，以及由此產生的數據安全問題。這是因為后續用戶上傳一個服務器中已有的文件時，在生成的標簽中含有用戶的身份，這會導致標簽與服務器中相應的文件之前的標簽不一致，使云服務器存儲了許多額外的數據，并且與完整性驗證工作造成沖突。為此，Yuan等[11]提出了一種支持數據去重的公開審計方案，將用戶端的計算和傳輸開銷減小至常數級，且支持批量審計，但是該方案的數據去重僅限于文件級，不夠靈活。隨后，Li等[12]設計了支持數據審計和安全去重的SecCloud方案，利用MapReduce云代替第三方審計者（TPA, third party auditor）完成數據的完整性審計，但是將數據直接發送給MapReduce云破壞了用戶身份的隱私性，且該方案不能降低用戶的帶寬消耗。為了解決帶寬問題，Kiraz[13]提出了一種支持公開審計的安全客戶端去重方案，該方案具有隱私保護性質，但是在上傳數據過程中，用戶完成所有權證明（PoW, proof of ownership）挑戰的計算量較大，效率較低。此外，Kiraz所提方案中的密鑰服務器可能會根據用戶發送的消息恢復出數據的部分加密密鑰。

另外，由于用戶安全意識薄弱或疏于管理的原因，在完整性審計過程中用戶的私鑰可能會丟失或遭到竊取。一旦惡意云得到了用戶的私鑰就能通過偽造認證標簽來隱藏數據丟失，甚至為了節省存儲空間刪除用戶不常訪問的數據而不被察覺。在傳統的完整性驗證方案中，如果用戶私鑰遭到泄露，則需要用戶下載其上傳的所有數據，更換新的公私鑰對后重新上傳，顯然這種方法效率極低，甚至是不可行的。因此，設計一種高效的抗密鑰泄露的完整性審計方案也是十分必要的。Yu等[14]基于二叉樹結構構造了一個密鑰更新算法，該算法保證了密鑰泄露之前的時間周期內認證標簽的安全性，即事前泄露。但從密鑰泄露之后到發現泄露之前，該方案無法保證之后認證標簽的安全性，這是由于在實際情況中密鑰泄露通常只能在用戶發現認證標簽不是自己生成的時候被察覺，因此 Yu所提方案的實用性較差。為了解決 Yu所提方案中的事前泄露問題，Yu等[15]又提出了強抗密鑰泄露的云存儲審計方案，使惡意的云不能通過已泄露時間周期的簽名私鑰獲得其他時間周期用戶的簽名私鑰，從而保護了除密鑰泄露發生的時間周期外任意時間周期審計方案的安全性。

雖然現有數據完整性驗證方案中已經實現了抗密鑰泄露或數據去重功能，但目前尚沒有同時支持這兩項功能的數據完整性驗證方案。如果只是單純地再支持去重的審計方案中加入密鑰更新，則可能會導致在不同時間周期由于用戶私鑰不同而無法成功去重。為解決這一問題，本文提出了一種具有密鑰更新和密態數據去重的完整性驗證方案。在本文方案中，采用收斂加密（convergent encryption）[12]方法保證文件的機密性；由第三方審計者協助用戶進行密鑰更新，能夠保證用戶在某一時間周期的私鑰與其余時間周期的私鑰相互獨立，從而使得半可信的云服務器不能通過用戶某一時間周期的私鑰得到該用戶其余時間周期私鑰的任何信息。

2 預備知識

2.1 雙線性映射

2.2 CDH困難問題假設

如果沒有多項式時間的算法能以至少ε的優勢解決CDH困難問題，那么就稱CDH困難問題假設成立。

2.3 布隆過濾器

布隆過濾器（Bloom filter）[17]作為一種概率數據結構，能夠近似表示集合中的元素并驗證某元素是否屬于該集合。由于存儲空間和插入/查詢請求時間均為常數，布隆過濾器較現有的其他支持以上功能的數據結構具有存儲時間與空間更為高效的優勢。與此同時，為了取得時空高效，布隆過濾器不可避免地犧牲了一定的準確率，即存在誤判。具體來說，誤判的定義是若某一元素不在集合中，在利用布隆過濾器驗證時也會以一定的概率將該元素判定為屬于集合；但是，若該元素是集合中的元素，則不會發生誤判。

布隆過濾器由k個隨機的散列函數h1(?),h2(?),和一個mbit的數組組成。初始化布隆過濾器時，需要將數組中的所有比特置為 0。若要向布隆過濾器中插入某一元素x，則需計算該元素在布隆過濾器的數組中的k個位置并將數組中相應比特置為 1。為了確定某元素是否在集合中，需要計算它的k個散列值然后驗證數組中相應比特的值是否均為 1。在不考慮誤判的情況下，該元素在集合中的充要條件是布隆過濾器數組中相應位置的值均為 1。此外，通過對布隆過濾器中誤判的分析[18]，只要k選取適當的值，布隆過濾器的誤判率可以很小。

2.4 系統描述

本文方案包含4個實體：云服務器、用戶、第三方審計者（TPA）和密鑰服務器（KS, key server），系統模型如圖1所示。

圖1 本文方案系統模型

在每個時間周期開始時，TPA通過向用戶發送密鑰更新消息來協助用戶更新文件的簽名私鑰，從而達到抗泄露的目的。TPA在完整性審計時是誠實的，但在密鑰更新時可能是不完全可信的。此外，在數據去重的過程中，用戶需要配合云服務器驗證是否需要將本地數據上傳至云服務器，或是在云服務器的協助下進行 PoW 挑戰而不需要上傳數據本身。當用戶需要對云服務器中存儲的數據進行完整性審計時，首先需要將數據的認證標簽發送給TPA驗證其有效性，若能通過驗證則TPA與云服務器執行挑戰與響應協議。密鑰服務器負責根據文件內容向用戶分發私鑰用于加密數據，用戶需要從密鑰服務器獲取收斂密鑰完成對文件進行加密。

2.5 一般方案

參考現有的支持密鑰更新的公開審計方案[15]和密文數據去重的公開審計方案[12,18-19]，支持密鑰更新和密文數據去重的公開審計方案通常包含以下5個算法。

密鑰生成（KeyGen）算法：利用密鑰生成算法，產生用戶ui的公私鑰對系統公開參數pp、TPA的私鑰skTPA、密鑰服務器的收斂密鑰種子ks及用于加密文件的加密密鑰ck。

更新消息生成（UMGen）算法：在每一時間周期開始時，由 TPA輸入系統公開參數pp、當前時間周期t和TPA的私鑰skTPA，并輸出更新消息tδ。

文件上傳（FileUpload）算法：若用戶ui需要上傳索引為idF的文件F，首先需要將文件F分為n塊，計算文件F的散列值H(F)并將其發送給云服務器，判斷云服務器中是否已經存儲了文件F，判斷結果分2種。

情形1 若云服務器中沒有存儲文件F，則需要通知用戶ui上傳數據。用戶ui收到通知后利用當前時間周期t、系統公開參數pp、用戶自己的私鑰ski和TPA發送的更新消息tδ來計算時間周期t的簽名私鑰skt，并利用密鑰服務器生成的加密密鑰對每個消息塊mj加密得到相應的密文ctj。隨后用戶ui生成文件F的一組認證標簽Φ，將文件F的n個消息塊分別存儲到布隆過濾器BFj中，并將文件F的所有密文集合索引值idj和布隆過濾器BFj一同發送給云服務器。

情形2 若云服務器中已經存儲了文件F，則云服務器向用戶ui發出驗證消息K，用戶ui收到之后生成一組證明值，這時云服務器就可以通過判斷這些證明值是否在布隆過濾器BFj中來確認用戶ui是否確實擁有文件F。

響應值生成（ResGen）算法：云服務器執行該算法。輸入系統公開參數pp、時間周期t、挑戰值chal、文件F的密文集合和文件F的一組認證標簽Φ，輸出響應值P。其中，云服務器輸入的(t,chal)由TPA發布。

響應值驗證（ResVerify）算法：TPA執行該算法。輸入系統公開參數pp、時間周期t、挑戰值chal和響應值P。若驗證通過，返回“真”；否則，返回“假”。

2.6 安全模型

用戶的隱私信息包含兩部分：一部分是用于在時間周期t內生成消息認證標簽的用戶ui的簽名私鑰skt；另一部分是用于在時間周期t內生成簽名私鑰的用戶ui的私鑰ski。基于Yu等[15]的支持強抗密鑰泄露的公開審計方案，本節定義了敵手A和挑戰者C之間的安全性游戲。在游戲中，A強大到甚至可以詢問用戶ui在除一個時間周期之外的所有時間周期用戶的私鑰。具體安全模型如下。

1) 系統建立（setup）：首先令時間周期t=0，C執行KeyGen算法，生成系統公開參數pp、TPA的私鑰skTPA和用戶ui的私鑰ski。C將pp發送給A，然后保留ski。

2) 詢問（query）：C生成用戶在時間周期t的簽名私鑰skt。

② 私鑰詢問：A選擇是否詢問時間周期t內用戶ui的私鑰，若是，C將用戶在時間周期t的私鑰和簽名密鑰skt發送給A；否則，發送⊥。

每個時間周期結束時，A可選擇再次詢問或進行挑戰。

3) 挑戰（challenge）：C選擇一個A在私鑰詢問階段中沒有詢問過的時間周期*t，并將挑戰值發送給A，其中索引集合且集合中的元素均屬于C向A請求時間周期*t下根據挑戰值chal生成的響應值P。

4) 偽造（forgery）：A輸出響應值P，若驗證通過，則A贏得游戲。

在上述安全模型中，A在沒有擁有挑戰值chal中涉及的所有消息的情況下，若不能猜測出所有的消息的內容，則無法提供私鑰沒有泄露的時間周期的有效響應。在每個時間周期內A均可詢問所有消息的認證標簽。A還可詢問除挑戰階段的時間周期外所有時間周期的用戶私鑰。A的目的是構造時間周期*t的有效響應值P。本文定義一個數據完整性審計方案的強抗密鑰泄露，即存在一個提取器能夠在A生成時間周期*t的有效響應值P時提取出挑戰的消息。

在實際情況下，許多用戶對云服務器并不完全相信，為了保證用戶數據的機密性，還需要在上傳文件前對其進行加密處理。然而如果采用一般的加密方法，在去重過程中會導致不同用戶利用不同密鑰加密相同的文件，從而導致方案無法實現去重，因此需要對文件采用特殊的加密方法。文件的機密性要求阻止云服務器獲取文件內容的攻擊。特別地，要求方案能夠抵抗字典攻擊，也就是說，即使半可信的云服務器預先獲得了包含所有可能文件及其密文的“字典”，仍舊無法恢復出目標文件。

在密鑰生成算法中，TPA在每一時間周期均生成更新消息來幫助用戶更新私鑰。進一步要求 TPA不能根據自身私鑰和生成的認證消息偽造任何認證標簽，也就是認證標簽的不可偽造性。

在文件上傳算法過程中，考慮到有些惡意用戶可能會通過偽造消息的證明值來試圖利用 PoW 挑戰獲取合法用戶上傳的文件，因此，本文方案的安全性還需要達到PoW挑戰中證明值的不可偽造性。如果惡意用戶需要通過PoW挑戰來獲得文件F，假設該惡意用戶已經擁有文件F的散列值和F的部分密文，那么惡意用戶就可以偽造剩余部分的證明值從而達到通過 PoW 挑戰的目的。本文方案不考慮惡意用戶已經擁有絕大部分密文的情況，因為這種情況下惡意用戶將不再需要偽造證明值。此外，本文方案利用收斂加密[7]的方法對文件F的n個消息塊進行了加密，在確保文件加密密鑰確定性的同時保證了文件的機密性，因此惡意用戶即使已經獲得了文件F的全部密文，也很難恢復出文件F對應的明文。

3 抗密鑰泄露和支持去重的完整性審計方案

在實現抗密鑰泄露時，本文方案中每一時間周期用戶的簽名私鑰均為兩部分的乘積，一部分是TPA根據自身私鑰生成的更新消息，另一部分是由用戶的私鑰和當前時間周期計算而來的。任何時間周期的簽名私鑰都需要用戶和TPA共同生成，這種方法能同時保證密鑰更新的安全性和高效性，因此在沒有TPA私鑰的情況下，即使攻擊者在某一時間周期入侵了用戶，該攻擊者也不能獲得用戶在其余時間周期的簽名私鑰。由于時間周期是認證標簽的一部分，且無法分離出來，因此相同消息在不同時間周期的認證標簽是不同的。在許多已有的云存儲審計方案[2]中，利用數字簽名SSig（secure signature）來保證文件索引idF的完整性。本文方案同樣采用這種方式來保證文件索引idF和時間周期t的完整性，且簽名SSig對應的公私鑰對(ssk,spk)由用戶生成。

定義3個抗碰撞散列函數H、H1和H2，其中，其中，m和len分別表示消息和證明值的長度是偽隨機函數[18]，其中，κ是正整數。方案的具體構造如下。并計算gxi，得到用戶ui的公私鑰對

2) 更新消息生成：在時間周期t開始時，TPA利用私鑰sk計算時間周期t的更新消息TPA并發送給用戶。用戶接收到更新消息tδ之后，利用驗證消息的有效性。

3) 文件上傳：若用戶ui在時間周期t內上傳文件F，首先需要將文件分為n個消息塊其中，然后計算并上傳給云服務器，云服務器收到hi之后判斷hi是否已存在。

情況 1 若云服務器中沒有找到相同的hi，則說明云服務器中沒有存儲過文件F，這時云服務器發送“No”給用戶ui。用戶ui收到后利用更新消息tδ計算并與密鑰服務器一起執行如下步驟對文件F進行加密并生成認證標簽Φ。

① 用戶ui計算每個消息塊的散列值mj并將所有計算結果發送給密鑰服務器。

② 密鑰服務器收到后對所有j=1,…,n，計算由密鑰服務器保管。

③ 用戶ui加密每個消息塊，計算(ksj,mj)，即得到文件F的密文其中，Enc(?)是一個對稱加密算法，idF為文件F的標識符。

④ 用戶ui用密鑰服務器為其分配的私鑰ck加密收斂密鑰ksj，并存儲在云服務器中。并由此計算每個消息塊mj的認證標簽為

⑤ 用戶ui隨機選擇計算

其中，idj和idF分別為消息塊mj和文件F的標識符。

⑥ 用戶ui生成文件F的標簽和認證標簽集合

用戶ui計算文件F中每個消息塊相應的證明值和偽隨機值然后將每個偽隨機值Pj插入布隆過濾器BFF中，并將布隆過濾器BFF連同文件F的密文集合 ( idF,ct1,… ,c tn)、文件標簽tagt和認證標簽集合Φ一起上傳給云服務器。云服務器計算H(F)，驗證認證標簽的正確性以及hi=H(F)是否成立。若驗證通過，云服務器將用戶ui上傳的內容存儲起來，并返回用戶ui文件F密文的鏈接和標簽tagt；否則，云服務器返回出錯消息。

情況2 若云服務器中已經存儲過文件F，則需要用戶ui通過與云服務器的 PoW 挑戰。首先，云服務器隨機選擇文件F中的s個密文消息塊，并將這些消息塊的索引集合K= {k1, … ,kl} (1 ≤l≤n)發送給用戶ui。用戶ui收到集合K后，計算集合中每個索引對應的證明值然后將返回給云服務器。對于所有云服務器選出的l個消息塊，云服務器利用用戶ui返回的計算其偽隨機值并驗證是否所有的Pkj均屬于布隆過濾器BFF。若屬于，則向用戶ui發送文件F密文的鏈接和認證標簽tagt；否則，返回出錯消息。

4) 響應值生成：若用戶ui需要驗證已上傳文件F的完整性，則首先將文件F的認證標簽tagt發送給 TPA。TPA收到后利用spk驗證文件認證標簽tagt的有效性，若有效，則選擇一個索引集合其中的每個元素均屬于對于每個idj∈I，TPA隨機選擇vj，并生成挑戰值發送給云服務器。云服務器在收到挑戰值chal后，計算并將響應值P= (t,R,σ, μ)返回給TPA。

5) 響應值驗證：TPA收到響應值P后，驗證

是否成立，若成立，返回“真”；否則，返回“假”。

4 安全性分析

4.1 方案的一致性

對于一個隨機的挑戰值 c hal = {idj,vj}idj∈I和有效的證明值P= (t,R,σ, μ)，響應值驗證算法總會返回“真”，因為有以下等式成立。

若用戶ui需要取回存儲在云服務器上的文件，那么在取回文件F的同時還需要下載事先已加密的收斂密鑰ksj，并用私鑰進行解密，從而得到相應的明文文件。

4.2 強抗密鑰泄露

定理1 若1G上的CDH問題是困難的，則方案是強抗密鑰泄露的。

證明 定義以下一系列安全性游戲，并分析敵手A在游戲中的行為差異。

游戲0 游戲0是第2.6節中定義的安全性游戲。

游戲1 游戲1基本與游戲0相同，不同之處在于，挑戰者C維護一個所有經過他簽名的認證標簽列表。當A提交一個未通過C簽名的有效標簽時，C中止游戲。

分析 若A在游戲1中使C中止游戲，則容易利用A構造一個攻擊攻破簽名方案SSig。以下假設idF和t在交互過程中均由C生成。

游戲2 游戲2與游戲1基本相同。不同之處在于，C維護一個對A認證標簽詢問的響應值列表。若A取得游戲勝利，而響應值P中的R與C維護的列表中不同，則C中止游戲。

分析 若A能夠使C在游戲2中中止游戲，則可以構造一個模擬算法S以不可忽略的概率解決CDH困難問題。S與游戲1中的C類似，但有以下不同：給予C一個CDH挑戰通過A計算gab，然后選擇簽名公私鑰對(ssk,spk)生成idF和t的簽名。假設A進行了qk次私鑰詢問和qs次認證標簽詢問。

詢問（query）：將H和H2看作 2個由C控制和存儲的隨機預言機，C需要對A發出的詢問做出回答。

1)H預言機詢問：C存儲一個初始為空的H列表。當A向C發送時間周期t來詢問H預言機時，C查找H列表，檢查是否有包含輸入的時間周期t的元素(t,c,λ,h)。若有，則向A發送h；否則，C擲一枚硬幣c∈ { 0 ,1}，滿足結果為 0的概率為結果為1的概率為若投擲結果為0，C隨機選擇并計算gλ，然后將加入H列表；否則，C隨機選擇，然后將(t, 1 ,λ,h=Yλ)加入H列表，最后，C向A發送h。

2)H2預言機詢問：C存儲一個初始為空的H2列表。當A向C發送進行詢問時，C查找H2列表，檢查是否有包含該輸入的元素若有，則向A發送h2；否則，C隨機選擇添加到H2列表，最后，C向A發送h2。

3) 私鑰詢問：當A在時間周期t內進行私鑰詢問時，C從H列表中取出不失一般性，假設A向H預言機詢問過時間周期t。若c=1，則C中止（用E1表示）；否則，C計算其中最后，C返回(ski, skt)。

挑戰（challenge）：C選擇一個A沒有進行過私鑰詢問的時間周期*t，然后向A發送一個挑戰值和時間周期*t，其中I是消息塊索引的一個子集。此外，C還要求A提供時間周期*t文件在挑戰值下的響應值P。

分析C在上述模擬算法中不中止的概率為

其中，pk和ps分別為A私鑰詢問和認證標簽詢問的數量。

如果A通過了挑戰，但響應值P中的R與C從H2列表中找到的R不相同，那么C能夠以不可忽略的概率解決CDH困難問題。

游戲3 游戲3與游戲2類似，不同之處在于C存儲一個生成的A認證標簽詢問的返回結果列表。C檢查列表中的元素，若任何元素中有A雖通過挑戰但A的認證標簽則C中止。

分析 假設使C中止的文件為 {1,F→m時間周期為t，文件的認證標簽集合為A 的響應值為挑戰值為A誠實情況下生成的預期響應值因此，有效的響應值可由式(1)驗證。

根據C中止可以推斷出σ′≠σ，且σ′能夠通過如下等式的驗證

設 Δ μ = μ ′- μ ，顯然有 Δμ≠0，否則與假設矛盾。構造如下模擬算法S解決CDH困難問題。

向S輸入(g,ga′,v)，最終輸出va′。S代替游戲2中的C，但有以下不同：在系統建立階段，S選擇計算并生成實際情況下所有時間周期的私鑰。H2可看作一個由S控制并存儲的隨機預言機，當A向H2預言機發送時，S驗證H2列表中是否已經存在相應的元素若有，S返回h2給A；否則，S隨機選擇將添加到H2列表，并向A返回h2。

當A詢問消息塊mj在時間周期t的認證標簽時，S隨機選擇計算R= (ga)?和與已有值碰撞的概率是可忽略的。S計算認證標簽

即

由此解決了CDH困難問題

若A贏得游戲2和游戲3的概率有不可忽略的差別，則S能夠解決CDH困難問題，所以在任何能夠通過驗證的響應值中σ必須是正確的。

游戲4 游戲4與游戲3除以下區別外基本相同：C存儲并檢查進行認證標簽詢問時給A的返回值。若存在A贏得游戲但A的聚合消息μ′≠則C中止游戲。

因此，若A在贏得游戲3和游戲4的概率之間存在一個不可忽略的差別，就可以構造一個模擬算法S解決離散對數問題。

根據本文分析，這些游戲之間僅存在可忽略的差別，且解決CDH問題的困難程度蘊含著解決離散對數問題的困難程度。若1G上的CDH問題是困難的，且簽名算法SSig是不可偽造的，則C除了A上傳正確的響應值P的情況外將無法驗證通過。

4.3 機密性

由于方案中引入了密鑰服務器來幫助用戶生成文件的收斂密鑰，因此若不利用密鑰服務器存儲的收斂密鑰種子，半可信的云服務器就不能以不可忽略的概率生成任何文件有效的收斂密鑰。由于文件的散列值可以看作一個有效的消息認證碼，因此云服務器在沒有密鑰服務器的幫助下就無法實施暴力攻擊。此外，所有消息塊在上傳給云服務器前均已加密，且收斂密鑰由密鑰服務器生成，并由上傳文件的用戶公鑰加密后存至云服務器的，也可以認為收斂密鑰是由文件本身和密鑰服務器的收斂密鑰種子共同產生的，這就意味著收斂密鑰并不僅僅源于文件本身。

假設半可信的云服務器不能與密鑰服務器共謀，那么即使文件是可預測的，半可信的云服務器也不能利用暴力攻擊推測出文件的內容，由此說明本文方案能夠抵抗字典攻擊。

4.4 可檢測性

假設云服務器存儲一個n塊的文件，其中的k塊均被損壞，在挑戰階段TPA的挑戰值中包含s塊，則損壞的塊被發現的必要條件是當且僅當被挑戰的塊中至少一個是損壞的塊。利用一個獨立的隨機變量X表示挑戰階段選擇的塊中損壞的塊數量，用PX表示在挑戰階段選擇的塊中至少有一個被損壞塊的概率。因此，有。也就是說，損壞的塊被檢測出的概率至少是說明損壞的塊越多，TPA選出進行挑戰的塊越多，損壞的塊被檢測出的概率越大。

4.5 認證標簽的不可偽造性

從文件上傳算法中可以看出，時間周期t內計算任何認證標簽均需要私鑰 skt，而用戶私鑰的生成過程中私鑰是由用戶ui的私鑰ski和TPA的私鑰這兩部分私鑰構成的，具體來說，就是由于方案中的TPA只擁有skTPA且僅需要計算更新消息tδ，因此TPA不知道用戶ui的私鑰ski也就不能計算出skt。因此TPA不能通過自己的私鑰skTPA和更新消息tδ偽造任何消息塊的認證標簽。

4.6 證明值的不可偽造性

在文件上傳算法中，若某一用戶需要向云服務器上傳文件，在上傳消息之前需要先發送文件的散列值來驗證云服務器中是否已經存儲該文件，若沒有存儲，則需要用戶上傳文件F、文件標簽tagt、認證標簽集合Φ和消息的布隆過濾器BFF；若云服務器中已經存儲過，則用戶不再需要上傳文件本身，而改為執行 PoW 挑戰，目的在于避免惡意用戶通過擁有文件的散列值而不是整個文件來惡意獲取合法用戶的數據。簡單地說，本文方案利用布隆過濾器匹配消息的證明值來實現PoW挑戰。

PoW 挑戰要求用戶生成云服務器隨機選取的k個消息塊的證明值，云服務器收到證明值后用偽隨機函數處理并用相應的布隆過濾器驗證是否屬于選定的消息。假設惡意用戶需要獲得消息mj，若惡意用戶擁有mj的一些消息塊，在進行PoW挑戰時惡意用戶需要生成所有云服務器選擇的k個消息塊的證明值。在Blasco等[18]的方案中已經得出，如果惡意用戶僅僅擁有少數消息塊，布隆過濾器的參數選取得當，且k足夠大，那么惡意用戶成功偽造消息證明值，從而通過PoW挑戰的概率是可忽略的。

不能否認的是，若用戶擁有絕大多數的消息塊，則會以很大概率通過 PoW 挑戰。在這種情況下，由于用戶幾乎已經擁有該消息，也就可以將這個用戶看作一個合法的擁有者了。

5 性能分析與實驗結果

本節從方案實現的功能和效率這2個方面進行分析。由于目前沒有能同時支持抗密鑰泄露和密文數據去重的完整性審計方案，本文方案在功能上更有優勢。在方案的效率方面將從計算效率和通信效率兩部分進行評價。為便于表示，用exp、mul、hash和pair分別表示指數運算、乘法運算、散列運算和對運算。

在文件上傳階段，若云服務器中沒有存儲需要上傳的文件，則用戶需要計算簽名私鑰skt、文件標簽tagt、認證標簽集合Φ和布隆過濾器BFF，計算開銷為(n+ 1 )hash + 2 exp + 3 mul+ s ig + p rf ，其中，sig和prf分別為數字簽名和偽隨機函數；反之，若云服務器中已經存儲過該文件，則用戶需要生成PoW挑戰的證明值，相應的計算開銷為(l+ 1 )hash 。在挑戰階段，TPA僅隨機選擇一些消息塊的索引生成挑戰值，因此計算開銷很小。然而在響應階段，云服務器生成響應值時的計算開銷為se xp + (s- 1 )mul +smul，其中s表示挑戰值中選取消息塊的個數。最后，在驗證階段，TPA判斷響應值是否有效，計算開銷為(s+ 2 )exp + (s+2)mul+ 3 pair。表1分析了方案的總體計算開銷。

表1 支持密鑰更新和密文數據去重的公開審計方案的計算開銷

本文方案的通信開銷主要包括文件上傳、挑戰階段和響應階段這3個部分。在文件上傳的過程中，用戶需要將發送給云服務器，這部分的通信開銷為分別表示文件的大小和Zp或G1上一個元素的大小。挑戰階段挑戰值TPA挑出的s個(idj,vj)組成，因此通信開銷為其中，為索引的長度。相應階段響應值的通信開銷為

實驗通過對方案的計算開銷和通信開銷進行比較，利用PBC庫給出Windows 7環境下的效率分析結果，實驗配置為 Intel Core I3-2120 CPU@3.30 GHz，4 GB RAM。假設1G和Zp上的元素大小均為160 bit，消息塊的大小為2 KB，集合I中的元素大小為20 bit，以下實驗結果為50次實驗的平均值。

圖2顯示了方案中用戶、云服務器和TPA在云服務器中有副本和無副本這2種情況下的計算開銷隨文件塊數和挑戰塊數取值的變化趨勢。仿真實驗選定文件的分塊數量為 400，選取挑戰塊數分別為50、100、150、200和 250。圖2(a)表明當云服務器中無副本時，TPA和云服務器的計算開銷隨著審計過程中挑戰塊數量的增加呈線性增長，而用戶的計算開銷只與文件分塊的個數n有關，故用戶的計算開銷呈直線，且大于TPA和云服務器的計算開銷。圖 2(b)表明當云服務器中有副本時，云服務器承擔了密文數據去重的大多數計算開銷，隨著審計過程中TPA挑戰塊數量的增加而呈線性增長，而用戶和TPA的計算開銷只與文件分塊的個數n有關，故呈直線，且用戶的計算開銷小于TPA的計算開銷。因此，在云服務器中無副本時，用戶的計算開銷較大；而有副本時，云服務器的計算開銷較大。

圖2 用戶、云服務器和TPA計算開銷的變化趨勢比較

圖3顯示了方案中用戶、云服務器和TPA三方在云服務器中有副本和無副本這2種情況下的通信開銷隨文件塊數和挑戰塊數取值的變化趨勢。在圖3(a)中，選取文件分塊數量分別為250、300、350、400和450，結果表明，在云服務器中無副本時，用戶的通信開銷隨著文件分塊數量增加而線性增加，而TPA和云服務器的通信開銷較小。在圖3(b)中，選定文件的分塊數量n為400，選取挑戰塊數分別為50、100、150、200和250，仿真結果表明，在云服務器中有副本時，TPA的通信開銷隨著審計過程中挑戰的文件塊數量的增加線性增長，而用戶和云服務器的通信開銷較小。因此，當云服務器中無副本時，用戶的通信開銷較大；而云服務器中有副本時，通信開銷主要在審計過程中由TPA承擔。

圖3 用戶、云服務器和TPA通信開銷的變化趨勢比較

6 結束語

本文提出了同時支持密鑰更新和密文數據去重的公開審計方案。新方案首次在支持數據去重的完整性審計方案中解決密鑰泄露問題，且方案不僅考慮密鑰泄露之前的安全性，還考慮到密鑰泄露之后的用戶數據機密性保護問題，使用戶在某一時間周期內的私鑰不會影響到其他時間周期，且敵手即使通過了PoW挑戰也很難恢復出明文數據。安全性分析表明，新方案達到了強抗密鑰泄露、機密性、可檢測性以及認證標簽和證明值的不可偽造性。下一步需要提高效率和進行全面形式化安全性證明。