[發明專利]構建密文范圍檢索結果完備性驗證數據結構的方法及系統

在審

• 申請號: 202310291313.6
• 申請日: 2023-03-23
• 公開（公告）號: CN116484399A
• 公開（公告）日: 2023-07-25
• 發明（設計）人: 王肇康;潘佳輝;周璐;季曹樅;張仲輝;宋雨欣
• 申請（專利權）人: 南京航空航天大學
• 主分類號: G06F21/60
• 分類號: G06F21/60;G06F16/22;G06F21/62
• 代理公司: 南京蘇高專利商標事務所(普通合伙) 32204
• 代理人: 張弛

1.一種構建密文范圍檢索結果完備性驗證數據結構的方法，其特征在于，包含以下步驟：

(1)從數據集所有者處獲取數據集，對數據集中的每條記錄賦予唯一且不重復的編號；

(2)獲取數據集中每個可檢索維度取值的全局最大值和全局最小值，從數據集中采樣部分數據記錄構成采樣數據集，根據采樣數據集在各可檢索維度上的取值以及該維度的全局最大值和全局最小值，計算各可檢索維度的分位數數組，分位數數組包含了可搜索維度中的多個分位數；

(3)對于數據集中的每條記錄，將記錄各維度的取值x歸一化到[0,1]范圍之間；對于記錄的每一個可檢索維度的取值x，根據相應維度的分位數數組，計算x所處于的分位數區間，如果x的取值在分位數數組中a％分位數與b％分位數范圍之間，則將x歸一化到[a/100％,b/100％]范圍之間，并用歸一化后的值替換取值x，從而得到歸一化數據集；

(4)根據歸一化數據集，通過迭代搜索合適的立方體編碼系統層次數L，在第L輪迭代中，將整個數據值域空間平均劃分為2^dL個立方體單元，其中d是數據集可檢索維度數量；根據立方體單元取值范圍與歸一化的數據記錄取值的包含關系，將數據記錄分配到相應的立方體單元中；如果立方體單元所包含記錄數量的最大值小于等于指定閾值，則迭代過程停止，此時的迭代輪數即為立方體編碼系統層次數；

(5)對于歸一化數據集中的每一條記錄，根據該記錄在各個立方體層次上所屬的立方體單元，生成立方體編碼集合；

(6)對歸一化數據集中的數據記錄按該數據記錄在最后一個立方體層次的立方體編碼進行分組，將具有相同立方體編碼的記錄分為一組，為每一組記錄構造立方格，記錄的立方體編碼構成立方格的鍵，每一組的記錄內容構成立方格的值，對立方格的值進行加密，形成加密的立方格索引；

(7)根據加密的立方格索引，構造k叉樹結構，k為任意大于等于2的正整數，k叉樹中的每個節點有至多k個子節點，k叉樹的葉節點數量與立方格數量相同，每一個葉節點對應一個不同的立方格；

(8)為k叉樹的每個樹節點附加一個布隆過濾器，對于每個樹節點，將該樹節點所覆蓋的葉節點對應的立方格的所有立方體編碼插入到布隆過濾器中；

(9)為k叉樹中的每個樹節點生成節點哈希簽名，節點哈希簽名與該樹節點的布隆過濾器的內容、該樹節點的所有子節點的節點哈希簽名有關；

(10)加密的立方格索引、k叉樹和立方體編碼系統層次數共同構成了該數據集的用于密文范圍檢索結果完備性驗證的驗證數據結構，將該驗證數據結構上傳至云數據庫；同時將驗證數據結構的摘要信息共享至客戶，客戶進行校驗及查詢。

2.根據權利要求1所述的構建密文范圍檢索結果完備性驗證數據結構的方法，其特征在于，步驟(3)中在將一條記錄進行歸一化時，對于該記錄的每一個可檢索維度的取值x，在該維度的分位數數組q中查找滿足條件q[y]≤x≤q[y+1]的最小數組下標y，計算下標y在分位數數組中對應的分位數為和其中|q|是分位數數組q包含的元素數量，根據公式計算x的歸一化值norm(x)，歸一化后的值norm(x)的取值范圍在[0,1]之間。

3.根據權利要求1所述的構建密文范圍檢索結果完備性驗證數據結構的方法，其特征在于，步驟(5)中為記錄生成立方體編碼時，為每個立方體層次中的所有立方體生成唯一的編號，記錄的立方體編碼與立方體層次數以及記錄在該層次所屬的立方體編號相關。

4.根據權利要求1所述的構建密文范圍檢索結果完備性驗證數據結構的方法，其特征在于，步驟(7)中構造k叉樹的過程采用自底層，即葉節點所在層向上逐層構造的方式，對于某一層的樹節點，以k個為一組分組，為每組節點創建一個新的樹節點，這組節點均是新創建的樹節點的子節點，逐層構造樹節點直到某一層中只有一個樹節點為止。