[發明專利]一種針對加密的空間數據的圓形范圍搜索方法

有效

• 申請號: 201610113032.1
• 申請日: 2016-02-29
• 公開（公告）號: CN105791283B
• 公開（公告）日: 2018-09-21
• 發明（設計）人: 李洪偉;任昊;陳昊
• 申請（專利權）人: 電子科技大學
• 主分類號: H04L29/06
• 分類號: H04L29/06
• 代理公司: 成都點睛專利代理事務所(普通合伙) 51232
• 代理人: 葛啟函

1.一種針對加密的空間數據的圓形范圍搜索方法，其特征在于，包括以下步驟：

a.搜索用戶根據目標圓形查詢范圍產生搜索令牌，并將搜索令牌上傳至云服務器；所述搜索令牌包括第一正方形和第二正方形的查詢范圍，第一正方形為目標圓形的內接正方形，第二正方形為目標圓形的外接正方形；

b.云服務器根據搜索令牌進行搜索得到中間搜索結果，并將中間搜索結果和搜索令牌發送到可信第三方；所述云服務器中存儲有加密的空間數據：采用R樹作為數據索引結構，在明文的環境下，所有的數據點都被使用對應的分組策略分成區塊，區塊是R樹的最小外接矩形，R樹的葉子節點對應于空間數據庫的數據點；

所述中間搜索結果為搜索第一正方形與第二正方形與區塊相交的數據點在第一正方形與第二正方形之間的數據點的集合；

c.可信第三方解密中間搜索結果和搜索令牌，在明文條件下檢查哪些結果沒有在目標圓形查詢范圍內，并將錯誤的結果過濾后將剩下的最終搜索結果重新加密后返回云服務器；

d.云服務器將最終所搜結果發送給搜索用戶。

2.根據權利要求1所述的一種針對加密的空間數據的圓形范圍搜索方法，其特征在于，步驟a中所述搜索用戶根據目標圓形查詢范圍產生搜索令牌的具體方法為：搜索用戶輸入圓心和圓的半徑，假設圓心為(X，Y)，半徑為R，則可獲得第一正方形查詢范圍Q_in為第二正方形查詢范圍Q_ex為{(X-R,Y-R),(X+R,Y+R)}。

3.根據權利要求2所述的一種針對加密的空間數據的圓形范圍搜索方法，其特征在于，步驟a中所述第一正方形和第二正方形的查詢范圍經過非對稱的向量積保持加密算法加密后上傳至云服務器。

4.根據權利要求3所述的一種針對加密的空間數據的圓形范圍搜索方法，其特征在于，步驟b中所述云服務器中存儲有加密的空間數據，空間數據具體加密方法為：采用R樹作為數據索引結構，在明文的環境下，所有的數據點都被使用對應的分組策略分成區塊，區塊是R樹的最小外接矩形，R樹的葉子節點對應于空間數據庫的數據點；采用非對稱的向量積保持加密算法對區塊進行加密：使用V∈R^d來表示最小外接矩形的頂點，并且使用非對稱的向量積保持加密算法來加密頂點，非對稱的向量積保持加密算法將V的維數擴展，得到V₊＝(V^T|1)^T，然后通過使用矩陣密鑰M進行加密得到V_E＝M^-1V₊；其中，矩陣密鑰M為一個可逆的(d+1)×(d+1)矩陣；則云服務器中存儲的加密的空間數據至少包括加密數據點、R樹的雙親節點和孩子節點的關系。

5.根據權利要求4所述的一種針對加密的空間數據的圓形范圍搜索方法，其特征在于，步驟b中所述云服務器根據搜索令牌進行搜索的具體方法為：

根據步驟a中生成的第一正方形查詢范圍和第二正方形查詢范圍，判斷查詢范圍的四個邊是否與區塊相交，若是，則依次判斷該節點的子節點是否與查詢范圍的相交，重復查詢直至數據點為止，遍歷查詢范圍的所有邊后退出該步驟并將相交的數據點生成中間搜索結果。