[發明專利]基于蒙特卡羅抽樣的前向安全k近鄰檢索方法及系統

有效

• 申請號: 202010319210.2
• 申請日: 2020-04-21
• 公開（公告）號: CN111552988B
• 公開（公告）日: 2023-05-02
• 發明（設計）人: 彭延國;王騰宇;候勇超;呂楨;王龍;李鑫
• 申請（專利權）人: 西安電子科技大學
• 主分類號: G06F21/62
• 分類號: G06F21/62
• 代理公司: 西安嘉思特知識產權代理事務所(普通合伙) 61230
• 代理人: 李園園

1.一種基于蒙特卡羅抽樣的前向安全k近鄰檢索方法，其特征在于，包括：

獲取數據集并進行預處理，得到若干復雜桶并根據所述復雜桶生成數據集字典，具體包括：

獲取數據集，并根據基于蒙特卡羅抽樣的局部敏感哈希函數將所述數據集生成若干均勻哈希桶；

將所述數據集生成若干均勻哈希桶；

對所述均勻哈希桶進行貪婪合并并加入假點，得到若干數據量完全相同的復雜桶；

根據所述復雜桶生成對應的數據集字典；

根據代理重加密算法對每個所述復雜桶進行加密，得到第一密鑰字典和雙向字典，具體包括：對每個所述復雜桶采用代理重加密算法生成第一密鑰對、第二密鑰對及對應的加密數據集；

根據所有復雜桶對應的第一密鑰對和第二密鑰對生成第一密鑰字典；

初始化一個雙向字典，并將所有復雜桶對應的加密數據集存儲到所述雙向字典中；

在所述數據集字典和所述第一密鑰字典中找到待搜索點對應的數據，并進行重加密處理，得到搜索令牌及第二密鑰字典，具體包括：

獲取待搜索點以及鄰近點的搜索數量；

在所述數據集字典中找到與所述待搜索點對應的復雜桶，并生成第三密鑰對以及對應的第三密文；

在所述第一密鑰字典中找到與所述待搜索點對應的第一密鑰對和第二密鑰對，并生成對應的第一密文和第二密文；

根據所述第三密鑰對對所述第一密鑰對和第二密鑰對進行重加密，生成第一重加密密鑰；

根據所述第一密文、所述第二密文、所述第三密文以及所述第一重加密密鑰生成搜索令牌；

根據所述第三密鑰對及其對應的第三密文形成第二密鑰字典；

根據所述搜索令牌在所述雙向字典中進行數據搜索，得到密文數據；

根據所述第二密鑰字典對所述密文數據進行解密，以得到明文點集，具體包括：

在所述第二密鑰字典中找到與所述待搜索點復雜桶對應的第三密鑰對；

根據所述第三密鑰對對所述密文數據進行解密，得到待篩選的明文點集；

若判斷所述待篩選的明文點集數量小于預設搜索數量k時，擴大搜索范圍至2r-1個復雜桶，并在所述雙向字典中重復搜索，直至所述待篩選的明文點集數量大于等于預設搜索數量k；其中，r、k均為正整數；其中，所述2r-1個復雜桶包括當前搜索點所在的復雜桶以及向該復雜桶左右兩側各延伸的r-1個復雜桶；

選取前k個最近的點作為最終的明文點集。

2.根據權利要求1所述的前向安全k近鄰檢索方法，其特征在于，在根據所述第三密鑰對及其對應的第三密文形成第二密鑰字典之后，還包括：

更新所述第一密鑰字典。

3.根據權利要求1所述的前向安全k近鄰檢索方法，其特征在于，根據所述搜索令牌在所述雙向字典中進行數據搜索，得到密文數據，包括：

根據所述搜索令牌生成臨時搜索字典；

根據所述搜索令牌在所述雙向字典中搜索數據，并對搜索結果進行重加密得到搜索結果數據集；

將所述搜索結果數據集插入到所述臨時搜索字典中，得到密文數據。

4.根據權利要求3所述的前向安全k近鄰檢索方法，其特征在于，根據所述搜索令牌在所述雙向字典中搜索數據，并對搜索結果進行重加密得到搜索結果數據集之后，還包括：

更新所述雙向字典。

5.一種基于蒙特卡羅抽樣的前向安全k近鄰檢索系統，用于實現權利要求1-4任一項所述的基于蒙特卡羅抽樣的前向安全k近鄰檢索方法，其特征在于，包括：數據集供應裝置(1)、搜索裝置(2)以及解密裝置(3)，其中，

所述數據集供應裝置(1)包括：

數據獲取模塊(11)，用于獲取數據集并進行預處理，得到若干復雜桶并生成數據集字典；

初始化模塊(12)，用于根據代理重加密算法對每個所述復雜桶進行加密，得到第一密鑰字典和雙向字典，并將所述雙向字典傳送至所述搜索裝置(2)；

加密模塊(13)，用于在所述數據集字典和所述第一密鑰字典中找到待搜索點對應的數據，并進行重加密處理，得到搜索令牌及第二密鑰字典，同時將所述搜索令牌及所述第二密鑰字典傳送至所述解密裝置(3)；

所述搜索裝置(2)包括數據搜索模塊(21)，用于根據所述搜索令牌在所述雙向字典中進行數據搜索，得到密文數據，并將所述密文數據傳送至所述解密裝置(3)；

所述解密裝置(3)包括：

第一數據接收模塊(31)，用于接收所述搜索令牌并上傳至所述數據搜索模塊(21)以供所述數據搜索模塊(21)進行數據搜索；

第二數據接收模塊(32)，用于接收所述第二密鑰字典以及所述密文數據，并根據所述第二密鑰字典對所述密文數據進行解密，以得到明文點集。