[發(fā)明專利]一種具有訪問模式保護(hù)的空間數(shù)據(jù)范圍查詢方法

有效

• 申請(qǐng)?zhí)枺?/td>: 202011194473.1
• 申請(qǐng)日: 2020-10-30
• 公開（公告）號(hào): CN112307149B
• 公開（公告）日: 2022-11-25
• 發(fā)明（設(shè)計(jì)）人: 田豐;任青;盧相宜
• 申請(qǐng)（專利權(quán)）人: 陜西師范大學(xué)
• 主分類號(hào): G06F16/29
• 分類號(hào): G06F16/29;G06F16/9537;G06F21/60;G06F21/62
• 代理公司: 西安西達(dá)專利代理有限責(zé)任公司 61202
• 代理人: 劉華

1.一種具有訪問模式保護(hù)的空間數(shù)據(jù)范圍查詢方法，其特征在于，包括以下步驟：

第一步，在數(shù)據(jù)預(yù)處理階段，在本地對(duì)數(shù)據(jù)進(jìn)行離散化處理，使用糾刪碼機(jī)制編碼，使用訪問模式混淆方法對(duì)索引進(jìn)行混淆，最后將索引和數(shù)據(jù)分別加密上傳至云端，本步驟的具體做法如下：

步驟一，對(duì)于二維平面的數(shù)據(jù)集D＝{D₁,D₂,…,D_n}，共包含n條數(shù)據(jù)，其中第i條數(shù)據(jù)D_i＝(P_i,R_i)，表示位置信息P_i與記錄R_i的對(duì)應(yīng)關(guān)系，P_i相當(dāng)于記錄R_i的索引信息，將數(shù)據(jù)集對(duì)應(yīng)的數(shù)據(jù)空間離散化，得到二維、每維為T個(gè)刻度的數(shù)據(jù)空間，其中x∈[0,T]且y∈[0,T]，對(duì)于每一個(gè)坐標(biāo)點(diǎn)，都使用T²位的一維向量表示其坐標(biāo)位置，具體而言，對(duì)坐標(biāo)P＝(x,y)，計(jì)算i＝xT+y，則將位置向量第i位設(shè)為1，其他位為0，對(duì)空間離散化后，得到新的數(shù)據(jù)集D＝{(P₁,R₁),…(P_i,R_i),…(P_n,R_n)}，其中位置信息P由T²位一維二進(jìn)制向量表示，且只有一位為1，其余位為0；

步驟二，使用糾刪碼機(jī)制對(duì)數(shù)據(jù)集進(jìn)行處理，對(duì)于數(shù)據(jù)集D中的每一個(gè)數(shù)據(jù)D_i，將其中的R_i平均分成k個(gè)分片，通過編碼擴(kuò)展為m個(gè)分片，以便在查詢階段從m個(gè)分片中的任意k個(gè)分片恢復(fù)出完整數(shù)據(jù)，其中對(duì)于同一個(gè)記錄R_i所生成的記錄分片，由相同的P_i所指向，此時(shí)的數(shù)據(jù)集可表示為D＝{D₁,D₂,…,D_n}，其中D_i＝{(P_i,R_i1),(P_i,R_i2),…,(P_i,R_im)}，P_i為T²位一維二進(jìn)制向量；

步驟三，對(duì)數(shù)據(jù)集中的索引進(jìn)行混淆，即對(duì)指向記錄的坐標(biāo)位置P進(jìn)行混淆，這將最終轉(zhuǎn)化為對(duì)訪問模式的混淆，設(shè)定隱私參數(shù)a、b，其中a為訪問模式本身為訪問，不翻轉(zhuǎn)的概率，b表示訪問模式為0時(shí)的翻轉(zhuǎn)概率，基于用戶自定義的a、b，對(duì)于數(shù)據(jù)集中每一個(gè)記錄分片R_ij所對(duì)應(yīng)的位置信息P_i，都將做出獨(dú)立的混淆，即對(duì)于每一個(gè)記錄分片R_ij，將對(duì)數(shù)據(jù)空間中的每一個(gè)位置點(diǎn)都做判斷：

上述步驟將會(huì)破壞二進(jìn)制索引向量中只有一位為1，其余位為0的特性；因此需要對(duì)數(shù)據(jù)集中混淆后的位置索引進(jìn)行拆分；將多位為1的位置索引拆分為多個(gè)只有一位為1的二進(jìn)制索引，這些索引將共同指向同一個(gè)記錄；

經(jīng)過此步驟的混淆后，屬于同一個(gè)記錄R_i的記錄分片{R_i1,R_i2,…,R_im}將會(huì)被不同的位置向量所指向，此時(shí)的數(shù)據(jù)集可表示為：D＝{D₁,D₂,…,D_n}，其中D_i＝{(P_i1,R_i1),(P_i2,R_i1),…,(P_im,R_im)}；

步驟四，加密上傳至云端。將混淆后的索引信息以及記錄集合分別加密，上傳至服務(wù)器，其中使用K_I加密索引信息，使用K_D加密記錄信息；

第二步，在數(shù)據(jù)查詢階段，用戶在本地生成查詢向量，加密后形成查詢令牌上傳至云端，服務(wù)器使用SSW機(jī)制進(jìn)行密文下的檢索，然后將密文檢索結(jié)果返回給用戶，用戶使用糾刪碼機(jī)制進(jìn)行解碼，對(duì)解碼的結(jié)果再進(jìn)行解密，本步驟的具體做法如下：

步驟一，用戶在本地對(duì)空間進(jìn)行離散化，使用向量表示空間，首先枚舉待查詢的幾何范圍內(nèi)的所有點(diǎn)的集合，然后使用這個(gè)集合來表示查詢空間，使用T²維的二進(jìn)制向量表示查詢空間Q，將空間所包含點(diǎn)的對(duì)應(yīng)位置設(shè)置為0，其余位設(shè)置為1，這與數(shù)據(jù)預(yù)處理階段對(duì)數(shù)據(jù)集位置索引的處理恰好相反；

步驟二，使用加密密鑰K_I對(duì)查詢向量Q進(jìn)行加密，生成查詢令牌，并上傳給服務(wù)器；

步驟三，服務(wù)提供者使用SSW機(jī)制在密文下進(jìn)行查詢。對(duì)于數(shù)據(jù)集中的每一個(gè)記錄R_ij，服務(wù)提供者將其對(duì)應(yīng)的位置索引P_ij進(jìn)行計(jì)算，判斷其是否屬于待查詢區(qū)域Q，具體而言，對(duì)于每個(gè)位置索引向量P_ij(i∈[1,T²],j∈[1,m])，服務(wù)提供者利用SSW機(jī)制判斷向量P_ij與向量Q的內(nèi)積是否為0，若為0，則表示該位置屬于待查詢范圍Q，反之則不屬于，

逐一判斷后，服務(wù)提供商將屬于查詢范圍內(nèi)的位置坐標(biāo)所對(duì)應(yīng)的加密記錄分片返回給用戶；

步驟四，用戶使用密鑰K_D對(duì)記錄進(jìn)行解密，獲得明文信息；最后，用戶使用糾刪碼機(jī)制對(duì)記錄分片進(jìn)行解碼，恢復(fù)出完整的加密記錄，如果用戶可以獲得屬于同一個(gè)記錄R_ij的m份記錄分片中的k份，則可以通過糾刪碼機(jī)制完全恢復(fù)記錄R_ij。