分布式隱私保護FHE-DBIRCH模型研究

劉英華

(中國青年政治學院，北京 100089)

1 引言

自1995年提出隱私保護數據挖掘以來，隱私保護數據挖掘就成為了數據挖掘領域的研究熱點和難點。隱私保護技術主要有數據擾動技術、匿名化技術和安全多方計算技術[1]。數據擾動技術隱藏了真實數據，挖掘者只能在被擾動的數據上挖掘知識(如添加了噪聲、數據交換等)；匿名化技術則是泛化和抑制操作微調了原始數據對象屬性值，數據擾動技術、匿名化技術都改變了原始數據，即在被修改了的數據上完成挖掘任務。

聚類分析是數據挖掘研究的一個重要部分，是實現數據深層使用價值的一個重要步驟，也是其他挖掘任務的基礎，聚類分析在數據挖掘領域得到了廣泛的研究和應用[2]。可以將聚類分析作為單獨的工具使用，分析、發現數據庫中存在的知識和信息，并且對聚類分析的每一類總結其特點。針對聚類分析的某個類，還可以聚類二次分析出更深層次的知識和信息，并以此類推，進行聚類的n次分析，所以也可以認為聚類分析是其他數據挖掘模型中的一個預先處理過程[3]。

聚類分析是根據數據對象的相似度劃分為若干個群組(簇)，而隱私保護中的數據擾動技術、匿名化技術微調了原始數據對象屬性值，這種操作將導致相似度計算值的誤差，從而引起數據分布、密度特征的改變，進而影響群組的劃分結果[4]。只有隱私保護中的安全多方計算技術，沒有改變原始數據集，而是加密后傳輸，確保參與方信息的獨立性和計算的正確性，同時又可以保護各參與方的信息不泄露給其他參與方或第三方。在基于安全多方計算技術隱私保護的數據集上完成聚類分析才能保證劃分的群組與在原始數據上聚類分析劃分的群組是完全一致的[5]。

本文提出的FHE-DBIRCH(Fully Homomorphism Encryption-Distribute Balanced Herative Reducing and Clustering using Hierarchies)模型是針對水平分布式數據存放模式，將各從數據集通過完全同態加密算法加密后發送到主數據集，并對主數據集的數據計算后解密，所有的計算對象均為加密后的數據。所以，半可信第三方數據挖掘者的聚類挖掘對象也是加密數據，無法重構原始數據，避免了原始數據的隱私泄露。理論證明了FHE-DBIRCH模型在聚類挖掘時對隱私的保護是可行的，并通過實驗進行了驗證。

2 問題描述

3 FHE-DBIRCH模型

為實現水平分布式數據集的隱私保護聚類挖掘，首先要實現各終端Ti到主數據集的隱私保護，首選的方法是加密技術[6～8]。

3.1 完全同態加密技術

完全同態加密FHE(Fully Homomorphism Encryption)技術是2009年由IBM研究員Gentry C首次提出的[9]。

定義1加密算法α，解密算法β，明文mi，運算符⊕和?。若存在公式α(β(m1)⊕β(m2)⊕…⊕β(mi))=α(β(m1+m2+…+mi))，即單個從數據集加密后進行的某種“加”計算后解密得到的結果，與單個從數據集“加”計算后加密后再解密得到的結果是相同的，則加密算法α和解密算法β基于運算符⊕滿足同態加密。若存在公式α(β(m1)?β(m2)?…?β(mi))=α(β(m1×m2×…×mi))，則加密算法α和解密算法β基于運算符?滿足同態加密。若兩個公式均存在，則加密算法α和解密算法β基于運算符⊕和?滿足完全同態加密。

算法1加密數據為m，密鑰是大數p(一個大數)，大數k(隨機生成，且k符合條件m<

加密算法：E(m)=qp+kr+m;

解密算法：D(E(m))=(E(m) modp)modk。

則算法1是一個符合完全同態加密的算法。

證明假設E(mi)=qip+kri+mi,則有：

E(m1)+E(m2)+…+E(mi)= (q1+q2+…+qi)p+(r1+r2+…+ri)k+(m1+m2+…+mi)

因為(r1+r2+…+ri)k+(m1+m2+…+mi)<

D(E(m1)+E(m2)+…+E(mi))=((E(m1)+E(m2)+…+E(mi)) modp) modk=(k(r1+r2+…+ri)+(m1+m2+…+mi)) modk=m1+m2+…+mi

則有E(m1)×E(m2)×…×E(mi)= (γ)p+(δ)k+(m1×m2×…×mi)，

其中(γ)p表示p的倍數，(δ)k表示k的倍數，

因為(δ)k+(m1×m2×…×mi) <

D(E(m1) ×E(m2)× …×E(mi))=((E(m1)×E(m2)×…×E(mi))modp) modk=((δ)k+(m1×m2×…×mi)) modk=m1×m2×…×mi得證。

□

加密算法E(m)的時間復雜度為O(1)，解密算法D(E(m))的時間復雜度為O(1)。

3.2 分布式BIRCH模型

分布式BIRCH(DBIRCH) 模型針對主數據集、從數據集分布式存儲結構，將各從數據集Di(i=1,2,…,n;n≥3)計算出CFi樹后發送到主數據集，主數據集聯合從數據集發來的CFi樹構建聯合數據集CF樹(即主CF樹)。然后,采用PAM算法對主CF樹的葉節點進行聚類，刪除離群點(即稀疏的簇)，合并稠密簇。

算法2分布式BIRCH算法

輸入：各站點數據集Di，每個Di對象個數mi(i=1,…,n;n≥3)，B值(任何的非葉節點可以擁有的孩子數目)，L值(葉子節點最多擁有的元組數目)，聚簇個數k。

輸出：k個聚簇。

分布式BIRCH算法——主數據集：

(1)fori=1 ton

(2)接收各站點發來的CFi樹

(3)end for

(4)構建主CF樹

①設CF1的根節點是主CF樹的根節點，非葉子節點根據root(CF1)逐級確定最近的子節點；

②葉子節點則計算最接近的元組Li可否吸收；

i.是，更新CF值；

ii.否，判定是否增加新元組;

a)是，增加新元組；

b)否，分裂距離最遠的元組，并將其作為種子分配給距離最近的元組；

③更新每一個非葉子節點的CF值，若分裂此節點node，則在parent(node)插入新元組直至分裂到根節點；

④合并：若在Nj節點(非葉子節點)不再分裂，則將離Nj最近的兩個節點的元組合并。

⑤輸出主CF樹；

(5)在CF樹中任選k個葉子節點；

(6)repeat

(7)分配剩余葉子到最近的代表對象所代表的簇；

(8)遞歸修改CF樹中非葉子節點的CF值；

(9)隨機選擇對象O并計算O交換Oj的代價；

(10)若代價<0，則Oj=O；

(11)until 不再發生變化;

分布式BIRCH算法——從數據集：

(1)fori=1 ton

(2)從根節點開始逐級確定非葉子節點最近的子節點；

(3)若是葉子節點，則計算最接近的元組Li可否吸收；

①是，更新CF值；

②否，再次判定可否增加一個新元組；

i.是，更新CF值；

ii.否，分裂距離最遠的元組,并將其作為種子分配給距離最近的元組；

(4)更新除葉子節點外的其他節點的CF值，若分裂此節點node，則為parent(node)插入新元組,直至分裂到根節點；

(5)合并：若在Nj節點(非葉子節點)不再分裂，則將離Nj最近的兩個節點的元組合并；

(6)發送CFi樹到主站點；

(7)end for

3.3 隱私保護FHE-DBIRCH模型

FHE-DBIRCH算法的基本思想是在從數據集計算CFi值，然后加密傳輸到主數據集;主數據集對密文進行某種計算后，解密后再構建聯合數據集CF樹(即主CF樹)。然后，采用PAM算法對主CF樹的葉節點進行聚類，刪除離群點(即稀疏的簇)，合并稠密簇。最后，將主站點計算的k個簇的集合廣播給各從站點Si。

模型中傳輸的數據均為加密數據，保證了原始數據的隱私性，但因為加密、解密操作增加了額外開銷，必然導致FHE-DBIRCH模型的運行時間高于DBIRCH模型。

算法3FHE-DBIRCH算法

輸入：各站點數據集Di，每個Di對象個數mi(i=1，…，n;n≥3)，B值(任何的非葉節點可以擁有的孩子數目)，L值(葉子節點最多擁有的元組數目)，聚簇個數k。

輸出：k個聚簇。

FHE-DBIRCH算法——主數據集：

(1)fori=1 ton

(2)接收各站點發來的加密CFi樹，根據解密算法得到CFi樹;

(3)end for

(4)構建主CF樹;

①設CF1的根節點是主CF樹的根節點，非葉子節點根據root(CF1)逐級確定最近的子節點；

②葉子節點則計算最接近的元組Li可否吸收；

i.是，更新CF值；

ii.否，判定是否增加新元組；

a)是，增加新元組；

b)否，分裂距離最遠的元組,并將其作為種子分配給距離最近的元組；

③更新除葉子節點外的其他節點的CF值，若分裂此節點node，則為parent(node)插入新元組直至分裂到根節點；

④合并：若在Nj節點(非葉子節點)處不再分裂，則將離Nj最近的兩個節點的元組合并;

⑤輸出主CF樹；

(5)在CF樹中任選k個葉子節點；

(6)repeat

(7)分配剩余葉子到最近的代表對象所代表的簇；

(8)遞歸修改CF樹中非葉子節點的CF值；

(9)隨機選擇對象O，計算O交換Oj的代價；

(10)若代價<0，則Oj=O；

(11)until 不再發生變化;

FHE-DBIRCH算法——從數據集：

(1)fori=1 ton

(2)從根節點開始逐級確定非葉子節點最近的子節點；

(3)葉子節點則計算最接近的元組Li可否吸收；

①是，更新CF值；

②否，再次判定可否增加一個新元組；

a)是，更新CF值；

b)否，分裂距離最遠的元組,并將其作為種子分配給距離最近的元組；

(4)更新除葉子節點外的其他節點的CF值，若分裂此節點node，則為parent(node)插入新元組直至分裂到根節點；

(5)合并：若在Nj節點(非葉子節點)處不再分裂，則將離Nj最近的兩個節點的元組合并；

(7)end for

4 實驗結果和分析

實驗平臺是具有以下參數的PC機：賽揚2.6 GHz CPU,4 GB內存，1 TB硬盤,Windows XP操作系統。本實驗隨機挑選了UCI中的三個數據集，在Weka平臺下封裝了FHE-DBIRCH算法，對三個數據集分別實現BIRCH算法和FHE-DBIRCH算法的對比實驗。

評價聚類挖掘結果的重要指標之一是聚類精度，聚類精度是用有明確的分類結構的數據作為輸入樣本，對比聚類結果和數據原來的分類結構，以評價聚類算法的優劣[10]。

因為采用FHE-DBIRCH算法的從數據集傳輸時均為加密后的數據，其他數據集都不能獲取其他從數據集的明文數據，所以FHE-DBIRCH算法避免了從數據集的隱私泄露。本文的FHE-DBIRCH算法符合完全同態加密，因此FHE-DBIRCH算法與不加隱私保護的聚類算法得到的聚類結果完全一致，即聚類精度一致。實驗結果如圖1所示。

Figure 1 Comparison of clustering accuracy圖1 聚類精度比較

FHE-DBIRCH算法需要加密解密過程，因此時間成本增加，相對不加隱私保護的BIRCH算法成本增加小于15%，如圖2所示。

Figure 2 Comparison of execution time圖2 執行時間比較

5 結束語

本文針對水平分布式環境中聚類數據挖掘算法中存在的隱私泄露問題，提出了一種完全同態加密FHE-DBIRCH模型。該模型將水平分布式數據分為主、從兩個數據集，采用完全同態加密算法對從數據集的數據進行加密，加密后的從數據集傳送到主數據集，主數據集對加密后的從數據集計算后得到結果再解密。 這樣的結果與各從數據集直接計算得到的結果是一致的。通過理論證明和實驗數據的分析均確認該模型可以保護水平分布式數據的隱私，在加密的同時實現聚類挖掘。

[1] Zhou Shui-geng, Li Feng, Tao Yu-fei, et al. Privacy preservation in database applications:A survey[J]. Chinese Journal of Computers, 2009, 32(5):847-860.(in Chinese)

[2] Han Jia-wei. Data mining concepts and techniques[M]. Beijing:China Machine Press, 2001.(in Chinese)

[3] Chong Zhi-hong, Ni Wei-wei, Liu Teng-teng, et al. A privacy-preserving data publishing algorithm for clustering application[J]. Journal of Computer Research and Development, 2010,47(12):2083-2089.(in Chinese)

[4] Gentry C. Fully homomorphic encryption using ideal lattices[C]∥Proc of the 41st Annual ACM Symposium on Theory of Computing (STOC’09), 2009:169-178.

[5] Kamakshi P, Babu A V. Preserving privacy and sharing the data in distributed environment using cryptographic technique on perturbed data[J]. Journal of Computing, 2010, 2(4):115-119.

[6] Vaidya J, Clifton C W, Zhu Y M. Privacy preserving data mining[M]. Purdue:Springer, 2006.

[7] Vaidya J, Clifton C. Privacy-preserving K-means clustering over vertically partitioned data[C]∥Proc of the SIGKDD’

03, 2003:24-27.

[8] Kumar K A, Rangan C P. Privacy preserving DBSCAN algorithm for clustering [J].Advanced Data Mining and Applications, 2007, 4632:57-68.

[9] Gentry C. Fully homomorphic encryption using ideal lattices[C]∥Proc of Symposium on the Theory of Computing (STOC), 2009:169-178.

[10] Halkidi M, Vazirgiannis M, Batistakis Y. Quality scheme assessment in the clustering process[C]∥Proc of PKDD Conference, 2000:265-276.

附中文參考文獻:

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

[2] 韓家煒．數據挖掘概念與技術[M]．北京:機械工業出版社,2001.

[3] 崇志宏,倪巍偉,劉騰騰,等. 一種面向聚類的隱私保護數據發布方法[J]. 計算機研究與發展,2010,47(12):2083-2089.