基于屬性加密的塊級云數據去重方案

葛文婷，李衛海，俞能海

基于屬性加密的塊級云數據去重方案

葛文婷，李衛海，俞能海

（中國科學技術大學網絡空間安全學院，安徽 合肥 230026）

針對已有的云數據去重方案主要集中在文件級去重。提出了一種基于屬性加密的支持數據塊級去重的方案，對文件級和數據塊級做雙粒度去重，并由屬性加密實現數據共享。在混合云架構上設計算法，私有云根據文件標簽和數據塊標簽進行重復性檢測和一致性檢測，并由塊級標簽建立默克爾樹，支持對用戶進行所有權證明。用戶上傳密文，私有云應用線性秘密共享技術，向密文添加訪問結構和輔助信息，并為新的擁有權限的用戶更新整體的密文信息。由私有云做代理重加密和代理解密，在無法獲得明文的情況下承擔大部分計算，減輕用戶的計算時間開銷。處理好的密文和標簽存入公有云中，由私有云進行存取。安全性分析表明，所提方案在私有云可達到PRV-CDA（privacy chosen-distribution attacks）安全。分別對固定分塊大小改變屬性個數和固定屬性個數改變分塊大小兩種情況進行仿真實驗，應用4種橢圓曲線加密測試密鑰生成、加密和解密計算時間，結果符合線性秘密共享的特性。仿真實驗和開銷分析表明所提方案可提升去重效率，并降低計算時間開銷。

數據去重；云存儲；屬性加密；所有權證明；線性訪問結構

0 引言

隨著云計算技術的發展，使用云存儲服務的用戶日益增多，而大量重復數據的存儲增加了網絡傳輸帶寬與存儲的開銷，降低了存儲利用率。因此，大規模云存儲系統往往需要去除重復的冗余信息，即去重技術[1]，以節省存儲開銷。在去重技術中，通用方式是為文件計算特定的標簽并存儲于服務器，對待上傳文件進行重復性檢測，進而判斷用戶是否需要上傳文件。對于重復性文件，服務器無須再重復存儲，從而達到節省帶寬和提高存儲利用率的目的。去重多見于文件級[2]的去重，即只檢測整個文件是否重復。幾乎相近的文件顯然會重復占用存儲空間。文獻[3]的BL-MLE（block-level message-locked encryption）方案將文件分割成固定大小的數據塊，實現數據塊級的去重，并能檢驗數據塊與文件的一致性。文獻[4]在BL-MLE的基礎上提出一種高效更新數據的方案，但未考慮數據共享。目前未見屬性加密應用于塊級去重，而屬性加密可實現高效的數據共享和細粒度的訪問控制。

用戶為保護數據安全與隱私，往往會將數據加密后再上傳云存儲系統，這使得云存儲系統在去重時必須考慮用戶對數據的加密。屬性加密（ABE，attribute-based-encryption）實現了一對多的訪問控制以實現數據共享。現有的ABE方案有密鑰策略的基于屬性加密（KP-ABE，key-policy attribute-based encryption）[5]和密文策略的基于屬性加密（CP-ABE，ciphertext-policy attribute-based encryption）[6]兩大分支，都可用于基于屬性的細粒度訪問控制。文獻[7]將屬性加密應用到文件級的密文數據去重，上傳者無須提前獲知待共享數據用戶的身份即可通過屬性值來達到秘密共享數據的目的。文獻[8]表明，線性訪問結構中的密文和加密時間隨訪問結構的增大呈線性增長，而在樹形訪問結構中呈指數型增長。線性訪問結構與樹形訪問結構可相互轉化。在數據去重中，訪問結構大小與用戶量相關，因此本文采用線性秘密共享方案（LSSS，linear secret sharing scheme）[9]。

云服務器通過標簽進行重復性檢測，但若攻擊者截獲標簽，則可冒充文件擁有者。因此在去重操作前，需對用戶進行所有權證明（PoW，proof of ownership）[10]，在文件上傳時建立默克爾樹（MT，Merkle tree）存儲于云服務器，僅需與客戶交互少量信息即可證明用戶是文件擁有者。服務器中的數據是動態變化的，文獻[11]實現對動態數據更便捷的所有權證明。

由于當訪問結構發生變化時，加密后的密文會發生變化，使用代理重加密[12]可以在原密文上生成新的密文，不需要解密再加密，而引入代理加密和代理解密，在云服務器上進行大部分復雜計算，可以減小用戶客戶端的計算時間開銷[13]。

盡管已有支持去重的ABE方案，但數據塊級的基于ABE的數據去重較為少見。本文提出了一種基于線性秘密共享的塊級云數據去重方案。該方案將線性秘密共享嵌入塊級去重算法，支持文件級和數據塊級的雙粒度去重，并實現數據塊級的數據共享；支持對用戶進行所有權證明，引入代理重加密實現更高效的訪問結構更新，引入代理加解密減輕客戶端的計算負擔；在進行所有權證明時，用私有云本身存儲的塊級標簽建立默克爾樹對用戶發起所有權證明，可節省存儲開銷。經仿真測試，該方案可提升去重效率，并節省計算時間開銷。

1 預備知識

本節介紹幾項重要的基礎知識：雙線性映射是標簽一致性檢測的重要方式，也應用于密文設計；LSSS訪問結構的定義和性質；建立默克爾樹是本文所有權證明的方式。決策（-1）假設是安全性證明時用到的重要假設。

1.1 雙線性映射

1.2 LSSS訪問結構

1.3 默克爾樹

默克爾樹[15]是一棵存儲hash值的樹。將文件劃分為多個數據塊，每個葉子節點存儲每個數據塊的hash值，非葉子節點存儲其子節點串聯字符串再進行hash運算的值。默克爾樹可用于數據的對比和驗證，實現可證明擁有。

可證明擁有由以下步驟組成：初始化、生成挑戰信息、生成響應信息和驗證響應信息。具體的實現過程如下。

1) 初始化：驗證者生成驗證數據。

3) 生成響應信息：用戶收到驗證者發送的挑戰信息之后，生成響應信息。

1.4 決策（q-1）假設

對于任何基于概率的多項式時間的算法，給定

2 屬性加密塊級去重方案

本節提出一種基于線性秘密共享的數據塊級去重方案。

2.1 系統模型

基于LSSS的塊級去重系統模型如圖1所示，主要由以下三方構成。

圖1 基于LSSS的塊級去重系統模型

Figure 1 Block-level deduplication system model based on LSSS

1) 屬性中心（AA，attribute authority）

第三方可信機構，為系統生成系統參數、主密鑰和公鑰。為擁有訪問權限的用戶生成屬性私鑰，用戶可與云服務器計算得到其有訪問權限的數據的明文。

2) 客戶端：包括第一位數據上傳者和其他用戶。

客戶端借助云服務器實現數據備份和存儲，并將復雜的計算外包給云服務器。屬性中心為用戶分配與其訪問權限相關的屬性，使擁有權限的用戶可通過分配到的屬性訪問其有權訪問的數據。

3) 云存儲服務器：包含公有云和私有云。私有云驗證用戶對文件是否擁有所有權，負責加解密和重加密計算，拒絕客戶重復上傳服務器中已存儲的數據，并將密文等數據上傳至公有云。公有云負責存儲大量密文數據。在同一服務器范圍內，數據具有唯一性。

在用戶上傳新文件時，先在用戶端通過比較文件級標簽，檢驗文件是否重復。若文件重復，則在通過所有權證明后進行文件級的去重，該步驟直接在客戶端進行，無須上傳服務器；若文件不重復，則將文件劃分成固定大小的數據塊，對分塊后的數據進行塊級去重。此時，屬性中心生成屬性集、主密鑰、公共參數和私鑰發送給用戶，用戶加密不重復的數據塊并上傳到私有云，私有云對該加密數據進行有效性測試和一致性測試，并將通過測試的塊密文存儲至公有云。對于公有云上的數據，另外建立一個標簽表來查找數據。對于重復的數據塊，用戶無須再次上傳，系統通過屬性加密分配給該用戶權限，屬性中心生成代理密鑰發送給私有云，使私有云代理重加密解密出一個中間值，再由私有云發送給用戶，由該擁有權限的用戶解密出明文。

2.2 方案詳細設計

基于線性秘密共享的塊級云數據密文去重方案由以下多項式時間算法組成。

2.2.1 初始化階段

該算法由屬性中心運行，生成系統公共參數和主密鑰，為系統初始化設置。

2.2.2 文件上傳階段

該算法由客戶端運行，先生成文件級標簽、數據塊標簽，發送給私有云，由私有云檢索標簽列表并進行一致性檢驗，判斷該用戶是否為第一位數據上傳者。若該用戶是數據上傳者，則繼續計算數據塊密文發送給私有云。

（2）數據塊密文相等性檢驗

該算法由私有云運行。若私有云發現相同標簽，則用兩數據塊對應的文件級標簽再次驗證兩數據塊密文是否相等。若相等，則可拒絕上傳重復數據。

（3）數據塊標簽與密文的一致性檢驗

該算法由私有云運行，驗證數據塊標簽與密文是否一致。

若成立，則可通過一致性驗證。

（4）所有權證明

當數據不重復上傳至服務器時，屬性中心生成代理密鑰，并將代理密鑰發送給私有云。

對于新加入的數據擁有者，更新屬性列表，則密文需要改變。對私有云上的數據進行代理重加密，使數據不需要解密再加密，實現更為方便的數據共享。

2.2.3 解密階段

塊級去重解密階段如圖2所示，擁有訪問權限的用戶向AA提出下載請求，AA計算代理密鑰并發送給私有云，由私有云解密出中間值再由用戶解密出明文。

對于有數據訪問權限的用戶，從服務器上下載數據時，需要由私有云進行代理解密。

私有云解出一個中間值ME，沒有用戶的私鑰不能繼續解密，保護了數據的安全性。

如圖2所示，解密階段私有云代理解密，承擔了大部分計算量，且僅有用戶可得到明文。

圖2 塊級去重解密階段

Figure 2 Block- level deduplication decryption phase

3 安全性分析

證明

PRV-CDA安全性由加密安全性和重加密安全性構成。加密安全性同定理1，只需考慮添加的部分不會暴露原來關于的信息，其他的證明可以參照Rouselakis-Waters方案的證明。

在考慮到重加密安全性時，需要回顧本文重加密方案的過程。假設有某個攻擊者算法破壞了PRV-CDA安全性，本文將構造出一個挑戰者算法解決BDH問題，以此來導出矛盾。

證畢。

4 仿真實驗與性能評估

本節給出對本文方案的運行性能評估，選取SS512、MNT159、MNT201、MNT224這4種橢圓曲線，對本文提出的基于屬性加密的塊級去重方案，分別測試固定分塊的算法運行時間，以及各方案對于不同大小的分塊的運行時間。

4.1 實驗環境

1) 硬件環境

CPU：AMD Ryzen 5 4600H, Radeon Graphics 3.00 GHz

內存：16 GB RAM SAMSUNG

硬盤：512 GB SSD SAMSUNG2

2) 開發環境

開發操作系統：Ubuntu 16.04（64 bit）

開發語言及工具：Python 3.5、GMP-6.2.0庫、PBC-0.5.14庫、Charm-0.50庫、Pycharm、VMware。

4.2 仿真結果

4.2.1 固定分塊大小對不同屬性個數的計算時間

選取SS512、MNT159、MNT201、MNT224這4種橢圓曲線對固定分塊大小為1 kB的基于屬性加密的塊級去重方案測試運行時間，如圖3所示。這4種曲線分別對應112 bit、80 bit、80 bit和100 bit的安全性。

實驗結果顯示，當屬性個數增加時，密鑰生成、加密、重加密和解密的計算時間線性增長。這與LSSS的特性相符合。在加解密和重加密的計算中，SS512擁有最小的計算時間開銷，而MNT224的計算時間開銷最大。在密鑰生成算法中，SS512的計算時間開銷最大，但對于100個屬性個數也僅占用360 ms，相比加密解密和重加密有較大的時間消耗，SS512依然是最優的方法。由實驗結果可知，對于固定1 kB的分塊，在屬性個數為100的情況下，對于最耗時的加密和重加密過程，可將計算時間控制在1.05 s內，對比文獻[7]的文件級去重的實驗結果，塊級的去重方案可節省對于每個分塊的計算時間開銷。

4.2.2 相同屬性個數對不同分塊大小的運行時間

對于固定的40個屬性，選取SS512、MNT159、MNT201和MNT224這4種橢圓曲線對分塊大小為1 MB到30 MB的數據分塊，運行本文算法并測試運行時間，實驗結果如圖4所示。

圖3 固定分塊大小對不同屬性個數的運行時間

Figure 3 Fixed block size running time for different number of attributes

圖4 相同屬性個數對不同分塊大小的運行時間

Figure 4 Fixed number of attributes running time for different block sizes

當屬性個數固定、分塊大小增加時，密鑰生成算法不受分塊大小的影響，加密和解密算法的運行時間隨分塊大小的增加呈線性增長，這同樣與LSSS的特性相符合。在密鑰生成算法中，SS512的運行時間最大，對于固定的40個屬性，運行時間為148 ms，是可以接受的。在加密和解密算法中，SS512的運行時間最小，MNT224的運行時間最大。

4種橢圓曲線的運行時間隨著分塊大小的增加，增長速率幾乎是一致的。對于40個屬性，在加密和解密中，MNT224的運行時間比SS512的運行時間約長200 ms。因此SS512是可以選取的最優方案。

值得注意的是，以上實驗曲線中都存在違反整體趨勢的“鋸齒”。在密鑰生成以及加解密時，出于安全性考慮都隨機選取了不同的隨機數，尤其選擇屬性參數時引入了隨機量，因此總體線性但有隨機誤差，產生“鋸齒”。若實驗增大屬性間隔可以減輕此類“鋸齒”的情況。

4.3 計算時間開銷分析

對本文方案的各多項式算法分析計算時間開銷，用表示訪問結構的屬性數量，用表示與私鑰關聯的屬性集的大小，用表示私有云現存的標簽數量。用Exp表示一個指數運算，用Pair表示一個雙線性配對運算。由前文已知，在計算標簽和進行一致性驗證時，將數據塊文件劃分塊。本文方案的各多項式算法的計算時間開銷如表1所示。

表1 本文方案的各多項式算法的計算時間開銷

指數運算主要存在于生成標簽和加解密運算，雙線性配對主要存在于一致性檢驗、相等性檢驗和解密。

相對文件級去重，塊級去重不可避免地增加了對數據塊分塊時額外產生的指數運算，以及在加解密中添加元組時產生的開銷。文獻[7]實現了基于屬性的文件級云數據去重，各方案的計算時間開銷對比如表2所示。

對比可知，本文方案的塊級去重的額外計算時間開銷均勻分配給數據上傳者、私有云和需要共享數據的用戶。本文方案設計的數據塊標簽計算方式增加了次指數運算，同時影響到一致性檢驗，本文方案增加了3次雙線性配對運算。由于在密文中增加新的元組，加解密的開銷分別增加了次指數運算和2次雙線性配對運算。由理論分析和前文的仿真實驗可知，這樣的開銷增加是可以接受的。

表2 各方案的計算時間開銷對比

5 結束語

隨著互聯網時代的快速發展，云計算憑借其高效和經濟的特性正在快速增長。云環境下的存儲效率和計算時間開銷以及安全性，需要兼顧和平衡。

云環境下基于屬性的塊級云數據去重方案，是在文件級的基于屬性的去重基礎上，引入了塊級去重，實現更細粒度的去重，提高去重效率。而在屬性加密基礎上的塊級去重，提高了數據共享的能力。本文設計了一種用雙線性配對驗證完成塊級去重情況下的標簽與密文一致性檢驗的方案，該方案由多個多項式時間算法組成。塊標簽可用于建立默克爾樹，對用戶進行所有權證明。針對塊級云數據去重的整個流程中的密鑰生成、加密、代理重加密、解密算法，在選取不同橢圓曲線的情況下，分別對固定分塊大小的不同數量的屬性集，以及固定屬性集數量文件的不同分塊大小，測試了計算時間開銷。實驗結果驗證了在LSSS屬性加密下，加解密的計算時間開銷隨屬性個數或分塊大小的增加而線性增長，而生成密鑰的計算時間開銷只與屬性個數有關，隨屬性個數的增加線性增長。另外，本文還對該方案進行了安全性分析，該方案是PRV-CDA安全的。下一步工作將重點考慮允許用戶自定義密鑰情況下的去重，以及海量用戶塊級去重后的數據所屬權管理等。

[1] BELLARE M, KEELVEEDH S. Interactive message-locked encryption and secure deduplication[C]//Public-Key cryptography - PKC 2015: 18th ICAR International Conference on Practice and Theory in Public Key Cryptography. 2015: 516-538.

[2] AHAMED N, DURAIPANDIAN N. Secured data storage using deduplication in cloud computing based on elliptic curve cryptography[J]. Tech Science Press, 2022, 41: 83-94.

[3] CHEN R, MU Y, YANG G, et al. BL-MLE: block-level message-locked encryption for secure large file deduplication[J]. IEEE Transactions on Information Forensics & Security, 2015, 10(12): 2643-2652.

[4] ZHAO Y, CHOW S. Updatable block-level message-locked encryption[J]. IEEE Transactions on Dependable and Secure Computing, 2021,18(4): 1620-1631.

[5] GOYAL V, PANDEY O, SAHAI A, et al. Attribute-based encryption for fine-grained access control of encrypted data[C]//Proceedings of the 13th ACM Conference on Computer and Communications Security. 2006: 89-98.

[6] EMURA K, MIYAJI A, OMOTE K, et al. A ciphertext-policy attribute-based encryption scheme with constant ciphertext length[J]. International Journal of Applied Cryptography, 2009, 2(1): 46-59.

[7] CUI H, DENG R, LI Y, et al. Attribute-based storage supporting secure deduplication of encrypted data in cloud[J]. IEEE Transactions on Big Data, 2019, 5(3): 330-342.

[8] GOYAL V, JAIN A, PANDEY O, et al. Bounded ciphertext policy attribute based encryption[C]//35th International Colloquium on Automata, Languages and Programming (ICALP 2008). 2008: 579-591.

[9] WATERS B. Ciphertext-policy attribute-based encryption: an expressive, efficient, and provably secure realization[C]//Public Key Cryptography-PKC 2011. 2011: 53-70.

[10] GONZALEZ-MANZANO L, ORFILA A. An efficient confidentiality-preserving proof of ownership for deduplication[J]. Journal of Network & Computer Applications, 2015, 50(4): 49-59.

[11] HUANG K, ZHANG X S, MU Y, et al. Bidirectional and malleable proof-of-ownership for large file in cloud storage[J]. IEEE Transactions on Cloud Computing, 2021, (99): 1.

[12] CHEN Y, HU Y, ZHU M, et al. Attribute-based keyword search with proxy re-encryption in the cloud[J]. IEICE Transactions on Communications, 2018, (8): 1798-1808.

[13] 劉尚, 郭銀章. 云計算多授權中心CP-ABE代理重加密方案[J]. 網絡與信息安全學報, 2022, 8(3): 176-188.

LIU S, GUO Y Z. Multi-authority based CP-ABE proxy re-encryption scheme for cloud computing[J]. Chinese Journal of Network and Information Security, 2022, 8(3): 176-188.

[14] BONEH D, FRANKLIN M. Identity-based encryption from the Weil pairing[J]. SIAM Journal on Computing, 2003, 32(3): 586-615.

[15] SZYDLO M, LECTURE NOTES IN COMPUTER SCIENCE 3027. Merkle Tree Traversal in Log Space and Time[C]//2004 International Conference on the Theory and Application of Cryptographic Techniques (EUROCRYPT 2004). 2004: 541-554.

[16] ROUSELAKIS Y, WATERS B. New constructions and proof methods for large universe attribute-based encryption[C]//ACM Sigsac Conference on Computer & Communications Security. 2013: 463-474.

[17] ROUSELAKIS Y, WATERS B. New constructions and proof methods for large universe attribute-based encryption[C]//Sigsac Conference on Computer & Communications Security. 2013.

Block level cloud data deduplication scheme based on attribute encryption

GE Wenting, LI Weihai, YUNenghai

School of Cyber Science and Technology, University of Science and Technology of China, Hefei 230026, China

Due to the existing cloud data deduplication schemes mainly focus on file-level deduplication. A scheme was proposed, based on attribute encryption, to support data block-level weight removal. Double granularity weight removal was performed for both file-level and data block-level, and data sharing was achieved through attribute encryption.The algorithm was designed on the hybrid cloud architectureRepeatability detection and consistency detection were conducted by the private cloud based on file labels and data block labels. A Merkle tree was established based on block-level labels to support user ownership proof.When a user uploaded the cipher text, the private cloud utilized linear secret sharing technology to add access structures and auxiliary information to the cipher text. It also updated the overall cipher text information for new users with permissions. The private cloud served as a proxy for re-encryption and proxy decryption, undertaking most of the calculation when the plaintext cannot be obtained, thereby reducing the computing overhead for users.The processed cipher text and labels were stored in the public cloud and accessed by the private cloud. Security analysis shows that the proposed scheme can achieve PRV-CDA (Privacy Choose-distribution attacks) security in the private cloud. In the simulation experiment, four types of elliptic curve encryption were used to test the calculation time for key generation, encryption, and decryption respectively, for different attribute numbers with a fixed block size, and different block sizes with a fixed attribute number. The results align with the characteristics of linear secret sharing. Simulation experiments and cost analysis demonstrate that the proposed scheme can enhance the efficiency of weight removal and save time costs.

deduplication, cloud storage, attribute-based-encryption, proof of ownership, linear secret sharing scheme

The National Key R&D Program of China (2018YFB0804101)

葛文婷, 李衛海, 俞能海. 基于屬性加密的塊級云數據去重方案[J]. 網絡與信息安全學報, 2023, 9(5): 106-115.

TP393

A

10.11959/j.issn.2096?109x.2023066

葛文婷（1998? ），女，江蘇泰州人，中國科學技術大學碩士生，主要研究方向為數據安全。

李衛海（1975? ），男，遼寧大連人，中國科學技術大學副教授，主要研究方向為多媒體內容安全、數據安全。

俞能海（1964? ），男，安徽無為人，中國科學技術大學教授、博士生導師，主要研究方向為視頻處理與多媒體通信、信息檢索、媒體內容安全、數據安全。

2023?02?17；

2023?05?28

李衛海，whli@ustc.edu.cn

國家重點研發計劃（2018YFB0804101）

GE W T, LI W H, YU N H. Block level cloud data deduplication scheme based on attribute encryption[J]. Chinese Journal of Network and Information Security, 2023, 9(5): 106-115.