無第三方服務器的基于數據流行度的加密去重方案

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

0 引言

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

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

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

表1 現有方案及其特點

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

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

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

2)通過在用戶間執行sPAKE 協議，本文方案實現了不流行數據的去重檢測和用戶間的密鑰傳遞，云服務器可同時對流行數據和不流行數據實現客戶端加密去重，最大限度地節省了系統的通信開銷和存儲開銷。

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

1 相關工作

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

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

2 預備知識

2.1 CM-sketch

CM-sketch 可在誤差較小的前提下利用有限的內存空間描述數據的頻率特征，其內部的數據結構是一個w×d的二維數組，其中，參數ε δ、表示在 1?δ的概率下統計結果的總誤差小于ε。CM-sketch 算法主要由以下3 個算法組成。

1)Setup(ε,δ)。輸入參數,ε，δ初始化一個w×d的二維數組count，將所有元素值置0；隨機選定d個兩兩獨立的哈希函數h1(?),h2(?),…,hd(?)，其中hi(?)(i∈[1,d])的輸出結果的長度為w。

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

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

2.2 sPAKE

sPAKE[11,25]是傳統密鑰協商的一個擴展。當運行協議的雙方共享同一個口令時，可協商出相同的密鑰；若雙方口令不同，則各自得到一個隨機密鑰，雙方均無法獲得對方密鑰的任何信息。

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

圖1 sPAKE 協議流程

2.3 Merkle Puzzles

Merkle Puzzles 基于對稱密碼原語實現了安全的密鑰協商。假設協商密鑰的雙方分別為Alice 和Bob，他們執行以下步驟協商密鑰。

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

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

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

本文基于上述設計思路和Yu 等[26]對Merkle Puzzles 的使用方式，將Merkle Puzzles 應用于加密去重場景下的數據流行度統計中。

2.4 收斂加密

收斂加密[4]使用消息內容的哈希值作為密鑰加密數據以實現密文去重，由以下3 個算法組成。

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

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

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

3 系統模型與定義

3.1 系統架構

本文方案的系統架構如圖2 所示，包括用戶U和云服務器CS。CS 為U提供數據存儲服務，基于數據的所有者數量將其劃分為流行數據和不流行數據，可對U的外包數據進行去重以節省存儲開銷。U外包加密數據至CS 以節省本地存儲開銷，并且需要在上傳數據后在CS 的協助下與其他上傳數據的用戶運行sPAKE 協議，以確定后續上傳數據的流行情況。

圖2 系統架構

3.2 威脅模型

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

1)內部敵手。內部敵手指系統中誠實但好奇的云服務器和合法用戶，其會誠實地執行方案中設定的協議流程，同時也會試圖窺探用戶的數據信息。

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

3.3 安全目標

本文方案的安全目標如下。

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

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

3.4 符號定義

本文使用的符號及其含義如表2 所示。

表2 符號及其含義

4 設計思路

基于流行度設計加密去重系統存在以下2個挑戰。

1)如何安全準確地統計數據流行度。若使用數據哈希值（如SHA-256 值）進行流行度檢測，不流行數據易受到離線字典攻擊。若使用隨機標簽[9]進行流行度檢測，在不引入第三方服務器的情況下難以判斷數據流行度。

2)如何實現不流行數據的加密去重。由于需要為不流行數據提供語義安全，數據哈希值不可用于去重檢測，并且用戶需要使用隨機密鑰加密不流行數據。如何實現不流行數據的跨用戶去重檢測，并在不同用戶間傳遞隨機密鑰以實現加密去重成為設計中的關鍵挑戰。

4.1 流行度檢測的設計思路

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

圖3 方案流程

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

4.2 不流行數據加密去重的設計思路

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

圖4 云服務器的存儲結構

5 方案詳細設計

本文方案流程主要分為系統初始化、流行度檢測、不流行數據上傳、流行數據上傳和數據下載。

5.1 系統初始化

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

5.2 流行度檢測

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

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

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

算法1流行度檢測

5.3 不流行數據上傳

不流行數據上傳的流程包括去重檢測、數據首次上傳、數據后續上傳和流行度轉換。

5.3.1 去重檢測

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

算法2去重檢測

5.3.2 數據首次上傳

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

5.3.3 數據后續上傳

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

算法3數據后續上傳

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

5.3.4 流行度轉換

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

5.4 流行數據上傳

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

5.5 數據下載

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

6 安全性分析

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

6.1 正確性分析

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

在不流行數據的首次上傳中，用戶U本地安全存儲了收斂密鑰kc和隨機密鑰kr。基于傳統對稱加密算法和CE 的解密正確性，下載數據時U可使用kc或kr恢復正確的數據內容。在不流行數據的后續上傳中，U收到CS發送的Ck和Cs。基于RSA 解密的正確性，擁有正確私鑰的U可恢復隨機值s。若擁有完整的數據內容，U可計算出收斂密鑰kc和所有權證明值pF=H(s,F)，并恢復出隨機密鑰kr。因此，U可通過方案中的密鑰傳遞過程得到正確的隨機密鑰kr和收斂密鑰kc，在數據下載時可使用kc或kr恢復正確的數據內容。流行數據上傳時，U本地存儲了收斂密鑰kc，下載數據時可使用kc恢復正確的數據內容。

6.2 內部敵手的安全性分析

本節分析方案在內部敵手攻擊下的安全性。根據3.2 節描述的威脅模型，內部敵手是誠實但好奇的云服務器或用戶。基于sPAKE 協議[11]的安全性，參與協議的誠實用戶不會獲取其他用戶的任何數據信息。因此，本節中的內部敵手AI指誠實但好奇的云服務器。本節分別從流行度檢測的安全性、流行數據的收斂安全性和不流行數據的語義安全性三方面進行安全性分析。

6.2.1 流行度檢測的安全性

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

6.2.2 流行數據的收斂安全性

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

6.2.3 不流行數據的語義安全性

本節通過定義安全游戲的方式形式化分析不流行數據的語義安全性。安全游戲將方案的安全性規約到對稱加密、RSA 加密和密碼本加密的安全性上。本節定義安全游戲G0模擬真實場景下的方案，其中敵手A 模擬誠實但好奇的云服務器，挑戰者C模擬誠實執行協議的用戶。本節將安全游戲中的哈希函數看作隨機預言機，挑戰者C 計算哈希值時需詢問隨機預言機。對于每次詢問，預言機將返回一個均勻隨機的輸出。對于重復出現的詢問，預言機將返回相同的結果。安全游戲G0的具體描述如下。

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

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

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

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

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

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

6.3 外部敵手的安全性分析

外部敵手AE可通過截獲通信數據并發起字典攻擊破壞數據機密性；通過篡改數據內容破壞數據完整性；發起密鑰和文件偽造攻擊破壞數據完整性；使用部分數據內容進行所有權欺騙攻擊試圖獲取數據所有權或篡改數據流行度，本節針對上述攻擊進行安全性分析。

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

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

3)密鑰偽造攻擊。在不流行數據上傳過程中，若AE為sPAKE 協議中的檢查者，則使用偽造的密鑰進行密鑰傳遞發起密鑰偽造攻擊，試圖破壞其他用戶的數據完整性。在密鑰驗證過程中，數據上傳者發送密文哈希值HC至云服務器。基于哈希函數的抗碰撞性，云服務器可通過比對哈希值識別出密鑰偽造攻擊，并中止數據去重。

4)文件偽造攻擊。在流行度轉換過程中，AE可通過上傳正確的文件哈希值HF和偽造的收斂密文發起文件偽造攻擊，試圖破壞數據完整性。在密文驗證的過程中，云服務器計算哈希值H(CF)并發送至檢查者Uj，Uj驗證H(CF)是否與本地存儲的HCE相等，并將比較結果返回給云服務器。基于哈希函數的抗碰撞性，云服務器可在密文驗證過程中檢測出文件偽造攻擊，通過中止數據去重防止數據完整性被破壞。

5)所有權欺騙攻擊。在流行數據上傳的過程中，AE需要與云服務器進行所有權證明，基于文獻[9]中的安全分析，僅擁有部分數據內容的AE通過所有權證明的概率是可忽略的。在不流行數據上傳的過程中，AE需要擁有完整的數據內容才能計算出H(F,s)以恢復密鑰kr。基于哈希函數的雪崩效應，僅擁有部分數據內容的AE無法恢復kr，從而無法進行所有權欺騙攻擊。

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

6.4 與現有方案的安全性對比

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

表3 安全性對比

7 性能分析

本節分別從算法復雜度和實驗評估兩方面分析方案的性能。

7.1 算法復雜度

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

表4 客戶端計算開銷

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

7.2 實驗評估

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

7.2.1 Merkle Puzzles 和sPAKE 的性能分析

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

圖5 不同文件數量下Merkle Puzzles 的時間開銷

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

圖6 執行不同次數sPAKE 協議的時間開銷

7.2.2 數據加密上傳的時間開銷

本文方案中的數據加密上傳可分為4 種情況：不流行數據首次上傳，不流行數據后續上傳、流行度轉換和流行數據上傳。7.2.2 節和7.2.3 節的實驗中均分別將Merkle Puzzles 使用的文件數量和執行sPAKE 協議的次數設定為20 個和5 次。

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

圖7 不同文件大小對數據加密上傳的時間開銷的影響

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

圖8 數據加密上傳的時間開銷中各部分的占比情況

本節還評估了執行不同次數sPAKE 協議對數據加密上傳的時間開銷的影響，如圖9 所示。從圖9可以看出，不同次數sPAKE 協議的執行對不流行數據后續上傳的時間開銷的影響有限。當測試文件的大小為1 024 MB，執行5 次sPAKE 協議時，不流行數據后續上傳的時間開銷約為執行160 次sPAKE協議時的時間開銷的90%，二者差距不大。

圖9 執行不同次數sPAKE 協議對數據加密上傳的時間開銷的影響

7.2.3 與現有方案的性能對比

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

圖10 不同方案的不流行數據加密上傳的時間開銷

8 結束語

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