基于K-匿名的數據隱私社交網絡保護方案

李秋賢，胡鈺，周全興，周國華

（凱里學院，貴州 凱里 556011）

0 引 言

近年來，隨著大數據和信息技術的不斷發展，以微信、QQ、Facebook等為代表的社交網絡平臺以前所未有的速度不斷收集著用戶的隱么數據，各類網絡社交平臺通過對所收集的數據進行數據分析和數據挖掘，獲取數據中蘊藏的價值，從而為平臺獲取更多的收益和財富。然而，對用戶數據進行數據分析和挖掘的行為，常常會導致嚴重的用戶個人信息泄露問題。因此，為了實現保護用戶數據隱么安全的目的，數據隱么保護技術應運而生，各種隱么保護技術都在一定程度上保護了社交網絡平臺中用戶數據的隱么安全以及用戶的個人信息安全。

由于社交網絡中產生的海量數據一定程度上反映了社會的發展規律，很多用戶已習慣在各社交網絡平臺上發布信息進行交流和溝通。但用戶在發布各類信息時存在個人隱么泄露的風險，因此能夠高效且安全地進行數據分析與挖掘對社交網絡平臺的數據保護具有一定的意義。目前保護社交網絡中數據隱么安全的技術有：基于隨機化的隱么保護技術、基于聚類的隱么保護技術和基于Maekov鏈的特征保持隱么保護技術等。2014年，Fu等人提出一種基于節點分割的匿名社交網絡隱么模型，在一定程度上降低了社交網絡中各節點隱么泄露的風險。Fu等人針對現有數據融合方法存在融合精度低、數據完整性差等問題，提出了基于云計算的社交網絡安全隱么數據融合方法，使得網絡數據的融合精度和完整性都得到了優化。

K-匿名是一種有效的隱么保護模型，可以有效地防止隱么泄露。現有很多社交網絡隱么保護技術都是基于K-匿名技術來保護用戶數據的隱么安全。Hu等人根據社交網絡中用戶信息泄露問題，提出一種基于k-均值聚類的隱么保護方法，通過局部最優聚類完成對數據的隱么保護。Zhang等人針對海量高維數據提出了基于k-均值的聯合聚類算法，使用戶數據得到更高的精確度。

由于大多數隱么保護匿名化算法的研究者在設計階段并未將數據的敏感問題考慮在內，導致經數據挖掘后產生的那些數據精度較低，信息損失度較高。本文就對社交網絡中的用戶數據進行數據挖掘存在隱么泄露風險這一問題，提出了一種基于K-匿名的社交網絡隱么保護方法。通過形式化社交網絡平臺，對社交網絡圖中的各節點進行匿名處理，優化社交網絡中各用戶的社交關系和用戶信息，提高社交網絡的數據價值，降低信息損失。

1 預備知識

1.1 社交網絡

社交網絡又稱為社交網絡服務，指的是社會關系中的個體信息和社交關系信息，不僅包括社交網站，還涉及社交軟件和服務等，可以用一個帶標簽的無向無權圖=（，）來表示，即社交網絡是具有個節點的圖，其中={v，…v}表示社交網絡的點集合，各節點v（=1…，）表示社交網絡中的各用戶，=（，）表示社交網絡中的邊集合，和表示各節點之間存在的某種關系。

社交網絡中不僅包含圖結構數據，每一個用戶也同時具有屬性數據，如圖1所示為簡單的社交網絡圖，該社交網絡中包含6個社交網絡關系，各用戶之間的關系也在本社交網絡圖中得以展示。由該圖可以看出，用戶A和A之間的交流和聯系（即A與A的通信）可以借助于A節點或A和A節點來實現。

圖1 簡單的社交網絡圖

1.2 K-匿名模型

K-匿名在數據表中是對所發布數據的一種隱么保護的方法，表示在一個數據表中，至少存在條記錄是不可區分的，即任意惡意敵手都不能在數據表中隨意區分隱么數據所屬的實體。數據K-匿名是指按各個記錄的標識屬性相近程度將數據表中的數據劃分為不同的等價集合。形式化表示即：給定數據表以及標識屬性集合中取值相近的等價集合，若數據表中的任意一個等價集合至少有條記錄，則稱數據表滿足K-匿名。

在本文中，我們創建了簡單的個人信息表格數據，如表1所示。以表格形式列出醫院病人的疾病情況，用以詳細說明K-匿名模型的定義和識別。表1中共有6條數據記錄，數據包含姓名、性別、年齡和疾病類型等四個屬性。其中“姓名”可以確定個人的身份信息，因此表1中“姓名”屬于標識符屬性。

表1 醫院病人個人信息表格數據樣例

表1中“疾病類型”屬于個人的隱么信息，“性別”屬于非敏感信息。因此我們在進行K-匿名處理時，需要將標識符屬性和非敏感信息進行移除，從而得到匿名后的表格，如表2所示。

表2 匿名化后醫院病人個人信息表格數據

以表2匿名化后的數據為例，K-匿名是指：如果把值設為3，當惡意攻擊者想要獲取病人的個人信息時，若惡意攻擊者知道他要攻擊的目標對象年齡在20至50歲之間，從表2中我們可以發現，年齡在20至50歲之間的等價集合中存在3條數據記錄，攻擊者能夠順利攻擊的概率為1/3，因此我們認為該表滿足了3-匿名模型。

2 基于K-匿名社交網絡模型

本文所設計的基于K-匿名的社交網絡模型是通過保護社交網絡節點隱么的形式來保護數據的隱么安全的，在基于K-匿名的社交網絡模型中，每一個網絡用戶節點都擁有不少于-1個候選節點，從而使得惡意攻擊者識別目標節點的概率小于1/。如圖2所示，我們將原始的社交網絡通過社交網絡圖進行形式化，圖2是用戶關系的社交網絡圖，各節點表示社交網絡中的各用戶，各邊線表示各節點與其他節點存在的某種關系。

圖2 原始社交網絡關系圖

在本方案中，我們通過修改社交網絡圖的頂點或邊的方式來實現匿名，即在社交網絡圖中增加社交關系，通過增加邊的方式實現社交網絡的匿名化。如圖3所示，我們在原始社交網絡中增加3條社交關系，通過黃色邊線標記從而實現3-匿名化。即使惡意攻擊者知道用戶有兩條社交關系，但也無法以高于1/3的概率正確推斷出哪個節點為用戶。因此，我們實現了3-匿名化，保護了用戶個人信息的安全和隱么性。

圖3 匿名化后社交網絡關系圖

3 基于K-匿名設計網絡隱私保護方案

本文提出的基于K-匿名的社交網絡隱么保護方案是基于K-匿名模型實現的，即方案中社交網絡節點的隱么保護是通過改變節點或邊的方式來實現匿名化，社交過程采用全同態加密技術實現對節點發送消息的加密，從而保證用戶個人以及消息的隱么性。該方案主要由4個算法組成，分別為節點K-匿名算法、密鑰生成算法、加密算法和解密算法，算法的詳細描述為：

（1）節點K-匿名算法。根據所設計的社交網絡模型輸入對應的社交網絡圖和安全參數，使用K-匿名算法將圖進行K-匿名處理，形成匿名化后的圖后將其輸出。

（2）秘鑰生成算法。輸入安全參數和匿名化后的社交網絡圖，通過全同態加密算法隨機生成公鑰和么鑰對（PK，SK）。

（3）加密算法。輸入秘鑰算法生成的公鑰PK和社交網絡平臺中需要加密的消息，利用加密算法產生對應的密文消息。

（4）解密算法。輸入公鑰所對應的么鑰SK需要解密的消息，利用解密算法輸出加密密文對應的明文消息，只有網絡結構中相應的節點才能進行訪問和解密。

在該方案中，只有社交網絡節點中的用戶才能從方案中獲取公鑰對應的么鑰，惡意敵手無法在多項式時間內以目標節點的圖結構信息作為先驗知識來攻擊用戶的隱么，以及破壞數據的安全性。

4 方案分析

本文主要對方案的安全性進行以下分析：

定理：在DDH（Decision Diffie-Hellman）假設下，本文所提出的基于K-匿名的數據隱么社交網絡保護方案是安全的。

證明：假設有惡意攻擊者以不可忽略的優勢攻擊本方案中的節點用戶，在節點K-匿名算法階段，惡意攻擊者以目標節點v的社交網絡圖結構信息為背景知識，對發布的圖進行攻擊，由于是經過K-匿名化的結構圖，所以惡意攻擊者能夠識別目標節點v的概率為1/。

然而，在消息發布傳播階段，我們通過構建模擬器P來模擬秘鑰的生成，惡意攻擊者A將兩次發布的消息，分別傳遞給模擬器。模擬器通過拋擲硬幣的方式選取=（0，1），從而猜測消息的么鑰，在兩次實驗過程中惡意攻擊者很有可能無法區分消息和′，若模擬器猜測’=，則模擬器可以輸出正確的消息，否則將輸出消息′。由于意攻擊者很有可能無法區分消息′和，因此在DDH判定下，本文所提出的基于K-匿名的數據隱么社交網絡保護方案是安全的。

5 結 論

本文為了解決社交網絡平臺中用戶個人信息安全、傳播數據的隱么泄露問題，構造一種新的社交網絡保護方案。通過設計基于K-匿名和全同態加密技術的社交網絡的安全模型保護方案，進一步保證了社交網絡平臺中隱么數據的安全性。在未來的工作中，我們將通過平衡各用戶節點的效用來保證社交網絡用戶數據的隱么安全。