賈春福，李瑞琪，王雅飛

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

1 引言

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

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

對數(shù)據(jù)集進(jìn)行加密時，如果使用傳統(tǒng)的加密算法，服務(wù)器無法直接對密態(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ù)不同，可大致分為以下幾類：支持無限次數(shù)和多種運(yùn)算的全同態(tài)加密（FHE,fully homomorphic encryption）算法、支持無限次數(shù)和有限種類的部分同態(tài)加密（PHE,partial homomorphic encryption）算法、支持有限次數(shù)和多種運(yùn)算的淺同態(tài)加密（SWHE,somewhat homomorphic encryption）算法[1-4]。大部分應(yīng)用場景只需要有限次同態(tài)加法或乘法操作，并且SWHE 算法相較于FHE 算法而言具有更好的效率，因此SWHE 算法具有更加廣泛的應(yīng)用場景[5]。BGV（Brakerski-Gentry-Vaikuntanathan）方案是一種常用的SWHE 算法，支持加密多項式或整數(shù)，同時也可以利用中國剩余定理實現(xiàn)并行化操作。

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

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

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

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

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

2 基礎(chǔ)知識

2.1 符號介紹

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

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

定義1 同態(tài)加密。同態(tài)加密算法主要包含4 個部分：密鑰生成（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)：輸入一個布爾電路C、一組密文 {c1,…,ck}和公鑰pk，輸出結(jié)果密文cEval。

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

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

KeyGen(λ)。選取s←χd，令私鑰為sk=。隨機(jī)抽取矩陣，向量e←χN，計算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 中除了上述算法之外還包括一些用于實現(xiàn)FHE 算法的處理程序[16]，例如key switching、modulus switching 和bootstrapping。FHE 算法存在密鑰過長、密文量級過大、降噪處理耗時較長等弊端，在實際應(yīng)用中具有一定的局限性；SWHE 算法雖然不支持無限次密文運(yùn)算，但其密文和密鑰的尺寸較小，也不需要bootstrapping 技術(shù)對密文進(jìn)行刷新，因而運(yùn)行效率較高。由于本文的場景只需有限次密文運(yùn)算，因此選擇使用SWHE 算法，以獲得較高的計算效率。

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

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

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

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

方式2移位舍入編碼

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

這種處理方式相當(dāng)于將原有數(shù)據(jù)擴(kuò)大了10v倍，然后根據(jù)實際要求，對擴(kuò)大后數(shù)據(jù)的小數(shù)部分進(jìn)行適當(dāng)?shù)纳崛?，從而既能夠保證該類型數(shù)據(jù)的精度，又不需要在加密時選取較大的加密方案參數(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ù)精度不會因預(yù)處理操作而受到損失，然而這種處理方式也存在一定的弊端。用戶若使用方式3 將原數(shù)據(jù)變?yōu)槎M，則數(shù)據(jù)量變?yōu)樵瓉淼膬杀叮瑥亩黾蛹用茈A段的開銷。除此之外，在執(zhí)行同態(tài)乘法操作時，由原來一對整數(shù)相乘變?yōu)閮蓪φ麛?shù)相乘，乘法次數(shù)增加，計算復(fù)雜度增加。

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

2.4 DBSCAN 算法

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

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

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

圖2 節(jié)點定義的實例化描述

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

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

DBSCAN 算法的流程如下。

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

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

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

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

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

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

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

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

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

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

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

本文構(gòu)建了一個在加密數(shù)據(jù)集上的同態(tài)聚類算法，從而實現(xiàn)在外包計算過程中敏感數(shù)據(jù)集的隱私保護(hù)。根據(jù)同態(tài)加密算法所支持的運(yùn)算方式，可以將DBSCAN 算法中的運(yùn)算劃分成2 類：同態(tài)加密算法支持的運(yùn)算和同態(tài)加密不支持的運(yùn)算。對于同態(tài)加密不支持的運(yùn)算，可以通過設(shè)計協(xié)議的方式來進(jìn)行處理，從而實現(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)在計算?ε?-鄰域時，需要計算點與點之間的距離，最常用的是歐氏距離，但其中所涉及的開方運(yùn)算并不被同態(tài)加密算法支持。

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

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

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

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

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

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

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

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

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

3.2 距離測度選取

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

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

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

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

依次計算x1,x2,…，序列將無限逼近方程的根。

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

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

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

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

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

3.3 密文比較協(xié)議

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

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

4 方案實現(xiàn)

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

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

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

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

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

選取合適的參數(shù)，分別對數(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é)果

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

表1 不同編碼方式時間開銷與準(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 方案評估

5.1 實驗結(jié)果分析

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

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

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

從表2 可以看出，預(yù)處理時保留3 位小數(shù)的加密數(shù)據(jù)集的聚類簇數(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é)果中，明文和密文聚類簇數(shù)相同，噪聲點數(shù)目接近，準(zhǔn)確率在99.7%以上。文獻(xiàn)[20]給出了現(xiàn)有其他使用同態(tài)加密實現(xiàn)機(jī)器學(xué)習(xí)隱私保護(hù)方案的準(zhǔn)確率，平均準(zhǔn)確率為95%，最高準(zhǔn)確率為99.8%，因此相較于此前的方案，本文方案實現(xiàn)了較高的準(zhǔn)確率。

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

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

5.2 安全性分析

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

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

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

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

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

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

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

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

6 結(jié)束語

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

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