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

有效

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

本發(fā)明公開了一種基于蒙特卡羅抽樣的前向安全k近鄰檢索方法及系統(tǒng)，所述方法包括：獲取數(shù)據(jù)集并進(jìn)行預(yù)處理，得到若干復(fù)雜桶并根據(jù)所述復(fù)雜桶生成數(shù)據(jù)集字典；根據(jù)代理重加密算法對每個所述復(fù)雜桶進(jìn)行加密，得到第一密鑰字典和雙向字典；在所述數(shù)據(jù)集字典和所述第一密鑰字典中找到待搜索點對應(yīng)的數(shù)據(jù)，并進(jìn)行重加密處理，得到搜索令牌及第二密鑰字典；根據(jù)所述搜索令牌在所述雙向字典中進(jìn)行數(shù)據(jù)搜索，得到密文數(shù)據(jù)；根據(jù)所述第二密鑰字典對所述密文數(shù)據(jù)進(jìn)行解密，以得到明文點集。本發(fā)明提供的前向安全k近鄰檢索方法通過使用代理重加密的加密方案和雙向字典存儲服務(wù)器中的密文數(shù)據(jù)，保證了數(shù)據(jù)提供商上傳給服務(wù)器的密文數(shù)據(jù)的前向安全屬性。

技術(shù)領(lǐng)域

本發(fā)明屬于數(shù)據(jù)安全技術(shù)領(lǐng)域，具體涉及一種基于蒙特卡羅抽樣的前向安全k近鄰檢索方法及系統(tǒng)。

背景技術(shù)

在大數(shù)據(jù)和云計算時代，越來越多的數(shù)據(jù)提供商選擇將數(shù)據(jù)上傳到云服務(wù)器進(jìn)行存儲，并通過付費的方法讓用戶進(jìn)行使用。但云服務(wù)器往往是不可信的，如果直接將數(shù)據(jù)不加密上傳，會導(dǎo)致數(shù)據(jù)提供商的隱私數(shù)據(jù)大量泄露。所以設(shè)計出安全高效的應(yīng)用與不同需求場景的加密技術(shù)，并支持對密文數(shù)據(jù)的動態(tài)更新的能力，是當(dāng)前云數(shù)據(jù)安全研究的熱點。

k近鄰檢索是為了檢索一個數(shù)據(jù)點的前k個最近鄰的點，是當(dāng)前大數(shù)據(jù)領(lǐng)域的重要技術(shù)，具有很大的應(yīng)用面，比如說空間數(shù)據(jù)的近鄰檢索、推薦系統(tǒng)等。傳統(tǒng)的k近鄰檢索技術(shù)，比如說近鄰圖和局部敏感哈希(LSH)等，均是明文上的檢索技術(shù)，當(dāng)直接上傳到云端時，會導(dǎo)致使用者的大量隱私信息泄露，所以需要將數(shù)據(jù)加密后上傳到服務(wù)器中，并保留對密文數(shù)據(jù)的k近鄰檢索和動態(tài)更新的能力。在解決k近鄰檢索的問題上，LSH方法是一個重要的解決方案，它通過將數(shù)據(jù)點通過局部敏感哈希函數(shù)進(jìn)行降維，然后壓縮進(jìn)對應(yīng)的哈希桶中，其中距離較近的點壓縮在同一哈希桶中的概率較大，而距離較遠(yuǎn)的點壓縮到同一哈希桶中的概率較小。

然而，現(xiàn)有的k近鄰檢索雖然可以保證對數(shù)據(jù)進(jìn)行加密，并支持近鄰查詢和動態(tài)更新的能力，但是都忽略了前向安全屬性，即數(shù)據(jù)提供商通常以付費的方式允許付費的用戶使用提供商外包給云服務(wù)器的密文數(shù)據(jù)，但是當(dāng)用戶付費的期限到期后，仍可使用之前獲得的令牌對服務(wù)器中新添加的數(shù)據(jù)進(jìn)行獲取和解密；此外，由于數(shù)據(jù)分布往往是不均勻的，這導(dǎo)致在使用LSH方法時，每個哈希桶內(nèi)點的數(shù)量差別很大，從而降低了數(shù)據(jù)安全性。

發(fā)明內(nèi)容

為了解決現(xiàn)有技術(shù)中存在的上述問題，本發(fā)明提供了一種基于蒙特卡羅抽樣的前向安全k近鄰檢索方法及系統(tǒng)。本發(fā)明要解決的技術(shù)問題通過以下技術(shù)方案實現(xiàn)：

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

獲取數(shù)據(jù)集并進(jìn)行預(yù)處理，得到若干復(fù)雜桶并根據(jù)所述復(fù)雜桶生成數(shù)據(jù)集字典；

根據(jù)代理重加密算法對每個所述復(fù)雜桶進(jìn)行加密，得到第一密鑰字典和雙向字典；

在所述數(shù)據(jù)集字典和所述第一密鑰字典中找到待搜索點對應(yīng)的數(shù)據(jù)，并進(jìn)行重加密處理，得到搜索令牌及第二密鑰字典；

根據(jù)所述搜索令牌在所述雙向字典中進(jìn)行數(shù)據(jù)搜索，得到密文數(shù)據(jù)；

根據(jù)所述第二密鑰字典對所述密文數(shù)據(jù)進(jìn)行解密，以得到明文點集。

在本發(fā)明的一個實施例中，獲取數(shù)據(jù)集并進(jìn)行預(yù)處理，得到若干復(fù)雜桶并生成數(shù)據(jù)集字典，包括：

獲取數(shù)據(jù)集，并根據(jù)基于蒙特卡羅抽樣的LSH函數(shù)將所述數(shù)據(jù)集生成若干均勻哈希桶；

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

根據(jù)所述復(fù)雜桶生成對應(yīng)的數(shù)據(jù)集字典。

在本發(fā)明的一個實施例中，所述根據(jù)代理重加密算法對每個所述復(fù)雜桶進(jìn)行加密，得到第一密鑰字典和雙向字典，包括：