[發(fā)明專利]基于向量同態(tài)加密的隱私保護(hù)K-NN分類方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201611190593.8
• 申請(qǐng)日: 2016-12-21
• 公開(kāi)（公告）號(hào): CN106790069B
• 公開(kāi)（公告）日: 2020-03-31
• 發(fā)明（設(shè)計(jì)）人: 楊浩淼;何偉超;黃云帆;冉鵬;姚銘軒;金保隆
• 申請(qǐng)（專利權(quán)）人: 電子科技大學(xué)
• 主分類號(hào): H04L29/06
• 分類號(hào): H04L29/06;H04L9/08;H04L9/00;G06F16/35;G06K9/62
• 代理公司: 成都希盛知識(shí)產(chǎn)權(quán)代理有限公司 51226
• 代理人: 濮云杉;楊冬

本發(fā)明涉及基于向量同態(tài)加密的隱私保護(hù)K?NN分類方法，包括：A.接收查詢向量組和標(biāo)準(zhǔn)向量組；B.通過(guò)查詢向量組生成矩陣G，標(biāo)準(zhǔn)向量組使用密鑰S通過(guò)向量同態(tài)加密生成密文組和新密鑰GS；C.對(duì)新密鑰GS進(jìn)行密鑰轉(zhuǎn)換為轉(zhuǎn)換密鑰S'，得到此時(shí)的轉(zhuǎn)換矩陣M和轉(zhuǎn)換密文組；D.使用轉(zhuǎn)換密鑰S'對(duì)轉(zhuǎn)換密文組解密，得到解密向量組；E.根據(jù)K個(gè)最小值的解密向量的分量為對(duì)應(yīng)的各查詢向量附上分類標(biāo)簽。本發(fā)明能夠良好的對(duì)用戶隱私數(shù)據(jù)保護(hù)，并且在隱私數(shù)據(jù)受到保護(hù)的情況下，通過(guò)K?NN算法對(duì)用戶的查詢向量進(jìn)行高效、準(zhǔn)確的分類，提高了對(duì)向量類型判斷的效率，擴(kuò)大了向量類型判斷的應(yīng)用范圍。

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

本發(fā)明涉及K-NN算法在隱私保護(hù)下的向量分類方法，具體的講是基于向量同態(tài)加密的隱私保護(hù)K-NN分類方法。

背景技術(shù)

K臨近算法(K-NN)廣泛應(yīng)用于模式識(shí)別中，在數(shù)據(jù)分類中也有良好的表現(xiàn)。在大數(shù)據(jù)時(shí)代，復(fù)雜的計(jì)算往往外包給第三方云。然而在這個(gè)過(guò)程中，外包的數(shù)據(jù)可能包含敏用戶的一些敏感的數(shù)據(jù)，直接將用戶的信息外包給第三方云很可能導(dǎo)致用戶的一些隱私信息泄露出去，給用戶造成損失。一種直接的解決方式就是將數(shù)據(jù)加密之后再上傳到云端，但是這也給K-NN算法的效率帶來(lái)一些新的挑戰(zhàn)。同態(tài)加密技術(shù)可以在密文下進(jìn)行操作，而解密之后的結(jié)果是正確的。于是可以將數(shù)據(jù)通過(guò)同態(tài)加密技術(shù)加密之后再在密文下運(yùn)行K-NN方法。傳統(tǒng)的加密方案主要針對(duì)整數(shù)進(jìn)行加密，對(duì)于向量的整體操作效率不高，出于效率方面的考慮可以使用向量的同態(tài)加密技術(shù)來(lái)加密數(shù)據(jù)，這樣可以大大提高運(yùn)行效率。

K-NN方法是以特征向量x為中心的一個(gè)鄰域里，固定落入鄰域中的樣本個(gè)數(shù)K(n)。通常采用如下方式實(shí)現(xiàn)：在一個(gè)合適的距離尺度下(常用的歐氏(Euclidean)距離)，逐漸地增大包圍x點(diǎn)的區(qū)域的體積，直到有K(n)個(gè)樣本點(diǎn)落入該區(qū)域中。在這過(guò)程中需要進(jìn)行概率密度估計(jì)，其密度估計(jì)形式為：其中，n為樣本個(gè)數(shù)，V(n)為該區(qū)域的體積。如果x點(diǎn)周圍的樣本點(diǎn)個(gè)數(shù)較少，那么相應(yīng)的區(qū)域就會(huì)變得很大，即V(n)的值很大，的值變得很小。相反，如果x點(diǎn)周圍的樣本點(diǎn)個(gè)數(shù)較多，那么相應(yīng)的區(qū)域就會(huì)變得較小，即V(n)的值較小，的值變得很大。并且K(n)也會(huì)隨n的增加而增加。由于K近鄰法則進(jìn)行概率估計(jì)密度時(shí)，存在兩個(gè)缺點(diǎn)，一是估計(jì)密度的積分必須擴(kuò)散到無(wú)窮大，二是計(jì)算上存在沉重的負(fù)擔(dān)。因此，一些研究學(xué)者直接用K-NN算法進(jìn)行分類，分類的原則是：在一定的距離尺度下，考慮待識(shí)別樣本x周圍的K(n)個(gè)最近鄰樣本，并將x歸入到K(n)個(gè)最近鄰中某一類樣本最多的那個(gè)類別中去。算法步驟：

(1)對(duì)一個(gè)待分類的數(shù)據(jù)對(duì)象y，計(jì)算它與訓(xùn)練集R中的每個(gè)數(shù)據(jù)對(duì)象的距離；

(2)找出待分?jǐn)?shù)據(jù)對(duì)象y與訓(xùn)練集R中的數(shù)據(jù)對(duì)象距離最近的k個(gè)；

(3)依次統(tǒng)計(jì)出這k個(gè)數(shù)據(jù)對(duì)象的所屬類別，找出包含最多個(gè)數(shù)的類；

(4)將待分?jǐn)?shù)據(jù)y劃分到此類中；

(5)重復(fù)以上步驟，直到所有待分?jǐn)?shù)據(jù)分類結(jié)束；

K-NN算法不僅可以用于分類，還可以用于回歸。通過(guò)找出一個(gè)樣本的K個(gè)最近鄰居，將這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。

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

本發(fā)明提供的基于向量同態(tài)加密的隱私保護(hù)K-NN分類方法，可在對(duì)用戶隱私數(shù)據(jù)保護(hù)的情況下，通過(guò)K-NN算法對(duì)用戶的查詢向量進(jìn)行高效、準(zhǔn)確的分類。

本發(fā)明基于向量同態(tài)加密的隱私保護(hù)K-NN分類方法，步驟包括：

A.接收查詢向量組(x₁，x₂，…x_n)和標(biāo)準(zhǔn)向量組(p₁，p₂，…p_m)，其中標(biāo)準(zhǔn)向量組(p₁，p₂，…p_m)對(duì)應(yīng)有標(biāo)準(zhǔn)分類標(biāo)簽(t₁，t₂，…t_m)；