姚禹丞，宋 玲，鄂 馳

(廣西大學 計算機與電子信息學院，廣西 南寧 530004)

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

姚禹丞，宋 玲，鄂 馳

(廣西大學 計算機與電子信息學院，廣西 南寧 530004)

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

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

0 引 言

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

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

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

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

1 相關工作

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

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

2 問題描述

2.1 合謀攻擊

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

圖1 中心站點SP與P1合謀的情況

2.2 竊聽隱私

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

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

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

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

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

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

(1)算法主要步驟。

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

(1)

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

(2)

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

3.2 PPDK算法

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

輸出:k個最終聚簇。

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

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

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

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

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

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

圖3 PPDK算法流程圖

4 算法理論分析及實驗

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

4.1 安全性分析

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

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

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

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

4.2 聚類精度分析

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

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

(3)

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

4.3 時間復雜度分析

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

4.4 實驗與結果分析

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

對UCI機器學習數(shù)據(jù)集中的3個數(shù)據(jù)集進行了對比實驗，如表1所示。

表1 UCI機器學習數(shù)據(jù)集

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

圖4 算法聚類精度對比

從圖4可見，PPDK算法的聚類精度與DK-MEANS算法保持一致。圖5顯示PPDK執(zhí)行時間略高于DK-MEANS，這是因為加密解密過程額外增加了算法的執(zhí)行時間，但為線性增長。

5 結束語

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

圖5 算法運行時間對比

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

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

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

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

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

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

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

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

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

[9] 方煒煒,楊炳儒,夏紅科.基于SMC的隱私保護聚類模型[J].系統(tǒng)工程與電子技術,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)境中支持隱私保護的可計算加密方法[J].計算機學報,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

時間：2017-01-10

廣西自然科學基金項目(2013GXNSFAA253003)

姚禹丞(1988-)，男，碩士研究生，研究方向為數(shù)據(jù)挖掘；宋 玲，教授，研究方向為網(wǎng)絡信息安全。

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