可驗證的隱私保護k-means聚類方案

張 恩，李會敏，常 鍵

（1.河南師范大學(xué)計算機與信息工程學(xué)院，河南新鄉(xiāng) 453007；2.智慧商務(wù)與物聯(lián)網(wǎng)技術(shù)河南省工程實驗室（河南師范大學(xué)），河南新鄉(xiāng) 453007）

（*通信作者電子郵箱zhangenzdrj@163.com）

0 引言

聚類算法在機器學(xué)習(xí)、信息檢索、模式識別等領(lǐng)域的數(shù)據(jù)挖掘中具有廣泛的應(yīng)用，在現(xiàn)實生活中，對醫(yī)療、社會科學(xué)、商業(yè)等應(yīng)用的研究有著重要的作用。例如，現(xiàn)有兩個醫(yī)療機構(gòu)，每個機構(gòu)都擁有患者的疾病和臨床等治療過程收集的數(shù)據(jù)集。假設(shè)這兩家機構(gòu)使用各自的方法收集數(shù)據(jù)后，希望將數(shù)據(jù)組合在一起進行訓(xùn)練，并確定使用聚類算法能夠給疾病控制機制提供更好的研究方向。由于政策法規(guī)的約束以及數(shù)據(jù)的敏感性，雙方均不愿意將數(shù)據(jù)共享，如何在保護隱私的前提下協(xié)作地在聯(lián)合數(shù)據(jù)集上進行聚類成為一個具有挑戰(zhàn)性的問題。

目前，大數(shù)據(jù)的存儲和計算研究已趨近成熟，但是面臨來自不同數(shù)據(jù)源的聯(lián)合數(shù)據(jù)的隱私問題仍有待優(yōu)化。在聯(lián)合計算過程中，如果有一個可信的第三方，Alice和Bob都愿意將數(shù)據(jù)發(fā)送給該第三方，那么該第三方可以使用聚類算法訓(xùn)練雙方的數(shù)據(jù)并將聚類中心發(fā)送給Alice和Bob。然而，在現(xiàn)實中，很難找到完全可信的第三方。針對此類問題，一系列文章結(jié)合安全多方計算［1-4］對聚類算法進行研究。

現(xiàn)有的保護隱私的聚類方法需要大量的計算、通信和存儲開銷，當(dāng)訓(xùn)練大量數(shù)據(jù)時，如果用戶沒有足夠的資源，就無法進行聚類。云外包計算的出現(xiàn)提供了很好的解決方法，云外包計算［5-6］的一個基本優(yōu)勢是數(shù)據(jù)外包的實現(xiàn)，使得用戶在資源受限的設(shè)備上進行大量的數(shù)據(jù)存儲和使用。通過云外包服務(wù)，企業(yè)或個人可以將大量復(fù)雜、耗時的計算和存儲任務(wù)外包給不可信的云服務(wù)提供商（Cloud Service Provider，CSP），這樣有利于分享資源、節(jié)約開銷和降低創(chuàng)業(yè)成本。然而將數(shù)據(jù)外包到云服務(wù)器，剝奪了客戶對其數(shù)據(jù)的直接控制權(quán)，不可避免帶來一些新的問題。在將數(shù)據(jù)外包到服務(wù)器進行計算時，服務(wù)器為了節(jié)省計算資源，可能不經(jīng)計算就返回錯誤結(jié)果。即使在半誠實模型中，服務(wù)器誠實的執(zhí)行協(xié)議也會在計算過程中遭遇黑客、病毒攻擊以及服務(wù)器故障等情況，導(dǎo)致返回錯誤結(jié)果。因此用戶在接收到服務(wù)器返回的結(jié)果后，需要一種驗證機制判斷結(jié)果的正確性?，F(xiàn)有云外包的隱私保護k-means聚類算法研究中尚不能解決驗證結(jié)果正確性的問題。此外，在外包環(huán)境下，聚類的初始化算法對聚類結(jié)果和算法的迭代效率有很大影響，但是先前云外包方案中并未對聚類初始化進行研究。

針對以上問題，本文提出了一種基于云外包的可驗證隱私保護k-means 算法方案，適用于訓(xùn)練任何分區(qū)的數(shù)據(jù)，目的是在不泄露各方隱私數(shù)據(jù)的情況下根據(jù)距離度量將相似的數(shù)據(jù)進行聚類，以及對云返回的結(jié)果進行驗證。本文主要工作如下：

1）結(jié)合秘密共享、混淆電路等多種安全計算方法，提出了一種基于外包的k-means聚類隱私保護方案，在多用戶的場景下將數(shù)據(jù)外包到兩個非合謀的服務(wù)器，服務(wù)器對隱私數(shù)據(jù)進行k-means聚類，節(jié)省了用戶的大量開銷。

2）在多用戶外包的條件下，提出了新的聚類初始化的方法。用戶對自己的明文數(shù)據(jù)執(zhí)行k-means 聚類算法，得到k個聚類中心，并將其拆分成子份額形式發(fā)送給服務(wù)器；服務(wù)器安全地求聚類的平均值，得到初始化后的聚類中心。此初始化方法可以有效提高算法的迭代效率。

3）在計算最小值算法中，建立一個數(shù)組記錄份額值屬于哪一個聚類中心，使得云服務(wù)器可單獨地計算更新的聚類中心份額值，節(jié)省了部分開銷和降低了時間復(fù)雜度。

4）首次提出了一種在隱私保護k-means 聚類算法云外包下的驗證機制，能夠有效驗證云返回的聚類結(jié)果。當(dāng)服務(wù)器返回聚類結(jié)果后，用戶之間協(xié)作進行驗證，從而判斷服務(wù)器是否誠實遵循協(xié)議。

1 相關(guān)工作

隨著數(shù)據(jù)挖掘的快速發(fā)展及應(yīng)用，其數(shù)據(jù)帶來的隱私問題越發(fā)受到關(guān)注。隱私保護數(shù)據(jù)挖掘最早由Agrawal 等［7］以及Lindell 等［8］于2000 年在不同的框架下提出，分別采用數(shù)據(jù)擾亂和安全多方計算方法對決策樹進行隱私保護訓(xùn)練。在數(shù)據(jù)挖掘中，聚類作為統(tǒng)計數(shù)據(jù)分析的一種常用技術(shù)，應(yīng)用于許多領(lǐng)域，以下主要討論k-means聚類隱私保護的相關(guān)研究。

現(xiàn)有的保護隱私聚類算法在不同數(shù)據(jù)分布下進行研究，包括水平分區(qū)數(shù)據(jù)、垂直分區(qū)數(shù)據(jù)和任意分區(qū)數(shù)據(jù)。Vaidya等［9］最早對垂直分區(qū)數(shù)據(jù)設(shè)計k-means 算法的隱私保護方案，數(shù)據(jù)按屬性分發(fā)到各個參與方，每個參與方僅對自己的屬性數(shù)據(jù)學(xué)習(xí)；但是該協(xié)議需要三個非共謀參與者的存在，在實際應(yīng)用中很難實現(xiàn)。Yi 等［10］在不泄露中間參數(shù)情況下完成聚類。Jha 等［11］提出了兩種k-means 聚類隱私保護協(xié)議，將算法各步驟的聚類均值泄露給參與方，分別采用基于不經(jīng)意多項式計算和基于同態(tài)加密實現(xiàn)，并且此方法僅適用于水平分區(qū)數(shù)據(jù)。Jagannathan 等［12］首次提出在任意分區(qū)數(shù)據(jù)上進行k-means聚類算法的隱私保護，通過兩方合作將所有中間參數(shù)分割成隨機的分區(qū)。Bunn 等［13］提出了一種基于同態(tài)加密的兩方k-means聚類保護協(xié)議，在尋找最優(yōu)聚類過程中不公開中間參數(shù)和聚類分配情況，但是擴展到多方k-means 聚類時，協(xié)議不能抵抗共謀攻擊。Xing等［14］解決了用戶和聚類算法服務(wù)提供者之間的合謀問題。Mohassel 等［15］通過1-out-of-N 不經(jīng)意傳輸技術(shù)實現(xiàn)了高效的安全乘法。Meskine 等［16］綜述了現(xiàn)有的基于安全多方計算的隱私保護k-means 聚類算法。Su等［17］從非交互角度提出了一種新的差分隱私k-means 聚類算法。Feldman 等［18］提出了一種差分隱私k-means 聚類，方案的誤差與維數(shù)之間呈亞線性。Huang 等［19］提出一種優(yōu)化差分隱私方法，通過Wasserstein距離減少差分隱私的誤差值。

利用云外包可以有效節(jié)省用戶的計算資源，將大量復(fù)雜、耗時的計算外包到云服務(wù)器。Rao 等［20］提出一種保護隱私的分布式聚類機制，通過將多用戶數(shù)據(jù)外包到云服務(wù)器，利用同態(tài)加密算法設(shè)計k-means聚類方案；但是該方案不能抵抗合謀攻擊。Liu 等［21］允許數(shù)據(jù)擁有者使用同態(tài)加密方案對數(shù)據(jù)加密，服務(wù)提供者對密文進行k-means 聚類，并使服務(wù)提供者可以將加密數(shù)據(jù)與數(shù)據(jù)提供的陷門信息進行比較；但是該方案只保護一方的隱私。Jiang 等［22］提出了兩方外包的k-means 隱私保護方案，每一方的數(shù)據(jù)僅加密一次，但是在計算過程中用戶和云交互次數(shù)多，且更新的聚類中心未保護。然而，以上云外包的方案均不能對云服務(wù)器返回的聚類結(jié)果進行有效驗證，此外現(xiàn)有云外包方案初始化產(chǎn)生的集群中心隨機性大，使得算法的迭代效率低。本文提出了一種驗證算法，使得用戶能有效驗證云服務(wù)器返回的聚類結(jié)果，并且改進了初始化中心方法，能提高算法的迭代效率。

2 基礎(chǔ)知識

2.1 k-means聚類

聚類在機器學(xué)習(xí)中屬于無監(jiān)督學(xué)習(xí)算法，給定一組數(shù)據(jù)，聚類算法根據(jù)數(shù)據(jù)的特征將數(shù)據(jù)點映射到不同的組，在同一組的數(shù)據(jù)具有相似的特征或?qū)傩裕诓煌M的數(shù)據(jù)應(yīng)具有高度不相似的特征或?qū)傩?。k-means 算法［23］為聚類應(yīng)用最廣泛的算法之一，以一種迭代循環(huán)的方式將一組數(shù)據(jù)分成k個聚類，其終止條件為聚類中心點之間的平方誤差值準則最小。以下對k-means聚類算法作簡單描述。

算法1k-means聚類算法。

輸入n個數(shù)據(jù)點，確定聚類的數(shù)目k；

輸出k個聚類中心μ={μ1，μ2，…，μk}。

1）初始化k個聚類中心：W={W1，W2，…，Wk}。

2）迭代開始，重復(fù)執(zhí)行以下步驟。

3）計算每個數(shù)據(jù)點到k個聚類中心的距離，并將其分配到最近的聚類中心。

4）更新聚類中心：對每個聚類中心，計算屬于此聚類中心所有數(shù)據(jù)點的平均值，作為新的聚類中心點。

5）判斷是否達到終止條件：若滿足條件，則返回新的聚類中心點；否則，繼續(xù)執(zhí)行3）、4）、5）。

2.2 加法秘密共享和乘法三元組

本文協(xié)議涉及的大部分數(shù)據(jù)是通過加法秘密共享技術(shù)［24］在兩個參與方之間共享，下面簡要回顧加法秘密共享的方案。

2.3 混淆電路

混淆電路是目前最常見的用于兩方安全計算的通用技術(shù)。Yao［2］首次提出混淆電路，后來Ballaer等［25］給出了標準化定義?；煜娐芳夹g(shù)的優(yōu)化研究主要有point-and-permute［26］、free-XOR 門［27］和半門［28］。本文使用Ballaer 等［25］提出的混淆方案，首先簡要地回顧此混淆方案，主要算法如下：

Gb：輸入（1λ，f），其中，λ為安全參數(shù)，f為布爾電路；輸出（F，e，d），其中，e為加密密鑰，d為解密密鑰，F(xiàn)為混淆電路。

En：輸入（e，x），其中x∈{0，1}n，輸出一個混淆輸入值X。

Ev：輸入（F，X），輸出混淆輸出值Y。

De：輸入（d，Y），輸出明文輸出值y。

在兩方安全計算中，Alice 和Bob 在不泄露各自隱私輸入的情況下，計算函數(shù)并得到輸出結(jié)果。Alice 將函數(shù)的布爾電路f轉(zhuǎn)換成混淆電路F，并將自己的混淆輸入發(fā)送給Bob。Bob在不泄漏輸入數(shù)據(jù)的情況下從Alice 那得到混淆輸入，并根據(jù)混淆電路計算出函數(shù)對應(yīng)的混淆輸出值。在計算過程中沒有泄露有關(guān)輸入的任何信息，得到兩方計算的結(jié)果。本文使用兩個簡單的混淆電路構(gòu)建安全協(xié)議：加法混淆電路和比較混淆電路。

2.4 半誠實模型

半誠實模型［29］下要求半誠實參與者或誠實參與者執(zhí)行協(xié)議。誠實參與者完全按照協(xié)議的步驟執(zhí)行，同時對協(xié)議中的輸入、輸出以及中間結(jié)果進行保密；半誠實參與者同樣會按照協(xié)議的步驟執(zhí)行，不會惡意修改數(shù)據(jù)，但是在協(xié)議的執(zhí)行過程中，會收集其他參與者的信息，以在協(xié)議結(jié)束后推斷其他參與者的輸入信息或?qū)⑵湫孤督o攻擊者。

定義 令π表示隱私保護k-means 算法協(xié)議，F(xiàn)表示理想模型下的函數(shù)。如果對于現(xiàn)實模型下任何概率多項式敵手A，存在理想模型下的敵手S，使得協(xié)議π在現(xiàn)實和理想情況下計算不可區(qū)分，即滿足

則證明協(xié)議π安全實現(xiàn)理想函數(shù)F。

3 構(gòu)建模塊

本章設(shè)計用于隱私保護k-means聚類算法的一些子模塊，包括聚類初始化算法、安全歐幾里得距離算法、安全計算最小值算法和驗證算法。方案使用的部分符號見表1。

表1 符號定義Tab.1 Notations definition

3.1 聚類中心初始化

聚類中心的初始化方法包括很多種，找到一個合適的初始化聚類中心方法對聚類的結(jié)果至關(guān)重要，所以在不同的聚類條件下，需要采用不同的初始化方法。一種常見的方法是隨機取k個聚類中心，在隱私保護環(huán)境下，讓一個參與方隨機產(chǎn)生k個聚類中心值，分成份額值發(fā)送到兩個服務(wù)器，這種方法易于實現(xiàn)；另一種方法是在數(shù)據(jù)集中挑選k個不同的數(shù)據(jù)點的值作為聚類中心，此條件下的隱私保護也可簡單地實現(xiàn)。但是，這兩種方法產(chǎn)生的聚類中心隨機性較強，會影響到k-means聚類的結(jié)果。

本文提出了一種新的適用于云外包情況下的初始化算法。首先每個參與方對各自的明文數(shù)據(jù)進行k-means聚類，得到k個聚類中心點，并將得到的值通過加法秘密共享技術(shù)分成兩個子份額，分別發(fā)送給兩個服務(wù)器；服務(wù)器接收到所有用戶的份額值相應(yīng)地求得對應(yīng)份額值的平均值，理論上是對參與者產(chǎn)生的聚類中心求平均。具體初始化算法如算法2。

算法2 聚類中心初始化算法。

3）Sj(j∈{0，1})有m個聚類中心集合，并計算得到初始化后的聚類中心：

按照以上初始化算法得到的聚類中心比隨機化生成的聚類中心在迭代次數(shù)上更具有優(yōu)勢。通過此初始化方法得到的聚類中心點能夠有效減少算法的迭代次數(shù)，使得整個隱私保護環(huán)境下的k-means算法訓(xùn)練的復(fù)雜度降低。

3.2 安全的計算歐幾里得距離

在機器學(xué)習(xí)中，歐幾里得距離是k-means聚類算法中最常用的判斷數(shù)據(jù)相似度的距離度量，計算距離的目的是對數(shù)據(jù)點計算得到的距離值進行比較。為了提高計算效率，將歐幾里得距離改為歐幾里得平方距離（Euclidean square distance，Esd），并不影響比較大小的結(jié)果。本文定義兩點x、y之間的安全歐幾里得平方距離計算公式為：z←FEsd(x，y)。

在歐幾里得計算時，需要使用安全乘法技術(shù)，利用乘法三元組協(xié)助計算乘法，可將大量的計算操作放在離線階段，在線階段只進行少量的計算便可完成安全乘法操作。

的結(jié)果份額值。最終，S0、S1在不泄露各自輸入數(shù)據(jù)的情況下，得到函數(shù)的結(jié)果份額值。

3.3 安全計算最小值算法

Qi(i∈{1，2，…，n}) 點到k個聚類中心的距離為{di1，di2，…，dik}，S0和S1分別持有數(shù)據(jù)和，需要考慮如何在不泄露各自份額值的情況下求出k個數(shù)據(jù)的最小值。采用混淆電路技術(shù)進行數(shù)值比較，可達到在不泄露任何輸入數(shù)據(jù)的信息下得到輸出結(jié)果。利用混淆電路的特點，設(shè)計了一個適合在秘密份額值的情況下比較大小的電路結(jié)構(gòu)（Secure CoMPare circuit，SCMP），并調(diào)用此電路得到一組數(shù)據(jù)的最小值。最小值算法如算法3所示。

圖1 SCMP電路圖Fig.1 SCMP circuit diagram

通過SCMP 電路圖實現(xiàn)兩個數(shù)值在不泄露數(shù)據(jù)的情況下安全地比較大小，調(diào)用此結(jié)構(gòu)k-1 次實現(xiàn)對k個值求得最小值，求最小值算法的復(fù)雜度為O(k)。

3.4 驗證算法

在將數(shù)據(jù)外包到服務(wù)器后，一個安全問題是由不受信任的第三方服務(wù)提供者執(zhí)行協(xié)議，其在計算過程中，為了節(jié)省計算資源，沒有執(zhí)行聚類算法直接返回錯誤結(jié)果，但是用戶并不能確定服務(wù)器返回的結(jié)果是否正確。即使服務(wù)器誠實地執(zhí)行協(xié)議，在計算過程中，可能遭受黑客攻擊或者服務(wù)器出現(xiàn)故障，導(dǎo)致返回錯誤的結(jié)果。所以，用戶需要對服務(wù)器返回的結(jié)果進行驗證，驗證的最終目標是驗證服務(wù)器返回的聚類中心結(jié)果是否達到局部最優(yōu)。

在驗證階段，用戶之間協(xié)作計算，通過驗證部分聚類點的準確性來判斷服務(wù)器是否誠實地執(zhí)行協(xié)議。例如，任意挑選兩個聚類中心點，每個用戶運行明文k-means 協(xié)議，得到屬于此兩個聚類的數(shù)據(jù)點，計算數(shù)據(jù)點的平均值并公開?，F(xiàn)在每個用戶接收到其他參與方的值，對接收到的所有值求平均，再計算與之前的兩個聚類中心點之間的歐幾里得距離，若結(jié)果小于不可忽略值，則證明服務(wù)器誠實的執(zhí)行協(xié)議。具體計算如下：

算法4 驗證算法。

在驗證算法中，參與方協(xié)商對e個聚類中心點進行驗證，有效地驗證服務(wù)器返回的結(jié)果是否達到局部最優(yōu)，以此判斷服務(wù)器是否誠實地執(zhí)行協(xié)議。

4 基于外包的多方k-means隱私保護方案

本文提出了一個可驗證的隱私保護k-means 聚類算法方案，整體框架如圖2 所示。首先，用戶在本地計算初始化聚類中心和乘法三元組，將其與用戶數(shù)據(jù)以份額值的形式發(fā)送到兩個云服務(wù)器；然后，服務(wù)器在隱私數(shù)據(jù)下進行k-means 聚類算法Lloyd迭代，最終得到訓(xùn)練好的聚類中心，并發(fā)送給用戶；最終，用戶使用算法4 對結(jié)果進行驗證。將協(xié)議分為兩個階段：離線階段和在線階段。

圖2 可驗證的隱私保護k-means聚類方案框架Fig.2 Framework of verifiable privacy-preserving k-means clustering scheme

4.1 離線階段

在離線階段需要處理k-means算法訓(xùn)練的數(shù)據(jù)集，以及用于算法訓(xùn)練過程的輔助參數(shù)。假設(shè)存在兩個非合謀的服務(wù)器S0和S1，m個用戶{U1，U2，…，Um}，Ui持有的數(shù)據(jù)為ai(i∈{1，2，…，m)}個。m個用戶總的數(shù)據(jù)為n個，且滿足a1+a2+…+am=n，組成的聯(lián)合數(shù)據(jù)為{Q1，Q2，…，Qn}。為了實現(xiàn)對多個用戶的聯(lián)合數(shù)據(jù)做分類處理，每個參與方通過加法秘密共享技術(shù)將隱私數(shù)據(jù)分發(fā)到兩個服務(wù)器：服務(wù)器S0持有的隱私數(shù)據(jù)為；服務(wù)器S1持有的隱私數(shù)據(jù)為

為了在線階段的運算，在離線階段需要生成一些輔助參數(shù)，產(chǎn)生大量的乘法三元組來協(xié)助在線階段計算安全乘法。

4.2 在線階段

在線階段調(diào)用第3 章的算法完成隱私k-means 聚類算法的訓(xùn)練。具體情況如下：

4.2.1 聚類初始化

初始聚類中心對聚類的結(jié)果有較大的影響，合適的初始化聚類中心在聚類算法中起到關(guān)鍵作用。調(diào)用第3 章的初始化算法2得到初始化聚類中心點并記為：

4.2.2 Lloyd’s迭代

執(zhí)行以下步驟，直到滿足終止條件，停止迭代。

1）安全歐幾里得平方距離。

迭代的第一步為計算每個點到每個聚類中心之間歐幾里得平方距離，調(diào)用第3 章的函數(shù)FEsd。對于i∈{1，2，…，n}，h∈{1，2，…，k}，S0和S1合作計算歐幾里得平方距離份額值為，最終每個數(shù)據(jù)點Qi得到的距離向量為(i={1，2，…，n})。

2）分配點到聚類中心。

迭代第2 步需要將每個點分配到對應(yīng)的聚類中心，在計算完每個點Qi到k個聚類中心值的距離份額值后，需要計算Qi點到k個聚類中心的距離最小值，并將此點分配給該類。定義一個大小為n的數(shù)組D并初始化為0。對于第i（1 ≤i≤n）個數(shù)據(jù)點Qi，S0和S1各自輸入k個距離份額值，并調(diào)用最小值算法3 計算得到的結(jié)果g，使得D[i]=g，表示把第i個數(shù)據(jù)點分配到第g個聚類中心點。將數(shù)據(jù)集Q={Q1，Q2，…，Qn}每個點構(gòu)成的距離向量Vi（1 ≤i≤n）按上述方法進行分類，最終數(shù)組D存放每點的分類情況，以此達到分配點到各個聚類中心的目的。

3）更新聚類中心。

迭代第3 步更新聚類中心，從上述步驟中，得到一個數(shù)組D[n]，根據(jù)D[n]的值，S0和S1分別求出新的聚類中心。Si設(shè)置兩個數(shù)組Hi［k］和Li［k］，將數(shù)組初始化為0，Hi［k］保存每個聚類的所有數(shù)據(jù)份額值的和，Li［k］保存每個聚類的數(shù)據(jù)個數(shù)，i=｛0，1｝。對于j∈{1，2，…，n}，Si計算Hi[D[j]]=和Li[D[j]]=Li[D[j]]+1。對 于h∈{1，2，…，k}，Si計 算最終

4）檢查終止條件。

S0和S1分別輸入新的聚類中心的秘密份額值和以前的聚類中心點的秘密份額值，并調(diào)用歐幾里得平方距離算法，計算得到為新舊聚類中心的相似度。定義φ為一個不可忽略值，將其作為算法的終止條件：若τ＜φ，停止算法的執(zhí)行，將新的聚類中心份額值發(fā)送給各個參與方；若τ＞φ，繼續(xù)迭代。

4.2.3 驗證算法

每個用戶Ui(i∈{1，2，…，m})接收到服務(wù)器返回的聚類結(jié)果份額值后，調(diào)用重構(gòu)算法得到聚類結(jié)果{ζ1，ζ2，…，ζk}；再調(diào)用第3 章的驗證算法對服務(wù)器返回的結(jié)果進行驗證，每個用戶執(zhí)行驗證算法得到的聚類中心和服務(wù)器返回的聚類中心之間的歐幾里得距離為，說明服務(wù)器誠實的執(zhí)行協(xié)議，否則服務(wù)器存在欺騙或遭受黑客病毒攻擊。

5 安全分析

本文提出的多方外包的k-means 聚類隱私保護協(xié)議在滿足以下定理時，達到在半誠實模型下是安全的。

定理如果初始化算法、安全歐幾里得算法FEsd、安全最小值算法、終止條件算法和驗證算法在半誠實模型下是安全的，則k-means聚類隱私保護協(xié)議在半誠實模型下是安全的。

為了證明上述定理，首先給出初始化算法、安全歐幾里得算法FEsd、安全最小值算法、終止條件算法和驗證算法的安全證明，然后根據(jù)組合定理［29］說明整個k-means協(xié)議為安全的。

假設(shè)有m個參與方C={U1，U2，…，Um}，和兩個服務(wù)器S0和S1且服務(wù)器不能合謀。

證明 假設(shè)存在一個半誠實敵手A，腐敗用戶的任何子集和最多腐敗一個服務(wù)器，敵手只能學(xué)習(xí)到已腐敗用戶的數(shù)據(jù)和輸出，而學(xué)習(xí)不到誠實用戶的數(shù)據(jù)。協(xié)議考慮存在一個敵手A腐敗了S0以及除了用戶Ui之外的所有用戶I，I為用戶集合C的子集，i∈{1，2，…，m}。腐敗S1的情況和S0類似，證明中不再詳細闡述。有一個模擬器S黑盒調(diào)用敵手A。

1）初始化算法的安全證明。構(gòu)建一個模擬器S，模擬器調(diào)用敵手A腐敗服務(wù)器S0和用戶集合I，并模擬其在協(xié)議執(zhí)行過程中的操作。在對用戶隱私數(shù)據(jù)處理時，模擬器S模擬誠實用戶Ui發(fā)送隨機份額值給敵手A。在初始化聚類中心時，敵手A產(chǎn)生k個隨機份額值發(fā)送模擬器S。S模擬誠實參與方S1運行初始化算法得到初始化聚類中心為根據(jù)秘密共享產(chǎn)生份額值的隨機性，模擬器S對得到的初始化聚類中心份額值具有不可區(qū)分性。

2）安全歐幾里得算法的安全證明。在計算歐幾里得距離時，模擬器S模擬誠實方S1與腐敗方S0交互計算模擬器S模擬誠實方利用三元組計算一些參數(shù)發(fā)送給敵手A，同樣敵手A產(chǎn)生隨機值發(fā)送給模擬器，模擬器S和敵手A得到的份額值。最終得到一組距離向量n}，j∈{1，2，…，k})。根據(jù)秘密共享的安全性和初始化過程產(chǎn)生的值為隨機的，模擬器和敵手A無法得知誠實用戶的隱私信息，所以在理想模型中，模擬器S計算的結(jié)果和現(xiàn)實世界運行同樣的協(xié)議輸出的結(jié)果具有不可區(qū)分性。

3）安全最小值算法的安全證明。在分配數(shù)據(jù)到最近的聚類中心時，模擬器S模擬誠實參與方S1和腐敗參與方S0交互比較數(shù)據(jù)的大小，在調(diào)用SCMP 比較電路時，模擬器S模擬誠實參與方產(chǎn)生混淆電路發(fā)送給敵手A，敵手A計算混淆電路的結(jié)果發(fā)送給模擬器S。交互實現(xiàn)最小值函數(shù)，得到距離向量的最小值索引值并將其賦值給D［i］。根據(jù)混淆電路的安全性，敵手A和模擬器S無法得到誠實參與方的隱私輸入，所以理想和現(xiàn)實模型下執(zhí)行協(xié)議輸出的結(jié)果具有不可區(qū)分性。

4）終止條件算法的安全證明。在檢查是否達到終止條件時，模擬器S模擬誠實參與方和腐敗參與方交互執(zhí)行安全歐幾里得距離，比較τ和φ，若τ＜φ，模擬器S將發(fā)送給敵手A。根據(jù)秘密共享的安全性，模擬器S和敵手A無法得到誠實參與方的輸入信息，所以現(xiàn)實和理想模型中運行此算法具有不可區(qū)分性。

5）驗證算法的安全性。在驗證時，模擬器S模擬誠實用戶Ui計算發(fā)送給敵手A，敵手A產(chǎn)生與相同數(shù)據(jù)格式的隨機數(shù)發(fā)送給模擬器S，模擬器S和敵手A判斷，來說明驗證服務(wù)器是否誠實執(zhí)行協(xié)議。在驗證服務(wù)器返回的結(jié)果是否正確時，用戶提供的是部分點的平均值，沒有泄露數(shù)據(jù)的任何信息。

綜上所述，提出的k-means隱私保護協(xié)議滿足在理想和現(xiàn)實中不可區(qū)分性，在半誠實模型下是安全的。

6 實驗與理論分析

6.1 功能比較

表1 是本文方案與文獻［10，14-15，20-22］中方案的功能比較。文獻［10，14-15］中提出的方案是用戶數(shù)據(jù)之間相互合作訓(xùn)練隱私數(shù)據(jù)。文獻［15］方案適用于任意分區(qū)的數(shù)據(jù)訓(xùn)練模型，文獻［14］方案是針對水平分區(qū)數(shù)據(jù)設(shè)計的方案，這兩個方案都保護了用戶的數(shù)據(jù)以及聚類中心；文獻［10］中提出的垂直分區(qū)數(shù)據(jù)的k-means隱私保護方案沒有保護聚類中心值。以上方案都是在用戶客戶端完成隱私保護訓(xùn)練的。文獻［20-22］中的這三個方案都是將數(shù)據(jù)外包后進行k-means 隱私訓(xùn)練，采用的都是同態(tài)加密方法，文獻［20-21］方案在密文比較上通過添加保序索引實現(xiàn)，文獻［21-22］方案在訓(xùn)練過程中會泄露聚類中心。本文方案采用秘密共享的技術(shù)將數(shù)據(jù)外包，相較其他方案在對隱私數(shù)據(jù)處理的問題上節(jié)省了用戶的計算資源，并在任意分區(qū)數(shù)據(jù)上進行訓(xùn)練，在保護用戶隱私數(shù)據(jù)的前提下能實現(xiàn)對聚類中心的保護。

針對以上外包方案沒有驗證服務(wù)器返回結(jié)果的正確性，提出了一種驗證機制，通過用戶之間協(xié)作計算部分聚類中心值，驗證服務(wù)器是否誠實地執(zhí)行協(xié)議。

從表2 中可以直觀看出，本文k-means 隱私保護方案在多用戶環(huán)境下對任意分區(qū)的數(shù)據(jù)實現(xiàn)了保護用戶數(shù)據(jù)和聚類中心，并驗證結(jié)果的功能。

表2 不同方案的功能比較Tab.2 Function comparison of different schemes

6.2 性能比較

在隱私保護環(huán)境下訓(xùn)練k-means 算法的時間主要分為用戶時間、通信時間和服務(wù)器時間。通過計算本文方案和文獻［20-22］方案的時間復(fù)雜度來研究方案的性能。其中：文獻［20］是2015 年提出的多方外包k-means 算法的隱私保護方案，文獻［21］是2014 年提出單用戶下外包k-means 算法的隱私保護方案，文獻［22］是2020 年提出的兩方外包k-means 算法的隱私保護方案。

根據(jù)不同方案中出現(xiàn)的算法，從加密、計算歐幾里得平方距離、計算最小值、更新聚類中心時的除法操作四個方面的時間復(fù)雜度分析，計算結(jié)果見表3。其中，n表示數(shù)據(jù)點的總數(shù)，d表示數(shù)據(jù)點的維數(shù)，k表示數(shù)據(jù)的分類個數(shù)，α表示距離值的二進制位數(shù)，m表示更新中心聚類點值的二進制位數(shù)。從比較結(jié)果中看出，協(xié)議在加密和歐幾里得平方距離兩個環(huán)節(jié)的計算時間復(fù)雜度保持不變的情況下，在求最小值和更新聚類中心時的除法操作環(huán)節(jié)時間復(fù)雜度明顯降低。

表3 時間復(fù)雜度比較Tab.3 Time complexity comparison

通信復(fù)雜度是指在訓(xùn)練k-means 算法時用戶和云服務(wù)器之間的通信。文獻［21］中提出的方案單用戶和云之間在每輪迭代時需要交互一次；文獻［22］中提出的方案兩方用戶和云之間進行O（n*k）輪交互；文獻［20］中提出的方案用戶和云之間進行O（k*l）輪交互；而本文方案在將數(shù)據(jù)外包之后，用戶不再參與k-means 算法的計算，直到返回滿足條件的聚類中心，用戶和云之間僅進行O（1）輪交互，因此本文方案的通信復(fù)雜度較低。

6.3 結(jié)果分析

本文算法的主要功能是兩個云服務(wù)器安全有效地訓(xùn)練隱私k-means 聚類算法。實驗主要研究算法的運行時間和運行效率以及隱私保護聚類算法的準確率。實驗中計算機配置如下：操作系統(tǒng)為Linux，CPU 為2.3 GHz，內(nèi)存為2.00 GB，結(jié)合Obliv-c庫，利用C++進行開發(fā)。

本文實驗選取2 個不同大小的數(shù)據(jù)集進行實驗。第一個數(shù)據(jù)集S1［30］是研究聚類方案的基準，本文選取500 個二維數(shù)據(jù)，聚類個數(shù)為8；第二個數(shù)據(jù)集為人工合成（Synthetic）二維數(shù)據(jù)，數(shù)據(jù)集大小為100，聚類點個數(shù)為｛2，5｝。表4為數(shù)據(jù)集的簡要描述。

表4 實驗中使用的數(shù)據(jù)集Tab.4 Datasets used in the experiment

首先對Synthetic 數(shù)據(jù)集進行實驗，分別在不同迭代次數(shù)和不同聚類個數(shù)的情況下運行。實驗中將迭代次數(shù)設(shè)置為1、5、10，將聚類個數(shù)設(shè)置為2 或4。在安全k-means 聚類訓(xùn)練時S1和S2的運行時間見表5，其中：n為數(shù)據(jù)點的個數(shù)，k為聚類的個數(shù)，T為迭代次數(shù)。表5 表明，隨著聚類迭代次數(shù)和聚類個數(shù)的增加，S1和S2的運行時間成倍地增加。當(dāng)n=100，k=4時，在迭代次數(shù)為10時運行時間大約2 min。

對兩個數(shù)據(jù)集進行隱私k-means 聚類，誤差值φ=10-5，結(jié)果見表6。Synthetic 數(shù)據(jù)集需要迭代10 次達到收斂，總運行時間大約178 s；S1 數(shù)據(jù)集需要迭代7 次達到收斂，總運行時間大約481 s。

本文對得到的聚類結(jié)果進行準確性分析。準確度是評估聚類數(shù)據(jù)集正確分類的百分比。在本文中，使用本文提出的隱私k-means聚類和明文k-means聚類算法比較來產(chǎn)生模型的準確性。通過實驗，Synthetic 數(shù)據(jù)集準確度達到97%，S1數(shù)據(jù)集準確度達到93%。S1數(shù)據(jù)集的明文k-means 聚類數(shù)據(jù)點和聚類中心分布圖見圖3（a），S1數(shù)據(jù)集的隱私訓(xùn)練k-means聚類的數(shù)據(jù)點和聚類中心分布圖見圖3（b）。通過本次實驗表明，可驗證隱私訓(xùn)練k-means 聚類準確度較高，具有較好的實用性。

表5 隱私保護聚類協(xié)議在Synthetic數(shù)據(jù)集上的運行時間單位：sTab.5 Running time of privacy-preserving clustering protocol on Synthetic dataset unit：s

表6 隱私保護k-means聚類在不同數(shù)據(jù)集的收斂時間和收斂時的迭代次數(shù)對比Tab.6 Comparison of convergence time and iterations when convergence by privacy-preserving k-means clustering on different datasets

圖3 S1數(shù)據(jù)集的明文和隱私的k-means聚類Fig.3 Plaintext and privacy k-means clustering of S1 dataset

7 結(jié)語

針對現(xiàn)有方案未對云服務(wù)器返回的聚類結(jié)果進行驗證的問題，本文提出了一種基于外包環(huán)境的多用戶隱私保護的可驗證k-means聚類協(xié)議。因為大部分計算在云上進行，任何計算能力較弱的參與方都可以運行協(xié)議實現(xiàn)保護隱私的k-means聚類。首先設(shè)計改進的初始化算法，有效提高算法迭代效率；同時利用乘法三元組實現(xiàn)安全乘法，并提出安全的求最小值結(jié)構(gòu)，以及在更新聚類中心時，直接本地計算，不需要復(fù)雜的密文除法操作；并且，本文還提出了一種驗證算法，當(dāng)云服務(wù)器不經(jīng)計算返回錯誤結(jié)果時，該算法使用戶能驗證部分聚類中心的正確性。在整個訓(xùn)練過程中，算法沒有泄露用戶的隱私信息。本文未考慮輸出隱私的問題，但是其對k-means隱私保護同樣重要，將作為下一步研究方向。