支持億級數(shù)據(jù)的高效密文范圍查詢完整性驗證

王肇康 潘佳輝 周 璐

一些在線運行的人工智能應(yīng)用需要服務(wù)器向客戶端提供一定類型的數(shù)據(jù)查詢服務(wù),但是隨著數(shù)據(jù)規(guī)模的持續(xù)積累,企業(yè)或機構(gòu)自建數(shù)據(jù)中心提供數(shù)據(jù)查詢服務(wù)的成本越來越高.越來越多的企業(yè)或機構(gòu)選擇將面向大規(guī)模用戶的數(shù)據(jù)查詢外包給公有云計算廠商處理,從而以較低的成本提供高并發(fā)的數(shù)據(jù)查詢服務(wù)[1].

但是將人工智能應(yīng)用的數(shù)據(jù)查詢功能外包給公有云服務(wù)器可能帶來敏感信息泄漏和查詢結(jié)果被篡改的雙重安全風(fēng)險[2].云服務(wù)器因為在開放互聯(lián)網(wǎng)環(huán)境下提供服務(wù),存在被攻擊而泄漏敏感信息的風(fēng)險.同時云服務(wù)器并不完全可信,來自外部人員的惡意攻擊或內(nèi)部員工的惡意行為可能篡改云服務(wù)器返回的查詢結(jié)果,以此獲取非法利益.而且云數(shù)據(jù)庫軟件本身可能存在缺陷,導(dǎo)致特定查詢不能被正確執(zhí)行而產(chǎn)生錯誤的查詢結(jié)果.

對于數(shù)據(jù)敏感型的關(guān)鍵應(yīng)用,保證查詢結(jié)果的完整性(即正確性與完備性)至關(guān)重要,如醫(yī)療危急值智能監(jiān)控應(yīng)用需要根據(jù)患者的檢查結(jié)果與病例記錄及時準(zhǔn)確地向醫(yī)生與患者推送告警記錄.在此類應(yīng)用中,必須保證云端數(shù)據(jù)查詢結(jié)果真實可信并且未經(jīng)篡改,錯誤或被篡改的查詢結(jié)果可能帶來嚴(yán)重后果.

基于證明的查詢完整性驗證框架是一種可在不可信的開放環(huán)境中實現(xiàn)云端大數(shù)據(jù)安全可信查詢的算法框架[3].該框架由數(shù)據(jù)擁有者、云服務(wù)器與客戶端三方組成.數(shù)據(jù)擁有者是數(shù)據(jù)的提供方,基于隨機生成的密鑰,為原始數(shù)據(jù)集構(gòu)建一種經(jīng)過密碼學(xué)簽名的特殊索引結(jié)構(gòu)——驗證數(shù)據(jù)結(jié)構(gòu)(Authen-tication Data Structure, ADS).數(shù)據(jù)擁有者將原始數(shù)據(jù)集與驗證數(shù)據(jù)結(jié)構(gòu)上傳給云服務(wù)器,由云服務(wù)器對外提供數(shù)據(jù)查詢服務(wù).數(shù)據(jù)擁有者同時將生成驗證數(shù)據(jù)結(jié)構(gòu)的密鑰以及驗證數(shù)據(jù)結(jié)構(gòu)的密碼學(xué)摘要分享給客戶端.當(dāng)客戶端進(jìn)行數(shù)據(jù)查詢時,客戶端根據(jù)分享的密鑰生成查詢陷門并向云服務(wù)器發(fā)送查詢請求.云服務(wù)器根據(jù)查詢陷門進(jìn)行(密文)數(shù)據(jù)查詢,并根據(jù)驗證數(shù)據(jù)結(jié)構(gòu)為查詢結(jié)果生成對應(yīng)的完整性證明,隨后將查詢結(jié)果與完整性證明同時返回客戶端.客戶端根據(jù)接收的完整性證明對查詢結(jié)果進(jìn)行校驗.如果查詢結(jié)果或完整性證明被篡改,則客戶端根據(jù)完整性證明重算的驗證數(shù)據(jù)結(jié)構(gòu)密碼學(xué)摘要將發(fā)生變化.客戶端通過比對重算的摘要與數(shù)據(jù)擁有者分享的摘要,可校驗查詢結(jié)果的完整性.

在眾多數(shù)據(jù)查詢類型中,本文重點關(guān)注范圍查詢的完整性驗證.范圍查詢是人工智能應(yīng)用常用的基礎(chǔ)查詢類型之一.現(xiàn)有范圍查詢完整性驗證方法根據(jù)對數(shù)據(jù)篡改等攻擊的檢測精度,可分為確定性驗證與概率性驗證兩類[3].確定性驗證方法可準(zhǔn)確檢測任意對查詢結(jié)果或完整性證明的篡改,檢測失敗概率在特定密碼學(xué)假設(shè)下幾乎可忽略不計,但方法涉及復(fù)雜的密碼學(xué)計算,計算開銷較高.概率性驗證方法[3]以較低的計算開銷僅保證以用戶指定概率檢測篡改等攻擊.對于數(shù)據(jù)敏感的應(yīng)用需采用確定性驗證方法.

根據(jù)云服務(wù)器在生成完整性證明時是否需要得知明文查詢結(jié)果,目前針對范圍查詢的確定性完整性驗證方法可進(jìn)一步分為明文驗證方法與密文驗證方法兩類.

明文驗證方法需要基于明文查詢結(jié)果生成完整性證明,因此在云服務(wù)器端存在查詢結(jié)果數(shù)據(jù)隱私泄漏的安全風(fēng)險.Merkle Hash Tree[4]及其變體(如Verifiable B-trees[5]、Merkle B+ tree[6]、HAT(Hybrid Authentication Tree)[7]、VKDTree(Verifiable KD-tree)[8])

是其中一類常用的驗證數(shù)據(jù)結(jié)構(gòu).此類結(jié)構(gòu)將數(shù)據(jù)記錄的哈希簽名作為葉節(jié)點,自底向上地構(gòu)建樹型數(shù)據(jù)結(jié)構(gòu),樹中節(jié)點的哈希簽名由其子節(jié)點的簽名以及節(jié)點自身信息共同確定.上述簽名方式保證對任意數(shù)據(jù)記錄的篡改都會導(dǎo)致根節(jié)點哈希簽名發(fā)生變化,從而可驗證查詢結(jié)果的完整性.另一類完整性驗證方式采用較復(fù)雜的數(shù)字簽名實現(xiàn),簽名鏈[9]將數(shù)據(jù)記錄按索引維度取值、排序,并采用鏈?zhǔn)椒绞綖槊織l記錄生成數(shù)字簽名,客戶端基于鏈?zhǔn)胶灻Y(jié)構(gòu)可同時驗證查詢結(jié)果的完備性與正確性.聚合簽名[10]利用雙線性聚合簽名等機制縮減完整性驗證證明的規(guī)模.此外,基于密碼學(xué)累加器[11-12]的方法在單維范圍查詢完整性驗證機制的基礎(chǔ)上,通過雙線性累加器等密碼學(xué)方法實現(xiàn)對多個單維范圍查詢結(jié)果的交集計算進(jìn)行驗證,從而支持多屬性范圍查詢的完整性驗證.

為了保護(hù)數(shù)據(jù)隱私,越來越多的應(yīng)用開始在云服務(wù)器端采用密文查詢技術(shù),云服務(wù)器僅存儲密文數(shù)據(jù)索引,查詢結(jié)果不經(jīng)過解密無法被第三方獲知.Ren等[13]提出基于可信執(zhí)行硬件的高效密文范圍查詢方法.Zhan等[14]提出MDOPE(Multi-dimensional Data Order Preserving Encryption),Zhang等[15]提出SOREL(Secure Order Revealing Encryption Enabled Framework),都針對支持范圍查詢的保序加密方法開展研究.Tian等[16]提出具有前向安全性的可搜索密文范圍查詢方法.Guo等[17]和Tian等[18]分別面向物聯(lián)網(wǎng)場景下非確定范圍查詢與確定性范圍查詢提出針對性的高效密文查詢方法.

為了保證密文范圍查詢結(jié)果的完整性,Wu等[19]提出針對密文范圍查詢的完整性驗證數(shù)據(jù)結(jié)構(gòu)——SVETree(Secure, Verifiable,and Efficient Tree)并開發(fā)相應(yīng)的原型系統(tǒng)——ServeDB(Secure, Veri-fiable, and Efficient Framework).ServeDB基于分層立方體編碼對數(shù)據(jù)記錄與范圍查詢進(jìn)行加密表示,集安全性、高效性與可驗證性為一體.Meng等[20]提出VSRQ(Verifiable Spatial Range Query),基于前綴編碼集合實現(xiàn)層次化的立方體編碼,并將范圍查詢轉(zhuǎn)換為編碼集的交集計算,利用基于多重集的累加器實現(xiàn)密文范圍查詢驗證.Cui等[21]提出SAGTree(Secure and Supporting Access Control Grid Tree),基于Hilbert曲線線性嵌入的密文空間關(guān)鍵詞查詢驗證數(shù)據(jù)結(jié)構(gòu),當(dāng)忽略關(guān)鍵詞查詢與訪問權(quán)限控制時,可退化為支持二維密文范圍查詢的驗證方法.Ma等[22]提出VeriRange(Verifiable Secure Range Query),采用基于局部敏感哈希的數(shù)據(jù)分塊方法與PKD(PivotedkDimensional)、AVL樹的檢索結(jié)構(gòu),實現(xiàn)可驗證的二維空間數(shù)據(jù)密文范圍查詢.此外,還有一些面向通用密文查詢的完整性驗證方法也支持對范圍查詢結(jié)果進(jìn)行驗證,但此類方法因需要考慮通用性,底層采用的可驗證賬本[23]或可驗證計算[24]技術(shù)存在較高的額外開銷.

現(xiàn)有針對密文范圍查詢完整性驗證問題的研究工作更關(guān)注于降低云服務(wù)器與客戶端側(cè)的計算與通信開銷,較少考慮優(yōu)化數(shù)據(jù)擁有者側(cè)驗證數(shù)據(jù)結(jié)構(gòu)的構(gòu)建開銷.同時,相關(guān)文獻(xiàn)[11,12,19-22]在實驗評估中所用數(shù)據(jù)集規(guī)模最大僅至百萬量級.這些方法在面對億級規(guī)模數(shù)據(jù)時,驗證數(shù)據(jù)結(jié)構(gòu)構(gòu)建階段產(chǎn)生的高昂時間與空間開銷將成為制約整個系統(tǒng)可擴展性的性能瓶頸.

針對現(xiàn)有密文范圍查詢完整性驗證方法對數(shù)據(jù)可擴展性考慮不足的問題,本文首先通過一系列執(zhí)行時間分解實驗,發(fā)現(xiàn)制約ServeDB數(shù)據(jù)可擴展性的性能瓶頸在于數(shù)據(jù)擁有者側(cè)的驗證數(shù)據(jù)結(jié)構(gòu)SVETree構(gòu)建過程.該過程涉及大量HMAC(Hash-Based Message Authentication Code)哈希函數(shù)計算,帶來高昂的計算開銷.對該步驟的復(fù)雜度分析表明,減少HMAC哈希函數(shù)計算次數(shù)的可能優(yōu)化方向包括降低驗證數(shù)據(jù)結(jié)構(gòu)的立方體編碼層次數(shù)、增加樹節(jié)點分支數(shù)及降低葉節(jié)點數(shù)量等.針對上述3個優(yōu)化方向,在SVETree驗證數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上,分別提出基于分位數(shù)歸一化的數(shù)據(jù)重分布、基于K叉平衡樹的驗證結(jié)構(gòu)扁平化、基于立方格索引的驗證結(jié)構(gòu)設(shè)計這3種優(yōu)化方法,進(jìn)而提出基于立方格索引的密文范圍查詢完整性驗證方法(Cube-Cell-Based Au-thentication Tree, CubeTree).相比SVETree,Cube-Tree大幅降低驗證數(shù)據(jù)結(jié)構(gòu)的存儲開銷與構(gòu)建過程的計算開銷,間接降低完整性證明的生成、傳輸與校驗開銷.通過一系列實驗驗證3種優(yōu)化方法的有效性以及CubeTree的高效性.相比SVETree驗證數(shù)據(jù)結(jié)構(gòu),CubeTree能將驗證數(shù)據(jù)結(jié)構(gòu)的構(gòu)建時間平均減少99.4%,存儲開銷平均減少85.5%.更輕量的驗證數(shù)據(jù)結(jié)構(gòu)幫助CubeTree將完整性證明的生成時間平均降低36.7%、傳輸開銷平均降低99.4%、校驗時間平均降低99.2%.相比現(xiàn)有的VeriRange[22],CubeTree在密文索引與驗證數(shù)據(jù)結(jié)構(gòu)構(gòu)建階段有較好的性能優(yōu)勢,更適用于三維及多維范圍查詢或云端算力資源豐富而客戶端存儲開銷緊張的二維范圍查詢場景.同時CubeTree具有良好的數(shù)據(jù)可擴展性,在相同時間限制下處理的數(shù)據(jù)集規(guī)模是SVETree的359.8倍,CubeTree的構(gòu)建用時與內(nèi)存開銷隨數(shù)據(jù)集規(guī)模呈線性增長,可擴展到包含1.2億條記錄的大型數(shù)據(jù)集.

1 ServeDB性能瓶頸分析

1.1 工作流程

ServeDB的工作流程遵循圖1所示的基于證明的查詢完整性驗證框架.ServeDB使用密鑰生成、驗證數(shù)據(jù)結(jié)構(gòu)構(gòu)建、查詢陷門生成、密文查詢與完整性驗證這5種算法描述整個工作流程.密鑰生成算法與驗證數(shù)據(jù)結(jié)構(gòu)構(gòu)建算法運行在數(shù)據(jù)擁有者側(cè),在每個數(shù)據(jù)集上執(zhí)行一次.數(shù)據(jù)上傳、私密共享密鑰與驗證數(shù)據(jù)結(jié)構(gòu)的密碼學(xué)摘要主要涉及數(shù)據(jù)傳輸,實現(xiàn)方式與算法無關(guān),因此不再進(jìn)一步介紹和分析.查詢陷門生成算法運行在客戶端側(cè),根據(jù)用戶給出的明文查詢范圍生成密文查詢陷門.密文查詢算法運行在云服務(wù)器中,根據(jù)客戶端提交的查詢陷門,在驗證數(shù)據(jù)結(jié)構(gòu)SVETree上進(jìn)行密文查詢,返回密文查詢結(jié)果與完整性證明.完整性驗證算法運行在客戶端側(cè),根據(jù)完整性證明對解密后的明文查詢結(jié)果進(jìn)行校驗.

圖1 基于證明的查詢完整性驗證框架

ServeDB驗證數(shù)據(jù)結(jié)構(gòu)SVETree的構(gòu)建過程可進(jìn)一步分解為圖2所示的5步.首先,立方體編碼系統(tǒng)(Cube Coding System, CCS)生成步驟對數(shù)據(jù)集的值域空間進(jìn)行從粗到細(xì)的多粒度網(wǎng)格劃分,劃分過程如圖3所示.立方體編碼系統(tǒng)的第l層將數(shù)據(jù)集值域的每個維度均勻劃分為2l個區(qū)間,將整個d維值域空間均勻劃分為2ld個網(wǎng)格(即立方體),每個立方體覆蓋特定范圍內(nèi)的數(shù)據(jù)記錄.SVETree的立方體編碼系統(tǒng)需要確保：每個立方體覆蓋的記錄數(shù)均小于等于用戶給定的記錄數(shù)閾值參數(shù)τ;如果當(dāng)前層次數(shù)不能滿足要求,增加立方體編碼系統(tǒng)層次數(shù),直到滿足閾值要求或達(dá)到最大層次數(shù).

然后,記錄編碼生成步驟為數(shù)據(jù)集上的每條記錄,按照立方體編碼系統(tǒng)的網(wǎng)格劃分方案,計算記錄在每層所屬的立方體,將所屬立方體標(biāo)識的哈希值作為此記錄在該層的立方體編碼.假設(shè)立方體編碼系統(tǒng)共L層,經(jīng)過編碼的每條記錄將對應(yīng)L個立方體編碼.立方體編碼隱藏記錄的原始數(shù)據(jù)取值,用于密文查詢與完整性證明生成過程.該步驟同時對記錄的明文屬性進(jìn)行加密,生成密文數(shù)據(jù)記錄.

圖2 驗證數(shù)據(jù)結(jié)構(gòu)SVETree構(gòu)建流程圖

圖3 二維立方體編碼系統(tǒng)網(wǎng)格劃分過程

驗證數(shù)據(jù)結(jié)構(gòu)SVETree是一棵平衡二叉樹,二叉樹的每個葉節(jié)點對應(yīng)數(shù)據(jù)集上的一條密文記錄.平衡二叉樹構(gòu)建步驟將根據(jù)密文數(shù)據(jù)記錄創(chuàng)建一棵滿足上述條件的平衡二叉樹結(jié)構(gòu),并維護(hù)葉節(jié)點與密文記錄的對應(yīng)關(guān)系.

二叉樹編碼步驟為二叉樹中的每個樹節(jié)點生成布隆過濾器.布隆過濾器存儲每個樹節(jié)點覆蓋的所有葉子節(jié)點對應(yīng)記錄的全部立方體編碼.布隆過濾器用于指導(dǎo)密文查詢與完整性證明生成.以圖2中平衡二叉樹結(jié)構(gòu)為例,黃色節(jié)點覆蓋4個葉子節(jié)點,分別對應(yīng)密文記錄R3、R2、R1、R4,黃色節(jié)點的布隆過濾器將存儲這4條記錄的全部立方體編碼.

最后,驗證信息生成步驟采用類似Merkle Hash Tree的方式,自底向上地根據(jù)每個樹節(jié)點的布隆過濾器內(nèi)容、密文記錄的數(shù)字簽名與子節(jié)點的哈希簽名,為每個樹節(jié)點生成哈希簽名.最終二叉樹根節(jié)點的哈希簽名是整個驗證數(shù)據(jù)結(jié)構(gòu)的密碼學(xué)摘要.上述生成方式保證對樹節(jié)點中任意內(nèi)容的篡改均會使根節(jié)點哈希簽名發(fā)生變化,從而使驗證者可通過檢查哈希簽名以檢測樹節(jié)點的內(nèi)容是否被篡改.

1.2 執(zhí)行時間分解分析

在圖1的ServeDB整體工作流程中,驗證數(shù)據(jù)結(jié)構(gòu)構(gòu)建算法需要處理全部數(shù)據(jù)集,執(zhí)行開銷與數(shù)據(jù)集規(guī)模密切相關(guān),密鑰生成算法的執(zhí)行開銷僅與密鑰長度相關(guān),查詢陷門生成、密文查詢、完整性驗證的執(zhí)行開銷主要受范圍查詢條件與查詢結(jié)果規(guī)模的影響.

因為客戶端觸發(fā)的查詢次數(shù)較多,因此之前的研究工作著重于降低查詢過程中密文查詢與完整性驗證算法的執(zhí)行開銷,忽略驗證數(shù)據(jù)結(jié)構(gòu)構(gòu)建算法對整個系統(tǒng)的數(shù)據(jù)可擴展性的制約.如果無法在可接受的時空開銷下生成驗證數(shù)據(jù)結(jié)構(gòu),ServeDB將難以實現(xiàn)大規(guī)模數(shù)據(jù)集的密文范圍查詢完整性驗證.

在真實數(shù)據(jù)集上的執(zhí)行時間分解實驗表明：驗證數(shù)據(jù)結(jié)構(gòu)構(gòu)建過程是ServeDB處理大規(guī)模數(shù)據(jù)集的性能瓶頸所在.在真實數(shù)據(jù)集foursquare2014[25]上運行ServeDB的完整執(zhí)行流程,保持查詢范圍占數(shù)據(jù)集值域空間的1‰(隨機選取5組查詢,每組查詢執(zhí)行5次,查詢相關(guān)步驟取平均用時),各步驟的執(zhí)行用時情況如表1所示.由表可見,ServeDB在驗證數(shù)據(jù)結(jié)構(gòu)構(gòu)建步驟上花費的執(zhí)行時間占總執(zhí)行時間的99.5%,遠(yuǎn)高于其它步驟.在更大規(guī)模的gowalla[26]、ebird[27]、foursquare2015[28]數(shù)據(jù)集上,構(gòu)建驗證數(shù)據(jù)結(jié)構(gòu)的執(zhí)行時間已超過6 h.當(dāng)縮小查詢范圍時,ServeDB中報道的密文查詢與完整性驗證的時間可降至1 s以下[19].根據(jù)表2中的實驗數(shù)據(jù)推算,假設(shè)ServeDB驗證數(shù)據(jù)結(jié)構(gòu)構(gòu)建時間隨數(shù)據(jù)集規(guī)模呈線性增長,當(dāng)數(shù)據(jù)集規(guī)模達(dá)到1億條時,驗證數(shù)據(jù)結(jié)構(gòu)的構(gòu)建用時將高達(dá)60 h.

表1 foursquare2014數(shù)據(jù)集上ServeDB工作流程各步驟執(zhí)行時間

為了發(fā)掘構(gòu)建過程性能瓶頸所在,進(jìn)一步對圖2中SVETree構(gòu)建過程中各步驟的執(zhí)行時間進(jìn)行分解,結(jié)果如表2所示.由表可見,整個執(zhí)行時間的98.3%花費在二叉樹編碼步驟.該步驟的主要任務(wù)是將密文記錄的立方體編碼插入二叉樹各節(jié)點的布隆過濾器中.而插入布隆過濾器過程的99.9%的執(zhí)行時間花費在根據(jù)HMAC哈希函數(shù)計算立方體編碼在布隆過濾器中對應(yīng)比特位置,布隆過濾器的比特置位開銷僅占0.1%.上述實驗數(shù)據(jù)表明,二叉樹編碼步驟是整個驗證數(shù)據(jù)結(jié)構(gòu)構(gòu)建過程的核心性能瓶頸所在,而該步驟的計算開銷幾乎全部來自HMAC哈希函數(shù)計算.

表2 foursquare2014數(shù)據(jù)集上驗證數(shù)據(jù)結(jié)構(gòu)SVETree構(gòu)建過程各步驟執(zhí)行時間

1.3 性能瓶頸來源分析

經(jīng)過提取關(guān)鍵操作與適當(dāng)簡化,二叉樹編碼步驟呈現(xiàn)算法1所示的4層循環(huán)結(jié)構(gòu).

算法1SVETree構(gòu)建過程的二叉樹編碼步驟

輸入SVETree平衡二叉樹結(jié)構(gòu)T,驗證私鑰sk,

立方體編碼系統(tǒng)CCS,哈希私鑰HK

輸出編碼后二叉樹結(jié)構(gòu)T

FORn∶=T.nodes() DO

FOR 樹節(jié)點n覆蓋的每個葉節(jié)點leafDO

record∶=GetCorrespondingRecord(leaf);

FORl∶=1 toCCS.LDO

//對于記錄在CCS層次l的立方體編碼

code∶=record.cube_codes[l];

//布隆過濾器使用r個比特存儲每個編碼

FORi∶=1 torDO

// 計算編碼對應(yīng)比特位置hash_pos

hash_key=HMAC(HK[i],code);

hash_pos=HMAC(n.randv,hash_key);

n.bloom_filter.SetBit(hash_pos);

END FOR

END FOR

END FOR

END FOR

最外層循環(huán)遍歷二叉樹中的每個樹節(jié)點,次外層循環(huán)遍歷該樹節(jié)點覆蓋的所有葉子節(jié)點leaf,次內(nèi)層循環(huán)遍歷葉子節(jié)點對應(yīng)記錄在CCS每層的立方體編碼code,最內(nèi)層循環(huán)根據(jù)HMAC哈希函數(shù)為立方體編碼計算其在布隆過濾器中的比特位置,并將相關(guān)比特置1.假設(shè)SVETree的二叉樹T的高度為H、葉節(jié)點數(shù)量(等于數(shù)據(jù)集記錄數(shù)量)為N,最外層兩重循環(huán)執(zhí)行次數(shù)為O(HN).假設(shè)立方體編碼系統(tǒng)有L層、一個編碼在布隆過濾器中使用r個比特存儲,最內(nèi)層兩重循環(huán)總執(zhí)行次數(shù)為O(Lr).綜上所述,HMAC哈希函數(shù)的總計算次數(shù)為O(rLHN),其中r為用戶給定的系統(tǒng)超參數(shù).

SVETree性能優(yōu)化應(yīng)關(guān)注于降低HMAC函數(shù)計算次數(shù)O(rLHN).由于r為用戶指定參數(shù),因此可從另外3個參數(shù)出發(fā),探索可能的優(yōu)化方向.

1)優(yōu)化1(降低立方體編碼系統(tǒng)層數(shù)L).一種可能的思路是在進(jìn)行立方體劃分時,使數(shù)據(jù)記錄在值域空間內(nèi)均勻分布,從而以更少的層數(shù)滿足劃分閾值τ的要求.

2)優(yōu)化2(降低SVETree樹高度H).一個可能的途徑是增加SVETree中樹節(jié)點分支數(shù)量,從二叉樹增長為K叉樹.對于|D|條數(shù)據(jù)記錄,K叉SVE-Tree的高度可降低為logK|D|.

3)優(yōu)化3(降低SVETree葉節(jié)點數(shù)量N).因為立方體編碼是以立方體為單位生成,屬于同個立方體的不同數(shù)據(jù)記錄具有相同的立方體編碼,在云服務(wù)器端進(jìn)行密文查詢與完整性證明生成時是不可區(qū)分的.因此可在SVETree中將具有相同編碼的葉節(jié)點合并,從而減少SVETree樹節(jié)點數(shù)量.

2 基于立方格索引的密文范圍查詢完整性驗證方法

基于性能優(yōu)化方向的分析,本文對SVETree的構(gòu)建流程與驗證數(shù)據(jù)結(jié)構(gòu)設(shè)計進(jìn)行針對性改進(jìn),并提出基于立方格索引的密文范圍查詢完整性驗證方法(CubeTree).

2.1 驗證數(shù)據(jù)結(jié)構(gòu)構(gòu)建

CubeTree驗證數(shù)據(jù)結(jié)構(gòu)以平衡多叉樹為基礎(chǔ),為樹中每個節(jié)點附加布隆過濾器,用于指導(dǎo)密文查詢與完整性證明生成,采用類似Merkle Hash Tree的簽名方式檢測數(shù)據(jù)篡改.CubeTree的構(gòu)建流程如算法2所示.

算法2CubeTree 構(gòu)建流程

輸入明文數(shù)據(jù)集D,加密密鑰SK,驗證密鑰sk,

哈希密鑰HK,分位數(shù)參數(shù)γ,

立方體記錄數(shù)閾值參數(shù)τ,樹節(jié)點分支數(shù)K,

布隆過濾器哈希函數(shù)數(shù)量r

輸出歸一化參數(shù)U,CubeTree驗證數(shù)據(jù)結(jié)構(gòu)T

1.D′,U∶=QuantileBasedNormalization(D,γ);

//基于分位數(shù)歸一化的數(shù)據(jù)重分布(優(yōu)化1)

2.CCS∶=GenerateCubeCodingSystem(D′,τ);

//立方體編碼系統(tǒng)生成

3.C∶=ConstructCubeCells(D′,CCS,SK);

//構(gòu)建立方格索引

4.T∶=GenerateTreeStructure(C,K);

//生成平衡K叉樹基礎(chǔ)結(jié)構(gòu)(優(yōu)化2,優(yōu)化3)

5.T∶=EncodeTree(T,C,sk,HK,r);

//K叉樹結(jié)構(gòu)編碼

6.T∶=AddVerificationSignature(T,sk);

//增加驗證簽名

7.RETURNU,T.

對于輸入的明文數(shù)據(jù)集D,CubeTree構(gòu)建流程中首先進(jìn)行基于分位數(shù)歸一化的數(shù)據(jù)重分布(優(yōu)化1),使數(shù)據(jù)集上所有記錄的各可查詢維度取值歸一化到[0, 1]區(qū)間內(nèi),在歸一化的過程中同時使記錄在值域空間內(nèi)的分布更均勻.優(yōu)化1會生成歸一化后的數(shù)據(jù)集D′以及對應(yīng)的歸一化參數(shù)U.數(shù)據(jù)擁有者在發(fā)送密鑰給客戶端時,會同時將歸一化參數(shù)U共享給客戶端;客戶端在進(jìn)行密文查詢時,首先將各維度查詢范圍采用參數(shù)U歸一化到[0, 1]區(qū)間,再生成查詢陷門.然后,根據(jù)歸一化后的數(shù)據(jù)集D′,生成立方體編碼系統(tǒng)CCS.基于CCS與加密密鑰SK,CubeTree構(gòu)建流程為D′生成對應(yīng)的加密立方格索引結(jié)構(gòu)C,并進(jìn)一步以C為基礎(chǔ)生成平衡K叉樹結(jié)構(gòu)(優(yōu)化2與優(yōu)化3).CubeTree構(gòu)建流程采用與SVETree相同的方式對平衡K叉樹進(jìn)行編碼,為每個樹節(jié)點生成布隆過濾器.最后,CubeTree構(gòu)建流程自底向上地為平衡K叉樹中所有節(jié)點增加驗證數(shù)字簽名,根節(jié)點的哈希簽名即為整棵樹的密碼學(xué)摘要.

2.2 基于分位數(shù)歸一化的數(shù)據(jù)重分布優(yōu)化

基于分位數(shù)歸一化的數(shù)據(jù)重分布優(yōu)化方法的目標(biāo)是降低立方體編碼系統(tǒng)在處理不均勻數(shù)據(jù)集時所需的層次數(shù)L,即對應(yīng)優(yōu)化方向1.SVETree在生成立方體編碼系統(tǒng)時會對數(shù)據(jù)值域空間進(jìn)行均勻網(wǎng)格劃分.但當(dāng)數(shù)據(jù)記錄在值域空間中的分布不均衡(如服從類指數(shù)分布、高斯分布等)時,數(shù)據(jù)密集區(qū)域的網(wǎng)格單元覆蓋的記錄數(shù)量將遠(yuǎn)超稀疏區(qū)域,如圖3中第2層和第3層.此時SVETree必須繼續(xù)增加立方體編碼系統(tǒng)的層次數(shù),使包含記錄數(shù)量最多的網(wǎng)格單元也在指定閾值τ以下.在理想情況下,如果能使數(shù)據(jù)完全均衡地分布在整個值域空間中,所需立方體編碼系統(tǒng)層次數(shù)L最小.

為了降低數(shù)據(jù)不均衡分布對立方體編碼系統(tǒng)層次數(shù)的影響,可采用自適應(yīng)網(wǎng)格劃分與數(shù)據(jù)重分布兩種思路.自適應(yīng)網(wǎng)格劃分的思路是根據(jù)數(shù)據(jù)分布情況自適應(yīng)生成劃分區(qū)間,使每個網(wǎng)格覆蓋的記錄數(shù)量盡量接近.但此方法要求記錄每個層次上所有維度的區(qū)間劃分點,當(dāng)層次數(shù)較高(如20層)時,每個維度需要記錄的劃分點數(shù)量在百萬規(guī)模,帶來較大的歸一化參數(shù)U空間開銷.因此本文采用基于分位數(shù)歸一化的數(shù)據(jù)重分布思路解決此問題,整體對記錄進(jìn)行均衡化的重分布操作,各層次依然可采用原有的均勻網(wǎng)格劃分方式.

重分布優(yōu)化的主要過程是：估計數(shù)據(jù)集在每個可查詢維度上的分位數(shù),根據(jù)分位數(shù)對原始數(shù)據(jù)取值進(jìn)行分段歸一化,從而使各維度取值分布更均衡.首先遍歷數(shù)據(jù)集中的每條記錄,獲得整個數(shù)據(jù)集在每個可查詢維度上的最小值min和最大值max.根據(jù)指定采樣率對數(shù)據(jù)集進(jìn)行隨機采樣,構(gòu)成小規(guī)模的采樣數(shù)據(jù)集.進(jìn)行隨機采樣的目的是為了以較低的開銷預(yù)估各維度的分位數(shù),避免全數(shù)據(jù)集分位數(shù)計算.對于每個可查詢維度i,獲取采樣數(shù)據(jù)集在該維度上的全部取值,形成維度值數(shù)組Vi,并將該維度在完整數(shù)據(jù)集上的最小值min[i]和最大值max[i]也加入Vi中.基于Vi,計算該維度的最小值、Q分位數(shù)與最大值,形成分位數(shù)數(shù)組qi,其中Q為用戶給定的分位數(shù)數(shù)量,qi包含Q+2個經(jīng)過排序的元素.

根據(jù)各維度的分位數(shù)數(shù)組qi,進(jìn)一步將所有記錄的取值歸一化到[0,1]區(qū)間上.對于數(shù)據(jù)記錄的第i個可查詢維度的取值x,在該維度的分位數(shù)數(shù)組qi中查找滿足條件

qi[y]≤x≤qi[y+1]

的最小數(shù)組下標(biāo)y,計算下標(biāo)y在分位數(shù)數(shù)組qi中的相對位置：

其中|qi|為分位數(shù)數(shù)組包含的元素數(shù)量.使用區(qū)間線性歸一化方法,計算x在[0,1]范圍內(nèi)的歸一化值：

后續(xù)步驟將使用歸一化后的數(shù)據(jù)集D′代替原始數(shù)據(jù)集進(jìn)行處理.需要注意的是,客戶端的查詢范圍也應(yīng)先用相同的分位數(shù)數(shù)組和公式進(jìn)行歸一化,再生成查詢陷門發(fā)送給云服務(wù)器進(jìn)行查詢.

圖4(a)為分布不均衡的原始數(shù)據(jù)集,圖中虛線表示數(shù)據(jù)集上兩個維度的分位數(shù)位置,(b)為分位數(shù)歸一化后的數(shù)據(jù)分布,記錄在值域空間[0,1]2中的分布更均衡.對于給定的網(wǎng)格劃分的閾值τ,在均衡的數(shù)據(jù)分布上只需更少的立方體編碼層次數(shù)L即可滿足要求.

在不進(jìn)行數(shù)據(jù)重分布的SVETree中,立方體編碼系統(tǒng)所需層次數(shù)受數(shù)據(jù)分布的顯著影響.在所有數(shù)據(jù)記錄集中分布在同個網(wǎng)格的最差情況下,SVETree的立方體編碼系統(tǒng)所需層次數(shù)可達(dá)用戶給出的層次數(shù)上限.在應(yīng)用基于分位數(shù)歸一化的數(shù)據(jù)重分布優(yōu)化后,將重分布后的歸一化值域空間記為[0,1]d,將子空間r?[0,1]d的體積記為|r|,將數(shù)據(jù)集D中被子空間r覆蓋的記錄集合記為

D(r)={i∈D|i的可查詢維度取值在r的范圍內(nèi)}.

(a)原始數(shù)據(jù)分布(b)歸一化數(shù)據(jù)分布

定理1給出在理想化重分布效果下立方體編碼系統(tǒng)所需的最小層次數(shù)L.

定理1在數(shù)據(jù)重分布后的d維值域空間[0,1]d中,如果對于任意體積相同的兩個子空間

?r?[0,1]d,r′?[0,1]d∶|r|=|r′|,

均有

|D(r)|=|D(r′)|,

則立方體編碼系統(tǒng)所需的最小層次數(shù)

證明立方體編碼系統(tǒng)的第l層將數(shù)據(jù)集值域的每個維度均勻劃分為2l個區(qū)間,將整個d維值域空間均勻劃分為2ld個網(wǎng)格(即子空間).因為任意體積相同的子空間包含記錄數(shù)相同,所以每個網(wǎng)格包含的記錄數(shù)為|D|/2ld.當(dāng)滿足|D|/2ld≤τ時,有

因此立方體編碼系統(tǒng)所需最小層次數(shù)為

2.3 基于平衡K叉樹的數(shù)據(jù)結(jié)構(gòu)扁平化

ServeDB的驗證數(shù)據(jù)結(jié)構(gòu)SVETree以平衡二叉樹為基礎(chǔ).在構(gòu)建時,二叉樹的每層都需要掃描一遍數(shù)據(jù)集上所有記錄,并根據(jù)記錄立方體編碼,利用HMAC哈希值計算布隆過濾器的插入位置,因此構(gòu)造開銷隨二叉樹的高度線性增長.

本文采用平衡K叉樹代替驗證數(shù)據(jù)結(jié)構(gòu)中的平衡二叉樹作為基礎(chǔ)數(shù)據(jù)結(jié)構(gòu),增加樹節(jié)點分支數(shù)K以降低整棵樹的高度H,K叉樹結(jié)構(gòu)同樣支持完整性驗證所需的遍歷、查詢與自底向上的哈希簽名計算等操作.下面介紹采用自底向上的方式確定性地構(gòu)造平衡K叉樹結(jié)構(gòu).首先,為數(shù)據(jù)集上d條記錄(或立方格)創(chuàng)建對應(yīng)的d個葉節(jié)點.然后,從葉節(jié)點所在的第0層出發(fā),逐層向上迭代以創(chuàng)建中間節(jié)點.假如第L層有x個樹節(jié)點,則每K個節(jié)點為一組,在第L+1層創(chuàng)建「x/K?個父節(jié)點,將其中第L層的第0至K-1個樹節(jié)點對應(yīng)第L+1層第0個父節(jié)點,第L層的第K至2K-1個樹節(jié)點對應(yīng)下一個父節(jié)點,依次類推.當(dāng)?shù)贚+1層只包含一個父節(jié)點時,停止創(chuàng)建,此時最后一個創(chuàng)建的節(jié)點為樹的根節(jié)點.

一棵平衡四叉樹結(jié)構(gòu)如圖5所示,每個葉節(jié)點對應(yīng)一個立方格,第0層的9個葉節(jié)點將在第1層中對應(yīng)創(chuàng)建3個父節(jié)點,其中編號為0～3的葉節(jié)點對應(yīng)編號為9的父節(jié)點(即第1層的第0個頂點).

定理2當(dāng)平衡K叉樹的葉節(jié)點數(shù)量為N時,平衡K叉樹的高度至多為logKN,樹節(jié)點數(shù)量為O(N).

證明根據(jù)平衡K叉樹的構(gòu)造過程,當(dāng)?shù)贚層的樹節(jié)點數(shù)量為x時,第L+1層的樹節(jié)點數(shù)量為「x/K?.根據(jù)遞推公式,當(dāng)?shù)?層的樹節(jié)點數(shù)量為N時,第L層的樹節(jié)點數(shù)量至少為N/KL.根節(jié)點的存在性要求N/KL≥1,從而L≤logKN.在不考慮節(jié)點數(shù)向上取整的情況下,樹中不同層包含的樹節(jié)點數(shù)量呈等比數(shù)列N,N/K,N/K2,…根據(jù)等比數(shù)列求和公式,樹中包含的節(jié)點數(shù)為(N-1)K(K-1)-1,考

圖5 平衡K叉樹結(jié)構(gòu)

慮每層樹節(jié)點數(shù)量的取整誤差,樹中包含的節(jié)點數(shù)上限為

因此樹中節(jié)點數(shù)量為O(N).

相比SVETree,采用平衡K叉樹并不會顯著增加樹中節(jié)點數(shù)量,反而可降低樹的高度,從而降低驗證數(shù)據(jù)結(jié)構(gòu)的構(gòu)建開銷.

不同葉節(jié)點數(shù)量下平衡K叉樹的高度隨分支數(shù)K的變化情況如圖6所示.由圖可知,當(dāng)K從2增長為4時,樹高度下降一半,但當(dāng)K繼續(xù)增加時,樹高度的降低效應(yīng)越來越不明顯.因為SVETree中每層樹節(jié)點的布隆過濾器的總長度相同,因此減少樹的高度可同時減少布隆過濾器的存儲開銷,但樹節(jié)點分支數(shù)K的增加可能會導(dǎo)致生成完整性證明所需遍歷的節(jié)點數(shù)量增加,從而增加驗證證明的存儲與傳輸開銷.在實踐中需要根據(jù)應(yīng)用的具體情況平衡分支數(shù)參數(shù)K的取值.

圖6 平衡K叉樹高度與分支數(shù)K的關(guān)系

2.4 基于立方格索引的驗證結(jié)構(gòu)

SVETree構(gòu)建過程計算開銷較高的一大原因是其內(nèi)部存在冗余HMAC哈希計算.SVETree為每條數(shù)據(jù)記錄建立一個對應(yīng)的葉節(jié)點,并根據(jù)葉節(jié)點構(gòu)建上層的平衡二叉樹.值得注意的是,在SVETree采用的立方體編碼系統(tǒng)中,被同個立方體(即網(wǎng)格單元)覆蓋的所有數(shù)據(jù)記錄具有相同的立方體編碼值.立方體編碼系統(tǒng)在每l層對每個維度均勻劃分為2l區(qū)間,相當(dāng)于將第l-1層的2l-1個區(qū)間進(jìn)一步均勻切分為2份.因此,如果2條記錄在第l層屬于同個立方體,則在第l-1層至第1層中均屬于同個父立方體,因此2條記錄在第l層及以上層次的立方體編碼相同.假設(shè)立方體編碼系統(tǒng)共包含L層,則2條記錄如果在第L層被同個立方體覆蓋,則這2條記錄將具有完全相同的立方體編碼集.SVETree在構(gòu)建時需要為2條記錄重復(fù)計算各自的HMAC哈希值,帶來大量的冗余計算開銷.

基于上述觀察,本文提出一種基于立方格索引的密文范圍查詢完整性方法(CubeTree),流程如圖7所示.CubeTree將歸一化后被同個最底層立方體(即最細(xì)粒度的立方體)覆蓋的所有記錄合并為一個立方格(Cube Cell),將每個葉節(jié)點索引一條數(shù)據(jù)記錄變?yōu)樗饕粋€立方格.立方格采用鍵值對的形式表示,其中鍵為立方格對應(yīng)最底層立方體的立方體編碼.鍵值對的值由兩部分組成：該立方格在每層的立方體編碼,該立方格覆蓋的所有記錄歸一化之前的原始記錄值.立方格中的原始記錄會進(jìn)一步被加密密鑰SK加密,從而得到密文立方格索引.數(shù)據(jù)擁有者向云服務(wù)器上傳密文立方格索引,從而避免向云服務(wù)器或其它第三方暴露明文記錄.

圖7 CubeTree流程圖

從原始數(shù)據(jù)集與歸一化數(shù)據(jù)集構(gòu)建立方格索引的過程如算法3所述.

算法3立方格索引構(gòu)建

輸入立方體編碼系統(tǒng)CCS,歸一化數(shù)據(jù)集D′,

原始數(shù)據(jù)集D,加密密鑰SK

輸出立方格索引C

C∶=newHashMap〈CubeCode,CubeCell〉();

FOR each recordr′∈D′ DO

code∶=GetCubeCode(CCS,r′,CCS.L);

//獲得歸一化記錄r′在第L層所屬立方體的編碼值

C[code].records.append(D[r′.ID]);

//將原始數(shù)據(jù)記錄加入立方格

END FOR

FOR eachcube_key∈C.keysDO

rid∶=C[cube_key].records[0].ID;

// 獲得一個代表性記錄的ID

tr∶=D′[rid];

// 獲得歸一化后的代表性記錄值

FORl∶= 1 toCCS.LDO

C[cube_key].codes[l]∶=

GetCubeCode(CCS,tr,l);

END FOR

C[cube_key].data∶=

Encrypt(C[cube_key].records,SK);

//對原始數(shù)據(jù)進(jìn)行加密

C[cube_key].records.clear();

//去除原始數(shù)據(jù)以保護(hù)隱私

END FOR

RETURNC

算法首先掃描一遍歸一化數(shù)據(jù)集,借助哈希表,對所有數(shù)據(jù)記錄按照記錄所屬最底層立方格的編碼code進(jìn)行分組,哈希表的鍵即為立方體編碼,哈希表的值存儲屬于該立方格的所有原始數(shù)據(jù)記錄.對于分組后的每個立方格,從立方格中隨機選取一條記錄作為代表記錄,根據(jù)歸一化后的記錄值,計算立方格在每層的立方體編碼,存儲到立方格的值部分中.然后,利用加密密鑰SK對立方格包含的原始數(shù)據(jù)記錄進(jìn)行整體加密,得到密文立方格數(shù)據(jù),并擦除明文數(shù)據(jù)以保護(hù)隱私.如果需要進(jìn)一步避免暴露每個立方格包含的記錄數(shù)信息,可對密文立方格進(jìn)行長度離散化處理,即向密文立方格數(shù)據(jù)的尾部填充一定長度的隨機值,使密文立方格對外顯示的數(shù)據(jù)長度為特定的離散化長度(如以1 KB為單位進(jìn)行離散化),從而模糊該立方格包含的具體記錄數(shù)量.

CubeTree可大幅減少立方格的數(shù)量及驗證數(shù)據(jù)結(jié)構(gòu)中對應(yīng)葉節(jié)點的數(shù)量,從而大幅降低HMAC哈希函數(shù)計算次數(shù)與驗證數(shù)據(jù)結(jié)構(gòu)的存儲開銷.定理3表明在理想化的重分布效果(見定理1的定義)下,采用CubeTree后立方格的數(shù)量為N/τ,其中τ為用戶給出的記錄數(shù)閾值.在理想化數(shù)據(jù)重分布的情況下,驗證數(shù)據(jù)結(jié)構(gòu)構(gòu)建過程中HMAC哈希函數(shù)的計算次數(shù)從SVETree的O(rLHN)降低為O(rLHN/τ).

定理3對于包含N條記錄的數(shù)據(jù)集D,在數(shù)據(jù)重分布后的d維值域空間[0,1]d中,如果對于任意體積相同的2個子空間

?r?[0,1]d,r′?[0,1]d∶|r|=|r′|,

均有

|D(r)|=|D(r′)|,

則立方格數(shù)量及驗證數(shù)據(jù)結(jié)構(gòu)中葉節(jié)點數(shù)量為「N/τ?.

證明根據(jù)定理1,立方體編碼系統(tǒng)所需最小層次數(shù)

在理想化的重分布效果下,在第L層中每個立方格中包含的記錄數(shù)為|D|/2Ld=τ,立方格的數(shù)量為「N/τ?.根據(jù)驗證數(shù)據(jù)結(jié)構(gòu)的構(gòu)造方法,每個立方格對應(yīng)一個葉節(jié)點,因此葉節(jié)點的數(shù)量也為「N/τ?.

2.5 驗證信息與完整性證明生成

CubeTree的驗證信息生成過程為CubeTree的樹節(jié)點增加布隆過濾器與哈希簽名,查詢結(jié)果的完整性證明的生成與校驗都需要哈希簽名的信息.

2.5.1 驗證信息生成

CubeTree的編碼過程(即為樹中的每個節(jié)點生成對應(yīng)的布隆過濾器)與SVETree的過程相同,在此不再贅述.CubeTree采用類似Merkle Hash Tree的方式,為經(jīng)過編碼的樹節(jié)點生成完整性驗證所需的數(shù)字簽名.在葉節(jié)點對應(yīng)立方格數(shù)據(jù)的哈希值與葉節(jié)點布隆過濾器哈希值拼接后,再利用HMAC機制由驗證密鑰SK簽名生成CubeTree葉節(jié)點的哈希簽名.所有子節(jié)點的哈希簽名以及該節(jié)點的布隆過濾器的哈希值拼接后,再利用HMAC機制由驗證密鑰sk簽名生成CubeTree的中間節(jié)點的哈希簽名.具體示例如圖8所示.此種簽名方式保證對任意立方格、任意節(jié)點的布隆過濾器數(shù)據(jù)的修改,都會導(dǎo)致CubeTree根節(jié)點的哈希簽名發(fā)生變化,從而可用于檢測整棵樹的數(shù)據(jù)是否被篡改.由于樹節(jié)點的哈希簽名由驗證密鑰sk生成,第三方在不知道密鑰的情況下無法偽造哈希簽名.

圖8 帶有驗證信息的CubeTree 結(jié)構(gòu)示例(K=3)

2.5.2 完整性證明生成與校驗

CubeTree在云服務(wù)器側(cè)根據(jù)用戶提交的查詢陷門進(jìn)行密文查詢、生成完整性證明的過程與SVETree類似.用戶提交的查詢陷門即為查詢范圍覆蓋的立方體編碼集合.在云服務(wù)器側(cè),SVETree與CubeTree既是密文查詢過程中使用的密文索引,也同時作為完整性驗證中的驗證數(shù)據(jù)結(jié)構(gòu)使用.云服務(wù)器在遍歷SVETree與CubeTree進(jìn)行密文查詢的過程中,會同步根據(jù)樹節(jié)點的驗證信息生成相應(yīng)的完整性證明.

對于用戶提交的查詢陷門,云服務(wù)器側(cè)從CubeTree的根節(jié)點出發(fā),自頂向下遞歸檢查查詢陷門集合中的每個立方體編碼是否存在于樹節(jié)點的布隆過濾器中.如果某個編碼存在,該樹節(jié)點屬于密文查詢的關(guān)鍵路徑,此時需要將該節(jié)點信息(包含布隆過濾器相關(guān)片段及樹節(jié)點的哈希簽名)加入完整性證明中,并遞歸查詢該節(jié)點的所有子節(jié)點;如果查詢陷門中的立方體編碼均不存在于樹節(jié)點的布隆過濾器,不再查詢該節(jié)點的子節(jié)點.在遞歸遍歷的過程中,如果遇到某個葉節(jié)點的布隆過濾器存在可匹配的立方體編碼,則該葉節(jié)點屬于被成功查詢的節(jié)點,將葉節(jié)點對應(yīng)的密文立方格加入查詢結(jié)果中,葉節(jié)點本身加入完整性證明中.

在圖8中,假設(shè)查詢陷門MQ中存在立方體編碼被包含在節(jié)點N12的布隆過濾器中,將節(jié)點N12加入完整性證明,并遞歸處理N12的所有子節(jié)點N9、N10和N11.假設(shè)N9的布隆過濾器與查詢陷門之間不存在匹配的立方體編碼,查詢過程終止在該節(jié)點.假設(shè)葉節(jié)點N4的布隆過濾器與查詢陷門中的每個編碼匹配,對應(yīng)的立方格C4被包含在查詢結(jié)果中.在圖8中,假設(shè)查詢陷門只包含立方格C4的立方體編碼,則所有被加入完整性證明的節(jié)點都以深色底紋標(biāo)出.

客戶端在接收到完整性證明后,根據(jù)查詢結(jié)果中的密文立方格數(shù)據(jù)重算對應(yīng)葉節(jié)點的哈希簽名,進(jìn)而從葉節(jié)點出發(fā)逐層向上重算至根節(jié)點的哈希簽名.在圖8中,可根據(jù)查詢結(jié)果中的立方格C4的數(shù)據(jù)以及完整性證明中N4的布隆過濾器內(nèi)容,重新計算N4的哈希簽名,并與證明中的N4的哈希簽名進(jìn)行比對.如果兩者一致,進(jìn)一步從N4逐層向上重算各父節(jié)點的哈希簽名,直至重算根節(jié)點的哈希簽名.將重算的根節(jié)點哈希簽名與數(shù)據(jù)擁有者共享的哈希簽名進(jìn)行比對,便可檢測查詢結(jié)果中C4的數(shù)據(jù)以及完整性證明中的相關(guān)節(jié)點數(shù)據(jù)是否被篡改.如果數(shù)據(jù)未被篡改,進(jìn)一步對其查詢過程的合法性進(jìn)行檢查,檢驗查詢陷門與樹節(jié)點布隆過濾器的匹配情況計算是否正確.

定理4在忽略布隆過濾器誤報概率的情況下,在一個具有n個立方格的CubeTree中,當(dāng)與查詢陷門匹配的葉節(jié)點數(shù)量為q時,完整性證明包含的樹節(jié)點數(shù)量為O(qKlogKn).

證明一個具有n個立方格的CubeTree的高度為logKn,從根節(jié)點出發(fā)到任意一個匹配的葉節(jié)點的路徑包含logKn個樹節(jié)點.對于每條路徑上的每個節(jié)點,完整性證明都會包含該節(jié)點以及該節(jié)點的K個子節(jié)點,因此完整性證明中包含的樹節(jié)點數(shù)量至少為O(qKlogKn).在忽略布隆過濾器誤報概率的情況下,如果一個節(jié)點被包含在完整性證明中,但該節(jié)點不在通往匹配葉節(jié)點的路徑上,則查詢陷門不會與這個節(jié)點的布隆過濾器匹配,完整性證明不會包含該節(jié)點的所有子節(jié)點,因此完整性證明至多包含O(qKlogKn)個樹節(jié)點.

CubeTree與SVETree完整性證明的構(gòu)建與傳輸開銷均受證明中包含的樹節(jié)點數(shù)量影響.如果查詢陷門與CubeTree的q個葉節(jié)點的布隆過濾器匹配,定理4表明CubeTree完整性證明中包含的樹節(jié)點數(shù)量為O(qKlogKn).因為SVETree的每個葉節(jié)點對應(yīng)一條記錄,同一查詢陷門在SVETree中所能匹配到的葉節(jié)點數(shù)量q′有可能遠(yuǎn)大于q(在理想重分布的情況下q′=τq),所以SVETree完整性證明中包含的樹節(jié)點數(shù)量遠(yuǎn)高于CubeTree,帶來較高的證明構(gòu)建與傳輸開銷.

3 實驗及結(jié)果分析

3.1 實驗環(huán)境

本節(jié)實驗將在配有Intel Xeon 6248@2.5 GHz CPU、192 GB內(nèi)存的Linux服務(wù)器上進(jìn)行,輸入輸出文件均存儲在服務(wù)器掛載的并行文件系統(tǒng)上.服務(wù)器的操作系統(tǒng)版本為CentOS 7.6(Linux Kernel 版本5.4),實驗中涉及程序均使用C++實現(xiàn),使用GCC 8.3.1編譯,采用OpenSSL庫版本1.1.1k進(jìn)行密碼學(xué)相關(guān)計算.

基于驗證數(shù)據(jù)結(jié)構(gòu)CubeTree,本節(jié)實現(xiàn)一個密文范圍查詢完整性驗證原型系統(tǒng),系統(tǒng)架構(gòu)如圖9所示.整個系統(tǒng)由數(shù)據(jù)擁有者、 查詢服務(wù)器與客戶端3個模塊組成.3個模塊之間的數(shù)據(jù)交互關(guān)系如圖9中箭頭所示.在3個模塊中,與完整性驗證相關(guān)的3個子模塊以灰色標(biāo)識,實驗將關(guān)注3個子模塊的性能表現(xiàn),包括子模塊執(zhí)行時間以及子模塊間數(shù)據(jù)傳輸開銷.

圖9 基于CubeTree的密文范圍查詢完整性驗證原型系統(tǒng)架構(gòu)

實驗中同時采用真實數(shù)據(jù)集與合成數(shù)據(jù)集.真實數(shù)據(jù)集選擇foursquare2014(簡記為fs14)[25]、gowalla(簡記為go)[26]、ebird(簡記為eb)[27]、foursquare2015(簡記為fs15)[28]、uswildfire(簡記為us)[29]數(shù)據(jù)集,具體信息如表3所示.由于在部分實驗中ServeDB執(zhí)行時間較長,因此從gowalla數(shù)據(jù)集上隨機抽樣50萬條記錄(簡記為go*)、從ebird數(shù)據(jù)集上隨機抽樣100萬條記錄(簡記為eb*)、從foursquare2015數(shù)據(jù)集上隨機抽樣300萬條記錄(簡記為fs15*)參與實驗.

表3 真實數(shù)據(jù)集信息

為了測試系統(tǒng)在大規(guī)模數(shù)據(jù)集上的性能表現(xiàn),采用隨機數(shù)生成器生成服從均勻分布(uni)、高斯分布(gau)、指數(shù)分布(exp)的合成數(shù)據(jù)集,3種分布的傾斜性逐漸增強,覆蓋完全均勻與極度不均衡的情況.如無特別說明,合成數(shù)據(jù)集的記錄數(shù)為200萬條,維度為三維.

如未特別說明,本節(jié)中所有實驗采用如下超參數(shù).對于SVETree和CubeTree,立方體編碼系統(tǒng)中每個立方體包含的記錄數(shù)閾值τ=10 000,立方體編碼系統(tǒng)的最大層次數(shù)L=25,布隆過濾器使用的哈希函數(shù)數(shù)量r=5,布隆過濾器以64 KB的固定長度進(jìn)行分段.CubeTree構(gòu)建時基于歸一化的數(shù)據(jù)重分布過程的采樣率為0.01%,分位數(shù)的最大數(shù)量為10 000,樹節(jié)點的分支數(shù)K=4.

3.2 與SVETree的性能對比

本節(jié)的目標(biāo)是對比ServeDB采用的驗證數(shù)據(jù)結(jié)構(gòu)SVETree與本文的CubeTree在驗證數(shù)據(jù)結(jié)構(gòu)構(gòu)建、驗證數(shù)據(jù)結(jié)構(gòu)存儲、完整性證明生成與校驗等階段的執(zhí)行開銷情況.同時評估CubeTree中采用的3種優(yōu)化方法(優(yōu)化1：基于分位數(shù)歸一化的數(shù)據(jù)重分布優(yōu)化.優(yōu)化2：基于平衡K叉樹的數(shù)據(jù)結(jié)構(gòu)扁平化.優(yōu)化3：基于立方格索引的驗證結(jié)構(gòu)設(shè)計)的有效性.

3.2.1 驗證數(shù)據(jù)結(jié)構(gòu)構(gòu)建用時

本節(jié)對比構(gòu)建驗證數(shù)據(jù)結(jié)構(gòu)的構(gòu)建用時情況.實驗中測量SVETree構(gòu)建算法、僅使用優(yōu)化1的構(gòu)建算法、同時使用優(yōu)化1+優(yōu)化2的構(gòu)建算法,以及同時應(yīng)用3種優(yōu)化的構(gòu)建算法(CubeTree)的執(zhí)行時間,結(jié)果如圖10所示.由圖可見,3種優(yōu)化方法都能起到降低驗證數(shù)據(jù)結(jié)構(gòu)構(gòu)建用時的效果,隨著優(yōu)化的不斷疊加,優(yōu)化效果越來越明顯.對于所有數(shù)據(jù)集的平均情況,相比SVETree使用優(yōu)化1可將構(gòu)建用時平均降低19.5%,同時使用優(yōu)化1與優(yōu)化2可將構(gòu)建用時平均降低56.7%,同時使用3種優(yōu)化可將構(gòu)建用時平均降低99.4%.

圖10 驗證數(shù)據(jù)結(jié)構(gòu)構(gòu)建過程中執(zhí)行時間對比

在3種優(yōu)化方法中,優(yōu)化1的效果受數(shù)據(jù)集分布的傾斜性影響.在均勻分布的合成數(shù)據(jù)集uni上構(gòu)建用時僅降低0.2%,而在分布較傾斜的指數(shù)分布數(shù)據(jù)集exp上構(gòu)建用時降低51.8%.在優(yōu)化1的基礎(chǔ)上,優(yōu)化2在不同數(shù)據(jù)集上均體現(xiàn)出明顯的優(yōu)化效果,構(gòu)建用時在所有數(shù)據(jù)集上比只使用優(yōu)化1平均降低45.9%.CubeTree的優(yōu)化效果最顯著,相比使用優(yōu)化1+優(yōu)化2的情況,CubeTree進(jìn)一步將構(gòu)建用時平均降低98.7%.在所有數(shù)據(jù)集上,CubeTree將驗證數(shù)據(jù)結(jié)構(gòu)中樹節(jié)點的數(shù)量平均降低為SVETree的0.58%,大幅降低驗證數(shù)據(jù)結(jié)構(gòu)的構(gòu)建開銷.

3.2.2 驗證數(shù)據(jù)結(jié)構(gòu)存儲開銷

本節(jié)對比SVETree、CubeTree以及不同優(yōu)化下驗證數(shù)據(jù)結(jié)構(gòu)占用的存儲開銷,具體如圖11所示.

對于所有數(shù)據(jù)集的平均情況,相比SVETree,優(yōu)化1由于只改變數(shù)據(jù)分布,對驗證數(shù)據(jù)結(jié)構(gòu)的存儲開銷幾乎沒有影響,而采用優(yōu)化2后存儲開銷平均降低27.2%,而同時采用3種優(yōu)化的CubeTree存儲開銷平均降低85.5%.CubeTree將樹節(jié)點的數(shù)量平均降低99.6%,從而減少大量的布隆過濾器存儲開銷.

圖11 驗證數(shù)據(jù)結(jié)構(gòu)的存儲開銷對比

3.2.3 查詢與完整性驗證開銷

與密文查詢過程有關(guān)的執(zhí)行開銷包括云服務(wù)器側(cè)的查詢延遲、云服務(wù)器與客戶端之間傳輸完整性證明的通信開銷,以及客戶端側(cè)對完整性證明進(jìn)行校驗的時間開銷.因為SVETree與CubeTree的密文查詢過程與完整性證明生成過程是交織在一起同步進(jìn)行的,因此實驗中測量的云服務(wù)器側(cè)查詢延遲也同時是完整性證明的生成用時.

因為密文查詢與完整性證明的開銷受查詢范圍與查詢結(jié)果規(guī)模的顯著影響,實驗首先分別在fs14、us數(shù)據(jù)集上測量查詢與完整性驗證開銷隨相對查詢范圍的變化情況.相對查詢范圍定義為查詢范圍空間占整個數(shù)據(jù)集值域空間的比例,以一個隨機采樣的數(shù)據(jù)記錄為中心確定.查詢范圍對查詢開銷與完整性驗證開銷的影響如圖12所示.由圖可見,CubeTree可有效降低查詢延時、完整性證明的通信開銷與客戶端側(cè)的驗證用時.對于實驗中采用的所有數(shù)據(jù)集與相對查詢范圍的平均情況,相比SVE-Tree,CubeTree的查詢延遲平均降低36.7%,完整性證明的傳輸開銷平均降低99.4%,完整性證明的校驗時間平均降低99.2%.CubeTree包含的樹節(jié)點數(shù)量顯著低于SVETree,而包含在樹節(jié)點中的布隆過濾器是完整性驗證證明生成與傳輸開銷的主要來源,因此CubeTree完整性證明的相關(guān)開銷顯著低于SVETree.

(a)服務(wù)器端查詢開銷 (b)完整性證明通信開銷 (c)完整性證明校驗開銷

進(jìn)一步在隨機數(shù)據(jù)集上評估數(shù)據(jù)集維度對查詢延遲與完整性驗證開銷的影響.實驗中采用隨機數(shù)生成器生成服從均勻分布(uni)與高斯分布(gau)、包含50萬條記錄且具有不同維度的數(shù)據(jù)集,在相對查詢范圍為10-3時,CubeTree與SVETree云服務(wù)器側(cè)的查詢延時、完整性證明的通信開銷與客戶端側(cè)完整性證明驗證時間如圖13所示.由圖可見,對于所有數(shù)據(jù)集與維度的平均情況,相比SVETree,CubeTree的云服務(wù)器側(cè)查詢延遲平均降低85.9%、完整性證明規(guī)模平均降低99.8%、客戶端側(cè)的完整性證明驗證時間平均降低99.8%.實驗結(jié)果顯示查詢維度對SVETree與CubeTree的性能具有一定影響,但沒有顯著且穩(wěn)定的變化趨勢.

查詢與驗證開銷主要受查詢結(jié)果數(shù)的影響,在相對查詢范圍相同的情況下,當(dāng)查詢維度從2增至5時,對于高斯分布和均勻分布數(shù)據(jù)集上的查詢結(jié)果數(shù)量僅分別增至1.98倍和1.05倍,因此未顯著影響查詢與驗證開銷.

(a)服務(wù)器端查詢開銷 (b)完整性證明通信開銷 (c)完整性證明校驗開銷

3.3 與VeriRange的性能對比

近年來提出的密文范圍查詢完整性驗證方法VSRQ[20]、SAGTree[21]與VeriRange[22]均已與Serve-DB對比查詢延遲與驗證開銷,其中VeriRange提出的時間最晚、相比ServeDB性能提升最明顯,因此本節(jié)進(jìn)一步對比CubeTree與VeriRange.

因為Veri-Range是面向二維范圍查詢設(shè)計、無法支持三維及以上的多屬性范圍查詢,因此本節(jié)實驗選擇真實數(shù)據(jù)集上的經(jīng)度與緯度屬性作為二維范圍查詢條件,實驗中隨機采樣50萬條記錄進(jìn)行實驗.

實驗中調(diào)節(jié)VeriRange的網(wǎng)格劃分參數(shù)λ,使VeriRange的數(shù)據(jù)網(wǎng)格可包含的最大記錄數(shù)量與CubeTree的記錄數(shù)閾值τ保持一致,均不超過25 000條記錄.

以VeriRange原文獻(xiàn)提供的程序為基礎(chǔ),跳過密文索引構(gòu)建過程中的偽數(shù)據(jù)點添加過程,保證與CubeTree行為保持一致.程序中采用與CubeTree相同的加密方法與HMAC哈希函數(shù).

3.3.1 數(shù)據(jù)擁有者端執(zhí)行開銷

在真實數(shù)據(jù)集上對比CubeTree與VeriRange在數(shù)據(jù)擁有者側(cè)構(gòu)建密文索引與驗證數(shù)據(jù)結(jié)構(gòu)的構(gòu)建開銷,具體如圖14所示.

由圖14可見,相比VeriRange,CubeTree在所有數(shù)據(jù)集上將構(gòu)建用時平均降低90.4%,但CubeTree的存儲開銷平均增長51.8%.CubeTree以可接受的額外存儲開銷換取更低的構(gòu)建用時,使其具有良好的可擴展性.

(a)構(gòu)建用時

(b)存儲開銷

3.3.2 查詢與驗證開銷

CubeTree與VeriRange在us、fs14數(shù)據(jù)集上云服務(wù)器端查詢延遲與客戶端完整性證明的驗證開銷如圖15所示.由圖可知,相比CubeTree,VeriRange的查詢延遲在所有查詢范圍上平均降低99.9%、完整性證明通信開銷平均降低34.5%、完整性證明驗證時間平均降低99.0%.

VeriRange在查詢與驗證階段的性能優(yōu)勢來自如下兩方面：1)VeriRange直接對數(shù)據(jù)網(wǎng)格位置標(biāo)簽建立查詢索引,避免CubeTree中采用的布隆過濾器機制,降低查詢與驗證階段所需的計算與存儲開銷.2)VeriRange將數(shù)據(jù)網(wǎng)格索引結(jié)構(gòu)PKD樹作為查詢密鑰的一部分發(fā)送給客戶端存儲;在客戶端進(jìn)行密文查詢時,需要先在本地通過PKD樹獲取查詢范圍涉及的所有數(shù)據(jù)網(wǎng)格位置標(biāo)簽,再將位置標(biāo)簽作為查詢陷門發(fā)送至云服務(wù)器.VeriRange服務(wù)器端查詢過程僅需根據(jù)位置標(biāo)簽進(jìn)行輕量的哈希表查詢,并且客戶端不需要對查詢結(jié)果的完備性進(jìn)行額外驗證,從而大幅降低查詢與驗證開銷.

VeriRange的弊端在于其將原本屬于云服務(wù)器端的部分密文查詢工作,通過密鑰中的PKD樹分?jǐn)傊量蛻舳诉M(jìn)行.PKD樹的存儲開銷會受數(shù)據(jù)集規(guī)模與網(wǎng)格劃分參數(shù)的顯著影響,隨著記錄數(shù)增加、網(wǎng)格劃分粒度變細(xì),VeriRange的密鑰數(shù)據(jù)規(guī)模將持續(xù)增長,而CubeTree的密鑰規(guī)模則與數(shù)據(jù)集記錄數(shù)無關(guān).

(a)服務(wù)器端查詢開銷 (b)完整性證明通信開銷 (c)完整性證明校驗開銷

CubeTree與VeriRange在不同數(shù)據(jù)集上生成的密鑰數(shù)據(jù)規(guī)模如圖16所示.由圖可知,CubeTree的密鑰數(shù)據(jù)規(guī)模在所有數(shù)據(jù)集上平均為VeriRange的3.5%,且CubeTree的密鑰規(guī)模不受數(shù)據(jù)規(guī)模影響.

上述實驗結(jié)果表明,相比VeriRange,CubeTree在密文索引與驗證數(shù)據(jù)結(jié)構(gòu)構(gòu)建階段具有更優(yōu)的性能優(yōu)勢,而VeriRange在查詢與驗證階段具有較強的優(yōu)勢.

CubeTree的設(shè)計思路是將計算開銷盡可能分?jǐn)傊翐碛袕姶笏懔Φ脑品?wù)器側(cè)進(jìn)行,以減輕客戶端的計算壓力,因此更適用于云端算力資源豐富而客戶端存儲開銷緊張的場景或是需要三維及以上多維范圍查詢的應(yīng)用.而VeriRange的設(shè)計思路則是通過使客戶端適當(dāng)分?jǐn)偯芪牟樵兊挠嬎闩c存儲開銷,從而降低查詢與驗證階段的整體開銷,因此更適合二維范圍查詢中云端算力相對緊張而客戶端存儲資源相對充裕的場景.

圖16 CubeTree與VeriRange密鑰數(shù)據(jù)規(guī)模對比

3.4 超參數(shù)影響評估

CubeTree的構(gòu)建過程受立方體編碼系統(tǒng)中底層立方體包含的最大記錄數(shù)閾值τ、樹節(jié)點的分支數(shù)K、基于分位數(shù)歸一化過程中的采樣率與分位數(shù)數(shù)量等超參數(shù)的影響.本節(jié)將通過實驗評估上述超參數(shù)的影響.

3.4.1 立方體包含記錄數(shù)閾值

最底層立方體包含的最大記錄數(shù)閾值τ影響最底層立方體的覆蓋范圍與立方體編碼系統(tǒng)的層次數(shù),從而間接影響驗證數(shù)據(jù)結(jié)構(gòu)與完整性證明的相關(guān)開銷.隨著閾值τ的增加各種開銷的變化情況如圖17所示.實驗中g(shù)o數(shù)據(jù)集隨機采樣100萬條記錄(簡記為go-100w)參與計算,查詢范圍占數(shù)據(jù)集值域空間的1.25×10-4.

因為不同數(shù)據(jù)集的執(zhí)行時間、存儲開銷差異較大,為了統(tǒng)一對比不同數(shù)據(jù)集的情況,圖17將CubeTree的執(zhí)行時間、存儲開銷、完整性證明規(guī)模換算為與SVETree對應(yīng)開銷的相對值,并且將閾值τ換算為相對于數(shù)據(jù)集記錄總數(shù)的相對閾值.

由圖17可見,閾值τ對驗證數(shù)據(jù)結(jié)構(gòu)的構(gòu)建時間與存儲開銷的影響趨勢高度一致.對于實驗中2個數(shù)據(jù)集的平均情況而言,隨著閾值τ的上升,相比SVETree,CubeTree的相對執(zhí)行時間從49.2%降至0.4%,相對存儲開銷從51.2%降至2.6%,而完整性證明的相對通信開銷從292%降低至0.7%.

對于SVETree和CubeTree,閾值τ的上升均會使立方體編碼系統(tǒng)所需層次數(shù)下降、最底層立方體的覆蓋范圍增加,每個立方體/立方格內(nèi)將包含更多的數(shù)據(jù)記錄,導(dǎo)致完整性證明中包含更多不在查詢范圍內(nèi)的假陽性數(shù)據(jù)記錄,使SVETree的完整性證明假陽性率從平均54.9%升至76.7%,CubeTree的完整性證明假陽性率從平均3.2%升至93.0%.因此在實際應(yīng)用中應(yīng)根據(jù)具體需求選擇合適的閾值參數(shù),在驗證數(shù)據(jù)結(jié)構(gòu)/完整性證明的計算開銷與假陽性率之間取得平衡.

(a)驗證數(shù)據(jù)結(jié)構(gòu)構(gòu)建時間

(b)驗證數(shù)據(jù)結(jié)構(gòu)存儲開銷

(c)完整性證明通信開銷

(d)完整性證明假陽性率

3.4.2 樹節(jié)點分支數(shù)

CubeTree中樹節(jié)點分支數(shù)參數(shù)K影響Cube-Tree的構(gòu)建時間、存儲開銷以及完整性證明的通信開銷.上述開銷隨樹節(jié)點分支數(shù)K的變化情況如圖18所示.

實驗中g(shù)o數(shù)據(jù)集隨機采樣100萬條記錄參與計算(簡記為go-100w),查詢范圍占數(shù)據(jù)集值域空間的1.25×10-4.實驗結(jié)果顯示增加分支數(shù)K可顯著降低驗證數(shù)據(jù)結(jié)構(gòu)的構(gòu)建時間、存儲開銷以及完整性證明的規(guī)模.但過高的分支數(shù)(如K>64)會導(dǎo)致驗證數(shù)據(jù)結(jié)構(gòu)過于扁平,在完整性證明中包含更多樹節(jié)點,反而增大驗證證明規(guī)模,因此需根據(jù)應(yīng)用數(shù)據(jù)特點選擇合適的分支數(shù).

(a)驗證數(shù)據(jù)結(jié)構(gòu)構(gòu)建時間 (b)驗證數(shù)據(jù)結(jié)構(gòu)存儲開銷 (c)完整性證明通信開銷

3.4.3 采樣率與分位數(shù)數(shù)量

采樣率與分位數(shù)數(shù)量是CubeTree采用的基于分位數(shù)歸一化步驟的超參數(shù),直接影響驗證數(shù)據(jù)結(jié)構(gòu)中立方體編碼系統(tǒng)的層次數(shù).層次數(shù)越高,驗證數(shù)據(jù)結(jié)構(gòu)的構(gòu)建與存儲開銷越大.實驗評估采樣率的影響時,分位數(shù)數(shù)量固定為1 000;評估分位數(shù)數(shù)量的影響時,采樣率固定為0.1.具體結(jié)果如圖19所示.

隨著采樣率的降低,分位數(shù)估計值的準(zhǔn)確度下降,歸一化的優(yōu)化效果變?nèi)?導(dǎo)致立方體編碼系統(tǒng)層次數(shù)增加.而對于固定的采樣率,分位數(shù)數(shù)量的變化并不會顯著影響立方體編碼系統(tǒng)的層次數(shù).實驗表明基于分位數(shù)的歸一化優(yōu)化方法對于采樣率更敏感,而對分位數(shù)的取值相對不敏感.在計算開銷允許的條件下,可增加采樣率以提升分位數(shù)估計的精確度.

(a)采樣率

(b)分位數(shù)數(shù)量

3.5 數(shù)據(jù)可擴展性評估

在服從高斯分布的合成數(shù)據(jù)集上,測量SVE- Tree與CubeTree驗證數(shù)據(jù)結(jié)構(gòu)構(gòu)建過程的構(gòu)建用時與內(nèi)存開銷隨數(shù)據(jù)集規(guī)模的變化情況,構(gòu)建用時超過5 h認(rèn)為超時,具體結(jié)果如圖20所示.由圖可知,SVETree與CubeTree的構(gòu)建用時與內(nèi)存開銷均隨數(shù)據(jù)規(guī)模呈線性增長.通過對實驗數(shù)據(jù)進(jìn)行線性擬合估計,SVETree的平均構(gòu)建速度為383.5條/秒,而CubeTree的平均構(gòu)建速度為137 968.2條/秒.SVE- Tree和CubeTree構(gòu)建過程的內(nèi)存開銷分別是每條記錄平均6.5 KB和0.32 KB.

(a)構(gòu)建用時

(b)內(nèi)存開銷

實驗結(jié)果表明CubeTree具有良好的數(shù)據(jù)可擴展性,可擴展到億級規(guī)模數(shù)據(jù)集.在相同時間約束下,CubeTree處理的數(shù)據(jù)規(guī)模是SVETree的359.8倍;在相同內(nèi)存容量約束下,CubeTree處理的數(shù)據(jù)規(guī)模是SVETree的20.3倍.CubeTree可在850 s、40 GB的時空開銷內(nèi)為1.2億規(guī)模數(shù)據(jù)集構(gòu)建驗證數(shù)據(jù)結(jié)構(gòu),而SVETree在處理800萬規(guī)模數(shù)據(jù)集時所需時間已超過5 h.

4 結(jié) 束 語

針對現(xiàn)有前沿密文范圍查詢完整性驗證方法ServeDB難以處理大規(guī)模數(shù)據(jù)集的缺陷,本文首先對ServeDB的計算性能瓶頸進(jìn)行分析.執(zhí)行時間分解實驗表明驗證數(shù)據(jù)結(jié)構(gòu)SVETree構(gòu)建過程是制約其數(shù)據(jù)可擴展性的關(guān)鍵瓶頸.基于對性能瓶頸的具體來源分析,對SVETree的構(gòu)建流程進(jìn)行針對性的改進(jìn),提出基于立方格索引的密文范圍查詢完整性驗證方法(CubeTree).CubeTree采用基于分位數(shù)歸一化的數(shù)據(jù)重分布、基于平衡K叉樹的數(shù)據(jù)結(jié)構(gòu)扁平化、基于立方格索引的驗證數(shù)據(jù)結(jié)構(gòu)設(shè)計等優(yōu)化方法,大幅降低驗證數(shù)據(jù)結(jié)構(gòu)的構(gòu)建開銷與存儲開銷.實驗表明,相比SVETree,CubeTree能將驗證數(shù)據(jù)結(jié)構(gòu)的構(gòu)建時間平均減少99.4%、存儲開銷平均減少85.5%,完整性證明的相關(guān)開銷同樣有所降低.相比VeriRange,CubeTree適用于云端算力資源豐富而客戶端存儲開銷緊張的場景.同時,CubeTree具有良好的數(shù)據(jù)可擴展性,在相同時間限制下處理的數(shù)據(jù)集規(guī)模是SVETree的359.8倍,CubeTree構(gòu)建用時與內(nèi)存開銷隨數(shù)據(jù)集規(guī)模呈線性增長,可高效擴展到億級規(guī)模數(shù)據(jù)集.

今后可考慮進(jìn)一步研究基于MapReduce編程模型的并行化CubeTree構(gòu)建算法,通過并行計算的方法進(jìn)一步提升可擴展性,使其突破單機計算性能與內(nèi)存容量限制,擴展到更大規(guī)模的數(shù)據(jù)集.