加密去重場景下基于AONT 和NTRU 的密鑰更新方案

賈春福，哈冠雄，武少強(qiáng)，陳杭，李瑞琪

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

1 引言

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

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

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

圖1 CE 中的密鑰更新

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

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

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

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

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

2.1 MLE

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

1) KeyGen(M)：MLE 密鑰生成算法輸入用戶數(shù)據(jù)M，輸出其對(duì)應(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，輸出其對(duì)應(yīng)的數(shù)據(jù)標(biāo)簽T。

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

2.2 AONT

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

2.3 NTRU

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

這里介紹一些NTRU 中的相關(guān)定義和概念。令Φ(x)=xn+1，其中，n為2 的冪次，Φ(x)為分圓多項(xiàng)式。q為一個(gè)素?cái)?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)?，則重新取樣。計(jì)算h=pgf-1，輸出私鑰sk=f和公鑰pk=h。

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

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

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

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

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

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

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

3 相關(guān)工作

3.1 加密去重

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

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

3.2 密鑰更新

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

3.2.1密鑰密文的密鑰更新

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

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

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

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

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

4 系統(tǒng)模型

4.1 應(yīng)用場景

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

圖2 應(yīng)用場景

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

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

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

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

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

4.3 敵手模型

本文主要考慮2 類敵手：內(nèi)部敵手和外部敵手。內(nèi)部敵手為誠實(shí)但好奇的云服務(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)意的偽隨機(jī)函數(shù)（OPRF,oblivious pseudo-random function），由于OPRF 的安全性已被證明[17]，本文假設(shè)密鑰服務(wù)器無法在密鑰生成階段獲取用戶的數(shù)據(jù)信息。

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

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

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

5 方案設(shè)計(jì)

5.1 設(shè)計(jì)思想

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

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

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

針對(duì)第一個(gè)難點(diǎn)，本文構(gòu)造一個(gè)適用于加密去重場景下的AONT 的變體來轉(zhuǎn)換用戶數(shù)據(jù)。首先，將原有AONT 中的隨機(jī)密鑰替換為基于數(shù)據(jù)內(nèi)容生成的確定性密鑰，構(gòu)造收斂AONT[27]（CAONT,convergent all-or-nothing transform）。擁有相同數(shù)據(jù)的不同用戶可計(jì)算得到相同的確定性密鑰，因此跨用戶間的相同數(shù)據(jù)經(jīng)AONT 轉(zhuǎn)換后可得到相同的包數(shù)據(jù)以便實(shí)現(xiàn)加密去重。ANRDup 中的數(shù)據(jù)加密過程的方案設(shè)計(jì)如圖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ī)加密后得到密文存根，用于客戶端進(jìn)行密鑰更新。由于不同用戶的NTRU 密鑰不同，云服務(wù)器無法對(duì)跨用戶的密文存根進(jìn)行去重，但由于其體量較小，不會(huì)引起過多的存儲(chǔ)開銷。

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

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

圖3 方案設(shè)計(jì)

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 公私鑰對(duì){pk=(e,N),sk=d}，將公鑰pk 分發(fā)至所有客戶端，安全存儲(chǔ)私鑰sk。

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

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

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

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

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

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

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

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

2) 使用Kh加密 (M||KM)得到密文C=EncSE(Kh,(M||KM))，本文的對(duì)稱加密使用了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 密鑰對(duì)(pk,sk)，使用公鑰pk 加密存根st 得到Cst=EncNTRU(pk,st)，其 中，EncNTRU(?)為NTRU 加密算法。

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

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(?)為對(duì)稱解密算法。

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

5.2.4密鑰更新

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

1) 假設(shè)泄露的密鑰對(duì)(pkold,skold)，客戶端生成新的NTRU 密鑰對(duì)(pknew,sknew)，輸入新舊私鑰至重加密密鑰生成算法RekeyGen(?)，計(jì)算得到重加密密鑰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}，計(jì)算這些數(shù)據(jù)塊的哈希值，基于OPRF[35]與密鑰服務(wù)器交互得到{M}對(duì)應(yīng)的MLE 密鑰{KM}。{M}經(jīng)AONT 轉(zhuǎn)換后得到存根{st}和修剪包{tp}，客戶端將文件F對(duì)應(yīng)的所有存根{st}寫入存根文件Fst。然后客戶端生成NTRU 密鑰對(duì)(pk,sk)，對(duì)Fst進(jìn)行NTRU 加密得到密文存根Cst=EncNTRU(pk,Fst)。由于NTRU 中的加密單元為多項(xiàng)式，客戶端需要在加密前將存根文件編碼為多項(xiàng)式系數(shù)，7.2.1 節(jié)對(duì)編碼方式進(jìn)行了詳細(xì)介紹。最后，客戶端將修剪包{tp}和密文存根Cst上傳至云服務(wù)器，本地存儲(chǔ)NTRU 密鑰對(duì)(pk,sk)用于解密數(shù)據(jù)；云服務(wù)器存儲(chǔ)客戶端上傳的密文存根和修剪包，并可對(duì)跨用戶上傳的修剪包進(jìn)行去重。

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

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

5.3.3密鑰更新

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

6 安全性分析

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

6.1 正確性分析

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

NTRU加密后得到的密文為c=hs+pe+m∈Rq，解密時(shí)計(jì)算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。解密時(shí)可使用新私鑰sk′ 計(jì)算得到c′s k′=pgs+pef+mf+pe′f′=mmodp∈M。因此，ANRDup 中的重加密過程滿足解密正確性。

6.2 AONT 的安全性分析

ANRDup 是基于AONT 的全有或全無特性而設(shè)計(jì)的，全有或全無特性表示只有當(dāng)?shù)玫紸ONT 轉(zhuǎn)換后的所有包數(shù)據(jù)（即修剪包和存根）時(shí)才可恢復(fù)數(shù)據(jù)信息，缺少任何一部分包數(shù)據(jù)均無法完成解密。這里以加密單個(gè)數(shù)據(jù)塊M為例對(duì)ANRDup 中所設(shè)計(jì)的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ī)比特串。因此，敵手依據(jù)CN 恢復(fù)數(shù)據(jù)信息的概率等于其成功猜測(cè)出AES 密鑰Kh的概率，為，實(shí)現(xiàn)了計(jì)算安全性。若密鑰長度為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)于對(duì)Kh進(jìn)行了一次一密，為其提供了信息論安全。缺少{C1,C2,…,Cn}中任何一份的敵手恢復(fù)Kh的概率為，同樣實(shí)現(xiàn)了計(jì)算安全性。

6.3 ANRDup 的安全性分析

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

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

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

1) Game0

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

詢問階段1。在e0≤ei

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

詢問階段2。在eC

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

2) Game1

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

3) Game2

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

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

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

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

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

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

引理 3若敵手在沒有私鑰的前提下區(qū)分NTRUReEncrypt 中的密文與等長的隨機(jī)比特串的概率為ξ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與隨機(jī)比特串strcst的概率ξN。

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

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

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

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

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

7 性能分析

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

7.1 理論分析

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

表1 密鑰更新中的開銷對(duì)比

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

表2 密鑰更新方式的對(duì)比

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

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

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

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

7.2.2性能評(píng)估

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

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

這里首先使用人工數(shù)據(jù)評(píng)估ANRDup 在數(shù)據(jù)加密上傳、下載解密和密鑰更新3 個(gè)方面的性能開銷，其中測(cè)試文件的大小從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ì)上的改進(jìn)，以及代碼實(shí)現(xiàn)上的優(yōu)化。REED_Enhanced 的AONT 加解密效率最低，原因在于其對(duì)用戶數(shù)據(jù)進(jìn)行了2 層加密。ANRDup_Basic 和REED_Basic 的AONT 加解密效率相近。

圖5 AONT 時(shí)間開銷

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

圖6 存根加解密的時(shí)間開銷

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

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

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

圖8 上傳下載的時(shí)間開銷

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

圖9 密鑰更新的時(shí)間開銷

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

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

圖10 存儲(chǔ)開銷

圖11 展示了ANRDup_OP 和與其安全性相同的REED_Enhanced 在真實(shí)數(shù)據(jù)集上的加解密性能。性能測(cè)試選擇了5 個(gè)用戶連續(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í)數(shù)據(jù)集上的加解密速度比REED_Enhanced 分別提高了20.9%和24.5%。

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

8 結(jié)束語

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