基于同態(tài)加密的DBSCAN 聚類隱私保護(hù)方案

賈春福，李瑞琪，王雅飛

（1.南開大學(xué)網(wǎng)絡(luò)空間安全學(xué)院，天津 300350；2.天津市網(wǎng)絡(luò)與數(shù)據(jù)安全技術(shù)重點(diǎn)實(shí)驗(yàn)室，天津 300350）

1 引言

云服務(wù)的快速發(fā)展，為用戶提供了更加多元化的數(shù)據(jù)處理方式。用戶可以選擇將數(shù)據(jù)集上傳到云服務(wù)器，由云服務(wù)器執(zhí)行相關(guān)操作，從而減少用戶計(jì)算資源的使用。由于用戶種類繁多，其提供的數(shù)據(jù)集也將涵蓋多種類型，比如電子郵件信息、后臺(tái)用戶數(shù)據(jù)庫(kù)信息、個(gè)人健康狀況等涉及個(gè)人隱私或企業(yè)商業(yè)機(jī)密的信息。用戶將上述信息進(jìn)行外包處理時(shí)，其中包含的敏感信息存在著泄露的風(fēng)險(xiǎn)。因此，如何對(duì)敏感數(shù)據(jù)所包含的隱私進(jìn)行保護(hù)是當(dāng)前的研究熱點(diǎn)。

隱私保護(hù)常見的處理方式主要有2 種：一種是通過(guò)硬件或可信第三方提供的可信信道來(lái)保證傳輸過(guò)程中的數(shù)據(jù)不被竊?。涣硪环N是將數(shù)據(jù)加密后進(jìn)行傳輸，即使攻擊者獲得密文，沒(méi)有密鑰也無(wú)法進(jìn)行解密。第一種方式雖然可以保證傳輸過(guò)程中的安全性，但其對(duì)第三方有較大依賴；并且，由于其使用明文傳輸，當(dāng)數(shù)據(jù)集傳輸?shù)皆品?wù)器端后，仍然存在著被竊取的風(fēng)險(xiǎn)。第二種方式將數(shù)據(jù)集加密后傳輸，這樣無(wú)論在傳輸過(guò)程中還是在服務(wù)器端計(jì)算過(guò)程中都能夠保證數(shù)據(jù)明文不會(huì)被泄露。

對(duì)數(shù)據(jù)集進(jìn)行加密時(shí)，如果使用傳統(tǒng)的加密算法，服務(wù)器無(wú)法直接對(duì)密態(tài)數(shù)據(jù)進(jìn)行處理，需要用戶向服務(wù)器提供密鑰或執(zhí)行解密操作。同態(tài)加密（HE,homomorphic encryption）是一種新型密碼學(xué)工具，其支持在加密信息上進(jìn)行任意函數(shù)運(yùn)算，并且解密后得到的結(jié)果與在明文上執(zhí)行相應(yīng)運(yùn)算的結(jié)果一致。同態(tài)加密算法依照所支持的運(yùn)算種類和次數(shù)不同，可大致分為以下幾類：支持無(wú)限次數(shù)和多種運(yùn)算的全同態(tài)加密（FHE,fully homomorphic encryption）算法、支持無(wú)限次數(shù)和有限種類的部分同態(tài)加密（PHE,partial homomorphic encryption）算法、支持有限次數(shù)和多種運(yùn)算的淺同態(tài)加密（SWHE,somewhat homomorphic encryption）算法[1-4]。大部分應(yīng)用場(chǎng)景只需要有限次同態(tài)加法或乘法操作，并且SWHE 算法相較于FHE 算法而言具有更好的效率，因此SWHE 算法具有更加廣泛的應(yīng)用場(chǎng)景[5]。BGV（Brakerski-Gentry-Vaikuntanathan）方案是一種常用的SWHE 算法，支持加密多項(xiàng)式或整數(shù)，同時(shí)也可以利用中國(guó)剩余定理實(shí)現(xiàn)并行化操作。

同態(tài)加密同時(shí)滿足保密性和密文可操作性的特點(diǎn)使其在隱私保護(hù)領(lǐng)域有較廣泛的應(yīng)用。基于同態(tài)加密的外包計(jì)算的隱私保護(hù)模型如圖1 所示。用戶對(duì)需要外包的數(shù)據(jù)集進(jìn)行加密，并上傳到服務(wù)器端（①），由服務(wù)器進(jìn)行較高計(jì)算復(fù)雜度的數(shù)據(jù)處理；然后，服務(wù)器將結(jié)果返回給用戶（②）。

機(jī)器學(xué)習(xí)是一種重要的數(shù)據(jù)外包計(jì)算，其隱私保護(hù)問(wèn)題是同態(tài)加密的一類重要應(yīng)用場(chǎng)景。在過(guò)去幾年中，研究者針對(duì)不同的應(yīng)用場(chǎng)景、不同的數(shù)據(jù)類型以及不同的機(jī)器學(xué)習(xí)算法，開展了許多同態(tài)加密在機(jī)器學(xué)習(xí)隱私保護(hù)中應(yīng)用的工作。文獻(xiàn)[6]實(shí)現(xiàn)了高效且安全的k 近鄰（kNN，k-nearest neighbor）算法。文獻(xiàn)[7-8]實(shí)現(xiàn)了加密數(shù)據(jù)集上的同態(tài)K-means 聚類算法，但其存在時(shí)間開銷較大的問(wèn)題。文獻(xiàn)[9-11]的加密對(duì)象是圖片，其對(duì)圖片型數(shù)據(jù)集執(zhí)行加密操作后，在密態(tài)圖片上提取特征，并應(yīng)用不同的圖像匹配算法，實(shí)現(xiàn)密態(tài)圖片的匹配。文獻(xiàn)[12]實(shí)現(xiàn)了密態(tài)數(shù)據(jù)集上的統(tǒng)計(jì)學(xué)習(xí)算法。文獻(xiàn)[13-14]通過(guò)逐比特運(yùn)算的方式實(shí)現(xiàn)了加密數(shù)據(jù)集上的比較算法或協(xié)議，但其開銷較大。文獻(xiàn)[15]預(yù)先在數(shù)字型數(shù)據(jù)集上提取相關(guān)特征，然后將特征加密后上傳到云端，在云端對(duì)相關(guān)特征的密文進(jìn)行同態(tài)運(yùn)算后，完成分類運(yùn)算。本文提出的方案與之不同，加密對(duì)象為原數(shù)據(jù)集，而后在云端執(zhí)行同態(tài)聚類操作。

圖1 基于同態(tài)加密的外包計(jì)算的隱私保護(hù)模型

常見的機(jī)器學(xué)習(xí)算法主要分為有監(jiān)督型和無(wú)監(jiān)督型。有監(jiān)督型機(jī)器學(xué)習(xí)算法能夠提取訓(xùn)練數(shù)據(jù)集的特征和真實(shí)標(biāo)簽以構(gòu)建模型，并對(duì)測(cè)試數(shù)據(jù)進(jìn)行測(cè)試從而得出相應(yīng)結(jié)果，代表算法有貝葉斯分類器、超平面分類器、決策樹分類器等；無(wú)監(jiān)督型機(jī)器學(xué)習(xí)算法不需要預(yù)先訓(xùn)練模型，代表算法主要有K-means 聚類算法、DBSCAN（density-based spatial clustering of application with noise）算法等。DBSCAN 是一種基于密度的無(wú)監(jiān)督型機(jī)器學(xué)習(xí)聚類算法，能夠在有噪聲點(diǎn)的情況下找到任意形狀的聚類簇，相較于另一個(gè)常見的聚類算法K-means，其應(yīng)用范圍更加廣泛，如可用于推薦系統(tǒng)等高級(jí)系統(tǒng)的實(shí)現(xiàn)。DBSCAN 還可用于與加速范圍訪問(wèn)（如R*?樹）相配合的一種數(shù)據(jù)庫(kù)結(jié)構(gòu)的設(shè)計(jì)。因此，DBSCAN 隱私保護(hù)問(wèn)題的研究具有重要意義。

本文提出了一個(gè)基于同態(tài)加密的聚類學(xué)習(xí)的隱私保護(hù)方案，實(shí)現(xiàn)了在密文數(shù)據(jù)集上進(jìn)行同態(tài)DBSCAN 的聚類操作。因?yàn)锽GV 同態(tài)加密算法計(jì)算效率較高、明文空間選擇靈活，所以本文選擇其對(duì)數(shù)據(jù)進(jìn)行加密。為了解決BGV 算法不能直接加密浮點(diǎn)型數(shù)據(jù)的問(wèn)題，本文提出了3 種不同的浮點(diǎn)型數(shù)據(jù)預(yù)處理方式，根據(jù)浮點(diǎn)型數(shù)據(jù)集自身特點(diǎn)、綜合考慮計(jì)算開銷和數(shù)據(jù)精度進(jìn)行選擇。對(duì)于同態(tài)加密不支持的密文比較運(yùn)算，本文設(shè)計(jì)了一個(gè)云服務(wù)器與用戶之間的協(xié)議實(shí)現(xiàn)密文的比較操作，協(xié)議只涉及同態(tài)密文之間的加減法操作，計(jì)算復(fù)雜度較低。

2 基礎(chǔ)知識(shí)

2.1 符號(hào)介紹

對(duì)于一個(gè)實(shí)數(shù)z，分別表示對(duì)z向上、向下和就近取整；[z]m表示zmodm。使用小寫粗體字母表示向量；大寫字母X={x1,x2,…,xi}表示集合，表示集合中元素的個(gè)數(shù)；大寫粗體字母表示矩陣（如A），AT表示矩陣的轉(zhuǎn)置。符號(hào)←表示隨機(jī)選取；R表示環(huán)，Rq=R/qR。對(duì)于明文空間中的元素m∈M，符號(hào)?m?表示其密文。

2.2 同態(tài)加密算法

定義1 同態(tài)加密。同態(tài)加密算法主要包含4 個(gè)部分：密鑰生成（KeyGen）、加密（Enc）、密文運(yùn)算（Eval）、解密（Dec）。

①(pk,sk)←KeyGen(λ)：輸入安全參數(shù)λ，輸出公鑰pk 和私鑰sk。

②c←Enc(pk,m)：輸入消息明文m∈M 和公鑰pk，輸出密文c。

③m←Dec(sk,c)：輸入密文c和私鑰sk，輸出消息明文m。

④cEval←Eval(C,{c1,…,ck},pk)：輸入一個(gè)布爾電路C、一組密文 {c1,…,ck}和公鑰pk，輸出結(jié)果密文cEval。

本文選取文獻(xiàn)[2]提出的BGV 方案，并借助于同態(tài)加密算法庫(kù)HElib 完成方案的實(shí)現(xiàn)。BGV 方案包括以下幾個(gè)算法。

Setup(1λ,1μ)。隨機(jī)選取μbit 的模數(shù)q，選取n=n(λ)，N=N(λ)，χ=χ(λ)，t=t(λ)，d=d(λ)。令R=Z[x]/f(x)，其中f(x)是n次分圓多項(xiàng)式。上述參數(shù)的選取應(yīng)保證方案的困難性能夠基于格困難問(wèn)題GLWE（general learning with error），并能夠抵御現(xiàn)有攻擊。

KeyGen(λ)。選取s←χd，令私鑰為sk=。隨機(jī)抽取矩陣，向量e←χN，計(jì)算b←As+te，令公鑰為B=[b,?A]。顯然，Bs=te。

Enc(pk,m)。將明文m∈Rt擴(kuò)展成m←(m,0,…,0)∈，隨機(jī)選取，輸出密文

Dec(sk,c)。輸出

Eval (c1,c2)。密文加法輸出c12，密文乘法輸出c12。

HElib 中除了上述算法之外還包括一些用于實(shí)現(xiàn)FHE 算法的處理程序[16]，例如key switching、modulus switching 和bootstrapping。FHE 算法存在密鑰過(guò)長(zhǎng)、密文量級(jí)過(guò)大、降噪處理耗時(shí)較長(zhǎng)等弊端，在實(shí)際應(yīng)用中具有一定的局限性；SWHE 算法雖然不支持無(wú)限次密文運(yùn)算，但其密文和密鑰的尺寸較小，也不需要bootstrapping 技術(shù)對(duì)密文進(jìn)行刷新，因而運(yùn)行效率較高。由于本文的場(chǎng)景只需有限次密文運(yùn)算，因此選擇使用SWHE 算法，以獲得較高的計(jì)算效率。

2.3 數(shù)據(jù)預(yù)處理算法

大多數(shù)實(shí)際應(yīng)用中的數(shù)據(jù)都不能夠直接作為加密算法的明文，需要一定的預(yù)處理算法將實(shí)際數(shù)據(jù)映射到明文空間。本文所研究的DBSCAN 算法需處理的數(shù)據(jù)是浮點(diǎn)型數(shù)據(jù)集，所以需要使用預(yù)處理算法將其映射至加密算法的明文空間。本節(jié)將介紹3 種數(shù)據(jù)預(yù)處理方式。

方式1整數(shù)對(duì)編碼

設(shè)原數(shù)據(jù)為浮點(diǎn)數(shù)c，選取整數(shù)a和b使b=a×c，則使用數(shù)對(duì)(a,b)表示數(shù)c。例如：1.5可使用數(shù)對(duì)(2,3)表示；1.2 可使用數(shù)對(duì)(2,2)、(5,6)等表示。選取數(shù)對(duì)時(shí)應(yīng)綜合考慮時(shí)間開銷和精度要求。

方式2移位舍入編碼

設(shè)原數(shù)據(jù)為c.d，其中c為整數(shù)部分，d為小數(shù)部分，且c與d位數(shù)基本相同。將原數(shù)據(jù)c.d的小數(shù)點(diǎn)后移v位，得到新的數(shù)據(jù)cd'。

這種處理方式相當(dāng)于將原有數(shù)據(jù)擴(kuò)大了10v倍，然后根據(jù)實(shí)際要求，對(duì)擴(kuò)大后數(shù)據(jù)的小數(shù)部分進(jìn)行適當(dāng)?shù)纳崛?，從而既能夠保證該類型數(shù)據(jù)的精度，又不需要在加密時(shí)選取較大的加密方案參數(shù)。

方式3多元處理編碼

原數(shù)據(jù)c.d如方式2 描述，且c與d的位數(shù)均小于加密算法所能處理的最大位數(shù)。

輸入c.d

輸出(c,d)

將原數(shù)據(jù)的整數(shù)部分c和小數(shù)部分d拆分為二元組(c,d)。

這種處理方式最具有普適性，能夠完全保證數(shù)據(jù)精度不會(huì)因預(yù)處理操作而受到損失，然而這種處理方式也存在一定的弊端。用戶若使用方式3 將原數(shù)據(jù)變?yōu)槎M，則數(shù)據(jù)量變?yōu)樵瓉?lái)的兩倍，從而增加加密階段的開銷。除此之外，在執(zhí)行同態(tài)乘法操作時(shí)，由原來(lái)一對(duì)整數(shù)相乘變?yōu)閮蓪?duì)整數(shù)相乘，乘法次數(shù)增加，計(jì)算復(fù)雜度增加。

在實(shí)際應(yīng)用過(guò)程中，根據(jù)所需處理的數(shù)據(jù)精度，可以選取上述3 種預(yù)處理方式中的一種，也可以選取多種預(yù)處理方式結(jié)合使用，使效率與精度之間保持平衡。與此同時(shí)，針對(duì)選取的同態(tài)加密算法不同，其明文空間的類型和容錯(cuò)能力也不相同的情況，在選取具體預(yù)處理方式時(shí)，也應(yīng)當(dāng)考慮預(yù)處理方式對(duì)后續(xù)同態(tài)加密計(jì)算開銷等方面的影響。

2.4 DBSCAN 算法

DBSCAN 算法是一種常見的聚類算法，用來(lái)在數(shù)據(jù)集中構(gòu)建聚類簇并發(fā)現(xiàn)噪聲數(shù)據(jù)[17-18]。相較于同樣常見的K-means 聚類算法，DBSCAN 算法不需要預(yù)先定義數(shù)據(jù)簇的個(gè)數(shù)，并且適用于任何形狀的聚類簇的構(gòu)建，甚至是無(wú)連接的環(huán)狀聚類簇。由于存在最少點(diǎn)數(shù)的限制，相較于K-means 算法，DBSCAN 算法可以避免single-link 影響，因此對(duì)于任意形狀的數(shù)據(jù)分布，DBSCAN 算法都具有較好的聚類效果。

DBSCAN 算法本身也有很多變形，原始的DBSCAN 算法復(fù)雜度為Ο(n2)，ρ-近似DBSCAN算法復(fù)雜度為Ο(n)，但是其對(duì)數(shù)據(jù)的維度有一些限制。DBSCAN 算法的選取與數(shù)據(jù)類型相關(guān)，根據(jù)本文方案數(shù)據(jù)集的數(shù)據(jù)類型，選取二維DBSCAN 算法完成相關(guān)實(shí)驗(yàn)。

DBSCAN 算法的一些概念定義如下。MinPts 定義了一個(gè)聚類簇所需的最少數(shù)據(jù)點(diǎn)數(shù)，ε-鄰域表示以某個(gè)點(diǎn)為中心點(diǎn)，并以其為圓心、以ε為半徑的圓所覆蓋的范圍。中心點(diǎn)，即聚類簇的中心，其ε-鄰域中包含的數(shù)據(jù)點(diǎn)比MinPts 多；邊緣點(diǎn)，即在聚類簇邊緣的節(jié)點(diǎn)，其ε-鄰域中包含的數(shù)據(jù)點(diǎn)比MinPts 少，并且其在其他中心點(diǎn)的ε-鄰域中；噪聲點(diǎn)，即數(shù)據(jù)集中非中心點(diǎn)和邊緣點(diǎn)的其他數(shù)據(jù)點(diǎn)。節(jié)點(diǎn)定義的實(shí)例化描述如圖2 所示。除此之外，定義2 和定義3 給出了密度可達(dá)和密度相連的定義。

圖2 節(jié)點(diǎn)定義的實(shí)例化描述

定義2密度可達(dá)。令xi,xj為2 個(gè)數(shù)據(jù)點(diǎn)。設(shè)存在樣本序列p1,p2,…,pn，其中p1，pn=xj，若對(duì)于1≤k≤n，都有pk+1在以pk為中心點(diǎn)的ε-鄰域中，則稱xj由xi密度可達(dá)。

定義3密度相連。對(duì)于數(shù)據(jù)點(diǎn)xi,xj，如果存在一個(gè)點(diǎn)xk，使通過(guò)xk后xi與xj是密度可達(dá)的，則稱xj與xi密度相連。

DBSCAN 算法的流程如下。

步驟1輸入數(shù)據(jù)集合。選擇一個(gè)未被標(biāo)記過(guò)的觀察點(diǎn)xI作為當(dāng)前節(jié)點(diǎn)，標(biāo)記第一個(gè)聚類簇1。

步驟2找出以xI為中心點(diǎn)的ε-鄰域內(nèi)的所有節(jié)點(diǎn)，其均為xI的鄰居節(jié)點(diǎn)。執(zhí)行下述操作。

①若找到的鄰居節(jié)點(diǎn)數(shù)目少于MinPts，則xI是一個(gè)噪聲點(diǎn)，執(zhí)行步驟4。

②若找到的鄰居節(jié)點(diǎn)數(shù)目不少于MinPts，則xI是一個(gè)中心點(diǎn)，執(zhí)行步驟3。

步驟3分別將所有鄰居節(jié)點(diǎn)作為中心點(diǎn)，重復(fù)步驟2，直到?jīng)]有新的鄰居節(jié)點(diǎn)可以作為中心點(diǎn)。

步驟4從數(shù)據(jù)集X中選擇下一個(gè)沒(méi)有被標(biāo)記的點(diǎn)作為當(dāng)前節(jié)點(diǎn)，將聚類簇的數(shù)目更新并加1。

步驟5重復(fù)步驟2～步驟4，直到數(shù)據(jù)集X中的所有點(diǎn)都被標(biāo)記。

2.5 方案的評(píng)估標(biāo)準(zhǔn)

方案的評(píng)估標(biāo)準(zhǔn)包括2 個(gè)方面：時(shí)間效率和準(zhǔn)確率。

時(shí)間方面，本文關(guān)注的是云端執(zhí)行同態(tài)DBSCAN 算法的時(shí)間。除了時(shí)間的評(píng)估外，另一個(gè)重要的評(píng)估標(biāo)準(zhǔn)是聚類的準(zhǔn)確率。根據(jù)DBSCAN算法的特點(diǎn)，準(zhǔn)確率的評(píng)估標(biāo)準(zhǔn)包含聚類簇?cái)?shù)量和噪聲點(diǎn)判斷。本文將對(duì)比直接在明文上進(jìn)行DBSCAN 算法所得結(jié)果和在密文上同態(tài)執(zhí)行DBSCAN 算法解密后得到的結(jié)果。聚類的準(zhǔn)確率定義為2 次聚類結(jié)果中相同結(jié)果的占比，最理想狀態(tài)為2 次結(jié)果完全相同。

3 DBSCAN 隱私保護(hù)方案

本文構(gòu)建了一個(gè)在加密數(shù)據(jù)集上的同態(tài)聚類算法，從而實(shí)現(xiàn)在外包計(jì)算過(guò)程中敏感數(shù)據(jù)集的隱私保護(hù)。根據(jù)同態(tài)加密算法所支持的運(yùn)算方式，可以將DBSCAN 算法中的運(yùn)算劃分成2 類：同態(tài)加密算法支持的運(yùn)算和同態(tài)加密不支持的運(yùn)算。對(duì)于同態(tài)加密不支持的運(yùn)算，可以通過(guò)設(shè)計(jì)協(xié)議的方式來(lái)進(jìn)行處理，從而實(shí)現(xiàn)加密數(shù)據(jù)集上的同態(tài)聚類功能。同態(tài)DBSCAN 算法如算法1 所示。

常見的同態(tài)加密方案僅能支持加法（減法）、乘法運(yùn)算，所以復(fù)雜運(yùn)算需要進(jìn)行相應(yīng)的轉(zhuǎn)換使其能夠用加法和乘法表示。算法1 的步驟3)中的函數(shù)所涉及的運(yùn)算并不能夠完全被同態(tài)加密算法所支持。不支持的運(yùn)算有以下2 種。

1)在計(jì)算?ε?-鄰域時(shí)，需要計(jì)算點(diǎn)與點(diǎn)之間的距離，最常用的是歐氏距離，但其中所涉及的開方運(yùn)算并不被同態(tài)加密算法支持。

2)本文所選取的同態(tài)加密方案不具備保序加密的性質(zhì)，加密后的密文之間不會(huì)保持原有明文間的大小關(guān)系，故需解決密文大小比較問(wèn)題。

上述2 個(gè)問(wèn)題的解決方式將分別在3.2 節(jié)和3.3節(jié)中進(jìn)行介紹。

3.1 數(shù)據(jù)集預(yù)處理

本節(jié)首先給出一種基于數(shù)據(jù)特點(diǎn)，結(jié)合精度和計(jì)算開銷等條件的選取數(shù)據(jù)預(yù)處理方式的方法，選取流程如圖3 所示。

圖3 預(yù)處理方式的選取流程

設(shè)需處理的數(shù)據(jù)集為X={x1,x2,…,xn}，數(shù)據(jù)整數(shù)部分的位數(shù)為p，小數(shù)部分的位數(shù)為q（有效位數(shù)不足時(shí)用0 補(bǔ)齊）。從X中選取較大的數(shù)xi和較小的數(shù)xj，計(jì)算的值，判斷此絕對(duì)值是否滿足＜?，其中?為用戶根據(jù)數(shù)據(jù)集的特點(diǎn)自行設(shè)定的閾值。若滿足（即數(shù)值相差較?。瑒t直接選用多元處理編碼方式以保證數(shù)據(jù)精度（此種情況說(shuō)明集合中的數(shù)值大小差異主要在小數(shù)部分）；若不滿足，則進(jìn)一步判斷是否滿足q?p＞η，其中η為用戶根據(jù)情況自主設(shè)定的閾值。若q?p＞η，則將小數(shù)部分的較低位舍去（大約舍去q?p位），即小數(shù)部分的位數(shù)由q變?yōu)閝′（使q′≈p）；否則直接跳轉(zhuǎn)到下一步判斷。此時(shí)，需要綜合考慮保留精度和后續(xù)計(jì)算開銷問(wèn)題來(lái)判斷是選擇整數(shù)對(duì)編碼方式還是移位舍入編碼方式：若此時(shí)的數(shù)據(jù)精度的損失對(duì)后續(xù)計(jì)算結(jié)果影響較大，為提高計(jì)算精度，則選擇整數(shù)對(duì)編碼方式；若數(shù)據(jù)精度的損失對(duì)后續(xù)計(jì)算結(jié)果影響較小，則選擇移位舍入編碼方式。

本文方案中需要保護(hù)的敏感信息是每條數(shù)據(jù)的坐標(biāo)值，是浮點(diǎn)型數(shù)據(jù)，因此需要根據(jù)數(shù)據(jù)集的特點(diǎn)以及本文方案所選用的加密方案來(lái)選擇適合的預(yù)處理算法。本文方案選取了2 個(gè)浮點(diǎn)型數(shù)據(jù)集A、B，A 中數(shù)據(jù)的小數(shù)點(diǎn)后位數(shù)較多，但其數(shù)值大小的差異較大，且小數(shù)位數(shù)遠(yuǎn)大于整數(shù)位數(shù)，故根據(jù)圖3 所示的選取流程，可以考慮采用整數(shù)對(duì)編碼方式或移位舍入編碼方式，并且對(duì)小數(shù)部分進(jìn)行舍去，本文方案中分別保留了3、4、5 位小數(shù)進(jìn)行后續(xù)實(shí)驗(yàn)。B 中數(shù)據(jù)間差異較大且小數(shù)位數(shù)與整數(shù)位數(shù)相差不大，因此根據(jù)上文所述的選取方法，也可以考慮使用整數(shù)對(duì)編碼方式或移位舍入編碼方式。使用整數(shù)對(duì)編碼方式處理數(shù)據(jù)后的加密過(guò)程如圖4 所示。

圖4 使用整數(shù)對(duì)編碼方式處理數(shù)據(jù)后的加密過(guò)程

從圖4 中可以看出，一個(gè)數(shù)據(jù)經(jīng)方式1 處理后會(huì)轉(zhuǎn)換成一個(gè)二元組進(jìn)行加密，后續(xù)的密文操作也會(huì)增多，從而計(jì)算開銷會(huì)變大，但整數(shù)對(duì)編碼方式能夠盡可能地保留當(dāng)前數(shù)據(jù)的精度。移位舍入編碼方式則會(huì)造成一定程度的數(shù)據(jù)精度損失，但相較于整數(shù)對(duì)編碼方式計(jì)算開銷會(huì)更低。因此，可以通過(guò)實(shí)驗(yàn)來(lái)觀測(cè)數(shù)據(jù)精度的損失對(duì)A、B 這2 個(gè)數(shù)據(jù)集聚類結(jié)果的影響，從而決定使用哪種預(yù)處理方式是更合適的（實(shí)驗(yàn)結(jié)果見4.1 節(jié)）。本文方案選取的加密算法的明文空間是有限比特長(zhǎng)度的整數(shù)集，因此預(yù)處理后的數(shù)據(jù)可以直接進(jìn)行加密。

3.2 距離測(cè)度選取

在機(jī)器學(xué)習(xí)算法中，常用的距離測(cè)度包括歐氏距離、曼哈頓距離、變形歐氏距離等。相較于傳統(tǒng)歐氏距離，變形歐氏距離能更進(jìn)一步保留數(shù)據(jù)的精度，降低由開方舍入造成的誤差影響。

定義4變形歐氏距離?，F(xiàn)有2 個(gè)點(diǎn)a(x1,y1)與b(x2,y2)，變形歐氏距離可表示為

在進(jìn)行距離比較時(shí)，歐氏距離和變形歐氏距離具有較高的準(zhǔn)確性，曼哈頓距離有一定的誤差。然而，歐氏距離中的開方運(yùn)算不被同態(tài)加密算法支持，需要對(duì)開方運(yùn)算進(jìn)行進(jìn)一步處理。文獻(xiàn)[19]中使用了牛頓迭代的方法進(jìn)行同態(tài)開方運(yùn)算，過(guò)程如下。

定理1牛頓迭代開方。若方程x2?t=0，其中t為實(shí)數(shù)，則在x0附近存在一個(gè)根，使用迭代公式

依次計(jì)算x1,x2,…，序列將無(wú)限逼近方程的根。

如定理1 所示，牛頓迭代法可將開方運(yùn)算轉(zhuǎn)換為基礎(chǔ)運(yùn)算，從而滿足同態(tài)加密方案的要求。這種解決方法雖然可以實(shí)現(xiàn)開方運(yùn)算，但式(2)涉及的所有常數(shù)均需提前進(jìn)行加密處理，并且在運(yùn)算過(guò)程中涉及多次密文乘法運(yùn)算，計(jì)算復(fù)雜度較高。除此之外，牛頓迭代法所得結(jié)果是近似結(jié)果，會(huì)有一定的誤差，此誤差可能會(huì)給聚類結(jié)果造成較大影響。

定理2令a和b為2 個(gè)整數(shù)，設(shè)a的比特長(zhǎng)度為l1，b的比特長(zhǎng)度為l2，那么有ab的比特長(zhǎng)度不大于l1+l2，的比特長(zhǎng)度不大于(l1+l2)/2。

如定理2 所示，使用變形歐氏距離所得結(jié)果的比特長(zhǎng)度為歐氏距離結(jié)果的兩倍。雖然這會(huì)導(dǎo)致在后續(xù)計(jì)算過(guò)程中數(shù)據(jù)規(guī)模變大，從而使計(jì)算時(shí)間略有上升，但變形歐氏距離的計(jì)算過(guò)程僅需2 次乘法，相較于牛頓迭代法（為了保證開方結(jié)果的精度，需要迭代多次，從而需要多次乘法），比特長(zhǎng)度增長(zhǎng)所帶來(lái)的額外開銷相對(duì)較低。

與此同時(shí)，本文進(jìn)行了距離測(cè)度對(duì)聚類準(zhǔn)確度影響的測(cè)試。一般情況下，聚類算法中使用的距離測(cè)度是歐氏距離，因此測(cè)試的主要方式是將歐氏距離分別替換成曼哈頓距離和變形歐氏距離后觀察聚類結(jié)果是否與使用歐氏距離時(shí)的聚類結(jié)果相近。選取同樣的輸入?yún)?shù)，使用這3 種距離測(cè)度在明文上進(jìn)行聚類，得到的結(jié)果如圖5 所示。其中，橫縱坐標(biāo)為數(shù)據(jù)點(diǎn)的值，相同顏色為同一聚類簇，不同顏色為不同聚類簇，邊緣深色數(shù)據(jù)點(diǎn)為噪聲點(diǎn)。圖5 中的3 幅圖分別表示選擇歐氏距離、曼哈頓距離和變形歐氏距離的聚類結(jié)果。由圖5 可知，歐氏距離和變形歐氏距離的聚類結(jié)果類似，而曼哈頓距離相較于歐氏距離的聚類結(jié)果有一定誤差。結(jié)合上述分析與實(shí)驗(yàn)結(jié)果，同時(shí)考慮數(shù)據(jù)集精度和后續(xù)同態(tài)運(yùn)算的開銷，本文方案采用變形歐氏距離。

圖5 數(shù)據(jù)集A 不同距離測(cè)度聚類結(jié)果

3.3 密文比較協(xié)議

用戶端與服務(wù)器端的交互場(chǎng)景如圖6 所示。服務(wù)器將需要解密的密文發(fā)送給用戶，用戶解密密文后將解密結(jié)果的最高位發(fā)回給服務(wù)器。在此過(guò)程中，用戶與服務(wù)器可以協(xié)商設(shè)置一個(gè)時(shí)間段t，每隔t時(shí)間，用戶向服務(wù)器發(fā)起詢問(wèn)，服務(wù)器依據(jù)運(yùn)算進(jìn)程返回需解密的中間結(jié)果或同態(tài)聚類結(jié)果。在這種情形下，用戶不需要一直在線等待，只需間隔一段時(shí)間發(fā)起詢問(wèn)即可。這一過(guò)程涉及明文的直接傳輸，攻擊者可能通過(guò)竊聽的方式獲得明文和密文，這一過(guò)程的安全問(wèn)題將在5.2 節(jié)中進(jìn)行詳細(xì)分析。

圖6 用戶端與服務(wù)器端的交互場(chǎng)景

4 方案實(shí)現(xiàn)

本文實(shí)驗(yàn)使用的配置為 Intel(R)Core(TM)i7-6700 CPU @ 3.40 GHz 3.41 GHz，16 GB 內(nèi)存，借助Helib 同態(tài)加密庫(kù)完成對(duì)數(shù)據(jù)集的加密和同態(tài)聚類運(yùn)算。方案選取2 個(gè)常見的聚類數(shù)據(jù)集。數(shù)據(jù)集A 是常見形狀數(shù)據(jù)集，共有5 個(gè)聚類簇，2 000 條數(shù)據(jù)，每條數(shù)據(jù)含有2 個(gè)坐標(biāo)，每個(gè)坐標(biāo)小數(shù)點(diǎn)后有10 位小數(shù)。數(shù)據(jù)集B 為Aggregation 數(shù)據(jù)集，是常用特殊形狀聚類數(shù)據(jù)集，共有750 條數(shù)據(jù)，每條數(shù)據(jù)含有2 個(gè)坐標(biāo)，每個(gè)坐標(biāo)小數(shù)點(diǎn)后有2 位小數(shù)，與整數(shù)部分位數(shù)基本相同。

本文通過(guò)比較明文數(shù)據(jù)的聚類結(jié)果和密文數(shù)據(jù)上的同態(tài)聚類結(jié)果來(lái)驗(yàn)證方案的準(zhǔn)確性。實(shí)驗(yàn)中，明文數(shù)據(jù)集和密文數(shù)據(jù)集在執(zhí)行DBSCAN 算法時(shí)，所用參數(shù)ε和MinPts 一致，實(shí)驗(yàn)中ε記作eps，MinPts 記作min_Pts。

4.1 數(shù)據(jù)預(yù)處理方式選取

數(shù)據(jù)集A和數(shù)據(jù)集B選取的是常見的聚類算法數(shù)據(jù)集，分別代表整數(shù)與小數(shù)部分位數(shù)相差較大和較小2 種情況，以此說(shuō)明本文方案具有普適性。本節(jié)通過(guò)實(shí)驗(yàn)結(jié)果來(lái)驗(yàn)證3.1 節(jié)選取方法的正確性，并得出更適合于數(shù)據(jù)集A 和數(shù)據(jù)集B 的預(yù)處理方式。實(shí)驗(yàn)使用3 種預(yù)處理方式分別對(duì)2 個(gè)數(shù)據(jù)集編碼，然后進(jìn)行同態(tài)聚類操作，得到同態(tài)聚類算法的時(shí)間開銷和同態(tài)聚類的準(zhǔn)確率，如表1 所示。從表1中可以看出，多元處理編碼的準(zhǔn)確率是100%，但是時(shí)間開銷較大；整數(shù)對(duì)編碼和移位舍入編碼的準(zhǔn)確率雖然均沒(méi)有達(dá)到100%，但也是非常準(zhǔn)確的，這說(shuō)明3.1 節(jié)的選取流程中首先將多元處理編碼排除，認(rèn)為數(shù)據(jù)集A 和數(shù)據(jù)集B 更適合采用整數(shù)對(duì)編碼方式或移位舍入編碼方式，并且對(duì)數(shù)據(jù)集A 中數(shù)據(jù)的小數(shù)部分進(jìn)行一定程度的舍棄是正確的。此外，整數(shù)對(duì)編碼方式的準(zhǔn)確率會(huì)略高于移位舍入編碼方式，但是移位舍入編碼的準(zhǔn)確率也非常高，并且移位舍入編碼的計(jì)算效率遠(yuǎn)高于整數(shù)對(duì)編碼。實(shí)驗(yàn)結(jié)果表明，本文實(shí)驗(yàn)選取的數(shù)據(jù)集更適合使用移位舍入編碼方式，所以本文實(shí)驗(yàn)給出的具體結(jié)論都是建立在選擇移位舍入編碼方式的基礎(chǔ)上的。

4.2 數(shù)據(jù)集明文聚類結(jié)果

選取合適的參數(shù)，分別對(duì)數(shù)據(jù)集A 和數(shù)據(jù)集B進(jìn)行聚類處理，結(jié)果如圖7 和圖8 所示。其中數(shù)據(jù)集A 選取參數(shù)為eps=0.547（編碼后為5 470），min_Pts=9；數(shù)據(jù)集B 選取參數(shù)為eps=1.8（編碼后為180），min_Pts=11。

4.3 數(shù)據(jù)集密文聚類結(jié)果

對(duì)數(shù)據(jù)集A和數(shù)據(jù)集B分別進(jìn)行移位舍入編碼處理后再加密，然后對(duì)加密后的數(shù)據(jù)執(zhí)行同態(tài)聚類操作。對(duì)數(shù)據(jù)集A 中的數(shù)據(jù)進(jìn)行移位舍入編碼處理，結(jié)果分別保留3、4、5 位小數(shù)，而后在密文上執(zhí)行同態(tài)聚類算法，解密后的聚類結(jié)果如圖9～圖11 所示。對(duì)數(shù)據(jù)集B 直接進(jìn)行移位舍入編碼，加密后進(jìn)行同態(tài)聚類，計(jì)算結(jié)束后解密得到的聚類結(jié)果如圖12 所示。

表1 不同編碼方式時(shí)間開銷與準(zhǔn)確率

圖7 數(shù)據(jù)集A 明文聚類結(jié)果

圖8 數(shù)據(jù)集B 明文聚類結(jié)果

圖9 數(shù)據(jù)集A 保留3 位小數(shù)密文聚類結(jié)果

圖10 數(shù)據(jù)集A 保留4 位小數(shù)密文聚類結(jié)果

圖11 數(shù)據(jù)集A 保留5 位小數(shù)密文聚類結(jié)果

圖12 數(shù)據(jù)集B 密文聚類結(jié)果

5 方案評(píng)估

5.1 實(shí)驗(yàn)結(jié)果分析

本節(jié)分別對(duì)比數(shù)據(jù)集A和數(shù)據(jù)集B的明文和密文聚類結(jié)果，得出方案準(zhǔn)確率如表2 和表3 所示。

表2 數(shù)據(jù)集A 明文和密文聚類結(jié)果對(duì)比

表3 數(shù)據(jù)集B 明文和密文聚類結(jié)果對(duì)比

從表2 可以看出，預(yù)處理時(shí)保留3 位小數(shù)的加密數(shù)據(jù)集的聚類簇?cái)?shù)與明文有較大差異，準(zhǔn)確率僅為80%；進(jìn)一步保留精度的加密數(shù)據(jù)集（4 位小數(shù)和5 位小數(shù)）具有更好的聚類準(zhǔn)確性，這2 種情況下的準(zhǔn)確率約為99.8%。表3 結(jié)果顯示，在數(shù)據(jù)集B 的聚類結(jié)果中，明文和密文聚類簇?cái)?shù)相同，噪聲點(diǎn)數(shù)目接近，準(zhǔn)確率在99.7%以上。文獻(xiàn)[20]給出了現(xiàn)有其他使用同態(tài)加密實(shí)現(xiàn)機(jī)器學(xué)習(xí)隱私保護(hù)方案的準(zhǔn)確率，平均準(zhǔn)確率為95%，最高準(zhǔn)確率為99.8%，因此相較于此前的方案，本文方案實(shí)現(xiàn)了較高的準(zhǔn)確率。

時(shí)間開銷方面，方案[8]對(duì)數(shù)據(jù)進(jìn)行逐比特加密，導(dǎo)致運(yùn)算時(shí)間較長(zhǎng)，對(duì)400 條密態(tài)二維數(shù)據(jù)的處理時(shí)間長(zhǎng)達(dá)15 h；本文方案時(shí)間開銷較低，在處理數(shù)據(jù)集B 時(shí)，對(duì)750 條密態(tài)二維數(shù)據(jù)進(jìn)行同態(tài)聚類算法僅需45.28 s。

聚類結(jié)果出現(xiàn)誤差的主要原因包括2 個(gè)方面：一方面是實(shí)際數(shù)據(jù)的舍入誤差，考慮到后續(xù)加密時(shí)間開銷問(wèn)題，在數(shù)據(jù)預(yù)處理階段對(duì)數(shù)據(jù)的精度進(jìn)行了一定程度的舍棄；另一方面，由于本文方案中的密文比較協(xié)議僅能得出兩密文之間的大于或小于關(guān)系，對(duì)于等于關(guān)系直接將其歸入大于的范圍內(nèi)，這會(huì)造成一定誤差。針對(duì)第二個(gè)問(wèn)題，可以考慮采用數(shù)值比較器進(jìn)行改善。HElib 已有相關(guān)函數(shù)，但該函數(shù)需要多次密文乘法操作，大大影響計(jì)算效率。

5.2 安全性分析

本節(jié)將對(duì)本文方案的安全性進(jìn)行評(píng)估。在本文方案中，將云服務(wù)器設(shè)定為誠(chéng)實(shí)但是具有好奇心的半誠(chéng)實(shí)模型，選取的BGV 算法是滿足語(yǔ)義安全的同態(tài)加密算法。

本文方案希望達(dá)到的安全目標(biāo)為云服務(wù)器和具備竊聽能力的敵手無(wú)法獲取用戶的數(shù)據(jù)信息，也無(wú)法通過(guò)同態(tài)DBSCAN 算法倒推出原始數(shù)據(jù)。在以上設(shè)定的前提下，下文將給出幾個(gè)定理并進(jìn)行證明，以說(shuō)明本文方案的安全性。

定理3云服務(wù)器或具備竊聽能力的敵手根據(jù)他們獲取的信息成功恢復(fù)用戶原始數(shù)據(jù)的概率是可忽略的。

證明云服務(wù)器或具備竊聽能力的敵手能夠獲得的數(shù)據(jù)為和參數(shù)?ε?、MinPts。從數(shù)據(jù)的組成來(lái)看，除了MinPts 之外，其他都是通過(guò)BGV 同態(tài)加密得到的密文。云服務(wù)器和敵手在不知道私鑰的情況下成功獲得用戶原數(shù)據(jù)的概率等同于攻破BGV 算法的概率。由同態(tài)加密算法的語(yǔ)義安全可知，攻破BGV 算法的概率是可忽略的，因此云服務(wù)器和敵手成功獲取用戶數(shù)據(jù)的概率也是可忽略的。云服務(wù)器或敵手能夠獲得的數(shù)據(jù)中唯一的明文是MinPts，而此明文只是表示聚類簇中包含的最小數(shù)據(jù)個(gè)數(shù)，并不會(huì)泄露用戶的任何數(shù)據(jù)。

此外，本文方案中涉及云服務(wù)器與用戶之間的一個(gè)協(xié)議。本質(zhì)上來(lái)說(shuō)，在此協(xié)議中云服務(wù)器將一個(gè)BGV 密文發(fā)送給用戶，用戶返還給云服務(wù)器0或1。云服務(wù)器或敵手在不知道私鑰的情況下，無(wú)法獲得該密文的具體內(nèi)容，并且此時(shí)的用戶返還的明文（0 或1）和其對(duì)應(yīng)的云服務(wù)器發(fā)送的密文也不構(gòu)成密碼學(xué)中定義的“明密文對(duì)”，因而無(wú)法在獲取足夠多的0 或1 明文與其對(duì)應(yīng)密文的情況下推測(cè)出密鑰。證畢。

定理4云服務(wù)器或具備竊聽能力的敵手獲取同態(tài)DBSCAN 算法后，能夠成功獲得用戶原始數(shù)據(jù)的概率是可忽略的。

證明云服務(wù)器或具備竊聽能力的敵手可能通過(guò)竊聽等手段獲得在云端執(zhí)行的同態(tài)DBSCAN算法的具體內(nèi)容。DBSCAN 是一種無(wú)監(jiān)督型機(jī)器學(xué)習(xí)算法，即不需要通過(guò)設(shè)立訓(xùn)練集預(yù)先構(gòu)建出模型再利用該模型對(duì)其他數(shù)據(jù)進(jìn)行處理，而是直接在數(shù)據(jù)上進(jìn)行聚類操作得到結(jié)果。本文方案保留了DBSCAN 算法的這一特點(diǎn)，直接作用于密文數(shù)據(jù)來(lái)獲得同態(tài)聚類結(jié)果，并不存在模型。與分類器的隱私保護(hù)方案不同，利用模型參數(shù)倒推用戶原始數(shù)據(jù)這類攻擊無(wú)法應(yīng)用于本文方案。另外，本文方案實(shí)質(zhì)上進(jìn)行的運(yùn)算是依據(jù)密文數(shù)據(jù)同態(tài)計(jì)算距離，然后給每個(gè)數(shù)據(jù)點(diǎn)標(biāo)記其歸屬的聚類簇或?qū)⑵錁?biāo)記為噪聲點(diǎn)，因而攻擊者即使獲取了算法過(guò)程，也無(wú)法通過(guò)算法內(nèi)容來(lái)推測(cè)出原始數(shù)據(jù)信息。因此，本文方案的數(shù)據(jù)安全性立足于加密算法的安全性。

綜上，攻擊者獲得同態(tài)DBSCAN 算法后，能夠成功獲取用戶原始數(shù)據(jù)的概率等同于攻破BGV 算法的概率，由定理4 可知，此概率是可忽略的。證畢。

6 結(jié)束語(yǔ)

本文提出了一種在加密數(shù)據(jù)集上進(jìn)行同態(tài)DBSCAN 聚類算法的方案，用于解決數(shù)據(jù)外包計(jì)算過(guò)程中的隱私保護(hù)問(wèn)題。該方案針對(duì)不同數(shù)據(jù)集精度，提出了多種編碼預(yù)處理方式，并且給出了一種基于數(shù)據(jù)集特點(diǎn)、綜合考慮數(shù)據(jù)精度和計(jì)算開銷等方面的數(shù)據(jù)預(yù)處理方式的選取策略；依據(jù)同態(tài)加密算法支持的運(yùn)算類型和實(shí)驗(yàn)測(cè)試結(jié)果，選取變形歐氏距離作為算法中的距離測(cè)度；針對(duì)同態(tài)加密算法

不支持的比較運(yùn)算，設(shè)計(jì)了一個(gè)交互協(xié)議來(lái)實(shí)現(xiàn)此功能。本文方案具有可靠的數(shù)據(jù)安全性、良好的聚類效果和計(jì)算性能。