支持隱私保護的k 近鄰分類器?

徐 劍 , 王安迪 , 畢 猛,3 , 周福才

1(東北大學(xué) 軟件學(xué)院,遼寧 沈陽 110169)

2(信息安全國家重點實驗室(中國科學(xué)院 信息工程研究所),北京 100093)

3(沈陽工業(yè)大學(xué),遼寧 沈陽 110023)

分類器是數(shù)據(jù)挖掘中對樣本進行分類的方法的統(tǒng)稱.其設(shè)計目標是在通過學(xué)習(xí)后,能夠?qū)?shù)據(jù)分到已知類別.分類器不僅應(yīng)用在搜索引擎以及各種檢索程序中,而且也大量應(yīng)用在數(shù)據(jù)分析與預(yù)測領(lǐng)域.kNN 分類器是一種重要的分類器,廣泛應(yīng)用于生物信息學(xué)、股票預(yù)測、網(wǎng)頁分類、鳶尾花類別預(yù)測等領(lǐng)域.

分類器在廣泛應(yīng)用的同時,也產(chǎn)生了嚴重的用戶隱私泄露問題[1,2],一旦泄露,會給數(shù)據(jù)擁有者帶來危害.比如,不法分子盜取患者癌癥信息,利用患者迫切希望治愈的心理,向患者銷售高價藥品,騙取錢財;在利用kNN 進行股票預(yù)測時,如果股民的個股信息在分類過程中被泄露,就會給股票市場帶來混亂.分類器處理的數(shù)據(jù)量大、種類多,與之相關(guān)的用戶數(shù)據(jù)隱私保護形勢也非常嚴峻.目前,針對數(shù)據(jù)分類過程中的隱私保護研究主要集中在密文數(shù)據(jù)運算方面,但是該類技術(shù)也存在如下問題:(1)一些分類器對密文數(shù)據(jù)的運算復(fù)雜,運算效率較低;(2)加密技術(shù)針對的是特定的分類器,缺乏普適性.

kNN 分類器是監(jiān)督學(xué)習(xí)中“懶惰學(xué)習(xí)”(lazy learning)的典型代表,監(jiān)督學(xué)習(xí)過程由兩個階段構(gòu)成.

(1)樣本訓(xùn)練階段:在此階段,首先獲取在準備工作階段處理好的訓(xùn)練數(shù)據(jù);然后根據(jù)分類器類型選擇分類算法,對訓(xùn)練數(shù)據(jù)進行訓(xùn)練得到模型W,以此作為分類階段的一項輸入.

(2)應(yīng)用階段(分類階段):分類器C通過模型W對測試向量X進行分類預(yù)測,得到最終的分類結(jié)果C(W,X).

在樣本訓(xùn)練和分類階段,都可能發(fā)生用戶隱私信息的泄露:在樣本訓(xùn)練階段,數(shù)據(jù)擁有者不希望自己擁有的數(shù)據(jù)信息被泄露出去,甚至對訓(xùn)練者也要進行保密,這就需要對訓(xùn)練數(shù)據(jù)進行加密處理;在分類階段,訓(xùn)練者會將得到的模型W作為分類器的構(gòu)成部分,并將分類器發(fā)布出去提供服務(wù),但不希望成果被第三方獲取,這就需要對分類模型和測試向量進行加密.總而言之,分類器要保證數(shù)據(jù)的隱私性必須從兩方面入手:(1)訓(xùn)練數(shù)據(jù)集和模型W的隱私保護;(2)測試向量X和分類結(jié)果C(W,X)的隱私保護.

目前已有一些關(guān)于分類器隱私保護的研究成果,但大多數(shù)方案都是針對訓(xùn)練階段數(shù)據(jù)的隱私保護,很少有針對分類模型和分類過程的保護.因此,設(shè)計基于加密數(shù)據(jù)的基本操作加密協(xié)議并以模塊化順序組合的方法構(gòu)造安全的分類器,使其從訓(xùn)練階段到分類過程都能保證安全性,同時保證待測數(shù)據(jù)能夠獲得一個準確的類別,是當(dāng)前機器學(xué)習(xí)隱私保護的重要研究方向之一.

1 相關(guān)工作

分類器的構(gòu)造和實施過程就決定其在隱私保護方面存在隱患,例如,在訓(xùn)練樣本上執(zhí)行分類器算法,生成分類模型,很容易造成樣本數(shù)據(jù)的泄露;在測試樣本上執(zhí)行分類模型,生成預(yù)測結(jié)果時,客戶端會很容易得到分類模型,而服務(wù)器端也可以輕易獲取到輸入的測試數(shù)據(jù).因此,分類器在樣本訓(xùn)練和分類階段的數(shù)據(jù)隱私問題已成為分類器隱私保護中最為重要的研究內(nèi)容之一.

(1)樣本訓(xùn)練階段

為了保證在樣本訓(xùn)練階段原始數(shù)據(jù)的隱私性,應(yīng)將原始數(shù)據(jù)隱藏起來,在此階段,不同的分類器會選擇不同的算法來訓(xùn)練原始數(shù)據(jù),比如貝葉斯算法、支持向量算法、決策樹算法等.這些算法包含了點積運算、加法運算、比較運算.為了保證隱藏后的數(shù)據(jù)仍然能夠進行上述運算,本階段使用的隱私保護技術(shù)應(yīng)滿足3 個方面的要求:(1)不改變原始數(shù)據(jù)的整體分布趨勢;(2)不能從隱藏后的數(shù)據(jù)中直接推算出原始數(shù)據(jù)值;(3)確保經(jīng)過變換后的數(shù)據(jù)不會降低分類器的分類效果.目前,研究人員采用的技術(shù)主要分兩類:數(shù)據(jù)干擾和數(shù)據(jù)加密.文獻[3]提出一種基于非線性維數(shù)降低(即非度量多維縮放)來干擾原始數(shù)據(jù)的隱私保護框架,使用k-Nearest Neighbor分類算法對分類任務(wù)中的新型隱私保護數(shù)據(jù)挖掘(privacy-preserving data mining,簡稱PPDM)方法進行了測試,在隱藏隱私數(shù)據(jù)的同時,保證了數(shù)據(jù)的有效性;文獻[4]提出了數(shù)據(jù)擾動技術(shù)并利用該技術(shù)構(gòu)建了決策樹分類器,之后,相繼提出了不同的擾動方法[5,6].但是,擾動技術(shù)不能保證密文數(shù)據(jù)的語義安全,且數(shù)據(jù)添加了統(tǒng)計噪聲易造成分類器的分類精度下降.文獻[7]提出了兩方參與的決策樹分類器,其假定數(shù)據(jù)分布在兩方;文獻[8-10]利用安全多方計算(secure multi-party computation,簡稱SMC)技術(shù)構(gòu)造了安全的分類器;文獻[11]設(shè)計了一種基于主成分分析(primary component analysis,簡稱PCA)的協(xié)同學(xué)習(xí)隱私保護方法,其利用PCA 實現(xiàn)了在協(xié)同學(xué)習(xí)過程中對壓縮數(shù)據(jù)的隱私保護;文獻[12]設(shè)計了一種加法同態(tài)代理聚合方案實現(xiàn)了云端患者的歷史數(shù)據(jù)的隱私保護,引入了隱私保護的top-k疾病名稱檢索協(xié)議保證了樸素貝葉斯分類器的安全性;文獻[13]提出了一種分布式系統(tǒng)的隱私保護數(shù)據(jù)分類和相似性評估方案,該方案在分類和相似度評估過程中不泄露任何關(guān)于新到達數(shù)據(jù)和訓(xùn)練模型的信息,其最終的分類結(jié)果除外;文獻[14]提出了將線性分類器和IPE(inner product encryption)相結(jié)合的方法來對加密數(shù)據(jù)進行分類,其隱私保護分類方案允許用戶的數(shù)據(jù)被加密,但服務(wù)器能夠獲知最終的加密結(jié)果;文獻[15]設(shè)計了實用的安全模型,通過研究在安全的兩方計算框架中的一些多元統(tǒng)計分析方法,生成了一些構(gòu)造塊,解決了安全的兩方多元線性回歸問題和安全的兩方多變量問題;文獻[16]基于安全多方協(xié)議與同態(tài)加密方案訓(xùn)練幾種簡單的分類器,例如線性分類器,該分類器是支持加密數(shù)據(jù)分類的,但是其構(gòu)造的模型安全性較低,導(dǎo)致客戶端不僅能夠得知最終的分類結(jié)果,而且可能會獲取分類模型的信息,造成分類模型信息的泄露.綜上所述,在樣本訓(xùn)練階段不僅要隱藏原始數(shù)據(jù),還要將分類規(guī)則進行隱藏,即保護服務(wù)器參與分類數(shù)據(jù)的隱私性,防止通過模型或分類過程推導(dǎo)出個人信息.

(2)分類階段

在分類階段,支持用戶數(shù)據(jù)隱私性保護的研究成果較少.在文獻[17]中,第三方運行醫(yī)療預(yù)測函數(shù)對全同態(tài)加密(fully homomorphic encryption,簡稱FHE)的患者數(shù)據(jù)進行運算,得到預(yù)測結(jié)果.該算法僅隱藏了來自云端的輸入數(shù)據(jù),在分類階段,任何一方都可以獲取到分類模型,容易泄露患者隱私給第三方或各參與方.文獻[18,19]構(gòu)造了線性分支程序的安全評估,用此實現(xiàn)了心電圖(electrocardiogram,簡稱ECG)信號的安全分類.這項技術(shù)是基于finely-tuned garbled 電路的,雖然保證了分類過程的安全性,但分支程序的運行速度較慢.文獻[20]利用神經(jīng)網(wǎng)絡(luò)[21]構(gòu)造了安全的分類器,這是感知器分類器的泛化,使神經(jīng)網(wǎng)絡(luò)分類器能夠支持對密文數(shù)據(jù)的分類.

綜上所述,在分類樣本訓(xùn)練階段的隱私保護研究成果較多,在分類過程中的隱私保護研究成果則不多見,容易造成用戶隱私信息的泄露.為此,本文首先對kNN 分類器的操作進行分析,提取出從樣本訓(xùn)練階段到分類過程中所包含的基本操作,包括加法、乘法、點積、比較;針對上述基本操作,設(shè)計了相應(yīng)的安全協(xié)議,然后以模塊化順序組合的方式將其組合生成PP-kNN 分類器,從而保證了樣本訓(xùn)練階段和分類過程的數(shù)據(jù)隱私性.本文所設(shè)計的PP-kNN 分類器的基本操作的隱私保護協(xié)議是基于差分隱私的,給加密數(shù)據(jù)加入噪聲,防止在交互式環(huán)境中信息的泄露.在設(shè)計基本操作的安全協(xié)議時,選擇了兩種同態(tài)加密方案對數(shù)據(jù)進行加密,以增加隱私保護的強度.同時,所設(shè)計的基本協(xié)議在半誠實模型下是安全的,模塊化順序組合方法在該模型下也是安全的,因此通過順序組合構(gòu)造的PP-kNN 分類器也是安全的.

本文第1 節(jié)對kNN 分類器和本文使用的加密方法進行描述.第2 節(jié)給出基本操作安全協(xié)議的設(shè)計.第3 節(jié)詳細說明支持隱私保護的kNN 分類器的構(gòu)造過程.第4 節(jié)從計算代價、存儲代價等方面對基本操作安全協(xié)議及PP-kNN 分類器進行性能評估.最后,對全文進行總結(jié).

2 預(yù)備知識

2.1 kNN分類器

在kNN 分類過程中,待分類對象的類別可以通過在它附近的訓(xùn)練數(shù)據(jù)的類別來確定,所以采取的策略就是找到離待分類對象最近的k個鄰居進行分析.kNN 分類器的工作流程如下.

Step 1.確定k值(最近鄰居的個數(shù)).一般為奇數(shù),通常是采用交叉檢驗來確定(經(jīng)驗規(guī)則:k一般低于訓(xùn)練樣本數(shù)的平方根).

Step 2.確定距離度量公式.以文本分類為例,采用夾角余弦,得出待分類數(shù)據(jù)點和所有已知分類數(shù)據(jù)點的夾角余弦值.按夾角余弦值從大到小排列,獲取距離最近的k個樣本(夾角余弦值越大,角度就越小,距離也就越近).

?距離度量公式還可使用歐式距離:

Step 3.統(tǒng)計這k個樣本點中各個類別的數(shù)量classCount[i].通過比較,得到類別數(shù)量最多的樣本對應(yīng)的分類ci,該類便是待分類樣本所屬分類.

2.2 加密方法

2.2.1 加密方案

本文使用了兩種同態(tài)加密方案(goldwasser-micali 的二次剩余加密系統(tǒng)(QR)[22]和Paillier 加密系統(tǒng)[23])及一種全同態(tài)加密方案(FHE)[24]對數(shù)據(jù)進行加密,前兩種加密方案滿足加法同態(tài),后一種方案同時滿足加法同態(tài)與乘法同態(tài).同態(tài)加密體制[25]的加法同態(tài)與乘法同態(tài)的概要描述如下.

設(shè)R和S為整數(shù)環(huán),R表示明文空間,S表示密文空間.a,b∈R,E是R→S上的加密函數(shù).如果存在算法PLUS和MULT,使其滿足:

這樣可以利用E(a)和E(b)的值計算出E(a+b)和E(a×b),而不需要知道a,b的值.它分別滿足加法同態(tài)和乘法同態(tài).

2.2.2 加密假設(shè)

下面對本文用到的二次剩余假設(shè)、判定性合數(shù)剩余假設(shè)和判定性RLWE 困難性假設(shè)進行介紹.

1)二次剩余假設(shè).假設(shè)N=p×q(p,q為奇素數(shù)),??N為模N的二次剩余集,???N為模N二次非剩余集(如果x是模N的非平方剩余,則x∈???N,且Jacobi符號等于1).{(N,??N):|N|=λ}和{(N,???N):|N|=λ}是概率多項式時間計算不可區(qū)分的.

2)判定性合數(shù)剩余假設(shè).令N=p×q,|N|=λ,N為兩個值不等但長度相等的奇素數(shù)p和q乘積.z稱為模N2的第N個剩余,如果存在,使得z=yNmodN2,其中,第N個剩余和第N個非剩余是概率多項式時間計算不可區(qū)分的.

3)判定性RLWE 困難性假設(shè).對于安全參數(shù)λ,令f(x)=xd+1,其中,d是2 的方冪,令q≥2 為一個整數(shù).令整數(shù)多項式環(huán)R=?[x]/f(x),Rq=R/qR,χ是R上的分布.DRLWEd,q,χ問題是指對下面2 種分布進行區(qū)分:(1)(ai,bi)隨機均勻取自;(2)首先隨機均勻選取s←Rq,然后隨機均勻選取ai←Rq和ei←χ并計算bi=ai?s+ei,最終得到DRLWEd,q,χ假設(shè)是指DRLWEd,q,χ問題中的兩種分布是不可區(qū)分的.

一般來講,噪聲分布χ通常為高斯分布.

2.2.3 安全兩方計算框架與模塊化順序組合

本文的基本操作安全協(xié)議都是兩方協(xié)議,其安全性依賴于兩方的安全計算框架.而本文將基本操作安全協(xié)議通過模塊順序組合技術(shù)構(gòu)成安全的分類器,因此分類器的安全性應(yīng)遵循模塊化順序組合的安全性和安全兩方計算框架的安全性.定義1 和定理1 分別對半誠實模型下的安全兩方計算定義和模塊化順序組合定理進行了描述.

定義1(半誠實模型下的安全性).設(shè)f=(fA,fB)為概率多項式函數(shù),A,B為參與方,fA(相應(yīng)地,fB)記為f(a,b)的第一元素(相應(yīng)地,第2 個元素),Π為計算f的兩方協(xié)議.A輸入a,B輸入b,A,B在通過Π和安全參數(shù)λ執(zhí)行f(a,b)過程中的視圖標記為VA(λ,a,b),即,其中,rA為A內(nèi)部擲幣過程的輸出,為參與方A接收到的第i個消息,B的視圖標記與A類同.

在協(xié)議Π執(zhí)行完畢后,A,B基于輸入(a,b)的輸出分別記為,顯然,輸出包含在參與者的視圖中,且有:

(一般情況)稱Π秘密地計算了f,若存在概率多項式算法分別標記為SA和SB,且使得等式(1)和等式(2)成立.

其中,≡c表示概率多項式時間計算不可區(qū)分,忽略不計安全參數(shù)λ.這里需要強調(diào)的是,VA(λ,a,b),VB(λ,a,b),為相關(guān)的隨機變量,由相同的隨機執(zhí)行函數(shù)定義.特別地,完全由Vi(λ,a,b)確定.

(確定情況)對一個確定的函數(shù)f,稱Π秘密地計算了f,如果存在概率多項式算法分別標記為SA和SB,且使得等式(3)和等式(4)成立.

為了簡化符號和證明,本文在確定情況下的符號表示省略了安全參數(shù).由于主要考慮確定性函數(shù)f,因此在進行安全性證明時,統(tǒng)一使用等式(3)和等式(4)的符號表示.

模塊化順序組合方法借鑒了文獻[26]中安全協(xié)議模塊化組合技術(shù),通過順序組合的方式,一個接一個簡單地運行多個安全協(xié)議,構(gòu)成了完整的、安全的分類器協(xié)議.其思想是:首先,為給定任務(wù)設(shè)計一個“高級”協(xié)議,假設(shè)可以安全的執(zhí)行其他簡單的子任務(wù);然后,為簡單的子任務(wù)設(shè)計安全協(xié)議;最后,通過在“高級”協(xié)議中插入簡單的安全協(xié)議作為子例程,為給定任務(wù)構(gòu)建一個完整的協(xié)議.

定理1(模塊化順序組合).設(shè)f1,…,fm和g為兩方概率多項式函數(shù),假設(shè)協(xié)議ρ1,…,ρm基于半誠實模型分別安全地評估函數(shù)f1,…,fm,協(xié)議Π基于半誠實模型安全地評估函數(shù)g,同時使用子程序調(diào)用理想函數(shù)f1,…,fm.然后從協(xié)議Π導(dǎo)出的協(xié)議通過替換協(xié)議Π的每個子程序調(diào)用安全地評估g,則稱在半誠實模型上安全評估了函數(shù)g.

3 面向基本操作的安全協(xié)議

3.1 符號描述

在進行面向基本操作的安全協(xié)議構(gòu)造之前,先給出相關(guān)符號的描述.安全協(xié)議由兩方構(gòu)成,協(xié)議雙方分別記作A和B.分類器的雙方分別記作C和S,C表示客戶端,S表示服務(wù)器.

本文的加密方案有3 種:QR 表示二次剩余加密方案,Paillier 表示Paillier 加密方案,FHE 表示全同態(tài)加密方案.在實現(xiàn)第3.2.1 節(jié)的比較協(xié)議時,使用了Damgard,Geisler and Kr?igaard(DGK)加密方案[27],符號描述見表1.

Table 1 Notation description表1 符號描述

對于常量b,a←b表示將b賦值給a.

對于分布D,a←D表示在分布D中隨機抽樣一個元素a.

3.2 比較協(xié)議

比較協(xié)議是構(gòu)造分類器的安全協(xié)議之一,用于比較兩個用Paillier 加密的密文數(shù)據(jù),獲取QR 加密的比較結(jié)果,比較協(xié)議的相關(guān)符號描述見表2.

Table 2 Comparison protocol表2 比較協(xié)議

3.2.1 改進的DGK 比較協(xié)議

DGK 比較協(xié)議[28]是兩方協(xié)議,參與方分別記為A,B,輸入分別為整數(shù)a,b,其比特位數(shù)相同,輸出分別為δA,δB.其計算思路是,從最高有效位開始依次比較ai,bi的值,記錄比較結(jié)果,其中,0≤i≤l,l表示比特位數(shù),s=a-2?δB,δB={0,1}由B方隨機選取.若ci=0,則δA=1;否則,δA=0,δA⊕δB=(a≤b).值得注意的是,在此過程中,ai,bi都是以DGK 加密的密文形式參與運算.

表2 的第1 行是基于DGK 比較協(xié)議的,并對其進行修改以適應(yīng)PP-kNN 分類器的應(yīng)用需求.其目的是比較兩個未加密的數(shù)據(jù)a和b,得出通過QR 加密的比較結(jié)果.本文增加以下操作滿足應(yīng)用需求:(1)A通過QR 對δA進行加密,將加密的[δA]發(fā)送給B;(2)B通過 QR 對δB進行加密,計算[δA]?[δB].因為[δA]?[δB]≡[δA⊕δB]modN≡ [a≤b],因此通過計算[δA]?[δB],可得出比較結(jié)果[a≤b].在此過程中,B沒有QR 私鑰,因此無法對δA進行解密,保證了計算過程中數(shù)據(jù)的安全性.

3.2.2 加密數(shù)據(jù)的比較協(xié)議

本文的比較協(xié)議是兩方協(xié)議,其中,一方A擁有待比較數(shù)據(jù)?a?,?b?,另一方B擁有解密密鑰.本文的比較協(xié)議是基于Veugen 比較協(xié)議[29]的,并對其進行了修改以適應(yīng)PP-kNN 分類器的應(yīng)用需求.具體修改如下:首先,在Veugen 的比較協(xié)議中調(diào)用一個子程序?qū)崿F(xiàn)兩個未加密數(shù)據(jù)的比較,本文使用表2 第1 行的比較協(xié)議替換該子程序;然后,將該子程序的兩方角色進行置換,即輸出方由A方置換為B方;然后,B進行計算并將計算結(jié)果發(fā)送給A,A進行解密得到未加密的比較結(jié)果.協(xié)議1 是對加密數(shù)據(jù)比較協(xié)議的描述.

比較協(xié)議的主要思想是,計算x=2l+b-a,得到x的第l+1 位(這一位正好對應(yīng)2l)的值:若是1,則a≤b;否則,a>b.本文的假設(shè)加密方案是加法同態(tài)的,其中,N表示Paillier 加密的模量.

協(xié)議1.加密數(shù)據(jù)的比較協(xié)議.

輸入方A:?a?,?b?,a和b的比特長度l,私鑰SKQR,公鑰PKP.

輸入方B:私鑰SKP,公鑰PKQR,比特長度l;

輸出方A:(a≤b).

1:A計算加密數(shù)據(jù)?a?,?b?,即?x?←?b???2l???a?-1modN2?x←b+2l-a

2:A從數(shù)據(jù)域(0,2λ+l)∩?中隨機選擇數(shù)r,即r←(0,2λ+l)∩?

3:A為?x?增加噪音?r?,即?z?←?x???r? modN2?z←x+r

4:A將?z?發(fā)送給B

5:B解密?z?

6:A:c←rmod 2l

7:B:d←zmod 2l

8:調(diào)用第3.2.1 節(jié)修改的DGK 比較協(xié)議,A,B作為輸入方,輸入數(shù)據(jù)分別為c,d,B,得到比較結(jié)果[t′],其中,t′=(d

9:A對r的第l+1 位rl+1進行加密,將加密的[rl+1]值傳送給B

10:B對z的第l+1 位zl+1進行加密,得到[zl+1]

11:B計算第l+1 位的值并賦給[t],即[t]←[t′]?[zl+1]?[rl+1]?t←t′⊕zl+1⊕rl+1

12:B將[t]發(fā)送給A

13:A解密[t]得到t

3.2.3 比較協(xié)議的正確性分析

協(xié)議1 中,a,b是l位整數(shù),x=2l+b-a是l+1 位整數(shù),x÷2l表示x的最高有效位,其運算為t=t′⊕zl+1⊕rl+1,當(dāng)該值等于1 時,a≤b.下面將給出其正確性證明.

證明:x是l+1 位整數(shù),x÷2l表示x的最高有效位,即第l+1 位的值,此時有:

其中,0≤xmod 2l≤2l.

因為z=x+r,所以有:

當(dāng)(xmod 2l)+(rmod 2l)<2l時,有:

當(dāng)(xmod 2l)+(rmod 2l)≥2l時,有:

將公式(5)、公式(6)整合可得:

則t′=0?(xmod 2l)+(rmod 2l)<2l,即

?當(dāng)t′=0 時,zmod 2l=(xmod 2l)+(rmod 2l);

?當(dāng)t′≠0 時,zmod 2l=(xmod 2l)+(rmod 2l)-2l.

因此,t′=0?zmod 2l=(xmod 2l)+(rmod 2l)?zmod 2l≥rmod 2l?d≥c.

因為x÷2l的值非0 即1,所以有x÷2l=(z÷2l)-(r÷2l)-t′ mod 2=zl+1⊕rl+1⊕t′.□

綜上所述,x的最高有效位可以通過zl+1⊕rl+1⊕t′正確計算,因此本文的比較協(xié)議是正確的.

3.2.4 比較協(xié)議在半誠實模型下的安全性分析

假設(shè)加密位[t′]是通過理想計算得到的.本節(jié)分析比較協(xié)議在半誠實模型下的安全性,并使用模塊化順序組合定理(定理1)得出結(jié)論.

A方的元組表示為VA=(?a?,?b?,l,SKQR,PKP;r,coins,[t]),其中,coins為加密2l,r,rl+1的隨機數(shù),給定(?a?,?b?,l,SKQR,PKP,a≤b),模擬器SA的構(gòu)建過程如下.

元組VA(?a?,?b?,l,SKQR,PKQR,SKP,PKP)和SA(?a?,?b?,SKQR,PKP,a≤b)的分布是相同的,因為這兩種情景下的隨機值取值相同且QR 加密的是同一比特位.

B方元組表示為其中,coins為加密zl+1的隨機數(shù),則模擬器SB(PKQR,SKP,l)的構(gòu)造過程如下.

隨機變量coins和生成方式相同且與其他參數(shù)獨立,因此,

從第3.2.2 節(jié)加密數(shù)據(jù)比較協(xié)議可知,z=x+rmodN,其中,x為l位整數(shù),r為λ+l位整數(shù).

因為QR 是語義安全的,因此有:

本文使用模塊化順序組合來實現(xiàn)協(xié)議執(zhí)行過程中的安全性銜接,使用改進的DGK 協(xié)議取代了理想計算得到的[t′],使用定理1 證明了其在半誠實模型下的安全性.綜上所述,本文的比較協(xié)議在半誠實模型下是安全的.

3.3 點積協(xié)議

本文通過歐式距離計算測試樣本與訓(xùn)練樣本之間的距離.為了保證PP-kNN 分類器中距離計算的安全性,本文設(shè)計了點積協(xié)議.

協(xié)議處理的是密文數(shù)據(jù),所有操作皆在密文空間進行.它由A和B兩方參與:A表示客戶端,輸入測試樣本,記作x;B表示服務(wù)器,輸入訓(xùn)練樣本,記作y.協(xié)議2 是點積協(xié)議的具體描述.

協(xié)議2.點積協(xié)議.

輸入方A:x=(x1,…,xd)∈?d,公鑰PKFHE.

輸入方B:y=(y1,…,yd)∈?d,私鑰SKFHE.

輸出方A:?[v]?.

1:B對向量y1,…,yd進行加密,然后將加密后的數(shù)據(jù)?[y]?發(fā)送給A

2:A對向量x1,…,xd進行加密,得到加密數(shù)據(jù)?[x]?

3:A計算?z?←?y???x?-1modN2?z=y-x

4:A計算,然后輸出加密的

協(xié)議2 在半誠實模型下的安全性:在本協(xié)議中,B未接收任何信息,僅提供了數(shù)據(jù)及用于加密的隨機數(shù),則模擬器SB可表示為SB(y,SKFHE)=(y,SKFHE;coins)=VB(x,y,SKFHE,PKFHE),其中,coins為B方生成的隨機數(shù).A的元組表示為VA(x,PKFHE;rA;?z1?,…,?zn?),模擬器SA的構(gòu)造過程如下.

Step 1.生成n個FHE 加密的0:cn,…,c0.

coins和的分布相同,因此,

由于FHE 加密方案的語義安全,所以有:

函數(shù)f滿足f(x,y,SKFHE,PKFHE)=(?[〈z,z〉]?,?)時,有:

本協(xié)議中,B將加密好的數(shù)據(jù)?[y]?發(fā)送給A,A沒有私鑰無法對其解密,保證了數(shù)據(jù)的安全性.加密方案是加法與乘法同態(tài)的,因此密文數(shù)據(jù)計算過程是安全且同態(tài)的.上述過程通過定義1 證明了其在半誠實模型下的安全性.綜上所述,本文的點積協(xié)議在半誠實模型下是安全的.

3.4 加密方案轉(zhuǎn)換協(xié)議

PP-kNN 分類器由點積協(xié)議、比較協(xié)議通過順序組合的方式構(gòu)造而成,點積協(xié)議的輸入與輸出數(shù)據(jù)是FHE進行加密的密文數(shù)據(jù),比較協(xié)議的輸入數(shù)據(jù)是Paillier 進行加密的密文數(shù)據(jù).為了保證PP-kNN 分類器的點積協(xié)議和比較協(xié)議可以進行模塊化順序組合,本文設(shè)計了加密方案轉(zhuǎn)換協(xié)議,實現(xiàn)了從一種加密方案到另一種加密方案的轉(zhuǎn)換.協(xié)議3 是加密方案轉(zhuǎn)換協(xié)議的描述.

協(xié)議3.加密方案轉(zhuǎn)換協(xié)議.

輸入方A:?c?1,公鑰PK1,PK2.

輸入方B:密鑰SK1,SK2.

輸出方A:?c?2.

1:A均勻隨機選擇一個數(shù)r←M

2:A計算?c′?1←?c?1??r?1將?c′?1發(fā)送給B?Blindc

3:B解密后得到c′,用E2重新加密

4:B將重新加密后的?c′?2發(fā)送給A

5:A去除噪音?r?2得到

6:A輸出?c?2

加密方案轉(zhuǎn)換協(xié)議中,E1,E2是兩種不同的加密方案,A通過E1對隨機數(shù)r進行加密,為?c?1添加噪音?r?1,將處理后的?c′?1發(fā)送給B,B解密后無法獲取c的真實值,保證了該值在解密-再加密過程中數(shù)據(jù)的安全性,其中,r是A,B共享,M表示E1的信息空間.B通過E2對c′重新加密,將?c′?2發(fā)送給A,A去除噪音,得到E2加密的真實值?c?2,實現(xiàn)了從加密方案E1到E2的轉(zhuǎn)換.整個加密方案轉(zhuǎn)換過程中,密文噪音并未增加,且中間解密時數(shù)據(jù)真實值亦無法獲取,因此,密文數(shù)據(jù)在加密轉(zhuǎn)換協(xié)議中是安全的.根據(jù)本文的應(yīng)用需求,設(shè)置加密方案E1是FHE,加密方案E2是Paillier,通過協(xié)議3 實現(xiàn)了從FHE 向Paillier 加密方案的轉(zhuǎn)換.

4 PP-kNN 分類器構(gòu)造及分類過程

4.1 浮點數(shù)據(jù)處理

本文的加密方案都是對整型數(shù)據(jù)進行加密,而原始數(shù)據(jù)中部分為浮點型數(shù)據(jù),因此對數(shù)據(jù)進行處理前,需將浮點型數(shù)據(jù)轉(zhuǎn)換為整型數(shù)據(jù),處理方法是用一個足夠大的常量K乘以浮點數(shù).下面詳細描述浮點數(shù)的處理過程:

首先,將浮點數(shù)據(jù)表示為IEEE 754 雙精度浮點數(shù)格式,即V=(-1)s?M?2E-1023,其中,S為符號位占1 比特,M為尾數(shù),二進制表示為(M)2=1.d,占52 比特位,1≤M≤2,M可重新表示為

其次,尋找合適的常量K,使得K滿足:

令e*=miniei,δi=ei-e*≥0,則

?首先,加密方案的明文空間大于252,,因此數(shù)據(jù)轉(zhuǎn)換過程中不存在空間溢出和精度損失.

?其次,kNN 分類器具有的基本操作只有加法、乘法和比較,因此對轉(zhuǎn)換后的數(shù)據(jù)進行操作仍能得到相同的分類結(jié)果.

?最后,在執(zhí)行加、乘、比較操作時,為確保操作不會造成密文數(shù)據(jù)的精度丟失,需要設(shè)置計算和比較所需的比特位數(shù).以比較協(xié)議為例:令d表示輸入數(shù)據(jù)x的屬性個數(shù),則比較時所需的最大比特位數(shù)為lmax=d+1+(52+δ*),其中,δ*=maxδi,1 表示類別標識,52+δ*表示密文數(shù)據(jù)的二進制位數(shù).因此,比較協(xié)議中比較位數(shù)必須大于lmax.此外,還要確保,其中,λ為安全系數(shù),N為Paillier 加密方案明文空間的模量.為了獲得高安全性,設(shè)≥1 024,即λ=100.

本文訓(xùn)練集和測試集分別用Y和X表示,其中,xi表示第i個訓(xùn)練樣本,則轉(zhuǎn)換后的數(shù)據(jù)表示為

其中,j表示樣本xi的第j個特征值.

4.2 PP-kNN分類器的構(gòu)造過程

本節(jié)利用第3 節(jié)的協(xié)議來構(gòu)造PP-kNN 分類器,構(gòu)造過程如下.

首先,將訓(xùn)練數(shù)據(jù)的類型由浮點數(shù)轉(zhuǎn)換為整數(shù),使用FHE 對其加密;其次,通過協(xié)議2 計算測試樣本與所有訓(xùn)練樣本的歐式距離,結(jié)果是FHE 加密的密文數(shù)據(jù).然后,通過協(xié)議3 將結(jié)果轉(zhuǎn)換為Paillier 加密的密文數(shù)據(jù),再通過getMINn得到距離數(shù)組中的最小值.其思想為:先將數(shù)組中的值兩兩比較,得到兩個中較小的值,將較大的賦值為0,較小的值的下標記為兩者下標中較小方的下標值,所有較小方組成新的數(shù)組.然后繼續(xù)比較新的數(shù)組,直到數(shù)組個數(shù)為1,該值即為最小值.其比較通過協(xié)議1 實現(xiàn),每次比較得到一個最小值,然后將最小值重新賦值為最大值.循環(huán)k次,得出k近鄰樣本.最后,使用第4.2.1 節(jié)中介紹的方法來統(tǒng)計類別個數(shù),得出分類結(jié)果.其中,將每個協(xié)議看作一個模塊,通過模塊化順序組合進行模塊銜接,構(gòu)造PP-kNN 分類器,使得客戶端只能獲知最后的分類結(jié)果,而不能知道測試樣本與訓(xùn)練樣本間的距離;使服務(wù)器無法獲取客戶端的輸入x(x是測試樣本的向量表示).

4.2.1 PP-kNN 分類器的近鄰樣本類別個數(shù)統(tǒng)計

計算測試樣本x=(x1,…,xd)與訓(xùn)練樣本yi=(yi1,…,yid)的距離d(xi,yi),通過比較進行排序,獲取前k個訓(xùn)練樣本對應(yīng)的分類標簽.

設(shè)N={y1,…,yk}表示包含k個訓(xùn)練樣本的數(shù)據(jù)集,則x對應(yīng)的分類其中,L=(c1,…,cm)是所有標記的集合,I(?)是用來獲取k個樣本所屬分類的函數(shù),執(zhí)行情況如下.

按上述步驟完成對k個樣本所屬分類個數(shù)的統(tǒng)計,類別個數(shù)最多的分類即為待測樣本的預(yù)測分類cx.

4.2.2 PP-kNN 分類器的分類過程

kNN 分類器由服務(wù)器端與客戶端兩部分組成,其處理的數(shù)據(jù)是通過FHE 加密的密文數(shù)據(jù),PP-kNN 分類器,其實質(zhì)是將kNN 分類器針對明文數(shù)據(jù)的基本計算用第3 節(jié)中的安全協(xié)議替換,使kNN 分類器在分類過程中對密文數(shù)據(jù)進行操作,保證數(shù)據(jù)在分類過程中的安全性與同態(tài)性,最后得出分類結(jié)果.協(xié)議4 是對PP-kNN 分類協(xié)議的描述.

協(xié)議4.PP-kNN 分類協(xié)議.

C輸入:測試樣本x=(x1,x2,…,xd)∈?d,公鑰PKP,PKFHE,私鑰SKQR..

S端輸入:私鑰SKP,SKFHE,公鑰PKQR,訓(xùn)練集D=(y1,…,ym),標記L=(c1,…,cm),近鄰數(shù)k.

C輸出:下標i,ci是k個近鄰樣本中類別個數(shù)最多的類.

1:S提供訓(xùn)練集D,對訓(xùn)練集中的訓(xùn)練樣本進行浮點數(shù)到整數(shù)的類型轉(zhuǎn)換,然后通過FHE 加密方案對訓(xùn)練樣本進行加密

2:S將加密的?[D]?和近鄰數(shù)k發(fā)送給C

3:設(shè)樣本容量為m,for 1≤i≤m,C通過點積協(xié)議計算測試樣本與訓(xùn)練樣本的距離?d(xi,yi)?其中,,取結(jié)果的平方存放到數(shù)組dis_fhe中

4:C,S通過加密方案轉(zhuǎn)換協(xié)議將FHE 轉(zhuǎn)換為Paillier 加密方案,存入dis_paillier中

5:C:for 0≤M

(1)C和S通過getMINn獲取數(shù)組dis_paillier中的最小值min,并將其存入隊列queue 中

(2)將min 對應(yīng)的值重新賦值為最大值

6:C和S通過第5 步得到k個近鄰樣本?d0??d1?…?dk?

7:統(tǒng)計k個近鄰樣本的類別數(shù)目,然后得到類別最多的類ci

4.2.3 安全性分析

由于點積協(xié)議、方案轉(zhuǎn)換協(xié)議、比較協(xié)議在半誠實模型下是安全的,模塊化線性組合在半誠實模型下也是安全的,因此,通過模塊化線性組合對點積協(xié)議、方案轉(zhuǎn)換協(xié)議、比較協(xié)議進行組合構(gòu)造的PP-kNN 分類器也是安全的.

?首先,點積協(xié)議在半誠實模型下是安全的.在通過點積協(xié)議計算測試樣本與訓(xùn)練樣本間距離時,服務(wù)器僅發(fā)送加密后的密文數(shù)據(jù)給客戶端,未接收來自客戶端的任何輸入,保證了客戶端輸入數(shù)據(jù)x的安全性.客戶端不擁有私鑰,無法解密來自服務(wù)器的輸入數(shù)據(jù);又因為FHE 加密方案的加法、乘法同態(tài)性,保證計算過程的安全性,因此,距離計算時是安全的.

?然后,加密方案轉(zhuǎn)換協(xié)議在半誠實模型下是安全的.距離數(shù)據(jù)增加噪音干擾后發(fā)送給服務(wù)器,保證其解密再加密過程無法獲知距離的真實值,因此不會推測出x的值;重新加密后,發(fā)送回客戶端,客戶端不具有Paillier 私鑰,無法解密.因此,加密方案轉(zhuǎn)換過程是安全的.

?最后,比較協(xié)議在半誠實模型下是安全的,因此調(diào)用比較協(xié)議獲取最小值的運算過程中數(shù)據(jù)也是安全的,又因為模塊化順序組合在半誠實模型下是安全的.

綜上所述,通過模塊化順序組合將點積協(xié)議、加密方案轉(zhuǎn)換協(xié)議、比較協(xié)議進行組合構(gòu)造的PP-kNN 分類器也是安全的.

5 實 驗

本文利用自定義加密數(shù)據(jù)對比較協(xié)議和加密方案轉(zhuǎn)換協(xié)議進行性能評估,利用4 種UCI 數(shù)據(jù)集[30]對PP-kNN 分類器的性能進行評估.

測試環(huán)境具體描述如下:CPU 為英特爾酷睿i7 處理器(雙核,3.4GHz);內(nèi)存為16GB.

實驗在相同的網(wǎng)絡(luò)下進行,因此,本文將一個數(shù)據(jù)包的往返時間記為40ms 來模擬網(wǎng)絡(luò)延遲.加密方案中的密鑰長度為1 024 位,統(tǒng)計安全參數(shù)λ=100.

5.1 比較協(xié)議的性能評估

首先,針對兩種比特長度的加密數(shù)據(jù),從客戶端、服務(wù)器運行時間、交換數(shù)據(jù)量、交換次數(shù)這4 個方面對比較協(xié)議進行了評估,實驗結(jié)果見表3.

Table 3 Evaluation of comparison protocol表3 比較協(xié)議評估

然后,分別對64 位、128 位、256 位、512 位、1 024 位比較比特長度的加密數(shù)據(jù)進行評估,如圖1 所示.

Fig.1 Performance of comparison protocol圖1 比較協(xié)議性能

表3 的實驗結(jié)果表明,比較協(xié)議的運行時間與比較比特長度有關(guān),比特長度越長,服務(wù)器和客戶機運行時間越長,交換數(shù)據(jù)量越多.

5.2 kNN分類器性能評估

本節(jié)實驗在Iris、Wine、Zoo、Glass Identification 公共數(shù)據(jù)集上進行測試.這些數(shù)據(jù)集是UCI 標準數(shù)據(jù)集[30],見表4.

Table 4 Standard dataset表4 標準數(shù)據(jù)集

測試數(shù)據(jù)與訓(xùn)練數(shù)據(jù)都是按一定比例隨機進行抽取,各訓(xùn)練樣本數(shù)見表4,樣本集中剩余樣本作為測試集.本實驗從客戶端和服務(wù)端各自的計算、比較時間、交換數(shù)據(jù)總量及交換次數(shù)這幾個方面進行評估,具體實驗結(jié)果見表5.

Table 5 Performance of PP-kNN classifier based on different test encrypted datasets表5 基于不同測試加密數(shù)據(jù)的PP-kNN 分類器性能

表5 的實驗結(jié)果表明,PP-kNN 分類器的運行時間在幾秒到幾十秒不等,執(zhí)行時間隨著訓(xùn)練樣本數(shù)與特征數(shù)的增加而增加.與貝葉斯分類器、線性分類器不同,kNN 分類器在訓(xùn)練階段的消耗為0,其計算全部集中在分類階段,因此在密文數(shù)據(jù)處理的速度方面具有一定優(yōu)勢.

5.3 安全兩方工具比較協(xié)議評估與對比

PP-kNN 中的基本操作協(xié)議都是兩方協(xié)議,并且支持當(dāng)前典型兩方協(xié)議(TASTY[31]、Fairplay[32,33])所支持的全部功能,為了進一步說明PP-kNN 的性能優(yōu)勢,將本文中的比較協(xié)議與TASTY 進行比對.

本文基于不同比特位數(shù)的數(shù)據(jù)設(shè)置相應(yīng)的比較位數(shù),對TASTY 安全兩方計算工具中的兩方比較協(xié)議進行了性能測試,實驗結(jié)果如圖2 所示.TASTY 與本文的比較操作都是基于Garble 電路的,但TASTY 的數(shù)據(jù)傳輸消耗時間長,本文的數(shù)據(jù)傳送時間較短,因此安全兩方比較協(xié)議總的運行時間約為TASTY 的1/100.綜上所述,本文的兩方比較協(xié)議在性能上有所提高.

Fig.2 Secure two-party comparison protocol runtime distribution of Tasty and ours圖2 Tasty 和本文的安全兩方比較協(xié)議運行時間分布

6 結(jié) 論

本文設(shè)計了一種支持隱私保護的kNN 分類器.首先,從kNN 分類器中提取出了一些基本操作,包括加法、乘法、比較等;其次,選擇了兩種同態(tài)加密方案和一種全同態(tài)加密方案對數(shù)據(jù)進行加密,基于此,設(shè)計了針對基本操作的安全協(xié)議,并證明了協(xié)議在半誠實模型下的安全性;然后,通過將基本操作的安全協(xié)議按照模塊化順序組合的方式構(gòu)造出了PP-kNN 分類器;最后,在自定義加密數(shù)據(jù)及4 種UCI 標準數(shù)據(jù)集上,分別對安全協(xié)議及所構(gòu)造的PP-kNN 分類器進行了性能評估.實驗結(jié)果表明,本文設(shè)計的安全協(xié)議是安全且高效的,分類器能夠以較高的效率對密文數(shù)據(jù)進行分類,同時實現(xiàn)了對用戶數(shù)據(jù)的隱私保護.