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

王肇康 潘佳輝 周 璐

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

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

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

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

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

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

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

是其中一類常用的驗證數據結構.此類結構將數據記錄的哈希簽名作為葉節點,自底向上地構建樹型數據結構,樹中節點的哈希簽名由其子節點的簽名以及節點自身信息共同確定.上述簽名方式保證對任意數據記錄的篡改都會導致根節點哈希簽名發生變化,從而可驗證查詢結果的完整性.另一類完整性驗證方式采用較復雜的數字簽名實現,簽名鏈[9]將數據記錄按索引維度取值、排序,并采用鏈式方式為每條記錄生成數字簽名,客戶端基于鏈式簽名結構可同時驗證查詢結果的完備性與正確性.聚合簽名[10]利用雙線性聚合簽名等機制縮減完整性驗證證明的規模.此外,基于密碼學累加器[11-12]的方法在單維范圍查詢完整性驗證機制的基礎上,通過雙線性累加器等密碼學方法實現對多個單維范圍查詢結果的交集計算進行驗證,從而支持多屬性范圍查詢的完整性驗證.

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

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

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

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

1 ServeDB性能瓶頸分析

1.1 工作流程

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

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

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

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

圖2 驗證數據結構SVETree構建流程圖

圖3 二維立方體編碼系統網格劃分過程

驗證數據結構SVETree是一棵平衡二叉樹,二叉樹的每個葉節點對應數據集上的一條密文記錄.平衡二叉樹構建步驟將根據密文數據記錄創建一棵滿足上述條件的平衡二叉樹結構,并維護葉節點與密文記錄的對應關系.

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

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

1.2 執行時間分解分析

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

因為客戶端觸發的查詢次數較多,因此之前的研究工作著重于降低查詢過程中密文查詢與完整性驗證算法的執行開銷,忽略驗證數據結構構建算法對整個系統的數據可擴展性的制約.如果無法在可接受的時空開銷下生成驗證數據結構,ServeDB將難以實現大規模數據集的密文范圍查詢完整性驗證.

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

表1 foursquare2014數據集上ServeDB工作流程各步驟執行時間

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

表2 foursquare2014數據集上驗證數據結構SVETree構建過程各步驟執行時間

1.3 性能瓶頸來源分析

經過提取關鍵操作與適當簡化,二叉樹編碼步驟呈現算法1所示的4層循環結構.

算法1SVETree構建過程的二叉樹編碼步驟

輸入SVETree平衡二叉樹結構T,驗證私鑰sk,

立方體編碼系統CCS,哈希私鑰HK

輸出編碼后二叉樹結構T

FORn∶=T.nodes() DO

FOR 樹節點n覆蓋的每個葉節點leafDO

record∶=GetCorrespondingRecord(leaf);

FORl∶=1 toCCS.LDO

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

code∶=record.cube_codes[l];

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

FORi∶=1 torDO

// 計算編碼對應比特位置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

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

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

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

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

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

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

基于性能優化方向的分析,本文對SVETree的構建流程與驗證數據結構設計進行針對性改進,并提出基于立方格索引的密文范圍查詢完整性驗證方法(CubeTree).

2.1 驗證數據結構構建

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

算法2CubeTree 構建流程

輸入明文數據集D,加密密鑰SK,驗證密鑰sk,

哈希密鑰HK,分位數參數γ,

立方體記錄數閾值參數τ,樹節點分支數K,

布隆過濾器哈希函數數量r

輸出歸一化參數U,CubeTree驗證數據結構T

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

//基于分位數歸一化的數據重分布(優化1)

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

//立方體編碼系統生成

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

//構建立方格索引

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

//生成平衡K叉樹基礎結構(優化2,優化3)

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

//K叉樹結構編碼

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

//增加驗證簽名

7.RETURNU,T.

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

2.2 基于分位數歸一化的數據重分布優化

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

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

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

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

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

的最小數組下標y,計算下標y在分位數數組qi中的相對位置：

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

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

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

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

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

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

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

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

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

均有

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

則立方體編碼系統所需的最小層次數

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

因此立方體編碼系統所需最小層次數為

2.3 基于平衡K叉樹的數據結構扁平化

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

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

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

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

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

圖5 平衡K叉樹結構

慮每層樹節點數量的取整誤差,樹中包含的節點數上限為

因此樹中節點數量為O(N).

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

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

圖6 平衡K叉樹高度與分支數K的關系

2.4 基于立方格索引的驗證結構

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

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

圖7 CubeTree流程圖

從原始數據集與歸一化數據集構建立方格索引的過程如算法3所述.

算法3立方格索引構建

輸入立方體編碼系統CCS,歸一化數據集D′,

原始數據集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]);

//將原始數據記錄加入立方格

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);

//對原始數據進行加密

C[cube_key].records.clear();

//去除原始數據以保護隱私

END FOR

RETURNC

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

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

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

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

均有

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

則立方格數量及驗證數據結構中葉節點數量為「N/τ?.

證明根據定理1,立方體編碼系統所需最小層次數

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

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

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

2.5.1 驗證信息生成

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

圖8 帶有驗證信息的CubeTree 結構示例(K=3)

2.5.2 完整性證明生成與校驗

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

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

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

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

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

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

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

3 實驗及結果分析

3.1 實驗環境

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

基于驗證數據結構CubeTree,本節實現一個密文范圍查詢完整性驗證原型系統,系統架構如圖9所示.整個系統由數據擁有者、 查詢服務器與客戶端3個模塊組成.3個模塊之間的數據交互關系如圖9中箭頭所示.在3個模塊中,與完整性驗證相關的3個子模塊以灰色標識,實驗將關注3個子模塊的性能表現,包括子模塊執行時間以及子模塊間數據傳輸開銷.

圖9 基于CubeTree的密文范圍查詢完整性驗證原型系統架構

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

表3 真實數據集信息

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

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

3.2 與SVETree的性能對比

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

3.2.1 驗證數據結構構建用時

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

圖10 驗證數據結構構建過程中執行時間對比

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

3.2.2 驗證數據結構存儲開銷

本節對比SVETree、CubeTree以及不同優化下驗證數據結構占用的存儲開銷,具體如圖11所示.

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

圖11 驗證數據結構的存儲開銷對比

3.2.3 查詢與完整性驗證開銷

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

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

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

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

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

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

3.3 與VeriRange的性能對比

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

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

實驗中調節VeriRange的網格劃分參數λ,使VeriRange的數據網格可包含的最大記錄數量與CubeTree的記錄數閾值τ保持一致,均不超過25 000條記錄.

以VeriRange原文獻提供的程序為基礎,跳過密文索引構建過程中的偽數據點添加過程,保證與CubeTree行為保持一致.程序中采用與CubeTree相同的加密方法與HMAC哈希函數.

3.3.1 數據擁有者端執行開銷

在真實數據集上對比CubeTree與VeriRange在數據擁有者側構建密文索引與驗證數據結構的構建開銷,具體如圖14所示.

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

(a)構建用時

(b)存儲開銷

3.3.2 查詢與驗證開銷

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

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

VeriRange的弊端在于其將原本屬于云服務器端的部分密文查詢工作,通過密鑰中的PKD樹分攤至客戶端進行.PKD樹的存儲開銷會受數據集規模與網格劃分參數的顯著影響,隨著記錄數增加、網格劃分粒度變細,VeriRange的密鑰數據規模將持續增長,而CubeTree的密鑰規模則與數據集記錄數無關.

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

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

上述實驗結果表明,相比VeriRange,CubeTree在密文索引與驗證數據結構構建階段具有更優的性能優勢,而VeriRange在查詢與驗證階段具有較強的優勢.

CubeTree的設計思路是將計算開銷盡可能分攤至擁有強大算力的云服務器側進行,以減輕客戶端的計算壓力,因此更適用于云端算力資源豐富而客戶端存儲開銷緊張的場景或是需要三維及以上多維范圍查詢的應用.而VeriRange的設計思路則是通過使客戶端適當分攤密文查詢的計算與存儲開銷,從而降低查詢與驗證階段的整體開銷,因此更適合二維范圍查詢中云端算力相對緊張而客戶端存儲資源相對充裕的場景.

圖16 CubeTree與VeriRange密鑰數據規模對比

3.4 超參數影響評估

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

3.4.1 立方體包含記錄數閾值

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

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

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

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

(a)驗證數據結構構建時間

(b)驗證數據結構存儲開銷

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

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

3.4.2 樹節點分支數

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

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

(a)驗證數據結構構建時間 (b)驗證數據結構存儲開銷 (c)完整性證明通信開銷

3.4.3 采樣率與分位數數量

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

隨著采樣率的降低,分位數估計值的準確度下降,歸一化的優化效果變弱,導致立方體編碼系統層次數增加.而對于固定的采樣率,分位數數量的變化并不會顯著影響立方體編碼系統的層次數.實驗表明基于分位數的歸一化優化方法對于采樣率更敏感,而對分位數的取值相對不敏感.在計算開銷允許的條件下,可增加采樣率以提升分位數估計的精確度.

(a)采樣率

(b)分位數數量

3.5 數據可擴展性評估

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

(a)構建用時

(b)內存開銷

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

4 結 束 語

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

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