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

有效

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

1.一種保護(hù)多方隱私的聯(lián)邦k近鄰查詢方法，其特征在于，具體包括：

首先，針對(duì)查詢點(diǎn)l_q，服務(wù)器生成k近鄰查詢請(qǐng)求q，并將該查詢請(qǐng)求q發(fā)送給n個(gè)數(shù)據(jù)擁有方客戶端，各客戶端分別執(zhí)行各自的本地k近鄰查詢，得到各自的本地查詢結(jié)果返給服務(wù)器端；

服務(wù)器端利用各本地查詢結(jié)果，確定聯(lián)邦k近鄰中第k近數(shù)據(jù)點(diǎn)距離的上界r_max和距離下界為r_min＝0；并進(jìn)一步通過(guò)上界r_max和下界r_min設(shè)定二分距離閾值r_q，利用二分距離閾值r_q生成范圍計(jì)數(shù)查詢請(qǐng)求RangeCount發(fā)送給各客戶端；

所述的確定聯(lián)邦k近鄰中第k近數(shù)據(jù)點(diǎn)距離的上下界，包括以下兩種：

1)、首先，客戶端F_i距查詢點(diǎn)l_q最遠(yuǎn)的距離為

L_i為客戶端F_i計(jì)算本地k近鄰查詢所得數(shù)據(jù)點(diǎn)集合，是客戶端F_i本地?cái)?shù)據(jù)集中，與查詢點(diǎn)l_q的距離值從小到大排序中第j近的數(shù)據(jù)點(diǎn)；

然后，各客戶端將各自的最遠(yuǎn)距離d₁,d₂,...,d_n分別發(fā)送至服務(wù)器端，服務(wù)器端選取其中最小值設(shè)為上界r_max＝min{d₁,d₂,...,d_n}；同時(shí)設(shè)定距離下界為r_min＝0；

2)、各客戶端將各自與查詢點(diǎn)的最遠(yuǎn)距離分別添加噪聲得d'_i＝d_i+Δ_i；

然后，各客戶端將添加噪聲后的最遠(yuǎn)距離d₁',d₂',...,d_n'分別發(fā)送至服務(wù)器端，服務(wù)器端選取其中最小值設(shè)為上界r_max＝min{d₁',d₂',...,d_n'}，同時(shí)設(shè)定下界為r_min＝0；

接著，各客戶端分別執(zhí)行查詢請(qǐng)求RangeCount，得到各自的查詢個(gè)數(shù)，結(jié)合多方安全計(jì)算技術(shù)，在保護(hù)各客戶端數(shù)據(jù)隱私的前提下將查詢個(gè)數(shù)進(jìn)行融合并發(fā)送至服務(wù)器端；

融合公式為：c＝c₁+c₂+…+c_n；c₁,c₂,...,c_n為各客戶端的查詢結(jié)果；

服務(wù)器端判斷融合結(jié)果是否滿足c≠k，且r_max-r_min＞t_r，如果是，更新聯(lián)邦k近鄰中第k近數(shù)據(jù)點(diǎn)距離的上界或下界；通過(guò)二分搜索不斷迭代從而逼近第k近數(shù)據(jù)點(diǎn)距離的值；否則，最終距離r為最終的r_q；t_r為設(shè)定閾值；

最后，服務(wù)器端根據(jù)查詢點(diǎn)l_q與最終距離r發(fā)起范圍查詢請(qǐng)求，并返給各客戶端；各客戶端分別在本地執(zhí)行范圍查詢請(qǐng)求，得到各自的查詢結(jié)果P₁,P₂,...,P_n；結(jié)合多方安全計(jì)算技術(shù)，在保護(hù)各客戶端數(shù)據(jù)來(lái)源隱私的前提下將最終的查詢結(jié)果進(jìn)行融合，并發(fā)送至服務(wù)器端，即為聯(lián)邦k近鄰查詢結(jié)果。

2.如權(quán)利要求1所述的一種保護(hù)多方隱私的聯(lián)邦k近鄰查詢方法，其特征在于，所述的k近鄰查詢請(qǐng)求q＝(l_q,k)，其中l(wèi)_q表示查詢點(diǎn)的坐標(biāo)，k表示與查詢點(diǎn)的距離最近的k個(gè)數(shù)據(jù)點(diǎn)。

3.如權(quán)利要求1所述的一種保護(hù)多方隱私的聯(lián)邦k近鄰查詢方法，其特征在于，所述的各客戶端為F₁,F₂,...,F_n；數(shù)據(jù)點(diǎn)集合為{L₁,L₂,...,L_i,...,L_n}。