姚禹丞，宋 玲，鄂 馳

(廣西大學(xué) 計(jì)算機(jī)與電子信息學(xué)院，廣西 南寧 530004)

同態(tài)加密的分布式K均值聚類算法研究

姚禹丞，宋 玲，鄂 馳

(廣西大學(xué) 計(jì)算機(jī)與電子信息學(xué)院，廣西 南寧 530004)

針對分布式環(huán)境下多方聯(lián)合執(zhí)行K均值聚類挖掘任務(wù)過程中存在的安全性問題，如潛在的合謀攻擊和竊聽攻擊導(dǎo)致隱私泄露和敏感知識被發(fā)現(xiàn)，提出了一種隱私保護(hù)算法(PPDK)。在數(shù)據(jù)對象水平分布的情況下，該算法利用同態(tài)加密的思想，設(shè)計(jì)了一種新的加密機(jī)制。通過改進(jìn)加密密鑰的生成方式，使得參與計(jì)算的各方持有不同的密鑰，對于產(chǎn)生的密文，其他參與方無法解密，并且在計(jì)算過程中所有的加密解密操作均由各參與方獨(dú)立完成，因此可以限制半誠實(shí)的參與方試圖竊聽其他參與方的私有信息，以及與中心站點(diǎn)合謀揭露隱私的可能性。通過理論分析和實(shí)驗(yàn)結(jié)果表明，在有效的時(shí)間內(nèi)，PPDK算法可以在確保分布式K均值聚類挖掘任務(wù)得到正確結(jié)果的前提下，很好地保護(hù)數(shù)據(jù)的隱私性。

分布式；K均值聚類；同態(tài)加密；隱私保護(hù)

0 引 言

隨著計(jì)算機(jī)網(wǎng)絡(luò)和數(shù)據(jù)庫技術(shù)的發(fā)展，許多組織和機(jī)構(gòu)收集和存儲了大量數(shù)據(jù)，這些數(shù)據(jù)背后蘊(yùn)含著很多重要的信息而且大部分都按地理位置分布于多個(gè)場所。為了更好地利用這些數(shù)據(jù)，人們希望對其進(jìn)行更深層次的分析。利用數(shù)據(jù)挖掘[1-4]技術(shù)可從這些數(shù)據(jù)中提取有價(jià)值的知識，但在分布式場景下，數(shù)據(jù)挖掘任務(wù)需要通過多方之間的合作來完成。

傳統(tǒng)的集中式數(shù)據(jù)挖掘無法勝任，首先將所有存儲在各個(gè)地方的數(shù)據(jù)放到一個(gè)中心進(jìn)行挖掘是不可能的，其次在雙方或多方合作進(jìn)行數(shù)據(jù)挖掘時(shí)，出于數(shù)據(jù)庫可能含有敏感的隱私或者商業(yè)價(jià)值的顧慮，參與者往往不愿意將數(shù)據(jù)與他人共享而只愿共享數(shù)據(jù)挖掘的結(jié)果，這種情況在科學(xué)研究、醫(yī)學(xué)研究及經(jīng)濟(jì)和市場動(dòng)態(tài)研究等方面屢見不鮮。這就要求提出在分布式環(huán)境下能保持隱私性的數(shù)據(jù)挖掘算法。對于參與者而言，只能獲得最終的挖掘結(jié)果，除此以外，不能獲得其他人的任何信息。

為了解決多方合作進(jìn)行聚類挖掘時(shí)帶來的隱私泄露和敏感知識被發(fā)現(xiàn)的問題,提出了越來越多的分布式算法。在分布式環(huán)境下，參與者根據(jù)其行為可分為準(zhǔn)誠信攻擊者和惡意攻擊者。準(zhǔn)誠信攻擊者是遵守相關(guān)計(jì)算協(xié)議但仍試圖進(jìn)行攻擊的站點(diǎn)；惡意攻擊者是不遵守協(xié)議且試圖披露隱私的站點(diǎn)。而分布式的數(shù)據(jù)集有兩種劃分方法：基于水平的劃分和基于垂直的劃分?；谒降膭澐质敲總€(gè)站點(diǎn)都存儲著全部數(shù)據(jù)對象的一個(gè)子集，且這些子集之間沒有交集?；诖怪钡膭澐謩t使得每個(gè)站點(diǎn)都存儲著所有數(shù)據(jù)對象全部屬性的一個(gè)子集，且子集之間沒有交集。

K均值是經(jīng)典的基于距離劃分的聚類算法，其具有簡單高效的特點(diǎn)，在很多領(lǐng)域都得到了廣泛應(yīng)用。文中假設(shè)所有站點(diǎn)為準(zhǔn)誠信攻擊者，并在水平劃分的數(shù)據(jù)集上進(jìn)行隱私保護(hù)的K均值聚類算法的研究。為了解決目前分布式K均值聚類算法中還存在的隱私泄露的問題，設(shè)計(jì)了一種可以獨(dú)自生成私有密鑰的同態(tài)加密算法，同時(shí)采用主從兩級節(jié)點(diǎn)的分布式計(jì)算模型來保證數(shù)據(jù)挖掘任務(wù)準(zhǔn)確高效的執(zhí)行。

1 相關(guān)工作

眾多分布式環(huán)境下基于隱私保護(hù)的數(shù)據(jù)挖掘應(yīng)用都可以抽象為安全多方計(jì)算(SecureMulti-partyComputation，SMC)的模型，SMC是近年來在信息安全與分布式計(jì)算領(lǐng)域迅速崛起的一個(gè)活躍的研究方向。它能夠保證參與計(jì)算的多方在各自的輸入信息不泄露的前提下獲得合作計(jì)算的結(jié)果，這正好符合分布式數(shù)據(jù)挖掘中隱私保護(hù)的要求。文獻(xiàn)[5]利用把私有數(shù)據(jù)劃分成n份并分發(fā)給其他參與方的思想，設(shè)計(jì)了安全多方求和協(xié)議和安全多方求平均值協(xié)議，使用該協(xié)議可以保證在水平分布或垂直模型中當(dāng)其余所有參與方合謀時(shí)，剩下一方的私有數(shù)據(jù)才受到威脅。文獻(xiàn)[6]引入一個(gè)半可信第三方，將本地?cái)?shù)據(jù)和擾亂后發(fā)送給半可信第三方可以實(shí)現(xiàn)安全求和與安全求平均值，該算法在保證隱私的前提下減少了各參與方之間的通信量。

基于數(shù)據(jù)加密的隱私保護(hù)技術(shù)可以實(shí)現(xiàn)通訊的安全性以及對私有數(shù)據(jù)的保護(hù)，因此其多用于分布式應(yīng)用中。在隱私保護(hù)數(shù)據(jù)挖掘算法中，SMC可以看成是基于加密技術(shù)的一個(gè)特例。2009年，GraigGentry提出基于理想格的完全同態(tài)加密技術(shù)(FullyHomomorphicEncryption,FHE)。如果一種加密算法對加法和乘法都能找到其對應(yīng)的同態(tài)操作，即滿足e(m1)⊕e(m2)=e(m1⊕m2)，則稱其為全同態(tài)加密算法。目前，基于同態(tài)加密的分布式隱私保護(hù)數(shù)據(jù)挖掘已經(jīng)取得了豐富的研究成果。文獻(xiàn)[7]基于同態(tài)加密和安全置換的算法，實(shí)現(xiàn)了在垂直劃分下隱私保護(hù)的K-means聚類。文獻(xiàn)[8]提出了一種完全同態(tài)加密的分布式聚類挖掘算法。文獻(xiàn)[9]基于全同態(tài)公鑰加密協(xié)議和數(shù)據(jù)擾亂方法，設(shè)計(jì)了一個(gè)安全比較協(xié)議。文獻(xiàn)[10-11]分別使用了Paillier公鑰加密機(jī)制[12]和ElGamal加密機(jī)制[13]，同樣具有同態(tài)的性質(zhì)。文獻(xiàn)[14]設(shè)計(jì)了一個(gè)加密方案用以提供云計(jì)算環(huán)境中的隱私保護(hù)。文獻(xiàn)[15]基于橢圓曲線的同態(tài)加密消除了SMC中的可信第三方。

2 問題描述

2.1 合謀攻擊

在多個(gè)參與方合作進(jìn)行分布式聚類挖掘任務(wù)時(shí)，存在信息泄露的問題。利用同態(tài)加密技術(shù)可以保證參與計(jì)算的多方在各自輸入信息不泄露的前提下獲得合作計(jì)算的結(jié)果。但是在對以往分布式隱私保護(hù)聚類算法的研究中發(fā)現(xiàn)，若使算法中的中心站點(diǎn)(SP)，即半可信的第三方，對中間計(jì)算結(jié)果進(jìn)行解密，這將對數(shù)據(jù)隱私構(gòu)成威脅。因?yàn)樵诂F(xiàn)實(shí)中很難找到可信的第三方，無法保證合謀的情況下私有數(shù)據(jù)不被泄露，如圖1所示。

圖1 中心站點(diǎn)SP與P1合謀的情況

2.2 竊聽隱私

此外，以往算法還不具備防竊聽的能力。參與分布式聚類計(jì)算的各方利用同態(tài)加密算法對私有數(shù)據(jù)進(jìn)行加密，各參與方可使用相同的密鑰P解密。由于相互之間不通信，可以保證各自的隱私。但若某參與方(如P1)竊聽了他方的發(fā)送數(shù)據(jù)，便可使用共有密鑰P對他方的數(shù)據(jù)進(jìn)行解密，從而暴露了隱私，如圖2所示。

圖2 P1竊聽其他參與方的情況

3 基于改進(jìn)同態(tài)加密的隱私保護(hù)分布式K均值算法

針對以上問題，基于同態(tài)加密算法設(shè)計(jì)了一種新算法(PPDK)，可以在參與方數(shù)n≥3的情況下保證隱私的安全。其基本思想是:利用改進(jìn)的同態(tài)加密算法，對分布式K均值算法中出現(xiàn)的敏感數(shù)據(jù)進(jìn)行加密，使得中心站點(diǎn)只負(fù)責(zé)計(jì)算密文的和，所有的加密解密過程全由局部站點(diǎn)執(zhí)行。改進(jìn)后加密算法中的密鑰(P,ri)有兩個(gè)參數(shù)，其中P為一個(gè)大數(shù)，ri?P(i=1,2,…,n;n≥3)為各參與方生成的隨機(jī)數(shù)，且值不相同，改進(jìn)后的算法仍滿足同態(tài)加密的性質(zhì)。由于各參與方的加密密鑰不同，使得在聯(lián)合計(jì)算中即使出現(xiàn)合謀或者竊聽的情況也能保證密文不被解密。

3.1 改進(jìn)的同態(tài)加密算法

基于同態(tài)加密思想，提出了一種新的加密算法，該算法滿足e(m1)+e(m2)=e(m1+m2)。

(1)算法主要步驟。

③Pi選擇一個(gè)大數(shù)P作為密鑰的一個(gè)參數(shù)，再各自選擇一個(gè)隨機(jī)數(shù)qi，最后對擾亂后的數(shù)據(jù)加密。

(1)

D(E(di))=(E(di)modP)-nR

(2)

(2)算法的同態(tài)性質(zhì)的證明。

3.2 PPDK算法

輸入:各站點(diǎn)Pi的數(shù)據(jù)集為Di(i=1,2,…,n;n≥3)，每個(gè)Di對象個(gè)數(shù)為mi(i=1,2,…,n;n≥3)，聚簇個(gè)數(shù)為k。

輸出:k個(gè)最終聚簇。

(1)PPDK算法-中心站點(diǎn)。

①中心站點(diǎn)SP隨機(jī)產(chǎn)生k個(gè)初始聚簇中心cj(j=1,2,…,k)以及隨機(jī)數(shù)R，并發(fā)送到從站點(diǎn)Pi。

③直到每個(gè)聚類不再發(fā)生變化。

(2)PPDK算法-局部站點(diǎn)。

①各局部站點(diǎn)Pi(i=1,2,…,n;n≥3)根據(jù)中心站點(diǎn)發(fā)來的初始聚簇中心cj(j=1,2,…,k)，計(jì)算其與本站點(diǎn)數(shù)據(jù)集Di包含的mi(i=1,2,…,n;n≥3)個(gè)對象的歐氏距離，確定每個(gè)對象所屬的類。

④直到每個(gè)聚類不再發(fā)生變化。

圖3 PPDK算法流程圖

4 算法理論分析及實(shí)驗(yàn)

文中對同態(tài)加密的密鑰引入了一組隨機(jī)數(shù)的和作為密鑰的另一個(gè)參數(shù)，對于涉及到數(shù)據(jù)隱私的以下幾方面，該算法都具有保護(hù)性：(1)聯(lián)合計(jì)算過程中各站點(diǎn)數(shù)據(jù)的安全性；(2)通信過程的安全以及防竊聽性；(3)合謀情況下數(shù)據(jù)隱私的安全性。加密解密過程會增加算法的時(shí)間復(fù)雜度，但由于算法本身時(shí)間復(fù)雜度不高，其增加在可以容忍的范圍之內(nèi)。

4.1 安全性分析

(1)聯(lián)合計(jì)算過程中各站點(diǎn)數(shù)據(jù)的安全性。

由于各站點(diǎn)輸入的是加密后數(shù)據(jù)，保證了在聯(lián)合計(jì)算時(shí)各站點(diǎn)的私有信息不被泄露，并且整個(gè)計(jì)算過程的加密解密操作全由各站點(diǎn)獨(dú)立完成，所以可以保證在聯(lián)合計(jì)算過程中各站點(diǎn)數(shù)據(jù)的安全性。

(2)通信過程的安全以及防竊聽性。

(3)合謀情況下數(shù)據(jù)隱私的安全性。

4.2 聚類精度分析

PPDK算法是對局部聚類中心進(jìn)行加密，但保留了分布式K均值聚類的迭代過程。分布式K均值聚類算法結(jié)果的差異性在于初始聚類中心的選取方式和距離的計(jì)算方式，PPDK算法沒有修改兩者，且迭代過程依然是從第一次迭代到最終次迭代不斷修正聚類中心，所以算法的正確性得到保證。

文中通過計(jì)算所有對象與其所屬聚簇的聚類中心的歐氏距離和來評價(jià)聚類的精度。

(3)

其中，k為聚類的簇?cái)?shù)；mj為第j個(gè)聚簇內(nèi)的對象數(shù)；dji為第j個(gè)聚簇內(nèi)第i個(gè)對象；cj為第j個(gè)聚簇的聚類中心。Precision的值越小說明聚類結(jié)果越好。

4.3 時(shí)間復(fù)雜度分析

從圖3可知，PPDK的時(shí)間復(fù)雜度為O(ktm+ktn)。其中，k為聚簇?cái)?shù)，t為循環(huán)次數(shù)，m為數(shù)據(jù)集的數(shù)據(jù)對象總數(shù)，n為參與方的個(gè)數(shù)。由于加密解密過程的存在增加了算法的時(shí)間復(fù)雜度，每次循環(huán)其時(shí)間復(fù)雜度為O(kn)，但同態(tài)加密算法本身的復(fù)雜度為常數(shù)級，因此相比于無隱私保護(hù)的分布式K均值挖掘過程，PPDK計(jì)算時(shí)間的增加在可容忍的范圍之內(nèi)。

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

文中算法用Java語言實(shí)現(xiàn)，在一臺計(jì)算機(jī)上模擬3個(gè)局部站點(diǎn)，使用RMI(Remote Method Invocation,遠(yuǎn)程方法調(diào)用)實(shí)現(xiàn)站點(diǎn)間的通信。實(shí)驗(yàn)運(yùn)行環(huán)境為：Intel(R) Core(TM) i5-4 200 M CPU @ 2.50 GHz 2.50 GHz 4.0 GB/Windows7。

對UCI機(jī)器學(xué)習(xí)數(shù)據(jù)集中的3個(gè)數(shù)據(jù)集進(jìn)行了對比實(shí)驗(yàn)，如表1所示。

表1 UCI機(jī)器學(xué)習(xí)數(shù)據(jù)集

需要說明的是，隨機(jī)選取的初始聚類中心會使算法的執(zhí)行時(shí)間具有不確定性。這里閾值ε=0.01，實(shí)驗(yàn)結(jié)果取10次運(yùn)行的平均值，見圖4和圖5。

圖4 算法聚類精度對比

從圖4可見，PPDK算法的聚類精度與DK-MEANS算法保持一致。圖5顯示PPDK執(zhí)行時(shí)間略高于DK-MEANS，這是因?yàn)榧用芙饷苓^程額外增加了算法的執(zhí)行時(shí)間，但為線性增長。

5 結(jié)束語

文中針對分布式環(huán)境提出了一種保護(hù)隱私的聚類挖掘算法—PPDK。該算法基于同態(tài)加密算法，使得各

圖5 算法運(yùn)行時(shí)間對比

參與方擁有不同的密鑰，從而避免合謀攻擊和竊聽攻擊。理論分析和實(shí)驗(yàn)結(jié)果表明，PPDK能在保持挖掘結(jié)果精確度的同時(shí)防止各參與方隱私數(shù)據(jù)的泄露，且時(shí)間增加在可容忍的范圍內(nèi)。

[1]HanJW，MichelineK.數(shù)據(jù)挖掘概念與技術(shù)[M].范 明，孟曉峰，譯.北京：機(jī)械工業(yè)出版社，2012.

[2] 周水庚，李 豐，陶宇飛，等.面向數(shù)據(jù)庫應(yīng)用的隱私保護(hù)研究綜述[J].計(jì)算機(jī)學(xué)報(bào)，2009，32(5):847-861.

[3]PrakashM,SingaravelG.Areviewonapproaches,techniquesandresearchchallengesinprivacypreservingdatamining[J].AustralianJournalofBasic&AppliedSciences,2014,8(10):251-259.

[4] 鄭苗苗,吉根林.DK-Means—分布式聚類算法K-Dmeans的改進(jìn)[J].計(jì)算機(jī)研究與發(fā)展,2007,44(s2):84-88.

[5] 楊丹鳳,余青松,鄭冀之.分布式數(shù)據(jù)隱私保護(hù)K-均值聚類算法[J].計(jì)算機(jī)與數(shù)字工程,2008,36(7):113-116.

[6] 張國榮,印 鑒.分布式環(huán)境下保持隱私的聚類挖掘算法[J].計(jì)算機(jī)工程與應(yīng)用,2007,43(18):165-167.

[7]VaidyaJ,CliftonC.Privacy-preservingk-meansclusteringoververticallypartitioneddata[C]//NinthACMSIGKDDinternationalconferenceonknowledgediscovery&datamining.[s.l.]:ACM,2003:206-215.

[8] 劉英華,楊炳儒,曹丹陽,等.分布式聚類算法的隱私保護(hù)研究[J].計(jì)算機(jī)科學(xué),2012,39(3):160-162.

[9] 方煒煒,楊炳儒,夏紅科.基于SMC的隱私保護(hù)聚類模型[J].系統(tǒng)工程與電子技術(shù),2012,34(7):1505-1510.

[10]ErkinZ,VeugenT,ToftT,etal.Privacy-preservingdistributedclustering[J].EURASIPJournalonInformationSecurity,2013,2013(1):1-15.

[11]YiX,ZhangY.Equallycontributoryprivacy-preservingk-meansclusteringoververticallypartitioneddata[J].InformationSystems,2013,38(1):97-107.

[12]PaillierP.Public-keycryptosystemsbasedoncompositedegreeresiduosityclasses[C]//Internationalconferenceontheoryandapplicationofcryptographictechniques.[s.l.]:Springer-Verlag,1999:223-238.

[13]ElgamalT.Apublickeycryptosystemandasignatureschemebasedondiscretelogarithms[J].IEEETransactionsonInformationTheory,1985,31(4):469-472.

[14] 黃汝維,桂小林,余 思,等.云環(huán)境中支持隱私保護(hù)的可計(jì)算加密方法[J].計(jì)算機(jī)學(xué)報(bào),2011,34(12):2391-2402.

[15]PatelSJ,ChouhanA,JinwalaDC.Comparativeevaluationofellipticcurvecryptographybasedhomomorphicencryptionschemesforanovelsecuremultipartycomputation[J].JournalofInformationSecurity,2014,5(1):12-18.

Investigation on DistributedK-means Clustering Algorithm of Homomorphic Encryption

YAO Yu-cheng,SONG Ling,E Chi

(College of Computer and Electronic Information,Guangxi University, Nanning 530004,China)

Aiming at security problems in the process of multi parties performingK-meanclusteringminingtaskunderdistributedenvironment,suchaspotentialcollusionattacksandeavesdroppingattacksleadingtoprivacydisclosureandsensitiveknowledgetobefound,aprivacyprotectionalgorithm,PPDK,isproposed.Inthecaseofthehorizontaldistributionofthedataobjects,thisalgorithmhasdesignedanewencryptionmechanismbasedontheideaofthehomomorphicencryption.Byimprovingthegenerationoftheencryptionkey,itmakeseachpartiesholddifferentkeys.Onepartycan’tdecrypttheciphergeneratedbyotherparties.Andintheprocessofcalculating,allencryptionanddecryptionoperationsareexecutedbytheparticipantsindependently.Therefore,itcanlimitthepossibilityofsemihonestpartiestryingtoeavesdroptheotherparties’privateinformationandconspirewithcentersite.Theoreticalanalysisandexperimentalresultsshowthatwithintheeffectivetime,PPDKalgorithmcanensurethatthedistributedK-meansclusteringminingtasksgetacorrectresults,andtheprivacyofthedatahasaverygoodprotection.

distributed;K-means;homomorphicencryption;privacyprotection

2016-04-01

2016-07-06

時(shí)間：2017-01-10

廣西自然科學(xué)基金項(xiàng)目(2013GXNSFAA253003)

姚禹丞(1988-)，男，碩士研究生，研究方向?yàn)閿?shù)據(jù)挖掘；宋 玲，教授，研究方向?yàn)榫W(wǎng)絡(luò)信息安全。

http://www.cnki.net/kcms/detail/61.1450.TP.20170110.1019.052.html

TP

A

1673-629X(2017)02-0081-05

10.3969/j.issn.1673-629X.2017.02.019