賈春福，哈冠雄，武少強，陳杭，李瑞琪

（1.南開大學(xué)網(wǎng)絡(luò)空間安全學(xué)院，天津 300350；2.天津市網(wǎng)絡(luò)與數(shù)據(jù)安全技術(shù)重點實驗室，天津 300350）

1 引言

云計算的飛速發(fā)展讓個人和企業(yè)都越來越傾向于將數(shù)據(jù)外包至云服務(wù)器存儲以節(jié)省本地的數(shù)據(jù)存儲和管理開銷[1-2]。面對海量的外包數(shù)據(jù)，如何實現(xiàn)高效的數(shù)據(jù)存儲成為云服務(wù)提供商面臨的關(guān)鍵問題。數(shù)據(jù)去重[3-4]是提高存儲利用率的有效方法，當(dāng)收到多份相同的數(shù)據(jù)副本時，云服務(wù)器可通過數(shù)據(jù)去重僅存儲其中的非重復(fù)內(nèi)容以節(jié)省存儲開銷。對用戶而言，出于對外包數(shù)據(jù)的機密性和隱私考慮，更希望能夠?qū)?shù)據(jù)在本地加密后上傳至云服務(wù)器，防止自己的數(shù)據(jù)信息被泄露。然而，在傳統(tǒng)的加密算法中，每個用戶使用自己的密鑰加密數(shù)據(jù)，不同用戶間的相同數(shù)據(jù)將被加密為不同的密文，云服務(wù)器無法進(jìn)行去重。

為此，文獻(xiàn)[5]提出了消息鎖加密（MLE,message-locked encryption），其中加密密鑰基于數(shù)據(jù)內(nèi)容生成，擁有相同數(shù)據(jù)的用戶可生成相同的加密密鑰，此特性可用于實現(xiàn)跨用戶的加密去重。但MLE 存在擁有相同數(shù)據(jù)的多個用戶共享同一加密密鑰的特點，使多用戶間的密鑰更新缺乏獨立性。系統(tǒng)中某一數(shù)據(jù)所有者進(jìn)行密鑰更新后，其他數(shù)據(jù)所有者均需同步該更新[6]，這為外包數(shù)據(jù)的密鑰更新帶來了困難。密鑰更新[7-9]是密鑰泄露后有效維持外包數(shù)據(jù)機密性，以及為外包數(shù)據(jù)提供有效訪問控制[10-11]的重要方法。缺少密鑰更新的云存儲系統(tǒng)將在密鑰泄露后的系統(tǒng)健壯性，以及在外包數(shù)據(jù)的訪問控制變更等方面存在嚴(yán)重不足。

收斂加密[12]（CE,convergent encryption）是MLE 中一個最常用的實例，其以數(shù)據(jù)的哈希值作為加密密鑰。下面以收斂加密為例說明基于MLE 的加密去重系統(tǒng)難以進(jìn)行密鑰更新的原因。假設(shè)云服務(wù)器存儲的某一外包數(shù)據(jù)為F，加密密鑰為數(shù)據(jù)本身的哈希值H(F)，其中H(?)表示哈希函數(shù)。當(dāng)H(F)泄露后，F(xiàn)的數(shù)據(jù)所有者需要更新加密密鑰，防止同時截獲密鑰H(F)和外包密文CF的敵手獲得數(shù)據(jù)信息。密鑰更新的過程如圖1 所示，數(shù)據(jù)所有者首先需要將原密文從云服務(wù)器端下載解密得到F；然后選擇一個新的哈希函數(shù)H′(?)作為新的MLE 密鑰生成函數(shù)，生成新的加密密鑰H′(F)，使用新密鑰重新加密數(shù)據(jù)上傳至云服務(wù)器；最后還需要將H′(?)廣播至其他全部數(shù)據(jù)所有者。其他數(shù)據(jù)所有者同樣需要完成下載外包數(shù)據(jù)，重新計算新MLE 密鑰的過程以保證密鑰更新后系統(tǒng)仍可進(jìn)行跨用戶數(shù)據(jù)去重。因此，基于MLE 的加密去重系統(tǒng)的密鑰更新過程非常煩瑣，并且具有較大的計算和通信開銷。

圖1 CE 中的密鑰更新

針對上述問題，本文提出了一種加密去重場景下基于 AONT 和 NTRU 的密鑰更新方案ANRDup，設(shè)計了一個全有或全無轉(zhuǎn)換[13-14]（AONT,all-or-nothing transform）的變體以解決多用戶數(shù)據(jù)去重時密鑰更新的同步問題，引入了一種基于NTRU 的代理重加密方案[15]以降低密鑰更新過程中的系統(tǒng)通信開銷和客戶端計算開銷。ANRDup 利用AONT 將用戶數(shù)據(jù)拆分為用于數(shù)據(jù)去重的修剪包和用于密鑰更新的存根?；贏ONT 的全有或全無特性，密鑰更新時客戶端僅需重加密外包數(shù)據(jù)的存根部分，而用于數(shù)據(jù)去重的修剪包可維持不變，這一特性實現(xiàn)了不同用戶密鑰更新時的獨立性，避免了多用戶密鑰更新時的同步問題。ANRDup中還引入了一種基于NTRU的代理重加密方案，密鑰更新時客戶端僅需計算并上傳一個重加密密鑰至云服務(wù)器，大大提升了密鑰更新的執(zhí)行效率。本文的主要貢獻(xiàn)總結(jié)如下。

1) 設(shè)計了一個加密去重場景下的AONT 的變體，安全高效地將整體外包數(shù)據(jù)的密鑰更新轉(zhuǎn)換到了體量較小的存根的密鑰更新上，解決了基于MLE 的加密去重系統(tǒng)中多用戶密鑰更新的同步問題。

2) 在密鑰更新的過程中引入了一種基于NTRU 的代理重加密方案，將計算量較大的密文轉(zhuǎn)換過程外包至計算能力更強的云服務(wù)器完成，可顯著降低密鑰更新過程中的系統(tǒng)通信開銷和客戶端計算開銷。

3) 分析了ANRDup 的正確性、安全性和效率，并對ANRDup 的原型進(jìn)行了性能評估。評估結(jié)果表明ANRDup 與現(xiàn)有方案[16]相比具有更高的加解密效率，并且顯著降低了密鑰更新過程中的時間開銷。

2 預(yù)備知識

2.1 MLE

MLE 是加密去重系統(tǒng)中一個常用的密碼原語，其加密密鑰基于數(shù)據(jù)內(nèi)容生成。這一特性使相同數(shù)據(jù)對應(yīng)的MLE 密鑰相同，保證了相同數(shù)據(jù)在加密后可得到相同的密文，便于云服務(wù)器檢測密文的重復(fù)性。MLE 密文需要對應(yīng)一個數(shù)據(jù)標(biāo)簽，用于檢測數(shù)據(jù)重復(fù)。MLE 一般由以下幾種算法組成。

1) KeyGen(M)：MLE 密鑰生成算法輸入用戶數(shù)據(jù)M，輸出其對應(yīng)的MLE 密鑰K。

2) Enc(K,M)：MLE 加密算法輸入MLE 密鑰K和用戶數(shù)據(jù)M，輸出M加密后的密文C。

3) Dec(K,C)：MLE 解密算法輸入MLE 密鑰K和密文C，輸出C解密后的明文M。

4) TagGen(C)：標(biāo)簽生成算法輸入密文C，輸出其對應(yīng)的數(shù)據(jù)標(biāo)簽T。

MLE 中的KeyGen() 和TagGen() 一般使用哈希函數(shù)將用戶數(shù)據(jù)和密文映射到體量較小的密鑰和標(biāo)簽中，加解密算法則一般使用傳統(tǒng)的對稱加密算法（如AES）。由于MLE 中的加密密鑰是基于數(shù)據(jù)內(nèi)容生成而非隨機生成，其無法為用戶數(shù)據(jù)提供語義安全。只有在數(shù)據(jù)不可預(yù)測，即敵手無法遍歷明文空間的情況下才可保證數(shù)據(jù)的機密性[17]。

2.2 AONT

AONT 是一個隨機加密模式，其特性是只有得到全部密文后才可恢復(fù)出數(shù)據(jù)信息，缺少任一部分的密文都無法正確解密。假設(shè)數(shù)據(jù)M被拆分為{M1,M2,…,Mn}，隨機密鑰為K。AONT 轉(zhuǎn)換后的前n個包為Ci=Mi⊕EncSE(K,i+1)，其中，i=1,2,3,…,n，EncSE(?)表示對稱加密算法，⊕表示異或，第n+1個包為Cn+1=K⊕H(C1||C2||…||Cn)。當(dāng)恢復(fù)數(shù)據(jù)時，解密方必須得到全部n+1個包才能恢復(fù)出密鑰K=Cn+1⊕H(C1||C2||…||Cn)并解密密文。AONT 的性質(zhì)類似于一個(n+1,n+1)的秘密共享[18]。除非得到全部n+1個包，否則任何數(shù)據(jù)信息都無法恢復(fù)。

2.3 NTRU

NTRU[19]是一種基于格的密碼算法。在眾多公鑰加密算法中，其加密效率較為出眾且可用于構(gòu)造代理重加密方案。如NTRUReEncrypt[15]就是一種高效的基于NTRU 的代理重加密方案。

這里介紹一些NTRU 中的相關(guān)定義和概念。令Φ(x)=xn+1，其中，n為2 的冪次，Φ(x)為分圓多項式。q為一個素數(shù)，滿足q=1 mod 2n。R為環(huán)Z[x]/Φ(x)，Rq=R/qR=Zq[x]/Φ(x)。NTRU 的加密方案定義在環(huán)R和Rq上，將Rq中的可逆元素集合定義為，消息空間M設(shè)定為環(huán)Rp=R/pR，其中，。NTRU 一般由以下幾種算法組成。

1) KeyGen()。密鑰生成算法從高斯分布中取樣f′ 和g，令f=pf′+1，若(fmodq)?或(gmodq)?，則重新取樣。計算h=pgf-1，輸出私鑰sk=f和公鑰pk=h。

2) Enc(pk,m)。加密算法輸入公鑰pk 和消息m∈M，從高斯分布中取樣噪聲多項式s和e，輸出密文c=hs+pe+m∈Rq。

3) Dec(sk,c)。解密算法輸入私鑰sk 和密文c，輸出消息m=((skc) modp)∈M。

NTRUReEncrypt 在NTRU 的基礎(chǔ)上加入了重加密密鑰生成算法ReKeyGen() 和重加密算法ReEnc()，設(shè)計了一種基于NTRU 的代理重加密方案，其由以下幾種算法組成。

1) KeyGen()。對于用戶A來說，密鑰生成算法從高斯分布中取樣和gA，令fA=+1，若(fAmodq)?或(gAmodq)?，則重新取樣。計算，輸出私鑰skA=fA和公鑰pkA=hA。

2) ReKeyGen(skA,skB)。重加密密鑰生成算法輸入用戶A的私鑰skA和用戶B的私鑰skB，輸出用 戶A和B之間的重加密密鑰

3) Enc(pkA,m)。加密算法輸入公鑰pkA和消息m∈M，從高斯分布中取樣噪聲多項式s和e，輸出密文cA=hAs+pe+m∈Rq。

5) Dec(skA,c)。解密算法輸入私鑰skA和密文cA，輸出消息m=((skA cA) modp)∈M。

3 相關(guān)工作

3.1 加密去重

針對傳統(tǒng)加密算法與數(shù)據(jù)去重間的矛盾，文獻(xiàn)[5]提出了MLE，其使用基于數(shù)據(jù)內(nèi)容生成的加密密鑰構(gòu)造確定性加密以實現(xiàn)跨用戶的加密去重。但由于MLE 的加密過程缺乏隨機性，當(dāng)用戶數(shù)據(jù)可預(yù)測時，易受到敵手的離線字典攻擊[17]。為此，DupLESS[17]引入了一個協(xié)助客戶端生成加密密鑰的密鑰服務(wù)器以構(gòu)造服務(wù)器輔助MLE。DupLESS中的密鑰生成需要客戶端與密鑰服務(wù)器交互，敵手無法進(jìn)行離線字典攻擊，并且，系統(tǒng)可通過在密鑰服務(wù)器端限制與客戶端的交互速率防止敵手進(jìn)行在線字典攻擊。但中心化的密鑰服務(wù)器易成為系統(tǒng)中的單點故障和效率瓶頸。因此，一些現(xiàn)有工作[20-22]設(shè)計了無第三方服務(wù)器的加密去重方案。但其中的客戶端交互過多，并且要求大量客戶端在線，難以適用于真實場景。

此外，加密去重系統(tǒng)中的安全問題還包括側(cè)信道攻擊[23-24]、所有權(quán)欺騙攻擊[6,25]、頻率分析攻擊[26]、故障容錯問題[27]和完整性審計[28-29]等。本文關(guān)注的主要問題是加密去重系統(tǒng)中的密鑰更新問題。

3.2 密鑰更新

在加密去重系統(tǒng)存在的眾多安全問題當(dāng)中，密鑰更新問題近年來得到了越來越多的關(guān)注。現(xiàn)有的密鑰更新方案可大致分為對加密密鑰的密文進(jìn)行密鑰更新和對外包數(shù)據(jù)本身進(jìn)行密鑰更新2 類。

3.2.1密鑰密文的密鑰更新

分層加密是實現(xiàn)加密去重系統(tǒng)中密鑰更新的重要方法?？蛻舳耸紫仁褂肕LE 密鑰加密用戶數(shù)據(jù)，然后使用一個用戶密鑰對MLE 密鑰進(jìn)行加密得到MLE 密鑰的密文。密鑰更新時僅對密鑰的密文進(jìn)行更新。EDedup[30]利用密鑰分層的思想實現(xiàn)密鑰更新，系統(tǒng)中的加密密鑰可分為段級別和文件級別，其中，段級別密鑰用于加密用戶數(shù)據(jù)，而文件級別密鑰用于加密段級別密鑰。系統(tǒng)通過重加密文件級別密鑰來實現(xiàn)密鑰更新。文獻(xiàn)[31]提出了將用戶角色與加密密鑰相關(guān)聯(lián)的思路，實現(xiàn)了分層結(jié)構(gòu)下的云數(shù)據(jù)去重。該方案通過撤銷角色樹的節(jié)點實現(xiàn)密鑰更新，主要思路是對密鑰分層結(jié)構(gòu)的調(diào)整。文獻(xiàn)[32]利用策略加密保護(hù)MLE 密鑰的安全性。在執(zhí)行密鑰更新時，該方案結(jié)合公鑰加密和身份認(rèn)證的思想實現(xiàn)密鑰密文的重加密。文獻(xiàn)[10]使用ElGamal 算法加密對稱密鑰，密鑰更新時通過重新拆分ElGamal 私鑰，并將其外包至分布式密鑰服務(wù)器以防止敵手通過已泄露的密鑰破壞數(shù)據(jù)機密性。

基于分層加密設(shè)計的密鑰更新方案的特點是系統(tǒng)僅對密鑰的密文進(jìn)行密鑰更新。當(dāng)外層密鑰泄露時，方案可保證數(shù)據(jù)機密性；但當(dāng)直接加密用戶數(shù)據(jù)的內(nèi)層密鑰泄露后，外包數(shù)據(jù)的機密性將受到破壞。

3.2.2數(shù)據(jù)密文的密鑰更新

由于對密鑰的密文進(jìn)行密鑰更新這一方法具有局限性，一些研究工作開始關(guān)注對外包數(shù)據(jù)本身進(jìn)行密鑰更新。一些可更新塊級別消息鎖加密（UMLE,updatable block-level message-locked encryption）的相關(guān)研究工作[33-34]試圖在文件的數(shù)據(jù)塊動態(tài)改變時高效地更新MLE 密鑰。UMLE 屬于對外包數(shù)據(jù)本身進(jìn)行密鑰更新的方法，但其研究重點主要在于數(shù)據(jù)內(nèi)容的變化對于MLE 密鑰的影響，而非系統(tǒng)應(yīng)如何對抗MLE 密鑰泄露。因此，在UMLE 中，當(dāng)敵手得到已泄露的MLE 密鑰和外包數(shù)據(jù)時，系統(tǒng)無法為用戶數(shù)據(jù)提供機密性保證。

REED[16]提出了支持密鑰更新的2 種加密去重方案：基本加密方案和增強加密方案，其主要思想是通過使用AONT 將用戶數(shù)據(jù)拆分為修剪包和存根，然后通過對存根進(jìn)行重加密實現(xiàn)外包數(shù)據(jù)的密鑰更新。該方案實現(xiàn)了外包數(shù)據(jù)本身的密鑰更新，可有效防止得到已泄露密鑰的敵手破壞數(shù)據(jù)機密性。然而，其提出的2 種方案均存在一定的缺陷：在基本加密方案中，一旦MLE 密鑰泄露，數(shù)據(jù)機密性將不能得到保證；增強加密方案為提高安全性需要對用戶數(shù)據(jù)進(jìn)行2 層加密，這帶來了額外的計算開銷。此外，在REED 的密鑰更新中，存根數(shù)據(jù)需要由客戶端從云服務(wù)器端下載、重加密并上傳。當(dāng)存根體量較大或密鑰更新頻繁時，仍會引起不小的計算和通信開銷。

4 系統(tǒng)模型

4.1 應(yīng)用場景

ANRDup 的應(yīng)用場景為某一群組的用戶（如公司內(nèi)的全體員工或高校內(nèi)的各個院系）共同外包數(shù)據(jù)至云服務(wù)器，如圖2 所示。用戶不完全信任云服務(wù)器，將自己的數(shù)據(jù)加密后外包，防止云服務(wù)器窺探其數(shù)據(jù)隱私。由于使用云存儲服務(wù)的用戶均屬于同一群組，其外包數(shù)據(jù)中很可能會存在大量的重復(fù)內(nèi)容，云服務(wù)器可使用去重技術(shù)節(jié)省存儲開銷。一旦外包數(shù)據(jù)的加密密鑰泄露，數(shù)據(jù)所有者可執(zhí)行密鑰更新操作防止同時得到已泄露的加密密鑰和外包密文的敵手獲取用戶數(shù)據(jù)信息。

圖2 應(yīng)用場景

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

ANRDup 中包括3 種實體：客戶端、密鑰服務(wù)器和云存儲服務(wù)器（簡稱為云服務(wù)器）。

客戶端：用戶通過客戶端外包數(shù)據(jù)至云服務(wù)器?？蛻舳藢⒂脩魯?shù)據(jù)拆分為數(shù)據(jù)塊，對其進(jìn)行加密，將密文塊上傳至云服務(wù)器。客戶端可在密鑰泄露后更新其外包數(shù)據(jù)的加密密鑰。

密鑰服務(wù)器：為了彌補MLE 難以為可預(yù)測數(shù)據(jù)提供機密性的缺陷，ANRDup 中部署了密鑰服務(wù)器以實現(xiàn)服務(wù)器輔助MLE。客戶端生成MLE密鑰時需要與密鑰服務(wù)器交互，MLE 密鑰的生成同時基于數(shù)據(jù)內(nèi)容與密鑰服務(wù)器管理的系統(tǒng)主密鑰。

云服務(wù)器：云服務(wù)器可為多個用戶提供數(shù)據(jù)存儲和管理服務(wù)，并可使用去重技術(shù)降低其存儲開銷。

4.3 敵手模型

本文主要考慮2 類敵手：內(nèi)部敵手和外部敵手。內(nèi)部敵手為誠實但好奇的云服務(wù)器，可通過外包數(shù)據(jù)和已泄露的用戶私鑰試圖獲取數(shù)據(jù)信息。外部敵手為系統(tǒng)外的惡意用戶，可得到已泄露的MLE 密鑰和用戶外包數(shù)據(jù)。

本文的敵手模型基于如下的安全假設(shè)。首先，假設(shè)客戶端與云服務(wù)器間的通信基于SSL/TLS 協(xié)議，二者在身份認(rèn)證后進(jìn)行通信。其次，由于系統(tǒng)可在密鑰服務(wù)器端設(shè)定與客戶端的交互速率限制，本文不考慮敵手的在線字典攻擊，并且，方案中客戶端與密鑰服務(wù)器間的交互基于不經(jīng)意的偽隨機函數(shù)（OPRF,oblivious pseudo-random function），由于OPRF 的安全性已被證明[17]，本文假設(shè)密鑰服務(wù)器無法在密鑰生成階段獲取用戶的數(shù)據(jù)信息。

基于上述的敵手模型，ANRDup 主要有以下2 個安全目標(biāo)。

1) 為用戶的外包數(shù)據(jù)提供機密性，即上述的內(nèi)部或外部敵手均無法獲取用戶的數(shù)據(jù)信息。

2) 為用戶的外包數(shù)據(jù)提供完整性，即客戶端從云服務(wù)器下載數(shù)據(jù)后可檢測外包數(shù)據(jù)是否被篡改。

5 方案設(shè)計

5.1 設(shè)計思想

通過對現(xiàn)有加密去重系統(tǒng)的研究與分析，總結(jié)了其進(jìn)行密鑰更新的2 個難點。

1) 在基于MLE 的加密去重系統(tǒng)中，擁有相同數(shù)據(jù)的多個用戶共享同一加密密鑰，使當(dāng)某個數(shù)據(jù)所有者對其外包數(shù)據(jù)進(jìn)行密鑰更新時，其他數(shù)據(jù)所有者必須同步該更新，否則將出現(xiàn)相同數(shù)據(jù)加密后無法去重的情況。

2) 當(dāng)需要更新密鑰的文件體量較大時，大量數(shù)據(jù)需要在客戶端和云服務(wù)器間傳輸，這將引起較大的通信開銷。此外，重加密大體量文件也給計算能力本就相對薄弱的客戶端帶來了較大的計算開銷。

針對第一個難點，本文構(gòu)造一個適用于加密去重場景下的AONT 的變體來轉(zhuǎn)換用戶數(shù)據(jù)。首先，將原有AONT 中的隨機密鑰替換為基于數(shù)據(jù)內(nèi)容生成的確定性密鑰，構(gòu)造收斂AONT[27]（CAONT,convergent all-or-nothing transform）。擁有相同數(shù)據(jù)的不同用戶可計算得到相同的確定性密鑰，因此跨用戶間的相同數(shù)據(jù)經(jīng)AONT 轉(zhuǎn)換后可得到相同的包數(shù)據(jù)以便實現(xiàn)加密去重。ANRDup 中的數(shù)據(jù)加密過程的方案設(shè)計如圖3 所示，客戶端首先將用戶文件拆分為數(shù)據(jù)塊{M1,M2,…,Mn}，然后將這些數(shù)據(jù)塊通過AONT 轉(zhuǎn)換為修剪包{tp1,tp2,…,tpn}和存根{st1,st2,…,stn}，其中，修剪包與用戶數(shù)據(jù)大小相同，用于云服務(wù)器進(jìn)行去重處理；存根則需要進(jìn)一步由NTRU 隨機加密后得到密文存根，用于客戶端進(jìn)行密鑰更新。由于不同用戶的NTRU 密鑰不同，云服務(wù)器無法對跨用戶的密文存根進(jìn)行去重，但由于其體量較小，不會引起過多的存儲開銷。

假設(shè)t個用戶{U1,U2,…,Ut}經(jīng)加密去重后共享同一密文C。當(dāng)某個用戶Ui進(jìn)行密鑰更新時，其僅需重加密外包數(shù)據(jù)的存根部分即可，而用于數(shù)據(jù)去重的修剪包部分維持不變，這維持了跨用戶數(shù)據(jù)去重的特性，其他用戶不需要同步Ui的密鑰更新，解決了上述的第一個難點。由于AONT 的“全有或全無”特性，解密方缺少密文的存根部分便無法恢復(fù)數(shù)據(jù)信息。因此，系統(tǒng)可通過重加密存根實現(xiàn)整體外包數(shù)據(jù)的密鑰更新。

針對第二個難點，避免密鑰更新時體量較大的外包數(shù)據(jù)在客戶端與云服務(wù)器間傳輸以及在客戶端完成計算量較大的加解密操作的方法是將密文轉(zhuǎn)換的過程直接外包至云服務(wù)器完成。此外，密文轉(zhuǎn)換的過程中需要保證云服務(wù)器無法獲取用戶的數(shù)據(jù)信息。代理重加密正是實現(xiàn)這一需求的有效方法。由于ANRDup 中使用NTRU 加密存根，密鑰更新的過程中可引入基于NTRU 的代理重加密方案NTRUReEncrypt[15]。客戶端使用新舊密鑰生成一個重加密密鑰，將其上傳至云服務(wù)器，云服務(wù)器完成數(shù)據(jù)的重加密過程，具體的方案設(shè)計如圖3 所示。云服務(wù)器使用該重加密密鑰和原存根密文通過重加密過程生成新的存根密文。因此，在整個密鑰更新的過程中，系統(tǒng)的通信開銷僅為一個重加密密鑰，客戶端的計算開銷僅為生成該重加密密鑰，這解決了上述的第二個難點。

圖3 方案設(shè)計

5.2 方案細(xì)節(jié)

本節(jié)主要介紹ANRDup 中的服務(wù)器輔助MLE密鑰生成，數(shù)據(jù)加解密和密鑰更新的詳細(xì)過程。

5.2.1服務(wù)器輔助MLE 的密鑰生成

在ANRDup 中，客戶端加密數(shù)據(jù)前需要與密鑰服務(wù)器交互生成MLE密鑰，這里使用RSA-OPRF[17]生成MLE 加密密鑰。具體過程如下。

1) 密鑰服務(wù)器生成 RSA 公私鑰對{pk=(e,N),sk=d}，將公鑰pk 分發(fā)至所有客戶端，安全存儲私鑰sk。

2) 客戶端計算用戶數(shù)據(jù)的哈希值h，從群中隨機選取用于盲化的隨機值，計算x=hremodN發(fā)送至密鑰服務(wù)器。

3) 密鑰服務(wù)器利用私鑰對客戶端發(fā)送的數(shù)據(jù)簽名，得到y(tǒng)=xdmodN。

4) 客戶端進(jìn)行去盲化過程，計算z=yr-1=hdmodN，驗證h是否與zemodN相等。若相等，說明該MLE 密鑰z有效；否則該密鑰無效，需重新生成。

5.2.2數(shù)據(jù)加密

ANRDup 中AONT 的確定性密鑰同時基于數(shù)據(jù)塊內(nèi)容和服務(wù)器輔助MLE 密鑰生成，此設(shè)計是為了防止出現(xiàn)類似于REED 的基本加密方案中MLE 密鑰泄露后數(shù)據(jù)機密性被破壞的情況。此外，為了在密鑰更新中引入基于NTRU 的代理重加密方案，客戶端使用NTRU 加密存根。圖4 描述了ANRDup 的數(shù)據(jù)加密流程。

圖4 數(shù)據(jù)加密流程

下面以加密單個數(shù)據(jù)塊M為例詳細(xì)介紹數(shù)據(jù)加密過程。假設(shè)M對應(yīng)的服務(wù)器輔助MLE 密鑰為KM，方案的加密過程如下。

1) 拼接M和KM得到(M||KM)，計算加密密鑰Kh=H(M||KM)。

2) 使用Kh加密 (M||KM)得到密文C=EncSE(Kh,(M||KM))，本文的對稱加密使用了AES 加密算法。

3) 將密文C拆分為{C1,C2,…,Cn}，其中每份密文均與密鑰Kh大小相同。異或n份密文和Kh得到t=C1⊕C2⊕ …⊕Cn⊕Kh。

4) 拼接C和t得到(C||t)，從中截取部分?jǐn)?shù)據(jù)（如64 byte）作為存根st，剩余部分作為修剪包tp。

5) 生成NTRU 密鑰對(pk,sk)，使用公鑰pk 加密存根st 得到Cst=EncNTRU(pk,st)，其 中，EncNTRU(?)為NTRU 加密算法。

不同用戶上傳相同數(shù)據(jù)塊時計算得到的確定性密鑰相同，因此得到的修剪包也相同，云服務(wù)器可對跨用戶上傳的修剪包進(jìn)行數(shù)據(jù)去重。此外，本文設(shè)計的加密方案是一個AONT 的變體，滿足計算安全性。除非敵手得到了全部的AONT 包數(shù)據(jù)或者可暴力猜測出加密密鑰，否則其無法得到數(shù)據(jù)塊的任何信息。6.2 節(jié)對該問題給出了更詳盡的安全分析。

5.2.3數(shù)據(jù)解密

客戶端從云服務(wù)器下載數(shù)據(jù)塊M的全部密文（即存根密文Cst和修剪包tp）后，可通過以下步驟完成解密操作以恢復(fù)M。

1) 使用 NTRU 私鑰sk 解密Cst得到存根st=DecNTRU(sk,Cst)，其中DecNTRU(?)為NTRU 解密算法。

2) 拼接tp 和st 得到完整的 AONT 包數(shù)據(jù)(tp||st)，從中截取與Kh大小相同的字節(jié)得到t，將剩余內(nèi)容作為密文C。

3) 將密文C拆分為{C1,C2,…,Cn}，與t異或得到Kh=C1⊕C2⊕ …⊕Cn⊕t。

4) 利用Kh解密密文C，得到(M||KM)=DecSE(Kh,C)，從中截取得到數(shù)據(jù)塊M，其中，DecSE(?)為對稱解密算法。

5) 計算(M||KM)的哈希值h=H(M||KM)，比較h和密鑰Kh是否相等，若相等則數(shù)據(jù)完整性未被損壞。否則，數(shù)據(jù)完整性已被損壞。

5.2.4密鑰更新

當(dāng)NTRU 密鑰對泄露時，數(shù)據(jù)所有者需要對外包數(shù)據(jù)進(jìn)行密鑰更新，具體過程如下。

1) 假設(shè)泄露的密鑰對(pkold,skold)，客戶端生成新的NTRU 密鑰對(pknew,sknew)，輸入新舊私鑰至重加密密鑰生成算法RekeyGen(?)，計算得到重加密密鑰rkold→new=RekeyGen(skold,sknew)，發(fā)送至云服務(wù)器。

2) 云服務(wù)器輸入重加密密鑰rkold→new和原密文Cst=EncNTRU(pkold,st)至重加密算法ReEnc(?)，輸出新密文C'st=ReEnc(rkold→new,Cst)，其中，僅可由sknew解密，而skold失效。

5.3 方案流程

本節(jié)詳細(xì)介紹ANRDup 中客戶端的數(shù)據(jù)上傳、數(shù)據(jù)恢復(fù)和密鑰更新的詳細(xì)操作流程。

5.3.1數(shù)據(jù)上傳

假設(shè)用戶的外包文件為F，客戶端首先將其拆分為大量數(shù)據(jù)塊{M}，計算這些數(shù)據(jù)塊的哈希值，基于OPRF[35]與密鑰服務(wù)器交互得到{M}對應(yīng)的MLE 密鑰{KM}。{M}經(jīng)AONT 轉(zhuǎn)換后得到存根{st}和修剪包{tp}，客戶端將文件F對應(yīng)的所有存根{st}寫入存根文件Fst。然后客戶端生成NTRU 密鑰對(pk,sk)，對Fst進(jìn)行NTRU 加密得到密文存根Cst=EncNTRU(pk,Fst)。由于NTRU 中的加密單元為多項式，客戶端需要在加密前將存根文件編碼為多項式系數(shù)，7.2.1 節(jié)對編碼方式進(jìn)行了詳細(xì)介紹。最后，客戶端將修剪包{tp}和密文存根Cst上傳至云服務(wù)器，本地存儲NTRU 密鑰對(pk,sk)用于解密數(shù)據(jù)；云服務(wù)器存儲客戶端上傳的密文存根和修剪包，并可對跨用戶上傳的修剪包進(jìn)行去重。

5.3.2數(shù)據(jù)恢復(fù)

客戶端從云服務(wù)器下載得到修剪包{tp}和密文存根Cst，使用 NTRU 私鑰sk 解密Cst得到Fst=DecNTRU(sk,Cst)，使用{tp}和Fst恢復(fù)文件F。若在恢復(fù)文件時檢測到外包數(shù)據(jù)已被篡改，則解密操作終止。

5.3.3密鑰更新

客戶端生成新的NTRU 密鑰對(pknew,sknew)，基于原密鑰對中的私鑰skold和新私鑰sknew生成重加密密鑰rkold→new，將rkold→new上傳至云服務(wù)器。云服務(wù)器利用原密文存根Cst和重加密密鑰rkold→new生成新的密文存根。

6 安全性分析

本節(jié)首先分析ANRDup 的正確性，即數(shù)據(jù)加密或密鑰更新后，客戶端可正確恢復(fù)用戶數(shù)據(jù)。然后，分析了ANRDup 中設(shè)計的AONT 的安全性，并基于4.3 節(jié)中的敵手模型分析了整體方案的安全性。

6.1 正確性分析

ANRDup 中所使用的對稱加密的正確性已被證明，這里基于文獻(xiàn)[15]對NTRU 的加解密和重加密過程進(jìn)行正確性分析，假設(shè)客戶端加密的存根數(shù)據(jù)為m。

NTRU加密后得到的密文為c=hs+pe+m∈Rq，解密時計算csk=cf=(hs+pe+m)f=(pgf-1s+pe+m)f=pgs+pef+mfmodp=mfmodp。由于f=1 modp，csk=mf=mmodp∈M，因此，ANRDup中NTRU 的加密部分滿足解密正確性。

假設(shè)原密文為c=hs+pe+m∈Rq，新私鑰為sk ′=f′。NTRU 重加密后得到的密文為c′=crk+pe′=pgf′-1s+peff′-1+mff′-1+pe′ ∈Rq。解密時可使用新私鑰sk′ 計算得到c′s k′=pgs+pef+mf+pe′f′=mmodp∈M。因此，ANRDup 中的重加密過程滿足解密正確性。

6.2 AONT 的安全性分析

ANRDup 是基于AONT 的全有或全無特性而設(shè)計的，全有或全無特性表示只有當(dāng)?shù)玫紸ONT 轉(zhuǎn)換后的所有包數(shù)據(jù)（即修剪包和存根）時才可恢復(fù)數(shù)據(jù)信息，缺少任何一部分包數(shù)據(jù)均無法完成解密。這里以加密單個數(shù)據(jù)塊M為例對ANRDup 中所設(shè)計的AONT 的全有或全無特性進(jìn)行分析，假設(shè)M在AONT 轉(zhuǎn)換后可得到n+1份密文C={C1,C2,…,Cn,t}，加密密鑰Kh的大小為lk。

定理1若AES 具有選擇明文攻擊下的不可區(qū)分性，則方案中的AONT 具有全有或全無特性。

證明M的密文塊共n+1份，假設(shè)敵手可得到其中的n份。分2 種情況討論，第一種即敵手得到了前n份數(shù)據(jù){C1,C2,…,Cn}，第二種即敵手得到了t和{C1,C2,…,Cn}中的n-1份。

1) 若敵手得到了CN={C1,C2,…,Cn}，由于CN為AES 密文，若AES 具有選擇明文攻擊下的不可區(qū)分性，敵手無法區(qū)分CN 與等長的隨機比特串。因此，敵手依據(jù)CN 恢復(fù)數(shù)據(jù)信息的概率等于其成功猜測出AES 密鑰Kh的概率，為，實現(xiàn)了計算安全性。若密鑰長度為128 位（即lk=128），敵手恢復(fù)數(shù)據(jù)信息的概率為1/2128，此概率是可忽略的。

2) 若敵手得到了t和{C1,C2,…,Cn}中的n-1份，由于ANRDup 中的Kh是經(jīng){C1,C2,…,Cn}異或后得到t的，這相當(dāng)于對Kh進(jìn)行了一次一密，為其提供了信息論安全。缺少{C1,C2,…,Cn}中任何一份的敵手恢復(fù)Kh的概率為，同樣實現(xiàn)了計算安全性。

6.3 ANRDup 的安全性分析

本節(jié)首先針對敵手模型中的內(nèi)部敵手對ANRDup 進(jìn)行了形式化的安全證明，將ANRDup的安全性規(guī)約到AES 和NTRUReEncrypt[15]等已被證明安全的密碼學(xué)原語上。證明了若存在內(nèi)部敵手可攻破ANRDup，則該敵手可成功攻破AES 和NTRUReEncrypt。此外，本節(jié)證明了可得到MLE密鑰的外部敵手同樣無法恢復(fù)數(shù)據(jù)信息，并對方案中外包數(shù)據(jù)的完整性進(jìn)行了分析。

定理2若方案中使用的AES和NTRUReEncrypt是密碼學(xué)安全的，則內(nèi)部敵手獲取用戶數(shù)據(jù)信息的概率是可忽略的。

證明這里通過定義多個不可區(qū)分的安全游戲來證明定理 2。Game0模擬了真實場景下的ANRDup 方案，敵手A 模擬了誠實但好奇的內(nèi)部敵手的行為。若A 贏得Game0的概率優(yōu)勢是可忽略的，則可認(rèn)為方案中內(nèi)部敵手獲取數(shù)據(jù)信息的概率是可忽略的。

1) Game0

初始化階段。挑戰(zhàn)者C 生成AES 密鑰k和NTRU 密鑰對(pk0,sk0)，將公鑰pk0發(fā)送至敵手A，安全存儲sk0和k。假設(shè)初始化階段為e0，挑戰(zhàn)階段為eC，猜測階段為eG。在每個時段ei開始前，C 生成新的密鑰對(pki,ski)，將此前時段ei-1的私鑰ski-1發(fā)送至A（挑戰(zhàn)階段的私鑰skC不會發(fā)送給A）。

詢問階段1。在e0≤ei

挑戰(zhàn)階段。在eC中，A 輸出2 個等長的挑戰(zhàn)明文m0和m1({m0,m1}?Qm)，C 隨機選擇b∈R{0,1}，返回mb對應(yīng)的挑戰(zhàn)密文Cb。

詢問階段2。在eC

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

2) Game1

與Game0流程相同，區(qū)別在于C 返回密文時使用一個與存根密文等長的隨機比特串strcst，即C 返回A 詢問的消息密文或重加密后的密文為Cm=(tp,strcst)。

3) Game2

與Game1流程相同，區(qū)別在于C 返回密文時使用一個與修剪包等長的隨機比特串strtp，即C 返回A 詢問的消息密文或重加密后的密文為Cm=(strtp,strcst)。

將A 在Gamei中輸出b=b'的事件定義為Si，A 在Gamei中可取得的概率優(yōu)勢定義為，其中i∈{0,1,2}。

引理1Pr[S2]=1/2。

在Game2中，A 得到的密文為Cm=(strtp,strcst)，存根與修剪包均為與m無關(guān)的隨機比特串，A 只能隨機輸出b'。因此，Pr[S2]=1/2。

引理2若敵手在沒有AES 密鑰的前提下區(qū)分AES 密文與等長的隨機比特串的概率為ξA，則|Pr[S1]-Pr[S2]|≤ξA。

在Game1中，密文為Cm=(tp,strcst)。A 區(qū)分Game1與Game2的概率將不超過其區(qū)分AES 密文tp 與等長的隨機比特串strtp的概率ξA。

引理 3若敵手在沒有私鑰的前提下區(qū)分NTRUReEncrypt 中的密文與等長的隨機比特串的概率為ξN，則|Pr[S0]-Pr[S1]|≤ξN。

在Game0中，A 可得到密文Cm=(tp,Cst)以及skC外的私鑰集合{sk0,…,skC-1,skC,…,skG-1}。在沒有skC的前提下，A 區(qū)分Game0與Game1的概率將不超過其區(qū)分密文Cst與隨機比特串strcst的概率ξN。

由以上3 條引理可知，A 贏得Game0的概率優(yōu)勢如式(1)所示。由于ξA和ξN均為可忽略的值，A贏得Game0的概率優(yōu)勢是可忽略的。

定理3得到外包數(shù)據(jù)和MLE 密鑰的外部敵手恢復(fù)用戶數(shù)據(jù)信息的概率是可忽略的。

證明外部敵手可同時得到MLE 密鑰和外包數(shù)據(jù)，ANRDup 可實現(xiàn)不可預(yù)測的數(shù)據(jù)塊的機密性保證。方案中的加密密鑰為Kh=H(M||KM)，鑒于哈希函數(shù)中的雪崩效應(yīng)（輸入發(fā)生任何微小的改變，都會導(dǎo)致輸出的不可區(qū)分性改變），除非外部敵手可得到完整的(M||KM)，否則其無法計算得到Kh。因此，外部敵手恢復(fù)數(shù)據(jù)信息的概率等于其暴力猜測密鑰Kh的概率，即，此概率是可忽略的。

定理4客戶端無法檢測數(shù)據(jù)完整性被損壞的概率是可忽略的。

證明客戶端下載解密數(shù)據(jù)后可得到(M||KM)，其可通過比較H(M||KM)和Kh是否相等來判斷數(shù)據(jù)完整性是否被損壞。由于哈希函數(shù)H(?) 的抗碰撞性，數(shù)據(jù)被篡改后仍滿足H(M||KM)=Kh的概率是可忽略的。

7 性能分析

本節(jié)分別從理論分析與性能評估2 個方面對ANRDup 進(jìn)行對比分析。

7.1 理論分析

本節(jié)從密鑰更新中的客戶端、服務(wù)器計算開銷和系統(tǒng)中的通信開銷3 個方面對方案的效率進(jìn)行理論分析，并比較了現(xiàn)有方案與ANRDup 在密鑰更新方式上的不同。表1 展示了不同方案在密鑰更新中的時間開銷，其中l(wèi)F和lS分別表示整體數(shù)據(jù)和存根的長度，lRK和lK分別表示重加密密鑰和對稱密鑰的長度，lSig和lAK分別表示方案中使用的簽名長度和對稱密鑰經(jīng)公鑰加密后的密文長度。SE 和SD 分別表示對稱加解密的計算開銷，AE 和AD 分別表示公鑰加解密的計算開銷，H和oprf 分別表示哈希函數(shù)和OPRF 引起的計算開銷，RKG 和RE 表示重加密密鑰生成和數(shù)據(jù)重加密的計算開銷。

表1 密鑰更新中的開銷對比

由表1 可以看出，CE、RCE 和DupLESS 3 個經(jīng)典的加密去重方案中密鑰更新的開銷較大，計算和通信開銷均與外包數(shù)據(jù)的長度線性相關(guān)。與近年來的幾種密鑰更新方案[16,30,32]相比，ANRDup 將部分計算開銷外包至服務(wù)器端，具有更低的客戶端計算開銷和通信開銷。表2 展示了現(xiàn)有方案在密鑰更新方式上的不同。雖然文獻(xiàn)[30]和文獻(xiàn)[32]具有較高的密鑰更新效率，但其密鑰更新方式屬于密鑰密文的更新，當(dāng)直接加密外包數(shù)據(jù)的密鑰泄露時，無法保證用戶數(shù)據(jù)的機密性。因此，只有REED 與ANRDup 實現(xiàn)了高效的數(shù)據(jù)密文更新，并且由表1 可以看出，與REED 相比，ANRDup 具有更低的客戶端計算開銷和帶寬開銷。

表2 密鑰更新方式的對比

7.2 系統(tǒng)實現(xiàn)與性能評估

7.2.1系統(tǒng)實現(xiàn)

本文基于開源的REED 代碼實現(xiàn)了ANRDup的原型，其中AES 和哈希函數(shù)等密碼學(xué)原語均基于OpenSSL 實現(xiàn)，NTRU 加密則基于NTL 庫實現(xiàn)。由于NTRU 的加密單元為多項式，客戶端在對存根進(jìn)行NTRU 加密前需要首先將其編碼為多項式系數(shù)。編碼方式如下：客戶端從存根中讀取一定數(shù)量的比特串，將其編碼為ASCⅡ碼。由于每個ASCⅡ碼占8 位，且NTRU 中的明文空間大小與參數(shù)p相關(guān)，客戶端將每p/8 個字符轉(zhuǎn)換為一個pbit 的整數(shù)，然后將其編碼為多項式系數(shù)?？蛻舳送瓿删幋a后，使用NTRU 加密得到存根密文。

此外，本文對開源代碼REED 中AONT 的實現(xiàn)進(jìn)行了優(yōu)化。為減少AONT 中的比特間操作，方案的原型實現(xiàn)中將待處理數(shù)據(jù)的每64 bit 分為一組執(zhí)行運算，這使程序可在64 位的機器上更高效地運行。

7.2.2性能評估

本節(jié)分別使用人工數(shù)據(jù)和真實數(shù)據(jù)集對ANRDup 的性能進(jìn)行了評估。實驗所使用的機器配備有3.40GHz Inter i7-6700 處理器，3.5 GB RAM，64 位Ubuntu 16.04.1 LTS。所有評估結(jié)果均是10次以上程序運行結(jié)果的平均值。人工數(shù)據(jù)包括一些內(nèi)容隨機填充的文件，真實數(shù)據(jù)集來自FSLhomes，是石溪大學(xué)文件系統(tǒng)和存儲實驗室所收集的包含9 個用戶的每日備份的一個數(shù)據(jù)集，很多加密去重系統(tǒng)[16,26,32]的評估均基于此數(shù)據(jù)集。本節(jié)將7.2.1節(jié)中程序優(yōu)化前后的ANRDup 原型分別命名為ANRDup_Basic 和ANRDup_OP，將REED 中的基本加密和增強加密方案分別命名為REED_Basic 和REED_Enhanced。

1) 人工數(shù)據(jù)上的評估

這里首先使用人工數(shù)據(jù)評估ANRDup 在數(shù)據(jù)加密上傳、下載解密和密鑰更新3 個方面的性能開銷，其中測試文件的大小從1 到1 000 MB，4 種方案的AONT 加解密開銷分別如圖5(a)和圖5(b)所示。不難看出ANRDup_OP 具有最好的AONT 加解密效率。與其他3 種方案相比，ANRDup_OP 分別降低了 45.3%～66.6%的 AONT 加密開銷和48.7%～72.5%的AONT 解密開銷，其性能提升的主要原因在于方案在AONT 設(shè)計上的改進(jìn)，以及代碼實現(xiàn)上的優(yōu)化。REED_Enhanced 的AONT 加解密效率最低，原因在于其對用戶數(shù)據(jù)進(jìn)行了2 層加密。ANRDup_Basic 和REED_Basic 的AONT 加解密效率相近。

圖5 AONT 時間開銷

圖6(a)和圖6(b)顯示了ANRDup 和REED 在加解密存根上的時間開銷對比。由于在ANRDup_OP 和ANRDup_Basic 中存根的加解密過程相同，且均是基于NTRU 加密算法實現(xiàn)的，因此統(tǒng)一簡稱為ANRDup_NTRU。而REED 中的2 種加密方案均是基于AES 加密算法實現(xiàn)的，因此統(tǒng)一簡稱為REED_AES。由于AES 的加解密速度明顯優(yōu)于NTRU，在加解密存根的時間開銷上ANRDup 要高于REED。然而，由于存根的體量較小，其加解密的開銷不會對整體的數(shù)據(jù)加密上傳或下載解密產(chǎn)生過大的影響，這一點在圖7 中得到了證明。

圖6 存根加解密的時間開銷

圖7 顯示了ANRDup 和REED 在整體的數(shù)據(jù)加解密上的時間開銷對比，圖7(a)和圖7(b)分別對應(yīng)數(shù)據(jù)加密和解密的時間開銷，其中包括了AONT過程和存根加解密過程中的時間開銷。ANRDup_OP 在整體的數(shù)據(jù)加解密上與其他3 個方案相比分別降低了19.6%～49.4%和37.1%～57.0%的時間開銷。ANRDup_Basic 在解密速度上與REED_Basic 相似，加密速度略慢于REED_Basic，但與安全性相同的 REED_Enhanced 相比，ANRDup_Basic 具有更好的加解密效率。整體的數(shù)據(jù)加解密開銷的對比情況充分說明了ANRDup 中NTRU 的引入并未對數(shù)據(jù)加解密的效率產(chǎn)生過大的影響，主要原因在于由NTRU 加解密的存根體量較小且方案在AONT 的設(shè)計和實現(xiàn)上均實現(xiàn)了優(yōu)化。

圖7 整體數(shù)據(jù)加解密的時間開銷

圖8(a)和圖8(b)比較了ANRDup 與REED 在數(shù)據(jù)上傳下載過程中客戶端的時間開銷。與圖7 相比，圖8 中增加了文件分塊和數(shù)據(jù)通信部分的開銷，反映了系統(tǒng)真實運行時客戶端的時間開銷。ANRDup_OP 在數(shù)據(jù)上傳和下載過程中與其他3 種方案相比分別降低了21.3%～22.1%和23.3%～38.8%的時間開銷。

圖8 上傳下載的時間開銷

ANRDup 與REED 在性能上最大的差距體現(xiàn)在密鑰更新的過程上，這同樣也是本方案設(shè)計的主要目標(biāo)。由于2 個版本的ANRDup 的密鑰更新開銷相同，統(tǒng)一稱為ANRDup。出于相同的原因，REED中基本加密和增強加密統(tǒng)一稱為REED。2 種方案密鑰更新過程中的性能差異主要集中在系統(tǒng)通信開銷和客戶端的計算開銷上。圖9 比較了2 種方案在密鑰更新過程中的時間開銷，REED 中密鑰更新的時間開銷隨文件大小的增加而增長，而ANRDup中的時間開銷是幾乎恒定的。原因在于在REED 的密鑰更新中客戶端需要下載密文存根、解密、重加密后上傳至云服務(wù)器。文件體量越大，其存根的體量也會隨之增加。因此，REED 中密鑰更新的時間開銷與文件大小線性相關(guān)，而ANRDup 中的數(shù)據(jù)重加密過程則外包至云服務(wù)器，無論需要密鑰更新的文件大小如何，客戶端的計算開銷都僅為生成一個重加密密鑰，系統(tǒng)的通信開銷都僅為該重加密密鑰的大小，二者均與文件大小無關(guān)。

圖9 密鑰更新的時間開銷

2) 真實數(shù)據(jù)集上的評估

本小節(jié)使用真實數(shù)據(jù)集FSLhomes 對ANRDup的存儲效率和加解密性能進(jìn)行了評估。圖10 中的邏輯數(shù)據(jù)（logical data）表示未經(jīng)任何加密和去重的原始數(shù)據(jù)，物理數(shù)據(jù)（physical data）表示去重后存儲在云服務(wù)器的修剪包，存根數(shù)據(jù)（stub data）表示云服務(wù)器存儲的存根數(shù)據(jù)。盡管ANRDup 并未對存根數(shù)據(jù)進(jìn)行去重，且NTRU 加密后的存根存在一定的密文擴張，但ANRDup 仍具有較高的存儲效率。圖10(a)比較了ANRDup 和REED 中物理數(shù)據(jù)和存根數(shù)據(jù)的總和與邏輯數(shù)據(jù)的大小關(guān)系，可以看出數(shù)據(jù)去重后2 種方案的存儲效率均得到了提高。存儲連續(xù)29 天的備份數(shù)據(jù)后，ANRDup 和REED的去重率分別為75.6%和78.8%，其中，去重率定義為物理數(shù)據(jù)和存根數(shù)據(jù)的總和除以邏輯數(shù)據(jù)的比率。由此可以看出，ANRDup 中NTRU 所引起的密文擴張并未對方案整體的存儲開銷帶來過大的影響。圖10(b)比較了ANRDup 和REED 中物理數(shù)據(jù)和存根數(shù)據(jù)分別所占的存儲開銷。與物理數(shù)據(jù)相比，存根數(shù)據(jù)所占的存儲開銷比例較低。ANRDup 中存根數(shù)據(jù)占總存儲量（即物理數(shù)據(jù)和存根數(shù)據(jù)的總和）的5%，而REED 中該比例為1%。二者間的差異主要來自NTRU 加密算法引起的密文擴張。

圖10 存儲開銷

圖11 展示了ANRDup_OP 和與其安全性相同的REED_Enhanced 在真實數(shù)據(jù)集上的加解密性能。性能測試選擇了5 個用戶連續(xù)6 天的日常備份數(shù)據(jù)。這6 天中ANRDup_OP 的平均加解密速度分別為73.83 Mbit/s 和57.12 Mbit/s，REED_Enhanced 為58.42 Mbit/s 和43.13 Mbit/s。ANRDup_OP 在真實數(shù)據(jù)集上的加解密速度比REED_Enhanced 分別提高了20.9%和24.5%。

圖11 真實數(shù)據(jù)集的加解密開銷

8 結(jié)束語

針對現(xiàn)有加密去重系統(tǒng)的密鑰更新過程中存在的困難，提出了基于AONT 和NTRU 的密鑰更新方案ANRDup。方案基于AONT 的全有或全無特性實現(xiàn)了不同用戶密鑰更新時的獨立性，解決了基于MLE 的加密去重系統(tǒng)中多用戶密鑰更新時存在的同步問題。同時，方案在密鑰更新中引入了一種基于NTRU 的代理重加密方案降低了系統(tǒng)的通信開銷和客戶端的計算開銷。性能評估表明所提方案具有較高的加解密效率，并且顯著降低了密鑰更新過程中的時間開銷。由于方案使用了第三方的密鑰服務(wù)器，易產(chǎn)生單點故障和效率瓶頸的問題。后續(xù)工作可通過設(shè)計基于閾值的分布式密鑰服務(wù)器以緩解該問題。