可證明安全的社交網絡隱私保護方案

何建瓊，田有亮，周凱

（1. 貴州大學計算機科學與技術學院，貴州 貴陽 550025；2. 貴州省公共大數據重點實驗室，貴州 貴陽 550025；3. 貴州大學密碼學與數據安全研究所，貴州 貴陽 550025）

可證明安全的社交網絡隱私保護方案

何建瓊1,2,3，田有亮1,2,3，周凱1,2,3

（1. 貴州大學計算機科學與技術學院，貴州 貴陽 550025；2. 貴州省公共大數據重點實驗室，貴州 貴陽 550025；3. 貴州大學密碼學與數據安全研究所，貴州 貴陽 550025）

針對社交網絡隱私保護方案的安全性證明問題，提出了一種可證明安全的社交網絡隱私保護方案。首先，通過分析社交網絡中節點隱私的安全需求（不可區分的節點結構和不可區分的發送消息），分別建立其安全模型；其次，基于該安全模型運用雙線性映射構造社交網絡節點隱私保護方案；最后，證明了該方案是可證明安全的，并且分析和對比了該方案的安全性，分析結果表明，該方案除了具有可證明安全性外，還能抵抗再識別攻擊、推理攻擊和信息聚集攻擊。

可證明安全；社交網絡；隱私保護；雙線性映射

社交網絡的隱私信息主要有節點隱私、邊隱私和圖性質隱私［2］。本文考慮的節點隱私信息，目前很多研究者已經做了一些研究。針對節點隱私的保護，文獻［3～5］針對攻擊者的背景知識是目標節點的圖結構信息，采用修改圖的方式實現節點的隱私保護，并且分析了匿名后社交網絡的有用性。文獻［6，7］針對攻擊者以目標節點鄰接的子圖結構為背景信息，通過泛化頂點標簽和擾亂圖的結構特征實現隱私保護。文獻［8～10］采用頂點進行聚類的匿名技術，把頂點間結構的差異性隱藏在等價類中。文獻［11］考慮到社交網絡隱私保護的個性化需求，提出一種個性化的（P，α，K）匿名模型。文獻［12］通過增加、刪除邊以及添加噪聲節點的方式，實現目標節點的屬性匿名。文獻［13］采用節點分割的隱私屬性匿名算法，通過分割節點的屬性連接和關系連接，提高了節點的匿名性，降低了目標節點隱私屬性泄露的風險。文獻［14］提出一種帶陷門的屬性加密算法，由屬性權威機構與數據屬主協同完成用戶私鑰的生成與分發，有效降低了數據屬主的密鑰管理代價，然后，通過令牌樹機制控制用戶對屬性陷門的獲取，實現了高效的屬性撤銷。

當前的研究者較少關心可證明安全理論在社交網絡隱私保護中的應用，未見可證明安全的社交網絡隱私保護方案。本文通過分析社交網絡中節點隱私保護的安全需求，建立社交網絡節點隱私保護安全模型，并基于該安全模型運用雙線性映射構造社交網絡節點隱私保護方案。最后，證明和分析了該方案的安全性。

2 基礎知識

定義1 雙線性映射。

設1G、2G是2個相同大素數階為q的群，其中，1G是加法群，2G是乘法群。令P為1G的任一生成元，aP記為a個P相加。若滿足下列3個性質，則稱映射為雙線性映射。

2） 非退化性。如果P是1G的生成元，則（，）ePP是2G的生成元，即

定義2 詢問。

給定一個社交網絡G，稱詢問Q為攻擊者可以用任何背景知識從G中獲取隱私信息，詢問的結果是頂點集合'V，其中'VV?，'V中的每個頂點稱為一個匹配頂點。

定義3 結構化攻擊。

給定一個已經發布的社交網絡G?，如果攻擊者對G?發起詢問Q并獲得有限數量的頂點集，那么目標x可能被唯一識別。如果Q是基于G?中目標x的結構化信息的詢問，這種攻擊就稱為結構化攻擊。

定義4 訪問結構。

定義5 判定雙線性Diffie-Hellman指數假設。

模擬器B以優勢在G中解決DBDHE問題并輸出，若

且沒有多項式時間的算法以不可忽略的優勢解決DBDHE問題，則稱DBDHE假設成立。

3 節點隱私保護算法框架與安全模型

3.1 算法框架

節點隱私保護的安全需求：不可區分的節點結構和不可區分的發送消息。節點隱私保護算法采用KM算法［5］對節點進行匿名，實現不可區分的節點結構；用基于密文策略屬性基加密［15］對節點發送的消息進行加密，實現不可區分的發送消息。因此，本節提出的節點隱私保護方案（NPPS， node privacy-preserving scheme）包含5個算法：節點匿名（NodeAnony）算法、初始化（Setup）算法、加密（Encrypt）算法、密鑰生成（KeyGen）算法、解密（Decrypt）算法，算法的功能描述如下。

1） NodeAnony（G，k）算法：輸入社交網絡圖G、參數k，對G采用KM算法后生成圖G?，輸出圖G?。

2） Setup（1k，*G）算法：輸入系統安全參數k和發布后的社交網絡圖G?，生成公鑰PK和主密鑰MK。

3） Encrypt（PK，M，A）算法：輸入系統公鑰PK、消息M和訪問結構A，用公鑰PK加密消息M，生成密文CT，其中，密文中包含了訪問結構A。只有當用戶具有的屬性集滿足訪問結構時，才能正確解密消息。

4） KeyGen（MK，S）算法：輸出系統主密鑰MK和用戶屬性集S，生成私鑰sk。

5） Decrypt（sk，CT）算法：輸入私鑰sk和密文CT，當私鑰中包含的屬性基S滿足密文訪問結構A時，就能正確解密恢復出消息M。

3.2 安全模型

本節給出節點隱私保護的標準模型來抵御節點結構攻擊和發送消息攻擊，下面通過2個實驗來說明這2個安全需求，如圖1和圖2所示。

在圖1、圖2的實驗中，KO、EO代表密鑰生成Oracle和加密Oracle，（）Qx表示敵手對目標節點x進行結構化查詢，（）Dx表示敵手通過獲取目標節點x發送的消息為背景知識進行目標節點身份的推斷。圖1實驗關注的是不可區分的節點結構，采用節點匿名算法的安全概念IND-NPPS-CNA，如果該實驗以不可忽略的概率返回1，則敵手A勝利。圖2實驗關注的是不可區分的發送消息，采用基于密文策略屬性基加密方案的安全概念IND-NPPS-CSMA，若該實驗以不可忽略的概率返回1，則敵手A勝利。

圖1 不可區分的節點結構的安全模型

圖2 不可區分的發送消息的安全模型

接下來，定義敵手A在IND-NPPS-CNA安全性概念下攻破社交網絡節點隱私保護方案的優勢為。

定義6 當敵手A攻擊能力和查詢Oracle的次數是關于ε多項式界定時，如果攻擊該NPPS方案成功的優勢是關于ε可忽略的，則稱這個社交網絡節點隱私保護方案是IND-NPPS-CNA安全的。

定義敵手A在IND-NPPS-CSMA安全性概念下攻破社交網絡節點隱私保護方案的優勢為。

定義7 當敵手A攻擊能力和查詢Oracle的次數是關于ε多項式界定的，如果攻擊該方案成功的優勢是關于ε可忽略的，則稱這個社交網絡節點隱私保護方案是IND-NPPS-CSMA安全的。

4 方案構造

基于以上安全模型，構建如下方案。

1） NodeAnony（G，k）：輸入社交網絡圖G和參數k，通過樸素匿名后轉變為'G圖。把'G劃分為n個塊并且把這些塊聚類為m個組每個iU至少有k個塊對每個iU中的所有塊ijP執行圖對齊后得到ijP′，用對齊后的塊ijP′替換塊ijP得到圖''G。對所有的交叉邊執行邊復制，得到k-自同構社交網絡圖G?，輸出圖G?。

3） Encrypt（PK，M，A）：輸入公鑰PK、消息M和訪問結構計算（其中，TU是行向量U的轉置），隨機選擇公布

4） KeyGen（MK，S）：輸入主密鑰MK和用戶的身份其中，隨機選取然后計算私鑰

5） Decrypt（sk，CT）：輸入匿名后的節點CT、用戶的私鑰sk，如果用戶的屬性S滿足訪問結構A，即當時，則可計算，通過S可以解匿名C得到消息

5 安全性證明

定理1 假定DBDHE假設成立，那么沒有多項式時間的敵手以目標節點的圖結構信息和發送的消息來選擇性攻擊本文系統。

證明 假設敵手A有不可忽略的優勢ε攻破本文方案。構建一個模擬器B，模擬器B輸入DBDHE挑戰和T。敵手將挑戰結構輸入算法中，其中，nq?≤。

1） 節點匿名算法：輸入社交網絡圖G和參數，通過樸素匿名轉變為圖G′。把G′劃分為n個塊并且把這些塊聚類為m個組，每個iU至少有k個塊對每個Ui中的所有塊Pij執行圖對齊后得到ijP′，用對齊后的塊ijP′替換塊得到圖G′′。對所有的交叉邊執行邊復制，得到k-自同構社交網絡圖G?，輸出圖G?。

階段1 這個階段敵手A以目標節點x的圖結構信息為背景知識，對發布的圖G?進行結構化查詢Q，由于圖G?是一個自同構的圖，所以則敵手A識別出目標節點x的概率為。

階段2 這個階段，模擬器B模擬生成私鑰。假定模擬器被給予一個對與用戶身份的集合S相對應的私鑰的詢問，其中，S不滿足訪問結構A?。模擬器B隨機選取，定義

那么

挑戰：敵手A將2個消息0M、1M給模擬器。模擬器通過拋擲硬幣的方式選取產生。使用模擬器B來模擬用其中來模擬隨機行向量，則。

階段3 與階段2相同。

猜測：敵手最終輸出猜測b′。若bb′=，模擬器B輸出0并且回答，否則，模擬器輸出1并且回答G中的一個隨機值。當T是DBDHE元組時，，當T是隨機時，。由于敵手A以不可忽略的優勢攻破方案，那么B也以不可忽略的優勢來模擬DBDHE游戲。

6 方案分析

下面將本文提出的社交網絡隱私保護方案與現有的方案進行比較。表1給出了各種方案間安全性的比較，其中“√”表示滿足該安全性，“×”表示不滿足該安全性。

從表1可以看出，文獻［5，8，9，13］提出的方案只能抵抗基于屬性的再識別攻擊和基于結構的再識別攻擊，而不能抵抗推理攻擊和信息聚集攻擊，也未能證明其具備可證明安全性。相比已有的社交網絡隱私保護方案，本文提出的方案采用KM算法對節點進行匿名，實現不可區分的節點結構，用基于密文策略屬性基加密對發送的消息進行加密，實現不可區分的發送消息，從而能抵抗再識別攻擊、推理攻擊和信息聚集攻擊。此外，本文運用可證明安全理論對方案的安全性進行了證明，使方案具有可證明安全性。

7 結束語

本文研究了社交網絡節點隱私保護的可證明安全問題，并建立社交網絡節點隱私保護安全模型，基于該模型，提出可證明安全的社交網絡隱私保護方案。該方案通過用匿名算法實現節點身份的隱藏和圖結構的匿名，防止敵手基于目標節點的結構化攻擊。同時，采用基于密文策略屬性基加密實現對節點發送消息的加密，防止敵手基于目標節點發送的消息推理出目標節點的身份信息。最后，證明和分析該方案的安全性。

表1 社交網絡隱私保護方案安全性比較

［1］ BHAGAT S， CORMODE G， KRISHNAMURTHY B， et al. Class-based graph anaonymization for social network data［EB/OL］. http：//www.vldb.org/pvldb/2/vldb09-pvldb26.pdf.

［2］ 劉向宇， 王斌， 楊曉春. 社會網絡數據發布隱私保護技術綜述［J］. 軟件學報， 2014， 25（3）：576-590. LIU X Y ，WANG B， YANG X C. Social network data privacy protection technology review ［J］. Journal of Software ， 2014 ， 25 （3） ：576-590 .

［3］ HAY M， MIKLAU G， JENSEN D， et al. Anonymizing social networks［R］. University of Massachusetts， 2007.

［4］ LIU K， TERZI E. Towards identity anonymization on graphs［C］// The ACM Sigmod International Conference on Management of Data. c2008.

［5］ ZOU L， CHEN L. K-automorphism：a general framework for privacy preserving network publication ［C］//The 35th International Conference on Very Large Data Base. c2009：946-957.

［6］ ZHOU B， PEI J. Preserving privacy in social networks against neighborhood attacks［C］//The 24th IEEE International Conference on Data Engineering （ICDE）. c2008.

［7］ 宋喜忠， 劉康明. 基于k-subgrap 算法的社交網絡隱私保護研究［J］. 科技通報， 2015 （1）：155-157. SONG X Z， LIU K M . Social network privacy protection study based on k-subgrap algorithm［J］. Bulletin Science and Technology ，2015 （1） ： 155-157 .

［8］ HAY M， MIKLAU G， JENSEN D， et al. Resisting structural re-identification in anonymized social networks ［J］. VLDB Journa1，2010， 19（6）： 797-823.

［9］ 韋偉， 李楊， 張為群. 一種基于 GSNPP 算法的社交網絡隱私保護方法研究［J］. 計算機科學， 2012， 39（3）：104-106. WEI W ， LI Y， ZHANG W Q . A GSNPP algorithm based on the social network privacy protection method research［J］. Journal of Computer Science ， 2012 ， 39 （3）： 104-106 .

［10］ THOMPSON B， YAO D F. The union-split algorithm and cluster-based anonymization of social networks ［C］//The 4th International Symposium on Information， Computer， and Communications Security. c2013：218-227.

［11］ 孔慶江. 社交網絡中個人信息與人際關系的隱私保護研究［D］.杭州： 浙江工業大學， 2011. KONG Q J. Personal information and relationships in the social network privacy protection research［D］. Hangzhou： Zhejiang University of Technology ， 2011 .

［12］ YUAN M X， CHEN L， YU PS， YU T. Protecting sensitive labels in social network data anonymization［J］. IEEE Transactions on Knowledge and Data Engineering， 2013， 25（3）：633-647.

［13］ 付艷艷， 張敏， 馮登國， 等. 基于節點分割的社交網絡屬性隱私保護［J］. 軟件學報， 2014， 4： 768-780. FU Y Y ， ZHANG M ， FENG D G ， et al . Social network privacy protection based on the node split attributes［J］. Journal of Software ，2014 ，4：68-780.

［14］ 呂志泉， 洪澄， 張敏， 等. 面向社交網絡的隱私保護方案［J］. 通信學報， 2014， 35（8）：23-32. LV Z Q， HONG C ， ZHANG M ， et al. Privacy protection scheme for social network ［J］. Journal on Communications ， 2014 ， 35 （8） ： 23-32 .

［15］ LING C， NEWPORT C. Provably secure ciphertext policy ABE［C］//The 14th ACM Conference on Computer and Communications Security. c2007： 456-465.

何建瓊（1991-），女，貴州遵義人，貴州大學碩士生，主要研究方向為密碼學與安全協議。

田有亮（1982-），男，貴州盤縣人，博士，貴州大學教授，主要研究方向為博弈論、密碼學與安全協議。

周凱（1991-），男，浙江衢州人，貴州大學碩士生，主要研究方向為密碼學與可信計算。

Provably secure social network privacy-preserving scheme

HE Jian-qiong1,2,3， TIAN You-liang1,2,3， ZHOU Kai1,2,3
（1. College of Computer Science and Technology， Guizhou University， Guiyang 550025， China；2. Guizhou Provincial Key Laboratory of Public Big Data， Guiyang 550025， China；3. Institute of Cryptography and Data Security， Guizhou University， Guiyang 550025， China）

A provable secure social network privacy-preserving scheme was proposed to solve the problem of social network privacy-preserving scheme's security proof. Firstly， through analyzing the security requirements about the node's privacy （indistinguishable node structure and indistinguishable sending messages）， the security model were established separately. Secondly， the bilinear mapping was used to construct the social network privacy-preserving scheme. Finally， it was proved that the scheme was provable secure， the security of the schemes were analyzed and compared. The analysis results show that the scheme not only has provable security， but also can resist re-identify attack， inference attack and information aggregation attack.

provable secure， social network， privacy-preserving， bilinear mapping

1 引言

社交網絡的迅速發展，給社交網絡用戶的隱私保護帶來了嚴重挑戰。人們在享受社交網絡提供服務的同時，個人發布的隱私信息卻未能得到很好的保護，如果在社交網絡發布之前不進行相應的隱私保護，攻擊者就很容易獲得用戶的隱私信息，可能會給用戶造成一定的經濟損失。現有的隱私保護技術主要集中在匿名化技術、泛化技術、隨機擾動技術、聚類這幾方面［1］，盡管應用這些隱私保護技術可以防止攻擊者輕而易舉獲得目標用戶的隱私信息，但是應用這些隱私保護技術后的安全性并沒有得到證明。針對隱私保護方案安全性的證明問題，可以運用可證明安全理論解決。可證明安全理論是從破譯密碼方案等價于解數學難題的角度間接證明密碼方案的安全性，這將密碼方案的安全性最終歸結為某個經過深入研究也無法解決的數學難題。

s： The National Natural Science Foundation of China （No.61363068），Graduate Innovation Foundation of Guizhou University （No.2016050）

TP393

A

10.11959/j.issn.2096-109x.2016.00082

2016-04-16；

2016-07-07。通信作者：田有亮，youliangtian@163.com

國家自然科學基金資助項目（No.61363068）；貴州大學研究生創新基金資助項目（No.2016050）