張 恩，李會(huì)敏，常 鍵

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

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

0 引言

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

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

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

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

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

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

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

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

1 相關(guān)工作

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

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

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

2 基礎(chǔ)知識

2.1 k-means聚類

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

算法1k-means聚類算法。

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

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

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

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

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

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

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

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

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

2.3 混淆電路

混淆電路是目前最常見的用于兩方安全計(jì)算的通用技術(shù)。Yao［2］首次提出混淆電路，后來Ballaer等［25］給出了標(biāo)準(zhǔn)化定義?；煜娐芳夹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，輸出一個(gè)混淆輸入值X。

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

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

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

2.4 半誠實(shí)模型

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

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

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

3 構(gòu)建模塊

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

表1 符號定義Tab.1 Notations definition

3.1 聚類中心初始化

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

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

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

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

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

3.2 安全的計(jì)算歐幾里得距離

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

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

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

3.3 安全計(jì)算最小值算法

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

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

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

3.4 驗(yàn)證算法

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

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

算法4 驗(yàn)證算法。

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

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

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

圖2 可驗(yàn)證的隱私保護(hù)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è)存在兩個(gè)非合謀的服務(wù)器S0和S1，m個(gè)用戶{U1，U2，…，Um}，Ui持有的數(shù)據(jù)為ai(i∈{1，2，…，m)}個(gè)。m個(gè)用戶總的數(shù)據(jù)為n個(gè)，且滿足a1+a2+…+am=n，組成的聯(lián)合數(shù)據(jù)為{Q1，Q2，…，Qn}。為了實(shí)現(xiàn)對多個(gè)用戶的聯(lián)合數(shù)據(jù)做分類處理，每個(gè)參與方通過加法秘密共享技術(shù)將隱私數(shù)據(jù)分發(fā)到兩個(gè)服務(wù)器：服務(wù)器S0持有的隱私數(shù)據(jù)為；服務(wù)器S1持有的隱私數(shù)據(jù)為

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

4.2 在線階段

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

4.2.1 聚類初始化

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

4.2.2 Lloyd’s迭代

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

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

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

2）分配點(diǎn)到聚類中心。

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

3）更新聚類中心。

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

4）檢查終止條件。

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

4.2.3 驗(yàn)證算法

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

5 安全分析

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

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

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

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

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

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

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

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

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

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

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

6 實(shí)驗(yàn)與理論分析

6.1 功能比較

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

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

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

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

6.2 性能比較

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

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

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

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

6.3 結(jié)果分析

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

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

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

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

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

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

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

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