張襄松，李晨，劉振華

（1. 西安工業(yè)大學(xué)理學(xué)院，陜西 西安 710021；2. 西安電子科技大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，陜西 西安 710071）

1 引言

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

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

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

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

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

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

2 預(yù)備知識

2.1 雙線性映射

2.2 CDH困難問題假設(shè)

如果沒有多項(xiàng)式時(shí)間的算法能以至少ε的優(yōu)勢解決CDH困難問題，那么就稱CDH困難問題假設(shè)成立。

2.3 布隆過濾器

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

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

2.4 系統(tǒng)描述

本文方案包含4個(gè)實(shí)體：云服務(wù)器、用戶、第三方審計(jì)者（TPA）和密鑰服務(wù)器（KS, key server），系統(tǒng)模型如圖1所示。

圖1 本文方案系統(tǒng)模型

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

2.5 一般方案

參考現(xiàn)有的支持密鑰更新的公開審計(jì)方案[15]和密文數(shù)據(jù)去重的公開審計(jì)方案[12,18-19]，支持密鑰更新和密文數(shù)據(jù)去重的公開審計(jì)方案通常包含以下5個(gè)算法。

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

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

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

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

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

響應(yīng)值生成（ResGen）算法：云服務(wù)器執(zhí)行該算法。輸入系統(tǒng)公開參數(shù)pp、時(shí)間周期t、挑戰(zhàn)值chal、文件F的密文集合和文件F的一組認(rèn)證標(biāo)簽Φ，輸出響應(yīng)值P。其中，云服務(wù)器輸入的(t,chal)由TPA發(fā)布。

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

2.6 安全模型

用戶的隱私信息包含兩部分：一部分是用于在時(shí)間周期t內(nèi)生成消息認(rèn)證標(biāo)簽的用戶ui的簽名私鑰skt；另一部分是用于在時(shí)間周期t內(nèi)生成簽名私鑰的用戶ui的私鑰ski?；赮u等[15]的支持強(qiáng)抗密鑰泄露的公開審計(jì)方案，本節(jié)定義了敵手A和挑戰(zhàn)者C之間的安全性游戲。在游戲中，A強(qiáng)大到甚至可以詢問用戶ui在除一個(gè)時(shí)間周期之外的所有時(shí)間周期用戶的私鑰。具體安全模型如下。

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

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

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

每個(gè)時(shí)間周期結(jié)束時(shí)，A可選擇再次詢問或進(jìn)行挑戰(zhàn)。

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

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

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

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

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

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

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

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

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

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

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

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

① 用戶ui計(jì)算每個(gè)消息塊的散列值mj并將所有計(jì)算結(jié)果發(fā)送給密鑰服務(wù)器。

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

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

④ 用戶ui用密鑰服務(wù)器為其分配的私鑰ck加密收斂密鑰ksj，并存儲在云服務(wù)器中。并由此計(jì)算每個(gè)消息塊mj的認(rèn)證標(biāo)簽為

⑤ 用戶ui隨機(jī)選擇計(jì)算

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

⑥ 用戶ui生成文件F的標(biāo)簽和認(rèn)證標(biāo)簽集合

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

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

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

5) 響應(yīng)值驗(yàn)證：TPA收到響應(yīng)值P后，驗(yàn)證

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

4 安全性分析

4.1 方案的一致性

對于一個(gè)隨機(jī)的挑戰(zhàn)值 c hal = {idj,vj}idj∈I和有效的證明值P= (t,R,σ, μ)，響應(yīng)值驗(yàn)證算法總會返回“真”，因?yàn)橛幸韵碌仁匠闪ⅰ?/p>

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

4.2 強(qiáng)抗密鑰泄露

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

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

游戲0 游戲0是第2.6節(jié)中定義的安全性游戲。

游戲1 游戲1基本與游戲0相同，不同之處在于，挑戰(zhàn)者C維護(hù)一個(gè)所有經(jīng)過他簽名的認(rèn)證標(biāo)簽列表。當(dāng)A提交一個(gè)未通過C簽名的有效標(biāo)簽時(shí)，C中止游戲。

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

游戲2 游戲2與游戲1基本相同。不同之處在于，C維護(hù)一個(gè)對A認(rèn)證標(biāo)簽詢問的響應(yīng)值列表。若A取得游戲勝利，而響應(yīng)值P中的R與C維護(hù)的列表中不同，則C中止游戲。

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

詢問（query）：將H和H2看作 2個(gè)由C控制和存儲的隨機(jī)預(yù)言機(jī)，C需要對A發(fā)出的詢問做出回答。

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

2)H2預(yù)言機(jī)詢問：C存儲一個(gè)初始為空的H2列表。當(dāng)A向C發(fā)送進(jìn)行詢問時(shí)，C查找H2列表，檢查是否有包含該輸入的元素若有，則向A發(fā)送h2；否則，C隨機(jī)選擇添加到H2列表，最后，C向A發(fā)送h2。

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

挑戰(zhàn)（challenge）：C選擇一個(gè)A沒有進(jìn)行過私鑰詢問的時(shí)間周期*t，然后向A發(fā)送一個(gè)挑戰(zhàn)值和時(shí)間周期*t，其中I是消息塊索引的一個(gè)子集。此外，C還要求A提供時(shí)間周期*t文件在挑戰(zhàn)值下的響應(yīng)值P。

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

其中，pk和ps分別為A私鑰詢問和認(rèn)證標(biāo)簽詢問的數(shù)量。

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

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

分析 假設(shè)使C中止的文件為 {1,F→m時(shí)間周期為t，文件的認(rèn)證標(biāo)簽集合為A 的響應(yīng)值為挑戰(zhàn)值為A誠實(shí)情況下生成的預(yù)期響應(yīng)值因此，有效的響應(yīng)值可由式(1)驗(yàn)證。

根據(jù)C中止可以推斷出σ′≠σ，且σ′能夠通過如下等式的驗(yàn)證

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

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

當(dāng)A詢問消息塊mj在時(shí)間周期t的認(rèn)證標(biāo)簽時(shí)，S隨機(jī)選擇計(jì)算R= (ga)?和與已有值碰撞的概率是可忽略的。S計(jì)算認(rèn)證標(biāo)簽

即

由此解決了CDH困難問題

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

游戲4 游戲4與游戲3除以下區(qū)別外基本相同：C存儲并檢查進(jìn)行認(rèn)證標(biāo)簽詢問時(shí)給A的返回值。若存在A贏得游戲但A的聚合消息μ′≠則C中止游戲。

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

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

4.3 機(jī)密性

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

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

4.4 可檢測性

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

4.5 認(rèn)證標(biāo)簽的不可偽造性

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

4.6 證明值的不可偽造性

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

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

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

5 性能分析與實(shí)驗(yàn)結(jié)果

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

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

表1 支持密鑰更新和密文數(shù)據(jù)去重的公開審計(jì)方案的計(jì)算開銷

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

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

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

圖2 用戶、云服務(wù)器和TPA計(jì)算開銷的變化趨勢比較

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

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

6 結(jié)束語

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