可證明安全的社交網(wǎng)絡隱私保護方案

何建瓊，田有亮，周凱

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

可證明安全的社交網(wǎng)絡隱私保護方案

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

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

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

可證明安全；社交網(wǎng)絡；隱私保護；雙線性映射

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

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

2 基礎(chǔ)知識

定義1 雙線性映射。

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

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

定義2 詢問。

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

定義3 結(jié)構(gòu)化攻擊。

給定一個已經(jīng)發(fā)布的社交網(wǎng)絡G?，如果攻擊者對G?發(fā)起詢問Q并獲得有限數(shù)量的頂點集，那么目標x可能被唯一識別。如果Q是基于G?中目標x的結(jié)構(gòu)化信息的詢問，這種攻擊就稱為結(jié)構(gòu)化攻擊。

定義4 訪問結(jié)構(gòu)。

定義5 判定雙線性Diffie-Hellman指數(shù)假設(shè)。

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

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

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

3.1 算法框架

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

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

2） Setup（1k，*G）算法：輸入系統(tǒng)安全參數(shù)k和發(fā)布后的社交網(wǎng)絡圖G?，生成公鑰PK和主密鑰MK。

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

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

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

3.2 安全模型

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

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

圖1 不可區(qū)分的節(jié)點結(jié)構(gòu)的安全模型

圖2 不可區(qū)分的發(fā)送消息的安全模型

接下來，定義敵手A在IND-NPPS-CNA安全性概念下攻破社交網(wǎng)絡節(jié)點隱私保護方案的優(yōu)勢為。

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

定義敵手A在IND-NPPS-CSMA安全性概念下攻破社交網(wǎng)絡節(jié)點隱私保護方案的優(yōu)勢為。

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

4 方案構(gòu)造

基于以上安全模型，構(gòu)建如下方案。

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

3） Encrypt（PK，M，A）：輸入公鑰PK、消息M和訪問結(jié)構(gòu)計算（其中，TU是行向量U的轉(zhuǎn)置），隨機選擇公布

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

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

5 安全性證明

定理1 假定DBDHE假設(shè)成立，那么沒有多項式時間的敵手以目標節(jié)點的圖結(jié)構(gòu)信息和發(fā)送的消息來選擇性攻擊本文系統(tǒng)。

證明 假設(shè)敵手A有不可忽略的優(yōu)勢ε攻破本文方案。構(gòu)建一個模擬器B，模擬器B輸入DBDHE挑戰(zhàn)和T。敵手將挑戰(zhàn)結(jié)構(gòu)輸入算法中，其中，nq?≤。

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

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

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

那么

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

階段3 與階段2相同。

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

6 方案分析

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

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

7 結(jié)束語

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

表1 社交網(wǎng)絡隱私保護方案安全性比較

［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］ 劉向宇， 王斌， 楊曉春. 社會網(wǎng)絡數(shù)據(jù)發(fā)布隱私保護技術(shù)綜述［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 算法的社交網(wǎng)絡隱私保護研究［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 算法的社交網(wǎng)絡隱私保護方法研究［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］ 孔慶江. 社交網(wǎng)絡中個人信息與人際關(guān)系的隱私保護研究［D］.杭州： 浙江工業(yè)大學， 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］ 付艷艷， 張敏， 馮登國， 等. 基于節(jié)點分割的社交網(wǎng)絡屬性隱私保護［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］ 呂志泉， 洪澄， 張敏， 等. 面向社交網(wǎng)絡的隱私保護方案［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-），女，貴州遵義人，貴州大學碩士生，主要研究方向為密碼學與安全協(xié)議。

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

周凱（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 引言

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

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）；貴州大學研究生創(chuàng)新基金資助項目（No.2016050）