[發(fā)明專利]一種保護(hù)多方隱私的聯(lián)邦k近鄰查詢方法

有效

• 申請?zhí)枺?/td>: 202110642737.3
• 申請日: 2021-06-09
• 公開（公告）號: CN113255002B
• 公開（公告）日: 2022-07-15
• 發(fā)明（設(shè)計）人: 童詠昕;李書緣;潘敘辰;薛春伯;史燁軒;陶乾;徐毅;許可
• 申請（專利權(quán)）人: 北京航空航天大學(xué)
• 主分類號: G06F21/62
• 分類號: G06F21/62;G06F16/9535
• 代理公司: 北京永創(chuàng)新實專利事務(wù)所 11121
• 代理人: 易卜

本發(fā)明公開了一種保護(hù)多方隱私的聯(lián)邦k近鄰查詢方法，屬于聯(lián)邦計算領(lǐng)域，具體為首先，針對查詢點l_q，服務(wù)器生成k近鄰查詢請求q并發(fā)送給n個客戶端，各客戶端分別執(zhí)行本地k近鄰查詢；服務(wù)器利用本地查詢結(jié)果確定聯(lián)邦k近鄰中第k近數(shù)據(jù)點的距離上界和下界，并生成范圍計數(shù)查詢請求發(fā)送給各客戶端；各客戶端將各自的查詢個數(shù)，結(jié)合多方安全計算技術(shù)進(jìn)行融合發(fā)送至服務(wù)器端。服務(wù)器端根據(jù)融合結(jié)果更新第k近數(shù)據(jù)點距離的上界或下界，通過迭代輸出最終距離r并發(fā)起范圍查詢請求。各客戶端在本地執(zhí)行后得到各自的查詢結(jié)果，進(jìn)行融合發(fā)送至服務(wù)器端，得到最終聯(lián)邦k近鄰查詢結(jié)果。本發(fā)明不僅能保護(hù)各數(shù)據(jù)擁有方的數(shù)據(jù)隱私，且能高效完成計算。

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

本發(fā)明屬于聯(lián)邦計算領(lǐng)域，具體涉及一種保護(hù)多方隱私的聯(lián)邦k近鄰查詢方法。

背景技術(shù)

隨著大數(shù)據(jù)時代的飛速發(fā)展，數(shù)據(jù)在各種產(chǎn)業(yè)應(yīng)用中具有越來越重要的價值。由于單一主體所擁有的數(shù)據(jù)有限，因此各主體間互相共享數(shù)據(jù)能進(jìn)一步挖掘數(shù)據(jù)所含價值。然而出于保護(hù)敏感數(shù)據(jù)隱私的考量以及受監(jiān)管政策所限制，各主體不能直接拿出數(shù)據(jù)進(jìn)行共享。因此如何在“數(shù)據(jù)不能出本地”這一保護(hù)隱私的聯(lián)邦場景下，完成多方協(xié)同的查詢與計算成為亟待解決的問題。

k近鄰查詢是指返回數(shù)據(jù)集中距查詢點最近的前k個點，是數(shù)據(jù)庫的經(jīng)典查詢之一，可用于聚類、檢索等。而聯(lián)邦k近鄰是指數(shù)據(jù)分布在多個數(shù)據(jù)擁有方中，如何在各數(shù)據(jù)擁有方不交出數(shù)據(jù)即“數(shù)據(jù)不出本地”的前提下，完成所有數(shù)據(jù)上的k近鄰查詢。

已有保護(hù)數(shù)據(jù)隱私的查詢處理方法如加密數(shù)據(jù)庫技術(shù)，是指數(shù)據(jù)擁有方將數(shù)據(jù)加密并上傳至云服務(wù)器，云服務(wù)器在加密數(shù)據(jù)上進(jìn)行查詢與計算操作；該技術(shù)也可應(yīng)用至多方共享數(shù)據(jù)場景下的k近鄰查詢：首先，各方使用同態(tài)加密技術(shù)將所有數(shù)據(jù)均加密上傳至云端服務(wù)器；服務(wù)器在密文上計算所有數(shù)據(jù)點距查詢點的距離；最后對這些距離排序并選出前k個最近的數(shù)據(jù)點作為答案。

盡管該方法在完成查詢的同時一定程度上保護(hù)了數(shù)據(jù)隱私，但是并不能滿足“數(shù)據(jù)不出本地”的隱私保護(hù)要求。但是由于各方均需要將全部數(shù)據(jù)加密傳出本地至云服務(wù)器，而云服務(wù)器匯集了所有數(shù)據(jù)一旦被攻擊，數(shù)據(jù)泄露風(fēng)險極大，且難以保證云服務(wù)提供商的可靠性。因此該方法不能滿足“數(shù)據(jù)不出本地”的聯(lián)邦隱私保護(hù)要求。

在聯(lián)邦數(shù)據(jù)庫技術(shù)中，其架構(gòu)主要由各數(shù)據(jù)擁有方的本地數(shù)據(jù)庫和中心管理系統(tǒng)組成。針對用戶發(fā)起的查詢，中心管理系統(tǒng)首先將該查詢進(jìn)行解析和拆分，其次由各數(shù)據(jù)擁有方的本地數(shù)據(jù)庫系統(tǒng)執(zhí)行拆分所得的子查詢，最后由中心管理系統(tǒng)聚合各查詢結(jié)果從而得到該查詢的最終結(jié)果。

該技術(shù)盡管避免了直接匯總各數(shù)據(jù)擁有方的數(shù)據(jù)，減少了發(fā)送出本地的數(shù)據(jù)量，一定程度上貼合“數(shù)據(jù)不出本地”的思想，但在查詢拆分和結(jié)果聚合過程中并不考慮保護(hù)數(shù)據(jù)隱私，因此該技術(shù)也難以滿足在聯(lián)邦場景下進(jìn)行保護(hù)隱私的查詢。

近年來也出現(xiàn)了一些基于聯(lián)邦數(shù)據(jù)庫架構(gòu)并保護(hù)數(shù)據(jù)隱私的數(shù)據(jù)聯(lián)邦系統(tǒng)，然而這些系統(tǒng)多針對關(guān)系型數(shù)據(jù)庫的查詢，并未解決諸如k近鄰查詢等空間數(shù)據(jù)上的經(jīng)典查詢。

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

針對現(xiàn)有技術(shù)的不足，本發(fā)明采用了多方安全計算技術(shù)，通過設(shè)計聯(lián)邦場景下k近鄰查詢的拆分與結(jié)果聚合方法，使各數(shù)據(jù)擁有方在不泄露本地數(shù)據(jù)隱私的前提下，達(dá)到了共享數(shù)據(jù)協(xié)同計算k近鄰查詢的效果，具體是一種保護(hù)多方隱私的聯(lián)邦k近鄰查詢方法，具有在大規(guī)模數(shù)據(jù)上安全高效的計算聯(lián)邦k近鄰查詢的優(yōu)勢，實現(xiàn)多數(shù)據(jù)擁有方在數(shù)據(jù)不出本地前提下完成保護(hù)數(shù)據(jù)隱私的數(shù)據(jù)共享。

所述的保護(hù)多方隱私的聯(lián)邦k近鄰查詢方法，具體步驟如下：

步驟一、針對查詢點l_q，服務(wù)器生成k近鄰查詢請求q；

q＝(l_q，k)，其中l(wèi)_q表示查詢點的坐標(biāo)，k表示與查詢點的距離最近的k個數(shù)據(jù)點。