同態加密的分布式K均值聚類算法研究

姚禹丞，宋 玲，鄂 馳

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

同態加密的分布式K均值聚類算法研究

姚禹丞，宋 玲，鄂 馳

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

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

分布式；K均值聚類；同態加密；隱私保護

0 引 言

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

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

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

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

1 相關工作

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

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

2 問題描述

2.1 合謀攻擊

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

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

2.2 竊聽隱私

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

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

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

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

3.1 改進的同態加密算法

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

(1)算法主要步驟。

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

(1)

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

(2)

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

3.2 PPDK算法

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

輸出:k個最終聚簇。

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

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

③直到每個聚類不再發生變化。

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

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

④直到每個聚類不再發生變化。

圖3 PPDK算法流程圖

4 算法理論分析及實驗

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

4.1 安全性分析

(1)聯合計算過程中各站點數據的安全性。

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

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

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

4.2 聚類精度分析

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

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

(3)

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

4.3 時間復雜度分析

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

4.4 實驗與結果分析

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

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

表1 UCI機器學習數據集

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

圖4 算法聚類精度對比

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

5 結束語

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

圖5 算法運行時間對比

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

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

[2] 周水庚，李 豐，陶宇飛，等.面向數據庫應用的隱私保護研究綜述[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].計算機研究與發展,2007,44(s2):84-88.

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

[6] 張國榮,印 鑒.分布式環境下保持隱私的聚類挖掘算法[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].系統工程與電子技術,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] 黃汝維,桂小林,余 思,等.云環境中支持隱私保護的可計算加密方法[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-)，男，碩士研究生，研究方向為數據挖掘；宋 玲，教授，研究方向為網絡信息安全。

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