哈冠雄，賈巧雯，陳杭，賈春福

0 引言

云存儲(chǔ)技術(shù)[1]的快速發(fā)展使越來越多的用戶選擇將數(shù)據(jù)外包至云服務(wù)器（CS,cloud server）。隨著數(shù)據(jù)量的不斷增加，如何高效存儲(chǔ)海量數(shù)據(jù)成為云服務(wù)提供商面臨的一個(gè)關(guān)鍵問題。數(shù)據(jù)去重[2-3]是一種節(jié)省存儲(chǔ)開銷的有效方法，云服務(wù)器可基于去重技術(shù)識(shí)別用戶間上傳的重復(fù)數(shù)據(jù)內(nèi)容，刪除其中的冗余部分以節(jié)省存儲(chǔ)開銷。近年來，隱私泄露問題受到了越來越多的關(guān)注，數(shù)據(jù)的隱私保護(hù)變得愈發(fā)重要。傳統(tǒng)加密算法可將數(shù)據(jù)轉(zhuǎn)換為與隨機(jī)比特串不可區(qū)分的密文形式，為其提供安全級(jí)別較高的語義安全。然而，傳統(tǒng)加密算法與去重技術(shù)難以兼容。不同用戶的加密密鑰不同，跨用戶上傳的相同數(shù)據(jù)在加密后將變成完全隨機(jī)的密文，這為重復(fù)數(shù)據(jù)的檢測(cè)帶來了困難。收斂加密（CE,convergent encryption）[4]使用數(shù)據(jù)哈希值作為加密密鑰，首次實(shí)現(xiàn)了加密去重。但Bellare 等[5]指出CE 只能提供收斂安全性，其僅能為不可預(yù)測(cè)數(shù)據(jù)（明文空間無限，敵手無法遍歷）提供語義安全。若使用CE 加密可預(yù)測(cè)數(shù)據(jù)，易受到離線字典攻擊。

因此，在實(shí)現(xiàn)數(shù)據(jù)去重的同時(shí)提供語義安全是一個(gè)關(guān)鍵挑戰(zhàn)。針對(duì)此問題，一些研究工作[6-9]基于數(shù)據(jù)流行度設(shè)計(jì)加密去重方案，旨在兼顧存儲(chǔ)效率與數(shù)據(jù)安全。數(shù)據(jù)流行度指的是數(shù)據(jù)的所有者數(shù)量。具體而言，首先設(shè)定一個(gè)流行度閾值t，若外包數(shù)據(jù)的所有者數(shù)量超過t，則認(rèn)為是流行數(shù)據(jù)，否則認(rèn)為是不流行數(shù)據(jù)。對(duì)于流行歌曲、熱門電影等流行數(shù)據(jù)，系統(tǒng)基于CE 為其提供安全級(jí)別較低的收斂安全性；對(duì)于研究報(bào)告、醫(yī)療記錄等不流行數(shù)據(jù)，系統(tǒng)使用隨機(jī)加密為其提供安全級(jí)別較高的語義安全?；诹餍卸葘?duì)用戶數(shù)據(jù)進(jìn)行分類，可有效平衡存儲(chǔ)效率與數(shù)據(jù)安全。Stanek 等[6]使用真實(shí)數(shù)據(jù)集分析了基于流行度的加密去重系統(tǒng)的存儲(chǔ)效率，結(jié)果表明當(dāng)流行數(shù)據(jù)的數(shù)量較多時(shí)，方案具有較高的存儲(chǔ)效率。其他相關(guān)研究工作[7-9]也充分說明了基于流行度設(shè)計(jì)加密去重方案這一思路的可行性與實(shí)用性。

在基于流行度的加密去重中，如何安全準(zhǔn)確地統(tǒng)計(jì)數(shù)據(jù)流行度是方案設(shè)計(jì)中面臨的關(guān)鍵挑戰(zhàn)。現(xiàn)有方案及其特點(diǎn)如表1 所示，一些經(jīng)典的加密去重方案（如CE[4]、DupLESS[5]）將數(shù)據(jù)哈希值作為去重標(biāo)簽用于重復(fù)性檢測(cè)，易使不流行數(shù)據(jù)受到離線字典攻擊；一些現(xiàn)有方案[6-7]部署可信第三方協(xié)助統(tǒng)計(jì)數(shù)據(jù)流行度，這一方法的弊端主要有以下兩點(diǎn)。1)系統(tǒng)中的所有用戶都需要與第三方交互，影響了系統(tǒng)的可擴(kuò)展性。當(dāng)用戶量較多、數(shù)據(jù)量較大時(shí)，第三方服務(wù)器的處理能力有限，易成為系統(tǒng)的效率瓶頸。2)第三方可得到系統(tǒng)中所有數(shù)據(jù)的流行信息，因此需要假設(shè)第三方是完全可信的，這一假設(shè)在真實(shí)場(chǎng)景中難以實(shí)現(xiàn)。并且，第三方易成為系統(tǒng)中的單點(diǎn)故障，一旦其被敵手攻破，所有不流行數(shù)據(jù)的語義安全都將被破壞。

表1 現(xiàn)有方案及其特點(diǎn)

文獻(xiàn)[8-9]弱化了第三方的安全假設(shè)，通過引入半可信（即誠實(shí)但好奇）的第三方來統(tǒng)計(jì)數(shù)據(jù)流行度。Ha 等[8]通過部署一個(gè)半可信的第三方同態(tài)解密服務(wù)器統(tǒng)計(jì)數(shù)據(jù)流行度，其中的解密服務(wù)器同樣易成為系統(tǒng)中的效率瓶頸。Gao 等[9]通過引入第三方密鑰管理服務(wù)器實(shí)現(xiàn)了基于流行度的加密去重，該方案使用收斂密文的哈希值作為去重標(biāo)簽，易使不流行數(shù)據(jù)受到離線字典攻擊。

由于引入第三方服務(wù)器會(huì)存在效率瓶頸和單點(diǎn)故障的問題，本文提出了一個(gè)無第三方服務(wù)器的基于數(shù)據(jù)流行度的加密去重方案。該方案基于Count-Min sketch（CM-sketch）算法[10]、sPAKE（symmetric password-authenticated key exchange）協(xié)議[11]以及Merkle Puzzles 協(xié)議[12]，在不需要部署任何第三方服務(wù)器的情況下實(shí)現(xiàn)了加密去重系統(tǒng)中的數(shù)據(jù)流行度精確檢測(cè)，并可分別為流行數(shù)據(jù)和不流行數(shù)據(jù)提供收斂安全和語義安全。本文的主要貢獻(xiàn)如下。

1)本文方案設(shè)計(jì)了兩步檢測(cè)的方法安全精確地統(tǒng)計(jì)數(shù)據(jù)流行度。首先，基于CM-sketch 算法在僅使用固定內(nèi)存空間的前提下實(shí)現(xiàn)了數(shù)據(jù)流行度的初步檢測(cè)，有效過濾了大量不流行數(shù)據(jù)。然后，通過用戶與云服務(wù)器間執(zhí)行Merkle Puzzles 協(xié)議進(jìn)一步準(zhǔn)確統(tǒng)計(jì)數(shù)據(jù)流行度。流行度檢測(cè)過程僅由云服務(wù)器和用戶兩方完成，不需要任何第三方服務(wù)器。

2)通過在用戶間執(zhí)行sPAKE 協(xié)議，本文方案實(shí)現(xiàn)了不流行數(shù)據(jù)的去重檢測(cè)和用戶間的密鑰傳遞，云服務(wù)器可同時(shí)對(duì)流行數(shù)據(jù)和不流行數(shù)據(jù)實(shí)現(xiàn)客戶端加密去重，最大限度地節(jié)省了系統(tǒng)的通信開銷和存儲(chǔ)開銷。

3)本文方案設(shè)計(jì)了密鑰驗(yàn)證和密文驗(yàn)證的過程，并結(jié)合所有權(quán)證明（PoW,proof of ownership）[13]技術(shù)，可有效對(duì)抗所有權(quán)欺騙攻擊[13-14]、文件偽造攻擊[15]和字典攻擊[15]等加密去重系統(tǒng)中的常見攻擊，可分別為流行數(shù)據(jù)和不流行數(shù)據(jù)提供收斂安全性和語義安全性。

1 相關(guān)工作

近年來，國內(nèi)外的多個(gè)研究團(tuán)隊(duì)均在加密去重領(lǐng)域進(jìn)行了深入研究。Douceur 等[4]提出了CE，首次實(shí)現(xiàn)了加密去重。Bellare 等[15]將CE 形式化定義為消息鎖加密（MLE,message-locked encryption)，并指出CE 無法為可預(yù)測(cè)數(shù)據(jù)實(shí)現(xiàn)語義安全。為此，Bellare 等提出了DupLESS[5]，其引入一個(gè)密鑰服務(wù)器協(xié)助用戶加密數(shù)據(jù)，有效防止了字典攻擊。Halevi等[14]發(fā)現(xiàn)了客戶端去重中的所有權(quán)欺騙問題。針對(duì)此問題，文獻(xiàn)[13-14,16]提出了所有權(quán)證明方案。此外，文獻(xiàn)[17-19]針對(duì)加密去重系統(tǒng)中的密鑰更新與訪問控制問題進(jìn)行了研究。Li 等[20]提出了加密去重系統(tǒng)中的頻率分析攻擊，并給出了相應(yīng)的防御方案[20-21]。文獻(xiàn)[22-24]針對(duì)客戶端去重中的側(cè)信道攻擊問題提出了防御方案。

在加密去重這一研究領(lǐng)域中，基于數(shù)據(jù)流行度設(shè)計(jì)加密去重方案[6-9]是一個(gè)重要的研究分支。Stanek 等[6]基于門限密碼系統(tǒng)和雙層加密實(shí)現(xiàn)了基于流行度的加密去重，當(dāng)超過流行度閾值t個(gè)的用戶上傳某一密文后，云服務(wù)器可對(duì)外層的隨機(jī)密文進(jìn)行解密，保留內(nèi)層的收斂密文，實(shí)現(xiàn)加密去重。Puzio 等[7]利用完美哈希實(shí)現(xiàn)了基于流行度的加密去重，用戶可在與云服務(wù)器的交互中獲取外包數(shù)據(jù)的流行信息。文獻(xiàn)[6-7]需要引入可信第三方協(xié)助統(tǒng)計(jì)數(shù)據(jù)流行度，具有一定的局限性。為此，Ha 等[8]基于同態(tài)加密實(shí)現(xiàn)了數(shù)據(jù)流行度的安全統(tǒng)計(jì)，客戶端上傳外包數(shù)據(jù)的隨機(jī)標(biāo)簽至云服務(wù)器，云服務(wù)器通過與同態(tài)解密服務(wù)器的交互進(jìn)行流行度檢測(cè)。Gao等[9]基于雙層加密和密鑰共享設(shè)計(jì)了基于流行度的加密去重方案，將第三方的安全假設(shè)降低為誠實(shí)但好奇的。然而，現(xiàn)有方案都需要引入第三方服務(wù)器，易出現(xiàn)效率瓶頸等問題，影響了方案在真實(shí)場(chǎng)景中的實(shí)用性。為此，本文提出了無第三方服務(wù)器的基于數(shù)據(jù)流行度的加密去重方案。

2 預(yù)備知識(shí)

2.1 CM-sketch

CM-sketch 可在誤差較小的前提下利用有限的內(nèi)存空間描述數(shù)據(jù)的頻率特征，其內(nèi)部的數(shù)據(jù)結(jié)構(gòu)是一個(gè)w×d的二維數(shù)組，其中，參數(shù)ε δ、表示在 1?δ的概率下統(tǒng)計(jì)結(jié)果的總誤差小于ε。CM-sketch 算法主要由以下3 個(gè)算法組成。

1)Setup(ε,δ)。輸入?yún)?shù),ε，δ初始化一個(gè)w×d的二維數(shù)組count，將所有元素值置0；隨機(jī)選定d個(gè)兩兩獨(dú)立的哈希函數(shù)h1(?),h2(?),…,hd(?)，其中hi(?)(i∈[1,d])的輸出結(jié)果的長(zhǎng)度為w。

2)Count(x,count)。輸入元素x和數(shù)組count，計(jì)算哈希值h1(x),h2(x),…,hd(x)用于更新count，令count 中被哈希值映射到的位的計(jì)數(shù)值加1，即count[i][hi(x)]=count[i][hi(x)]+1，其中i∈[1,d]。

3)Freq(x,count)。輸入元素x和數(shù)組count，輸出x的頻率信息。計(jì)算哈希值h1(x),h2(x),…,hd(x)，取{count[i][hi(x)]|i∈[1,d]}中的最小值作為元素x的頻率信息輸出。

2.2 sPAKE

sPAKE[11,25]是傳統(tǒng)密鑰協(xié)商的一個(gè)擴(kuò)展。當(dāng)運(yùn)行協(xié)議的雙方共享同一個(gè)口令時(shí)，可協(xié)商出相同的密鑰；若雙方口令不同，則各自得到一個(gè)隨機(jī)密鑰，雙方均無法獲得對(duì)方密鑰的任何信息。

本文使用了目前已知最高效的sPAKE[11]，參與協(xié)議的雙方僅需執(zhí)行2 次冪運(yùn)算，具有很高的執(zhí)行效率，并且協(xié)議在隨機(jī)預(yù)言機(jī)模型下是可證明安全的。具體的協(xié)議流程如圖1 所示。本文方案使用數(shù)據(jù)哈希值取代了原協(xié)議中的口令。若參與sPAKE 協(xié)議的雙方擁有相同的哈希值，可協(xié)商出相同的輸出結(jié)果K1和K2，否則，雙方得到完全隨機(jī)的輸出結(jié)果。

圖1 sPAKE 協(xié)議流程

2.3 Merkle Puzzles

Merkle Puzzles 基于對(duì)稱密碼原語實(shí)現(xiàn)了安全的密鑰協(xié)商。假設(shè)協(xié)商密鑰的雙方分別為Alice 和Bob，他們執(zhí)行以下步驟協(xié)商密鑰。

1)Alice 窮舉密鑰集合中的所有密鑰{k1,k2,…,kn}，并生成n個(gè)密文{Ci=Enc(ki,0),Enc(ki,xi),，其中xi和si為隨機(jī)值，Enc(?)為對(duì)稱加密算法。Alice 將隨機(jī)排序后發(fā)送給Bob。

2)Bob 隨機(jī)選擇一個(gè)密文Cj=(c1,c2,c3)，使用{k1,k2,…,kn}中的所有密鑰嘗試解密c1。當(dāng)解密結(jié)果為0 時(shí)，Bob 確定對(duì)應(yīng)的密鑰為kj，然后使用kj解密c2和c3得到xj和sj，并將xj返回給Alice。

3)Alice 收到sj后密鑰協(xié)商結(jié)束，雙方得到的協(xié)商密鑰為kj。

本文基于上述設(shè)計(jì)思路和Yu 等[26]對(duì)Merkle Puzzles 的使用方式，將Merkle Puzzles 應(yīng)用于加密去重場(chǎng)景下的數(shù)據(jù)流行度統(tǒng)計(jì)中。

2.4 收斂加密

收斂加密[4]使用消息內(nèi)容的哈希值作為密鑰加密數(shù)據(jù)以實(shí)現(xiàn)密文去重，由以下3 個(gè)算法組成。

1)CE.KG(M)：輸入消息M，輸出收斂密鑰kc。

2)CE.Enc(kc,M)：輸入收斂密鑰kc和消息M，輸出收斂密文C。

3)CE.Dec(kc,C)：輸入收斂密鑰kc和收斂密文C，輸出消息M。

3 系統(tǒng)模型與定義

3.1 系統(tǒng)架構(gòu)

本文方案的系統(tǒng)架構(gòu)如圖2 所示，包括用戶U和云服務(wù)器CS。CS 為U提供數(shù)據(jù)存儲(chǔ)服務(wù)，基于數(shù)據(jù)的所有者數(shù)量將其劃分為流行數(shù)據(jù)和不流行數(shù)據(jù)，可對(duì)U的外包數(shù)據(jù)進(jìn)行去重以節(jié)省存儲(chǔ)開銷。U外包加密數(shù)據(jù)至CS 以節(jié)省本地存儲(chǔ)開銷，并且需要在上傳數(shù)據(jù)后在CS 的協(xié)助下與其他上傳數(shù)據(jù)的用戶運(yùn)行sPAKE 協(xié)議，以確定后續(xù)上傳數(shù)據(jù)的流行情況。

圖2 系統(tǒng)架構(gòu)

3.2 威脅模型

本文主要考慮以下兩類敵手。

1)內(nèi)部敵手。內(nèi)部敵手指系統(tǒng)中誠實(shí)但好奇的云服務(wù)器和合法用戶，其會(huì)誠實(shí)地執(zhí)行方案中設(shè)定的協(xié)議流程，同時(shí)也會(huì)試圖窺探用戶的數(shù)據(jù)信息。

2)外部敵手。外部敵手指系統(tǒng)中的惡意攻擊者，其可在與云服務(wù)器交互的任何階段發(fā)起攻擊。具體來說，外部敵手可通過竊聽信道得到用戶上傳的數(shù)據(jù)內(nèi)容，發(fā)起字典攻擊試圖恢復(fù)數(shù)據(jù)信息，發(fā)起所有權(quán)欺騙攻擊試圖篡改數(shù)據(jù)流行度[9]或騙取數(shù)據(jù)所有權(quán)，發(fā)起密鑰偽造攻擊或文件偽造攻擊試圖破壞數(shù)據(jù)完整性。

3.3 安全目標(biāo)

本文方案的安全目標(biāo)如下。

1)數(shù)據(jù)機(jī)密性。任何敵手均無法恢復(fù)不流行數(shù)據(jù)的任何信息。對(duì)于流行數(shù)據(jù)，本文方案提供收斂安全性。

2)數(shù)據(jù)完整性。任何敵手不能篡改用戶的外包數(shù)據(jù)，所有合法用戶均可正確恢復(fù)其外包數(shù)據(jù)并驗(yàn)證數(shù)據(jù)完整性。

3.4 符號(hào)定義

本文使用的符號(hào)及其含義如表2 所示。

表2 符號(hào)及其含義

4 設(shè)計(jì)思路

基于流行度設(shè)計(jì)加密去重系統(tǒng)存在以下2個(gè)挑戰(zhàn)。

1)如何安全準(zhǔn)確地統(tǒng)計(jì)數(shù)據(jù)流行度。若使用數(shù)據(jù)哈希值（如SHA-256 值）進(jìn)行流行度檢測(cè)，不流行數(shù)據(jù)易受到離線字典攻擊。若使用隨機(jī)標(biāo)簽[9]進(jìn)行流行度檢測(cè)，在不引入第三方服務(wù)器的情況下難以判斷數(shù)據(jù)流行度。

2)如何實(shí)現(xiàn)不流行數(shù)據(jù)的加密去重。由于需要為不流行數(shù)據(jù)提供語義安全，數(shù)據(jù)哈希值不可用于去重檢測(cè)，并且用戶需要使用隨機(jī)密鑰加密不流行數(shù)據(jù)。如何實(shí)現(xiàn)不流行數(shù)據(jù)的跨用戶去重檢測(cè)，并在不同用戶間傳遞隨機(jī)密鑰以實(shí)現(xiàn)加密去重成為設(shè)計(jì)中的關(guān)鍵挑戰(zhàn)。

4.1 流行度檢測(cè)的設(shè)計(jì)思路

針對(duì)第一個(gè)挑戰(zhàn)，本文設(shè)計(jì)了一個(gè)兩步檢測(cè)的方案來安全準(zhǔn)確地統(tǒng)計(jì)數(shù)據(jù)流行度，如圖3 所示。首先，使用外包數(shù)據(jù)的短哈希值進(jìn)行流行度的初步檢測(cè)，旨在過濾掉大量不流行數(shù)據(jù)。短哈希值[26-27]可通過截取哈希值的部分位數(shù)來實(shí)現(xiàn)（如截取SHA-256 值的前13 位）。由于短哈希值具有較高的沖突率，敵手無法基于短哈希值進(jìn)行字典攻擊。然而，當(dāng)數(shù)據(jù)量較大時(shí)，統(tǒng)計(jì)大量短哈希值的所有者數(shù)量可能會(huì)給云服務(wù)器帶來較大的內(nèi)存開銷。為此，本文在初步檢測(cè)中使用了CM-sketch 算法，其特點(diǎn)是可以基于固定長(zhǎng)度的內(nèi)存空間進(jìn)行流行度統(tǒng)計(jì)，有利于系統(tǒng)的可擴(kuò)展性。即使數(shù)據(jù)量不斷增加，用于統(tǒng)計(jì)流行度的內(nèi)存空間仍可保持不變。

圖3 方案流程

CM-sketch 的統(tǒng)計(jì)結(jié)果存在一定誤差，與真實(shí)結(jié)果相比可能偏大。若CM-sketch 的統(tǒng)計(jì)值vm小于流行度閾值t，則數(shù)據(jù)一定不流行；若vm大于或等于t，需要進(jìn)行后續(xù)檢測(cè)。在后續(xù)檢測(cè)中，云服務(wù)器與用戶執(zhí)行Merkle Puzzles 協(xié)議以檢測(cè)外包數(shù)據(jù)的哈希值（如SHA-256 值）是否與現(xiàn)有流行數(shù)據(jù)的哈希值匹配。若用戶可恢復(fù)出正確的pti[0]，則數(shù)據(jù)流行；否則，數(shù)據(jù)不流行。在后續(xù)檢測(cè)中，云服務(wù)器可準(zhǔn)確判斷數(shù)據(jù)是否流行。

4.2 不流行數(shù)據(jù)加密去重的設(shè)計(jì)思路

云服務(wù)器若檢測(cè)到外包數(shù)據(jù)是流行數(shù)據(jù)，可基于CE 實(shí)現(xiàn)加密去重；若檢測(cè)到外包數(shù)據(jù)是不流行數(shù)據(jù)，如圖3 所示，可基于sPAKE 協(xié)議進(jìn)行去重檢測(cè)，并在用戶間傳遞隨機(jī)密鑰，以實(shí)現(xiàn)不流行數(shù)據(jù)的加密去重。假設(shè)用戶U的外包文件為F，云服務(wù)器索引短哈希值sh(F)對(duì)應(yīng)的不流行數(shù)據(jù)的用戶列表為（云服務(wù)器的存儲(chǔ)結(jié)構(gòu)如圖4 所示），要求U與使用數(shù)據(jù)哈希值運(yùn)行sPAKE 協(xié)議。協(xié)議結(jié)束后，云服務(wù)器可通過協(xié)議的輸出結(jié)果進(jìn)行去重檢測(cè)，判斷本次數(shù)據(jù)上傳為首次上傳或后續(xù)上傳。若數(shù)據(jù)為首次上傳，用戶執(zhí)行首次上傳的流程；若數(shù)據(jù)為后續(xù)上傳，執(zhí)行密鑰傳遞的數(shù)據(jù)過程在用戶間安全地傳遞隨機(jī)密鑰，實(shí)現(xiàn)不流行數(shù)據(jù)的加密去重。

圖4 云服務(wù)器的存儲(chǔ)結(jié)構(gòu)

5 方案詳細(xì)設(shè)計(jì)

本文方案流程主要分為系統(tǒng)初始化、流行度檢測(cè)、不流行數(shù)據(jù)上傳、流行數(shù)據(jù)上傳和數(shù)據(jù)下載。

5.1 系統(tǒng)初始化

用戶生成各自的RSA 公私鑰對(duì)(pk,sk)。為防止在線字典攻擊，用戶為每個(gè)外包文件設(shè)置一個(gè)參與sPAKE 協(xié)議的數(shù)量上限NP[27]。若用戶在某一時(shí)間段Δ 內(nèi)收到了對(duì)某一個(gè)文件超過NP次的sPAKE請(qǐng)求，則拒絕執(zhí)行協(xié)議。云服務(wù)器CS 設(shè)定系統(tǒng)的安全參數(shù)λ和流行度閾值t。若數(shù)據(jù)的所有者數(shù)量num≥t，則認(rèn)為是流行數(shù)據(jù)；否則，認(rèn)為是不流行數(shù)據(jù)。此外，云服務(wù)器設(shè)定CM-sketch 的參數(shù)。CM-sketch 由一個(gè)二維數(shù)組組成，包含r行、w列，共r×w個(gè)計(jì)數(shù)器。云服務(wù)器發(fā)布用于CM-sketch的r個(gè)獨(dú)立的短哈希函數(shù)，每個(gè)短哈希函數(shù)均可將數(shù)據(jù)對(duì)應(yīng)到CM-sketch 的r行中的一個(gè)計(jì)數(shù)器j(1≤j≤w)上。

5.2 流行度檢測(cè)

流行度檢測(cè)的流程如算法1 所示，具體可分為基于CM-sketch 的初步檢測(cè)和基于Merkle Puzzles的后續(xù)檢測(cè)，詳細(xì)流程如下。

1)基于CM-sketch 的初步檢測(cè)。假設(shè)外包文件為F，用戶U計(jì)算短哈希值sh(F)和并將其發(fā)送至云服務(wù)器CS。CS 將中的每個(gè)值映射到CM-sketch 的r行中的計(jì)數(shù)器上，并將相應(yīng)計(jì)算器的值加1。統(tǒng)計(jì)流行度時(shí)，云服務(wù)器使用r個(gè)計(jì)數(shù)值中的最小值vm作為sh(F)當(dāng)前的流行度統(tǒng)計(jì)值。CM-sketch 的統(tǒng)計(jì)值與真實(shí)結(jié)果相比可能偏大。因此，若vm

2)基于Merkle Puzzles 的后續(xù)檢測(cè)。云服務(wù)器CS在流行數(shù)據(jù)列表中檢索sh(F)（云服務(wù)器的存儲(chǔ)結(jié)構(gòu)如圖4 所示）。若無法檢索到sh(F)，則F是不流行數(shù)據(jù)；否則，CS檢索sh(F)對(duì)應(yīng)的流行數(shù)據(jù)列表中的所有輔助信息[26]（其生成細(xì)節(jié)見5.3.4 節(jié)），其中表示文件哈希值。CS發(fā)送至用戶U。U基于文件F的哈希值HF解密，得到隨機(jī)值集合，計(jì)算哈希值并返回CS。CS檢查是否存在。若存在，說明F為流行數(shù)據(jù)；否則，F(xiàn)為不流行數(shù)據(jù)。至此，流行度檢測(cè)結(jié)束，CS可精確統(tǒng)計(jì)文件F的流行度。

算法1流行度檢測(cè)

5.3 不流行數(shù)據(jù)上傳

不流行數(shù)據(jù)上傳的流程包括去重檢測(cè)、數(shù)據(jù)首次上傳、數(shù)據(jù)后續(xù)上傳和流行度轉(zhuǎn)換。

5.3.1 去重檢測(cè)

去重檢測(cè)的流程如算法2 所示。若檢測(cè)到文件F不流行，云服務(wù)器CS索引sh(F)對(duì)應(yīng)的所有不流行數(shù)據(jù)的用戶列表，在每個(gè)列表中選擇一個(gè)當(dāng)前在線的用戶組成檢查者列表，要求U與中的用戶運(yùn)行sPAKE 協(xié)議。在sPAKE 協(xié)議中，U輸入文件F的哈希值HF，每個(gè)Ui輸入各自的文件哈希值，協(xié)議中的通信數(shù)據(jù)均由CS轉(zhuǎn)發(fā)，用戶間不需要直接通信。協(xié)議結(jié)束后，每個(gè)Ui得到sPAKE 協(xié)議的輸出值Ki，U得到輸出值列表，U和將輸出值發(fā)送至CS。CS 收到U發(fā)送的發(fā)送的后，檢查是否存在=Kj。若存在，說明U的外包文件F與Uj此前上傳的文件相同，U執(zhí)行數(shù)據(jù)后續(xù)上傳的流程；否則，U執(zhí)行數(shù)據(jù)首次上傳的流程。

算法2去重檢測(cè)

5.3.2 數(shù)據(jù)首次上傳

用戶U生成收斂密鑰kc=CE.KG(F)，對(duì)F進(jìn)行收斂加密得到收斂密文CF=CE.Enc(kc,F)，計(jì)算哈希值HCE=H(CF)；生成隨機(jī)密鑰kr←{0,1}λ和隨機(jī)值s←{0,1}λ，對(duì)F進(jìn)行隨機(jī)加密得到Cr=Enc(kr,F)；計(jì)算所有權(quán)證明值pF=H(s,F)；上傳Cr至CS，本地存儲(chǔ)(HF,kr,kc,pF,s,HCE)。

5.3.3 數(shù)據(jù)后續(xù)上傳

數(shù)據(jù)后續(xù)上傳的流程如算法3 所示。方案實(shí)現(xiàn)了不流行數(shù)據(jù)的客戶端加密去重，若數(shù)據(jù)為后續(xù)上傳，則不需要用戶U上傳完整的數(shù)據(jù)內(nèi)容，僅需進(jìn)行所有權(quán)證明和密鑰驗(yàn)證的過程，可有效節(jié)省系統(tǒng)的通信開銷。在后續(xù)上傳中，CS發(fā)送U的公鑰pkU至檢查者列表中的Uj。Uj計(jì)算Ck=kr⊕pF和Cs=并將其返回至CS，二者用于密鑰傳遞和所有權(quán)證明。CS將(Ck,Cs)轉(zhuǎn)發(fā)至U。U使用私鑰skU解密Cs得到；使用s和F計(jì)算所有權(quán)證明值pF=H(s,F)，恢復(fù)隨機(jī)密鑰k r=Ck⊕pF；計(jì)算收斂密鑰kc=CE.KG(F)和哈希值HCE=H(CF)；本地存儲(chǔ)(HF,kr,kc,pF,s,HCE)。

算法3數(shù)據(jù)后續(xù)上傳

為防止密鑰傳遞時(shí)出現(xiàn)偽造情況，方案設(shè)計(jì)了密鑰驗(yàn)證過程。U使用kr計(jì)算隨機(jī)密文=Enc(kr,F)，計(jì)算哈希值HC=并發(fā)送至CS。CS檢索本地存儲(chǔ)的隨機(jī)密文Cr，驗(yàn)證HC是否與H(Cr)相等。若不相等，說明存在密鑰偽造攻擊，CS不進(jìn)行數(shù)據(jù)去重以防止數(shù)據(jù)完整性被破壞；若相等，將U加入用戶列表當(dāng)中，并將文件的所有者數(shù)量num 加1。若此時(shí)num 小于t，上傳過程結(jié)束；若num 等于t，表明此次數(shù)據(jù)上傳后F變?yōu)榱餍袛?shù)據(jù)，CS需與U進(jìn)行流行度轉(zhuǎn)換。

5.3.4 流行度轉(zhuǎn)換

在流行度轉(zhuǎn)換中，用戶U發(fā)送收斂密文CF至CS，CS進(jìn)行如下的密文驗(yàn)證過程。CS 計(jì)算哈希值H(CF)發(fā)送至Uj，Uj檢查H(CF)與本地存儲(chǔ)的HCE是否相等。若不相等，可能存在文件偽造攻擊，CS 不進(jìn)行數(shù)據(jù)去重以防止數(shù)據(jù)完整性被破壞；若相等，說明U與Uj計(jì)算的收斂密文一致，云服務(wù)器存儲(chǔ)CF，并刪除此前存儲(chǔ)的隨機(jī)密文Cr以節(jié)省存儲(chǔ)開銷。最后，U生成隨機(jī)值rM←{0,1}λ，計(jì)算輔助信息pt=(H(HF,rM),Enc(HF,rM))并發(fā)送至CS，用于后續(xù)其他用戶的流行度檢測(cè)。

5.4 流行數(shù)據(jù)上傳

若外包文件F是流行數(shù)據(jù)，方案可實(shí)現(xiàn)客戶端去重，用戶U只需與云服務(wù)器CS 進(jìn)行如下的所有權(quán)證明[9]。CS生成隨機(jī)種子u發(fā)送至U。U計(jì)算收斂密文CF，根據(jù)u生成隨機(jī)索引序列，計(jì)算所有權(quán)證明值pF=H(H(CF[u1]),H(CF[u2]),…,并返回至CS。CS 基于本地存儲(chǔ)的收斂密文CF與判斷pF是否正確。若正確，CS將U加入所有者列表中，U存儲(chǔ)收斂密鑰kc；否則，所有權(quán)證明失敗。

5.5 數(shù)據(jù)下載

用戶U向CS發(fā)出文件F的下載請(qǐng)求。CS根據(jù)F的流行情況返回收斂密文CF或隨機(jī)密文Cr。U使用kc或kr解密CF或Cr以恢復(fù)F，并通過驗(yàn)證H(F)與HF是否相等來檢測(cè)數(shù)據(jù)完整性是否被破壞。

6 安全性分析

本節(jié)分析了方案的正確性以及在內(nèi)部敵手和外部敵手攻擊下的安全性并做出如下安全假設(shè)。1)方案中使用的對(duì)稱加密和RSA 加密具有語義安全性；2)方案中使用的哈希函數(shù)（短哈希函數(shù)除外）滿足抗碰撞性，且可看作隨機(jī)預(yù)言機(jī)；3)方案中的sPAKE 協(xié)議是安全的，若參與協(xié)議的雙方輸入不同，則無法獲取對(duì)方輸入的任何信息；若雙方輸入相同，則可得到相同的協(xié)議輸出結(jié)果。

6.1 正確性分析

本節(jié)分析方案在不流行數(shù)據(jù)首次上傳、后續(xù)上傳以及流行數(shù)據(jù)上傳3 種情況下的解密正確性。

在不流行數(shù)據(jù)的首次上傳中，用戶U本地安全存儲(chǔ)了收斂密鑰kc和隨機(jī)密鑰kr?；趥鹘y(tǒng)對(duì)稱加密算法和CE 的解密正確性，下載數(shù)據(jù)時(shí)U可使用kc或kr恢復(fù)正確的數(shù)據(jù)內(nèi)容。在不流行數(shù)據(jù)的后續(xù)上傳中，U收到CS發(fā)送的Ck和Cs?；赗SA 解密的正確性，擁有正確私鑰的U可恢復(fù)隨機(jī)值s。若擁有完整的數(shù)據(jù)內(nèi)容，U可計(jì)算出收斂密鑰kc和所有權(quán)證明值pF=H(s,F)，并恢復(fù)出隨機(jī)密鑰kr。因此，U可通過方案中的密鑰傳遞過程得到正確的隨機(jī)密鑰kr和收斂密鑰kc，在數(shù)據(jù)下載時(shí)可使用kc或kr恢復(fù)正確的數(shù)據(jù)內(nèi)容。流行數(shù)據(jù)上傳時(shí)，U本地存儲(chǔ)了收斂密鑰kc，下載數(shù)據(jù)時(shí)可使用kc恢復(fù)正確的數(shù)據(jù)內(nèi)容。

6.2 內(nèi)部敵手的安全性分析

本節(jié)分析方案在內(nèi)部敵手攻擊下的安全性。根據(jù)3.2 節(jié)描述的威脅模型，內(nèi)部敵手是誠實(shí)但好奇的云服務(wù)器或用戶?；趕PAKE 協(xié)議[11]的安全性，參與協(xié)議的誠實(shí)用戶不會(huì)獲取其他用戶的任何數(shù)據(jù)信息。因此，本節(jié)中的內(nèi)部敵手AI指誠實(shí)但好奇的云服務(wù)器。本節(jié)分別從流行度檢測(cè)的安全性、流行數(shù)據(jù)的收斂安全性和不流行數(shù)據(jù)的語義安全性三方面進(jìn)行安全性分析。

6.2.1 流行度檢測(cè)的安全性

在流行度檢測(cè)中，AI可得到短哈希值sh(F)、和哈希值集合。由于短哈希值具有高碰撞率，AI無法將短哈希值與用戶文件一一對(duì)應(yīng)，因此無法通過離線字典攻擊恢復(fù)數(shù)據(jù)信息。由于隨機(jī)值對(duì)AI保密，且哈希函數(shù)可看作隨機(jī)預(yù)言機(jī)，與等長(zhǎng)的隨機(jī)比特串具有不可區(qū)分性，AI無法獲得數(shù)據(jù)信息。

6.2.2 流行數(shù)據(jù)的收斂安全性

對(duì)于流行文件F，AI可得到其收斂密文CF、密文哈希值HCE、所有權(quán)證明值pF和輔助信息pt。基于收斂安全性[5]的定義，AI通過(CF,HCE)恢復(fù)不可預(yù)測(cè)的流行數(shù)據(jù)的概率是可忽略的；pF為CF抽樣后的哈希值，同樣不泄露不可預(yù)測(cè)數(shù)據(jù)的任何信息；pt[0]和pt[1]分別為隨機(jī)值rM的哈希值和對(duì)稱密文，由于哈希函數(shù)可看作隨機(jī)預(yù)言機(jī)且對(duì)稱加密具有語義安全性，因此pt 與等長(zhǎng)的隨機(jī)比特串具有不可區(qū)分性，不泄露數(shù)據(jù)信息。

6.2.3 不流行數(shù)據(jù)的語義安全性

本節(jié)通過定義安全游戲的方式形式化分析不流行數(shù)據(jù)的語義安全性。安全游戲?qū)⒎桨傅陌踩砸?guī)約到對(duì)稱加密、RSA 加密和密碼本加密的安全性上。本節(jié)定義安全游戲G0模擬真實(shí)場(chǎng)景下的方案，其中敵手A 模擬誠實(shí)但好奇的云服務(wù)器，挑戰(zhàn)者C模擬誠實(shí)執(zhí)行協(xié)議的用戶。本節(jié)將安全游戲中的哈希函數(shù)看作隨機(jī)預(yù)言機(jī)，挑戰(zhàn)者C 計(jì)算哈希值時(shí)需詢問隨機(jī)預(yù)言機(jī)。對(duì)于每次詢問，預(yù)言機(jī)將返回一個(gè)均勻隨機(jī)的輸出。對(duì)于重復(fù)出現(xiàn)的詢問，預(yù)言機(jī)將返回相同的結(jié)果。安全游戲G0的具體描述如下。

1)初始化階段。挑戰(zhàn)者生成隨機(jī)密鑰kr、隨機(jī)種子s和RSA 公私鑰對(duì)(pku,sku)。

2)挑戰(zhàn)階段。敵手A 輸出2 個(gè)等長(zhǎng)的挑戰(zhàn)明文(M0,M1)。C 隨機(jī)選擇b∈R{0,1}，計(jì)算PF=H(s,Mb)，返回Cr=Enc(kr,Mb)、Cs=和Ck=kr⊕pF至A。

3)猜測(cè)階段。A 輸出b'，如果b=b'，則A 贏得G0。將A 在G0中具有的概率優(yōu)勢(shì)定義為Adv(A)=。

定義1若對(duì)于任意的概率多項(xiàng)式時(shí)間（PPT,probabilistic polynomial time）敵手A，存在一個(gè)可忽略的值ε，滿足Adv(A)≤ε，則認(rèn)為本文方案中誠實(shí)但好奇的云服務(wù)器無法破壞不流行數(shù)據(jù)的語義安全性。

定理1若方案中使用的對(duì)稱加密和RSA 加密是語義安全的，則在隨機(jī)預(yù)言機(jī)模型下本文方案中的云服務(wù)器無法破壞不流行數(shù)據(jù)的語義安全性。

這里通過定義多個(gè)不可區(qū)分的安全博弈游戲來證明定理1。

6.3 外部敵手的安全性分析

外部敵手AE可通過截獲通信數(shù)據(jù)并發(fā)起字典攻擊破壞數(shù)據(jù)機(jī)密性；通過篡改數(shù)據(jù)內(nèi)容破壞數(shù)據(jù)完整性；發(fā)起密鑰和文件偽造攻擊破壞數(shù)據(jù)完整性；使用部分?jǐn)?shù)據(jù)內(nèi)容進(jìn)行所有權(quán)欺騙攻擊試圖獲取數(shù)據(jù)所有權(quán)或篡改數(shù)據(jù)流行度，本節(jié)針對(duì)上述攻擊進(jìn)行安全性分析。

1)字典攻擊。不流行數(shù)據(jù)均為隨機(jī)加密后的密文，基于對(duì)稱加密的語義安全性，AE無法進(jìn)行離線字典攻擊。對(duì)于不可預(yù)測(cè)的流行數(shù)據(jù)，基于CE 提供的收斂安全性，AE無法運(yùn)行離線字典攻擊。由于用戶為每個(gè)文件設(shè)置了進(jìn)行sPAKE 協(xié)議次數(shù)的上限NP，AE無法通過頻繁運(yùn)行sPAKE 協(xié)議進(jìn)行在線字典攻擊。

2)數(shù)據(jù)篡改攻擊。AE可在用戶下載數(shù)據(jù)時(shí)截獲通信數(shù)據(jù)并進(jìn)行篡改。用戶下載數(shù)據(jù)后可通過驗(yàn)證H(F)與HF是否相等來檢測(cè)數(shù)據(jù)完整性是否被損壞。若檢測(cè)到完整性損壞，用戶可重新下載數(shù)據(jù)，并刪除已被篡改的數(shù)據(jù)。

3)密鑰偽造攻擊。在不流行數(shù)據(jù)上傳過程中，若AE為sPAKE 協(xié)議中的檢查者，則使用偽造的密鑰進(jìn)行密鑰傳遞發(fā)起密鑰偽造攻擊，試圖破壞其他用戶的數(shù)據(jù)完整性。在密鑰驗(yàn)證過程中，數(shù)據(jù)上傳者發(fā)送密文哈希值HC至云服務(wù)器?；诠：瘮?shù)的抗碰撞性，云服務(wù)器可通過比對(duì)哈希值識(shí)別出密鑰偽造攻擊，并中止數(shù)據(jù)去重。

4)文件偽造攻擊。在流行度轉(zhuǎn)換過程中，AE可通過上傳正確的文件哈希值HF和偽造的收斂密文發(fā)起文件偽造攻擊，試圖破壞數(shù)據(jù)完整性。在密文驗(yàn)證的過程中，云服務(wù)器計(jì)算哈希值H(CF)并發(fā)送至檢查者Uj，Uj驗(yàn)證H(CF)是否與本地存儲(chǔ)的HCE相等，并將比較結(jié)果返回給云服務(wù)器?；诠：瘮?shù)的抗碰撞性，云服務(wù)器可在密文驗(yàn)證過程中檢測(cè)出文件偽造攻擊，通過中止數(shù)據(jù)去重防止數(shù)據(jù)完整性被破壞。

5)所有權(quán)欺騙攻擊。在流行數(shù)據(jù)上傳的過程中，AE需要與云服務(wù)器進(jìn)行所有權(quán)證明，基于文獻(xiàn)[9]中的安全分析，僅擁有部分?jǐn)?shù)據(jù)內(nèi)容的AE通過所有權(quán)證明的概率是可忽略的。在不流行數(shù)據(jù)上傳的過程中，AE需要擁有完整的數(shù)據(jù)內(nèi)容才能計(jì)算出H(F,s)以恢復(fù)密鑰kr?；诠：瘮?shù)的雪崩效應(yīng)，僅擁有部分?jǐn)?shù)據(jù)內(nèi)容的AE無法恢復(fù)kr，從而無法進(jìn)行所有權(quán)欺騙攻擊。

綜上，外部敵手無法通過上述攻擊方式破壞數(shù)據(jù)完整性和機(jī)密性。

6.4 與現(xiàn)有方案的安全性對(duì)比

表3 將本文方案與現(xiàn)有基于流行度的加密去重方案的安全性進(jìn)行了對(duì)比。與文獻(xiàn)[6-7]相比，本文方案引入了所有權(quán)證明和完整性驗(yàn)證，可有效對(duì)抗所有權(quán)欺騙攻擊并可提供數(shù)據(jù)完整性。與文獻(xiàn)[8]相比，本文在不流行數(shù)據(jù)上傳的過程中設(shè)計(jì)了密鑰傳遞過程，可實(shí)現(xiàn)不流行數(shù)據(jù)的加密去重以節(jié)省存儲(chǔ)空間（表3 中的數(shù)據(jù)去重指同時(shí)實(shí)現(xiàn)流行數(shù)據(jù)和不流行數(shù)據(jù)的去重）。與文獻(xiàn)[9]相比，本文使用短哈希值進(jìn)行流行度檢測(cè)，可為不流行數(shù)據(jù)提供語義安全。另外，本文方案最關(guān)鍵的特性是在不需要部署任何第三方服務(wù)器的情況下，實(shí)現(xiàn)了數(shù)據(jù)流行度的安全統(tǒng)計(jì)以及不流行數(shù)據(jù)的加密去重，這使本文方案不存在性能瓶頸和單點(diǎn)故障等缺陷。

表3 安全性對(duì)比

7 性能分析

本節(jié)分別從算法復(fù)雜度和實(shí)驗(yàn)評(píng)估兩方面分析方案的性能。

7.1 算法復(fù)雜度

表4 分析了不流行數(shù)據(jù)首次/后續(xù)上傳和流行度轉(zhuǎn)換3 種不同情況下的客戶端計(jì)算開銷，鑒于流行數(shù)據(jù)上傳的過程較為簡(jiǎn)單，且本文方案與現(xiàn)有方案[6,8-9]的開銷幾乎相同，因此這里不做分析。為方便表述，方案中哈希值、加密密鑰和隨機(jī)值的大小統(tǒng)一用λ表示，lF和lλ分別表示外包數(shù)據(jù)大小和隨機(jī)值s的RSA 密文大小；SE、H、TE、HE、SS、PoW、sPAKE、SK、PT 分別表示對(duì)稱加密、哈希函數(shù)、門限加密[6]、同態(tài)加密[8]、秘密共享[9]、所有權(quán)證明[8,13]、sPAKE[11]、RSA 解密和生成輔助信息pt 的計(jì)算開銷。由表4 可以看出，現(xiàn)有方案在不同情況下的計(jì)算開銷類似，而本文方案在3 種不同情況下的計(jì)算開銷則略有不同。由于實(shí)現(xiàn)了不流行數(shù)據(jù)的客戶端去重，本文方案中流行度轉(zhuǎn)換和不流行數(shù)據(jù)后續(xù)上傳的計(jì)算開銷略高于不流行數(shù)據(jù)首次上傳。

表4 客戶端計(jì)算開銷

另外，與現(xiàn)有方案[6,8-9]相比，本文方案數(shù)據(jù)上傳的計(jì)算開銷差距不大，都主要集中在對(duì)外包數(shù)據(jù)的哈希和對(duì)稱加密上；本文方案增加的計(jì)算開銷主要在于sPAKE 協(xié)議的執(zhí)行和密文/密鑰的驗(yàn)證過程。由7.2.1 節(jié)的實(shí)驗(yàn)結(jié)果可知，sPAKE 協(xié)議對(duì)方案的性能影響不大。在不流行數(shù)據(jù)后續(xù)上傳中，由于引入了密鑰驗(yàn)證的過程，本文方案與現(xiàn)有方案[6,8-9]相比增加了一次數(shù)據(jù)哈希的操作，這增加了一定的計(jì)算開銷。本文方案引入的計(jì)算開銷主要用于消除系統(tǒng)對(duì)第三方服務(wù)器的依賴，提高方案在真實(shí)場(chǎng)景中的應(yīng)用價(jià)值。

7.2 實(shí)驗(yàn)評(píng)估

本節(jié)通過仿真實(shí)驗(yàn)對(duì)本文方案進(jìn)行了性能評(píng)估。實(shí)驗(yàn)使用戴爾Inspiron 5680 臺(tái)式計(jì)算機(jī)模擬實(shí)現(xiàn)了方案中的云服務(wù)器和用戶，其配備有3.20 GHz Intel(R)Core(TM)i7-8700 六核處理器和8 GB 運(yùn)行內(nèi)存，運(yùn)行操作系統(tǒng)為64 bit Ubuntu 20.04.1。對(duì)于加密去重系統(tǒng)來說，存儲(chǔ)效率和加密上傳的時(shí)間開銷是2 個(gè)關(guān)鍵的性能指標(biāo)。本文方案同時(shí)實(shí)現(xiàn)了流行數(shù)據(jù)和不流行數(shù)據(jù)的去重，達(dá)到了最佳的去重效率。因此，本節(jié)主要針對(duì)方案中數(shù)據(jù)上傳的時(shí)間開銷進(jìn)行分析。本節(jié)中的所有實(shí)驗(yàn)結(jié)果均為50 次以上實(shí)驗(yàn)結(jié)果的平均值。實(shí)驗(yàn)中短哈希值位數(shù)為13，哈希函數(shù)使用SHA-256 算法，對(duì)稱加密使用AES，密鑰長(zhǎng)度為256 位。

7.2.1 Merkle Puzzles 和sPAKE 的性能分析

本文方案的數(shù)據(jù)上傳過程中，Merkle Puzzles和sPAKE 的時(shí)間開銷會(huì)隨著系統(tǒng)中的數(shù)據(jù)量和用戶量而變化。本節(jié)首先測(cè)試了不同文件數(shù)量下Merkle Puzzles 的時(shí)間開銷，如圖5 所示。從圖5可以看出即使文件數(shù)量為1 024 個(gè)，Merkle Puzzles的時(shí)間開銷也僅為210 μs 左右。由于Merkle Puzzles僅需對(duì)長(zhǎng)度較短的隨機(jī)值進(jìn)行對(duì)稱加解密和哈希操作，這部分的時(shí)間開銷極小，在數(shù)據(jù)加密上傳的整體時(shí)間開銷中占比極低，幾乎可忽略不計(jì)。

圖5 不同文件數(shù)量下Merkle Puzzles 的時(shí)間開銷

此外，本節(jié)測(cè)試了執(zhí)行不同次數(shù)sPAKE 的時(shí)間開銷，如圖6 所示。從圖6 可以看出，相比于Merkle Puzzles，sPAKE 的時(shí)間開銷明顯更大。當(dāng)用戶執(zhí)行160 次sPAKE 協(xié)議時(shí)，時(shí)間開銷約為4.2 s。雖然本文使用了目前已知最高效的sPAKE 協(xié)議[11]，但sPAKE 協(xié)議的參與方仍需執(zhí)行2 次冪運(yùn)算。當(dāng)sPAKE 協(xié)議的執(zhí)行次數(shù)較多時(shí)，仍會(huì)產(chǎn)生一定的時(shí)間開銷。但是，本文方案為防止敵手的在線字典攻擊，需要對(duì)執(zhí)行sPAKE 協(xié)議的次數(shù)進(jìn)行限制。因此，系統(tǒng)中執(zhí)行sPAKE 協(xié)議的時(shí)間開銷的上限是固定的。當(dāng)系統(tǒng)設(shè)定參與sPAKE 協(xié)議的數(shù)量上限為80時(shí)，執(zhí)行sPAKE 協(xié)議的時(shí)間開銷的上限約為2.1 s?？傮w而言，由于次數(shù)限制，執(zhí)行sPAKE 協(xié)議的時(shí)間開銷在整體數(shù)據(jù)加密上傳的過程中占比不大，這一點(diǎn)可以通過7.2.2 節(jié)中的實(shí)驗(yàn)分析看出。

圖6 執(zhí)行不同次數(shù)sPAKE 協(xié)議的時(shí)間開銷

7.2.2 數(shù)據(jù)加密上傳的時(shí)間開銷

本文方案中的數(shù)據(jù)加密上傳可分為4 種情況：不流行數(shù)據(jù)首次上傳，不流行數(shù)據(jù)后續(xù)上傳、流行度轉(zhuǎn)換和流行數(shù)據(jù)上傳。7.2.2 節(jié)和7.2.3 節(jié)的實(shí)驗(yàn)中均分別將Merkle Puzzles 使用的文件數(shù)量和執(zhí)行sPAKE 協(xié)議的次數(shù)設(shè)定為20 個(gè)和5 次。

首先，本節(jié)使用不同大小的測(cè)試文件對(duì)這4 種情況下的數(shù)據(jù)加密上傳的時(shí)間開銷進(jìn)行了評(píng)估，如圖7 所示。從圖7 可以看出，當(dāng)數(shù)據(jù)變得流行后，數(shù)據(jù)加密上傳的時(shí)間開銷明顯降低。當(dāng)測(cè)試文件的大小為1 024 MB 時(shí)，流行數(shù)據(jù)上傳的時(shí)間開銷僅為不流行數(shù)據(jù)首次上傳的42.6%。流行度轉(zhuǎn)換的時(shí)間開銷較高，原因在于流行度轉(zhuǎn)換過程中需要生成隨機(jī)密文以進(jìn)行密鑰驗(yàn)證和密文驗(yàn)證，并且需要加密上傳收斂密文至云服務(wù)器。但是在數(shù)據(jù)上傳過程中，系統(tǒng)大概率僅需進(jìn)行一次流行度轉(zhuǎn)換過程。因此，這一過程的時(shí)間開銷對(duì)大多數(shù)用戶的影響較小。

圖7 不同文件大小對(duì)數(shù)據(jù)加密上傳的時(shí)間開銷的影響

本節(jié)還統(tǒng)計(jì)了數(shù)據(jù)加密上傳的時(shí)間開銷中的各部分占比情況，如圖8 所示，其中，P、UP_F、UP_S 和Conv 分別表示流行數(shù)據(jù)上傳、不流行數(shù)據(jù)首次上傳、不流行數(shù)據(jù)后續(xù)上傳和流行度轉(zhuǎn)換4 種情況。由圖8 可知，對(duì)于流行數(shù)據(jù)上傳而言，收斂加密占比極高，約占81%。在其他3 種情況中，數(shù)據(jù)加密（收斂加密+隨機(jī)加密）的時(shí)間開銷分別占總開銷的66%、50%和49%。在不流行數(shù)據(jù)后續(xù)上傳和流行度轉(zhuǎn)換過程中，用戶需要在密鑰驗(yàn)證過程中計(jì)算隨機(jī)密文的哈希值，這部分的時(shí)間開銷占比較高，約占總開銷的20%。方案中引入的所有權(quán)證明和sPAKE 協(xié)議的時(shí)間開銷相對(duì)于其他部分占比較低，在不流行數(shù)據(jù)后續(xù)上傳和流行度轉(zhuǎn)換的過程中占比均約為9%。

圖8 數(shù)據(jù)加密上傳的時(shí)間開銷中各部分的占比情況

本節(jié)還評(píng)估了執(zhí)行不同次數(shù)sPAKE 協(xié)議對(duì)數(shù)據(jù)加密上傳的時(shí)間開銷的影響，如圖9 所示。從圖9可以看出，不同次數(shù)sPAKE 協(xié)議的執(zhí)行對(duì)不流行數(shù)據(jù)后續(xù)上傳的時(shí)間開銷的影響有限。當(dāng)測(cè)試文件的大小為1 024 MB，執(zhí)行5 次sPAKE 協(xié)議時(shí)，不流行數(shù)據(jù)后續(xù)上傳的時(shí)間開銷約為執(zhí)行160 次sPAKE協(xié)議時(shí)的時(shí)間開銷的90%，二者差距不大。

圖9 執(zhí)行不同次數(shù)sPAKE 協(xié)議對(duì)數(shù)據(jù)加密上傳的時(shí)間開銷的影響

7.2.3 與現(xiàn)有方案的性能對(duì)比

本節(jié)對(duì)比分析了本文方案與文獻(xiàn)[6,8]方案的不流行數(shù)據(jù)加密上傳的時(shí)間開銷，如圖10 所示。由于本文方案未部署第三方服務(wù)器，引入了sPAKE、Merkle Puzzles 以及密鑰/密文驗(yàn)證等過程，因此與現(xiàn)有方案相比增加了一些計(jì)算開銷。本文方案的不流行數(shù)據(jù)上傳分為首次上傳和后續(xù)上傳，文獻(xiàn)[6,8]方案中不流行數(shù)據(jù)上傳不區(qū)分首次上傳和后續(xù)上傳。本文方案的首次上傳過程并未引入過多的計(jì)算開銷，但后續(xù)上傳過程中需要進(jìn)行密鑰傳遞和密鑰驗(yàn)證的過程，與現(xiàn)有方案相比增加了一定的計(jì)算開銷。當(dāng)測(cè)試文件大小為1 024 MB 時(shí)，與現(xiàn)有方案相比，本文方案的不流行數(shù)據(jù)首次上傳和后續(xù)上傳分別增加了約1%和13%的時(shí)間開銷。

圖10 不同方案的不流行數(shù)據(jù)加密上傳的時(shí)間開銷

8 結(jié)束語

本文提出了一個(gè)無第三方服務(wù)器的基于數(shù)據(jù)流行度的加密去重方案，在不需要部署任何第三方服務(wù)器的情況下實(shí)現(xiàn)了數(shù)據(jù)流行度的精確統(tǒng)計(jì)，并為不流行數(shù)據(jù)提供了語義安全和加密去重。首先，基于CM-sketch 算法實(shí)現(xiàn)了數(shù)據(jù)流行度的初步統(tǒng)計(jì)；然后，基于Merkle Puzzles 協(xié)議實(shí)現(xiàn)了數(shù)據(jù)流行度的精確統(tǒng)計(jì)；最后，通過用戶間執(zhí)行sPAKE 協(xié)議實(shí)現(xiàn)了不流行數(shù)據(jù)的客戶端加密去重。本文還考慮了加密去重場(chǎng)景下常見的字典攻擊、文件偽造攻擊和所有權(quán)欺騙攻擊等，在所提方案中設(shè)計(jì)了密鑰驗(yàn)證和密文驗(yàn)證的過程，并結(jié)合了速率限制和所有權(quán)證明等過程為用戶數(shù)據(jù)提供了全面的安全保障。如何進(jìn)一步提高方案的數(shù)據(jù)加密上傳的性能是接下來需要研究的重要課題。