基于K-匿名的數(shù)據(jù)隱私社交網(wǎng)絡(luò)保護(hù)方案

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

（凱里學(xué)院，貴州 凱里 556011）

0 引 言

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

由于社交網(wǎng)絡(luò)中產(chǎn)生的海量數(shù)據(jù)一定程度上反映了社會的發(fā)展規(guī)律，很多用戶已習(xí)慣在各社交網(wǎng)絡(luò)平臺上發(fā)布信息進(jìn)行交流和溝通。但用戶在發(fā)布各類信息時存在個人隱么泄露的風(fēng)險，因此能夠高效且安全地進(jìn)行數(shù)據(jù)分析與挖掘?qū)ι缃痪W(wǎng)絡(luò)平臺的數(shù)據(jù)保護(hù)具有一定的意義。目前保護(hù)社交網(wǎng)絡(luò)中數(shù)據(jù)隱么安全的技術(shù)有：基于隨機(jī)化的隱么保護(hù)技術(shù)、基于聚類的隱么保護(hù)技術(shù)和基于Maekov鏈的特征保持隱么保護(hù)技術(shù)等。2014年，F(xiàn)u等人提出一種基于節(jié)點(diǎn)分割的匿名社交網(wǎng)絡(luò)隱么模型，在一定程度上降低了社交網(wǎng)絡(luò)中各節(jié)點(diǎn)隱么泄露的風(fēng)險。Fu等人針對現(xiàn)有數(shù)據(jù)融合方法存在融合精度低、數(shù)據(jù)完整性差等問題，提出了基于云計算的社交網(wǎng)絡(luò)安全隱么數(shù)據(jù)融合方法，使得網(wǎng)絡(luò)數(shù)據(jù)的融合精度和完整性都得到了優(yōu)化。

K-匿名是一種有效的隱么保護(hù)模型，可以有效地防止隱么泄露?，F(xiàn)有很多社交網(wǎng)絡(luò)隱么保護(hù)技術(shù)都是基于K-匿名技術(shù)來保護(hù)用戶數(shù)據(jù)的隱么安全。Hu等人根據(jù)社交網(wǎng)絡(luò)中用戶信息泄露問題，提出一種基于k-均值聚類的隱么保護(hù)方法，通過局部最優(yōu)聚類完成對數(shù)據(jù)的隱么保護(hù)。Zhang等人針對海量高維數(shù)據(jù)提出了基于k-均值的聯(lián)合聚類算法，使用戶數(shù)據(jù)得到更高的精確度。

由于大多數(shù)隱么保護(hù)匿名化算法的研究者在設(shè)計階段并未將數(shù)據(jù)的敏感問題考慮在內(nèi)，導(dǎo)致經(jīng)數(shù)據(jù)挖掘后產(chǎn)生的那些數(shù)據(jù)精度較低，信息損失度較高。本文就對社交網(wǎng)絡(luò)中的用戶數(shù)據(jù)進(jìn)行數(shù)據(jù)挖掘存在隱么泄露風(fēng)險這一問題，提出了一種基于K-匿名的社交網(wǎng)絡(luò)隱么保護(hù)方法。通過形式化社交網(wǎng)絡(luò)平臺，對社交網(wǎng)絡(luò)圖中的各節(jié)點(diǎn)進(jìn)行匿名處理，優(yōu)化社交網(wǎng)絡(luò)中各用戶的社交關(guān)系和用戶信息，提高社交網(wǎng)絡(luò)的數(shù)據(jù)價值，降低信息損失。

1 預(yù)備知識

1.1 社交網(wǎng)絡(luò)

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

社交網(wǎng)絡(luò)中不僅包含圖結(jié)構(gòu)數(shù)據(jù)，每一個用戶也同時具有屬性數(shù)據(jù)，如圖1所示為簡單的社交網(wǎng)絡(luò)圖，該社交網(wǎng)絡(luò)中包含6個社交網(wǎng)絡(luò)關(guān)系，各用戶之間的關(guān)系也在本社交網(wǎng)絡(luò)圖中得以展示。由該圖可以看出，用戶A和A之間的交流和聯(lián)系（即A與A的通信）可以借助于A節(jié)點(diǎn)或A和A節(jié)點(diǎn)來實(shí)現(xiàn)。

圖1 簡單的社交網(wǎng)絡(luò)圖

1.2 K-匿名模型

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

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

表1 醫(yī)院病人個人信息表格數(shù)據(jù)樣例

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

表2 匿名化后醫(yī)院病人個人信息表格數(shù)據(jù)

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

2 基于K-匿名社交網(wǎng)絡(luò)模型

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

圖2 原始社交網(wǎng)絡(luò)關(guān)系圖

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

圖3 匿名化后社交網(wǎng)絡(luò)關(guān)系圖

3 基于K-匿名設(shè)計網(wǎng)絡(luò)隱私保護(hù)方案

本文提出的基于K-匿名的社交網(wǎng)絡(luò)隱么保護(hù)方案是基于K-匿名模型實(shí)現(xiàn)的，即方案中社交網(wǎng)絡(luò)節(jié)點(diǎn)的隱么保護(hù)是通過改變節(jié)點(diǎn)或邊的方式來實(shí)現(xiàn)匿名化，社交過程采用全同態(tài)加密技術(shù)實(shí)現(xiàn)對節(jié)點(diǎn)發(fā)送消息的加密，從而保證用戶個人以及消息的隱么性。該方案主要由4個算法組成，分別為節(jié)點(diǎn)K-匿名算法、密鑰生成算法、加密算法和解密算法，算法的詳細(xì)描述為：

（1）節(jié)點(diǎn)K-匿名算法。根據(jù)所設(shè)計的社交網(wǎng)絡(luò)模型輸入對應(yīng)的社交網(wǎng)絡(luò)圖和安全參數(shù)，使用K-匿名算法將圖進(jìn)行K-匿名處理，形成匿名化后的圖后將其輸出。

（2）秘鑰生成算法。輸入安全參數(shù)和匿名化后的社交網(wǎng)絡(luò)圖，通過全同態(tài)加密算法隨機(jī)生成公鑰和么鑰對（PK，SK）。

（3）加密算法。輸入秘鑰算法生成的公鑰PK和社交網(wǎng)絡(luò)平臺中需要加密的消息，利用加密算法產(chǎn)生對應(yīng)的密文消息。

（4）解密算法。輸入公鑰所對應(yīng)的么鑰SK需要解密的消息，利用解密算法輸出加密密文對應(yīng)的明文消息，只有網(wǎng)絡(luò)結(jié)構(gòu)中相應(yīng)的節(jié)點(diǎn)才能進(jìn)行訪問和解密。

在該方案中，只有社交網(wǎng)絡(luò)節(jié)點(diǎn)中的用戶才能從方案中獲取公鑰對應(yīng)的么鑰，惡意敵手無法在多項(xiàng)式時間內(nèi)以目標(biāo)節(jié)點(diǎn)的圖結(jié)構(gòu)信息作為先驗(yàn)知識來攻擊用戶的隱么，以及破壞數(shù)據(jù)的安全性。

4 方案分析

本文主要對方案的安全性進(jìn)行以下分析：

定理：在DDH（Decision Diffie-Hellman）假設(shè)下，本文所提出的基于K-匿名的數(shù)據(jù)隱么社交網(wǎng)絡(luò)保護(hù)方案是安全的。

證明：假設(shè)有惡意攻擊者以不可忽略的優(yōu)勢攻擊本方案中的節(jié)點(diǎn)用戶，在節(jié)點(diǎn)K-匿名算法階段，惡意攻擊者以目標(biāo)節(jié)點(diǎn)v的社交網(wǎng)絡(luò)圖結(jié)構(gòu)信息為背景知識，對發(fā)布的圖進(jìn)行攻擊，由于是經(jīng)過K-匿名化的結(jié)構(gòu)圖，所以惡意攻擊者能夠識別目標(biāo)節(jié)點(diǎn)v的概率為1/。

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

5 結(jié) 論

本文為了解決社交網(wǎng)絡(luò)平臺中用戶個人信息安全、傳播數(shù)據(jù)的隱么泄露問題，構(gòu)造一種新的社交網(wǎng)絡(luò)保護(hù)方案。通過設(shè)計基于K-匿名和全同態(tài)加密技術(shù)的社交網(wǎng)絡(luò)的安全模型保護(hù)方案，進(jìn)一步保證了社交網(wǎng)絡(luò)平臺中隱么數(shù)據(jù)的安全性。在未來的工作中，我們將通過平衡各用戶節(jié)點(diǎn)的效用來保證社交網(wǎng)絡(luò)用戶數(shù)據(jù)的隱么安全。