基于BloomFiltering檢測(cè)的安全重復(fù)數(shù)據(jù)刪除技術(shù)分析

張 瑞, 溫 蜜

(上海電力學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 上海 200090)

基于BloomFiltering檢測(cè)的安全重復(fù)數(shù)據(jù)刪除技術(shù)分析

張 瑞, 溫 蜜

(上海電力學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 上海 200090)

數(shù)據(jù)的不斷增長(zhǎng)推動(dòng)了云計(jì)算、云存儲(chǔ)的發(fā)展,大量數(shù)據(jù)被存儲(chǔ)到云端,數(shù)據(jù)的不斷積累占據(jù)了太多存儲(chǔ)空間.為了節(jié)省空間,重復(fù)數(shù)據(jù)刪除技術(shù)被提出并廣泛使用.在原始信息鎖加密的基礎(chǔ)上進(jìn)行改進(jìn),引入布隆過(guò)濾器來(lái)實(shí)現(xiàn)重復(fù)檢測(cè)，繼而完成安全存儲(chǔ).對(duì)方案性能進(jìn)行分析后發(fā)現(xiàn),可以實(shí)現(xiàn)基本的安全機(jī)密性，并降低了計(jì)算開(kāi)銷(xiāo).

云存儲(chǔ); 重復(fù)數(shù)據(jù)刪除; 信息鎖加密; 布隆過(guò)濾器; 安全存儲(chǔ)

隨著大數(shù)據(jù)時(shí)代的發(fā)展,數(shù)據(jù)每時(shí)每刻都影響著處于信息時(shí)代的人們.人類(lèi)社會(huì)產(chǎn)生了多樣化的數(shù)據(jù)渠道,有互聯(lián)網(wǎng)、日常生活等眾多數(shù)據(jù)來(lái)源.據(jù)統(tǒng)計(jì),這些數(shù)據(jù)已累積到前所未有的體量,IDC預(yù)計(jì)到2020年,全球?qū)a(chǎn)生近40 ZB的數(shù)據(jù)[1].數(shù)據(jù)的不斷增長(zhǎng)同時(shí)會(huì)占據(jù)越來(lái)越多的存儲(chǔ)空間.由此看來(lái),為了節(jié)省存儲(chǔ)空間及上傳帶寬,解決辦法的提出就變得尤為重要.

數(shù)據(jù)不斷產(chǎn)生,難免會(huì)存在許多重復(fù)的數(shù)據(jù),并被重復(fù)存儲(chǔ),浪費(fèi)大量的空間.因此,重復(fù)數(shù)據(jù)刪除技術(shù)[3]就被提出并得到了廣泛使用,例如DropBox，Mozy及百度云等的云服務(wù)器[2].重復(fù)數(shù)據(jù)刪除技術(shù)的作用就是云服務(wù)器只存儲(chǔ)數(shù)據(jù)的一個(gè)副本,刪除數(shù)據(jù)集中重復(fù)的數(shù)據(jù),只把相應(yīng)鏈接發(fā)送給擁有相同數(shù)據(jù)的用戶,從而消除冗余數(shù)據(jù),達(dá)到節(jié)省存儲(chǔ)空間的目的.

據(jù)統(tǒng)計(jì)調(diào)查,該技術(shù)去重效果顯著,可以節(jié)省約90%的存儲(chǔ)空間[4].但是由于數(shù)據(jù)都是被存儲(chǔ)到云服務(wù)器端,用戶就失去了對(duì)數(shù)據(jù)的直接控制權(quán),有些重要數(shù)據(jù)如用戶的隱私信息也就得不到保護(hù),信息容易泄露或被篡改.因此，如何保證用戶信息的安全機(jī)密性和完整可用性又是一個(gè)重要的挑戰(zhàn).為此,數(shù)據(jù)就必須要加密保存.然而,重復(fù)數(shù)據(jù)刪除和加密技術(shù)的理念截然相反[5].重復(fù)數(shù)據(jù)刪除的原理是利用數(shù)據(jù)相似性來(lái)檢測(cè)相同數(shù)據(jù),以降低存儲(chǔ)空間中重復(fù)數(shù)據(jù)占有的比例;而加密的目的則在于使得生成的密文與理論上的隨機(jī)數(shù)無(wú)差別.相同數(shù)據(jù)由不同的人加密，所得到的密文完全不同,難以實(shí)現(xiàn)重復(fù)數(shù)據(jù)的刪除.

針對(duì)上述問(wèn)題,DOUSCEUR J R等人[6]提出了采用收斂加密來(lái)實(shí)現(xiàn)安全高效的數(shù)據(jù)重復(fù)刪除.在該方案中,以文件自身生成的摘要值作為密鑰，使用對(duì)稱(chēng)加密算法進(jìn)行加密,保證了相同的明文可以得到相同的密文,允許云存儲(chǔ)提供商利用重復(fù)數(shù)據(jù)刪除而只能獲得加密的數(shù)據(jù).在此基礎(chǔ)上,各種改進(jìn)方案相繼被提出.BELLARE M等人[7]提出了信息鎖加密方案,相比于原始收斂加密更安全高效;JIANG T等人[8]提出了完全隨機(jī)的信息鎖加密方案,在文獻(xiàn)[7]的基礎(chǔ)上做了改進(jìn),加入了樹(shù)結(jié)構(gòu)實(shí)現(xiàn)重復(fù)檢測(cè),但樹(shù)結(jié)構(gòu)進(jìn)行檢測(cè)時(shí)比較復(fù)雜.本文采用簡(jiǎn)單的布隆過(guò)濾器來(lái)檢測(cè)重復(fù),可以更加快速高效地檢測(cè)到重復(fù)數(shù)據(jù)，并完成去重.

1 基礎(chǔ)知識(shí)

1.1 布隆過(guò)濾器

布隆過(guò)濾器(Bloom filtering，BF)多用于對(duì)重復(fù)數(shù)據(jù)的檢測(cè),其基本過(guò)程簡(jiǎn)單易懂,且在不斷被改進(jìn),以降低其誤判率.算法過(guò)程如下.

首先創(chuàng)建一個(gè)m位的BitSet,將所有位初始化為零,然后選擇k個(gè)不同的哈希函數(shù),第i個(gè)哈希函數(shù)對(duì)字符串str哈希的結(jié)果記為hi(str),其值在0～(m-1)內(nèi).

其中，加入字符串過(guò)程為：對(duì)字符串str,分別計(jì)算h1(str),h2(str),h3(str)，…，hk(str)，然后將BitSet的第h1(str)，h2(str)，h3(str)，…，hk(str)位設(shè)為1，如圖1所示.

圖1 Bloom Filtering的創(chuàng)建過(guò)程

檢查字符串是否存在的過(guò)程為：檢查BitSet的第h1(str)，h2(str)，h3(str)，…,hk(str)位是否為1,若其中任何一位不為1,則可以判定str一定沒(méi)有被記錄過(guò).若全部位都是1,則認(rèn)為字符串str存在.

若一個(gè)字符串對(duì)應(yīng)的bit不全為1,則可以肯定該字符串一定沒(méi)有被Bloom Filtering記錄過(guò).但是若一個(gè)字符串對(duì)應(yīng)的bit全為1,實(shí)際上是不能完全肯定該字符串被Bloom Filtering記錄過(guò)的,這是因?yàn)槠渲写嬖谡`識(shí)別率(假陽(yáng)性).

定義BF用于查詢檢測(cè)過(guò)程中會(huì)存在一定的誤識(shí)別率,即把不存在的數(shù)據(jù)視為存在集合中,稱(chēng)為假陽(yáng)性.這個(gè)概率是很小且可計(jì)算的,適當(dāng)選擇哈希函數(shù)k的個(gè)數(shù)和數(shù)組m的大小,來(lái)控制假陽(yáng)性概率使其達(dá)到最小.可忽略的假陽(yáng)性概率大小為:

式中：n——元素個(gè)數(shù).

1.2 信息鎖加密

1.3 所有權(quán)認(rèn)證

所有權(quán)認(rèn)證[9](Proof of Ownership,PoW)就是對(duì)用戶進(jìn)行一種檢測(cè),判斷用戶是否擁有數(shù)據(jù)的全部?jī)?nèi)容,而不是僅有數(shù)據(jù)的摘要值,目的是在客戶端重復(fù)數(shù)據(jù)刪除時(shí)保證數(shù)據(jù)的安全性.通過(guò)這種方法,用戶可以向服務(wù)器證明其確實(shí)擁有整個(gè)文件,而后即可進(jìn)行訪問(wèn)操作.

此處所有權(quán)認(rèn)證運(yùn)用橢圓形曲線加密方法來(lái)實(shí)現(xiàn),其中(Vi,si)代表用戶的一對(duì)密鑰對(duì),用來(lái)重復(fù)檢測(cè)認(rèn)證,P代表橢圓形曲線加密的基準(zhǔn)點(diǎn).在用戶上傳數(shù)據(jù)發(fā)現(xiàn)標(biāo)簽T已存在時(shí),就需要對(duì)用戶進(jìn)行PoW檢測(cè),所有權(quán)認(rèn)證過(guò)程[10]如下:

(1) 服務(wù)器選擇一個(gè)隨機(jī)數(shù)c∈R{0,1,2,…,2σ-1},發(fā)送給用戶;

(2) 用戶計(jì)算y=h(M)+sic,將y通過(guò)安全通道發(fā)送給服務(wù)器;

(3) 服務(wù)器計(jì)算h(yP+cVi),判斷結(jié)果是否等于T;如果結(jié)果為T(mén),則證明用戶對(duì)該數(shù)據(jù)擁有所有權(quán),可以進(jìn)行重復(fù)數(shù)據(jù)刪除操作;如果結(jié)果不為T(mén),服務(wù)器則終止后續(xù)操作.

2 系統(tǒng)模型

2.1 模型介紹

本系統(tǒng)模型只包括用戶和云服務(wù)器兩個(gè)實(shí)體,二者之間進(jìn)行通信交流，如圖2所示.用戶將個(gè)人數(shù)據(jù)經(jīng)外包加密上傳至不完全可信的云存儲(chǔ)服務(wù)器.在原始信息鎖加密方案的基礎(chǔ)上有許多變體方案,JIANG T等人[8]在信息鎖加密方案的基礎(chǔ)上引入決策樹(shù)的數(shù)據(jù)結(jié)構(gòu),實(shí)現(xiàn)了信息鎖加密的相等檢測(cè).本文采用布隆過(guò)濾器的結(jié)構(gòu)來(lái)實(shí)現(xiàn)信息鎖加密的相等檢測(cè).本方案和信息鎖加密有些許不同,不再是簡(jiǎn)單使用收斂密鑰對(duì)數(shù)據(jù)加密,而是采用隨機(jī)密鑰加密數(shù)據(jù),再對(duì)隨機(jī)密鑰進(jìn)行加密的方法.

圖2 系統(tǒng)模型

用戶在上傳數(shù)據(jù)到云存儲(chǔ)服務(wù)器時(shí),實(shí)現(xiàn)了客戶端與服務(wù)器端的相互作用.其中，用戶在上傳數(shù)據(jù)時(shí)被分為初始上傳者(數(shù)據(jù)所有者)和后續(xù)上傳者(數(shù)據(jù)持有者).

2.1.1 初始上傳者

2.1.2 后續(xù)上傳者

數(shù)據(jù)持有者在將數(shù)據(jù)存儲(chǔ)到服務(wù)器時(shí),如果經(jīng)檢測(cè)前面已有人上傳,則后續(xù)上傳者需要進(jìn)行EQ檢測(cè),判斷重復(fù)性,并且需要對(duì)該用戶進(jìn)行所有權(quán)認(rèn)證,判斷其是否真正擁有該數(shù)據(jù),再進(jìn)行后續(xù)操作.

2.2 方案介紹

2.2.1 BF實(shí)現(xiàn)重復(fù)檢測(cè)

布隆過(guò)濾器技術(shù)用于數(shù)據(jù)的檢測(cè)查詢,是重復(fù)數(shù)據(jù)檢測(cè)技術(shù)常用的一種方法.該技術(shù)過(guò)程簡(jiǎn)單易懂,并且具有較高的時(shí)間和空間利用效率.本文將布隆過(guò)濾器結(jié)構(gòu)用于信息鎖加密技術(shù)的相等檢測(cè)部分,通過(guò)標(biāo)簽信息檢測(cè)冗余.具體算法過(guò)程如下.

從上述算法過(guò)程可知,利用BF可以簡(jiǎn)便地實(shí)現(xiàn)重復(fù)檢測(cè),也可以保證數(shù)據(jù)的隱私,實(shí)現(xiàn)數(shù)據(jù)的安全存儲(chǔ),節(jié)省空間.用戶和服務(wù)器之間對(duì)數(shù)據(jù)進(jìn)行重復(fù)檢測(cè)時(shí),只需要上傳摘要值的密文,不需要上傳所有數(shù)據(jù),既可實(shí)現(xiàn)客戶端重復(fù)數(shù)據(jù)刪除,又可以節(jié)約帶寬,提高帶寬利用率.

2.2.2 CBF實(shí)現(xiàn)重復(fù)檢測(cè)

上述BF技術(shù)可以實(shí)現(xiàn)重復(fù)檢測(cè),但BF只能實(shí)現(xiàn)插入操作，不能實(shí)現(xiàn)刪除操作,對(duì)動(dòng)態(tài)集合支持有限.后來(lái)有學(xué)者提出了計(jì)數(shù)布隆過(guò)濾器(Counter Bloom Filtering,CBF),CBF將BF二進(jìn)制向量的每一位擴(kuò)展成一個(gè)計(jì)數(shù)器,如圖3所示.

該方案算法過(guò)程與BF結(jié)構(gòu)過(guò)程幾乎完全相同.

圖3 BF到CBF的轉(zhuǎn)換示意

上述過(guò)程為整個(gè)上傳數(shù)據(jù)的過(guò)程,可以實(shí)現(xiàn)重復(fù)數(shù)據(jù)的查詢刪除,查詢效率與BF結(jié)構(gòu)相同,可以實(shí)現(xiàn)BF結(jié)構(gòu)所支持的所有操作,并具有自己的特色.本方案在用戶要?jiǎng)h除數(shù)據(jù)時(shí),需要同時(shí)刪除對(duì)應(yīng)CBF哈希表中的記錄,即對(duì)應(yīng)哈希位的計(jì)數(shù)器減1,這是BF結(jié)構(gòu)無(wú)法支持的操作.

本文中采用的BF結(jié)構(gòu)可以方便快捷地實(shí)現(xiàn)重復(fù)檢測(cè),從而完成重復(fù)數(shù)據(jù)的刪除,并保證了數(shù)據(jù)的安全.

3 性能分析

本文的方案較信息鎖加密存在不同,不用收斂密鑰對(duì)數(shù)據(jù)加密,而是采用隨機(jī)密鑰加公共參數(shù)來(lái)加密數(shù)據(jù),并對(duì)隨機(jī)密鑰再進(jìn)行加密,以保證數(shù)據(jù)的機(jī)密安全性，采用所有權(quán)認(rèn)證以保證數(shù)據(jù)的完整可用性.

與文獻(xiàn)[6]相比,本方案在安全性方面優(yōu)于單純使用收斂加密方案.在忽略BF錯(cuò)誤率的情況下,本方案操作簡(jiǎn)單,計(jì)算開(kāi)銷(xiāo)小.文獻(xiàn)[8]使用樹(shù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)重復(fù)檢測(cè),再加上各種配對(duì)計(jì)算,計(jì)算開(kāi)銷(xiāo)遠(yuǎn)超過(guò)本方案.與文獻(xiàn)[7]提出的方案進(jìn)行比較,結(jié)果如表1所示.由表1可以看出，由于哈希操作簡(jiǎn)單耗時(shí)較短,本方案在計(jì)算開(kāi)銷(xiāo)方面耗時(shí)較少.

表1 數(shù)據(jù)重復(fù)刪除的計(jì)算消費(fèi)

由文獻(xiàn)[12]可知,對(duì)于160位的數(shù)據(jù),單一指數(shù)運(yùn)算耗時(shí)1.1 ms,配對(duì)運(yùn)算耗時(shí)3.1 ms,乘法操作耗時(shí)0.6 ms,哈希運(yùn)算可忽略不計(jì)(0.2 ms),方案計(jì)算花費(fèi)比較如圖4所示.由圖4可以看出,本方案的計(jì)算開(kāi)銷(xiāo)較文獻(xiàn)[7]的方案明顯降低.

圖4 3種方案的用戶端計(jì)算開(kāi)銷(xiāo)

4 結(jié) 語(yǔ)

本文提出了基于Bloom Filtering檢測(cè)的信息鎖加密的方法,實(shí)現(xiàn)了重復(fù)數(shù)據(jù)的安全刪除,安全性高于基礎(chǔ)的收斂加密方法;提高了系統(tǒng)的運(yùn)行效率,節(jié)約了計(jì)算成本.該方法的設(shè)計(jì)思想簡(jiǎn)單且易于實(shí)現(xiàn),在目前的重復(fù)數(shù)據(jù)刪除技術(shù)研究中應(yīng)用比較廣泛.

[1] LI J,CHEN X,LI M,etal.Secure deduplication with efficient and reliable convergent key management[J].IEEE Transactions on Parallel and Distributed Systems,2014,25(6):1 615-1 625.

[2] LI J,CHEN X,HUANG X,etal.Secure distributed deduplication systems with improved reliability[J].IEEE Transactions on Computers,2015,64(12):3 569-3 579.

[3] 敖莉,舒繼武,李明強(qiáng).重復(fù)數(shù)據(jù)刪除技術(shù)[J].軟件學(xué)報(bào),2010,21(5):916-929.

[4] ARMKNECHT F,BOHLI J M,KARAME G O,etal.Transparent data deduplication in the cloud[C]//Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security,2015:886-900.

[5] 張明月.客戶端加密重復(fù)數(shù)據(jù)刪除機(jī)制的研究[D].西安:西安電子科技大學(xué)，2014.

[6] DOUCEUR J R,ADYA A, BOLOSKY W J,etal.Reclaiming space from duplica files in a serverless distributed file system[C]//Proc of the 22nd Int Conf on Distributed Computing Systems.Piscataway:IEEE,2002:617-624.

[7] BELLARE M,KEELVEEDHI S,RISTENPART T.Message-locked encryption and secure deduplication[C]//EUROCRYPT，2013:296-312.

[8] JIANG T,CHEN X,WU Q,etal.Towards efficient fully randomized message-locked encryption[C]//Australasian Conference on Information Security and Privacy.Springer International Publishing,2016:361-375.

[9] HALEVI S,HARNIK D,PINKAS B,etal.Proofs of ownership in remote storage systems[C]//ACM Conference on Computer and Communica-tions Security,2011：491-500.

[10] YAN Z,DING W,YU X,etal.Deduplication on encrypted big data in cloud[J].IEEE Transactions on BigData,2016,2(2):138-150.

[11] HUR J,KOO D,SHIN Y,etal.Secure data deduplication with dynamic ownership management in cloud storage[J].IEEE Transactions on Knowledge and Data Engineering,2016,28(11):3 113-3 125.

[12] SCOTT M.Efficient implementation of cryptographic pairings[EB/OL].[2007-04-05].http://www.pairing-conference.org/2007/invited/Scottslide.pdf.

(編輯 白林雪)

AnalysisofSecurityDeduplicationBasedonBloomFilteringDetection

ZHANGRui,WENMi

(SchoolofComputerScienceandTechnology,ShanghaiUniversityofElectricPower,Shanghai200090,China)

The fast growth of data promotes the development of cloud computing and cloud storage,so a large amount of data is stored in the cloud,and the accumulation of data occupies too much storage space.In order to save space,data deduplication technology is proposed and widely used.Based on the original message-lock encryption(MLE),bloom filtering is used to achieve the duplicate detection then complete the safety storage.The performance of scheme is analyzed,which can achieve basic security and confidentiality and reduces the computational overhead.

cloud storage; deduplication; message-lock encryption; bloom filtering; secure storage

10.3969/j.issn.1006-4729.2017.04.019

2017-04-17

張瑞(1990-),女,在讀碩士,安徽宿州人.主要研究方向?yàn)榘踩貜?fù)數(shù)據(jù)刪除,信息安全.E-mail:593705081@qq.com.

國(guó)家自然科學(xué)基金(61572311);上海市地方能力項(xiàng)目(15110500700).

TP309;TP309.7

A

1006-4729(2017)04-0402-05