社會機會網(wǎng)絡中基于局部敏感哈希的用戶隱私保護方案

劉軒甫，劉玉梅

哈爾濱工程大學信息與通信工程學院，黑龍江哈爾濱150001

機會網(wǎng)絡是一種不要求網(wǎng)絡全連通、容延容斷的網(wǎng)絡[1]。整個網(wǎng)絡不需要發(fā)送端節(jié)點和接收端節(jié)點有完整的鏈路，而是通過節(jié)點的移動創(chuàng)造節(jié)點的相遇機會，從而實現(xiàn)網(wǎng)絡通信。如今移動設備的普及使得網(wǎng)絡中通信節(jié)點一定程度上代表了人類活動的社會性，利用社會網(wǎng)絡有助于該類網(wǎng)絡路由算法的設計實現(xiàn)，這類網(wǎng)絡被稱為社會機會網(wǎng)絡。社會機會網(wǎng)絡大多利用中繼節(jié)點與目的節(jié)點之間接觸信息、節(jié)點上下文信息（能量、移動速度、鄰居變化及位置等）、節(jié)點之間社會關系、節(jié)點的社會地位[2?4]，網(wǎng)絡中各節(jié)點分享各自歷史消息，從而預測未來與目的節(jié)點相遇機會。

由于社會機會網(wǎng)絡是基于社會網(wǎng)絡分析方法提出的[5?6]，網(wǎng)絡中節(jié)點大多代表人類活動，在實際社會活動中用戶不會希望社會關系隱私信息暴露在網(wǎng)絡中，但網(wǎng)絡路由需要利用各用戶隱私信息完成決策。本文針對此矛盾，設計了基于局部敏感哈希（locality-sensitive Hashing）計算方式[7]加密用戶隱私背景信息，保證用戶隱私安全性；同時由于加密后數(shù)據(jù)相似度與原始數(shù)據(jù)相似度一致[8?9]，從而公開各自加密信息表就可以比對任意兩用戶的社會背景相似度，保證了路由的正常性能。

節(jié)點社會背景信息進行轉(zhuǎn)發(fā)判決的路由協(xié)議在近些年來得到極大的發(fā)展[10?12]，研究人員根據(jù)不同的社會背景和環(huán)境條件制定不同的判決條件。Bubble rap[13]、Simbet[14]、Propicman[15]等經(jīng)典的社會機會網(wǎng)絡路由中，通過收集歷史社區(qū)、習慣、興趣等信息判斷節(jié)點與目的節(jié)點相似性從而預測未來的相遇機會。但社會機會網(wǎng)絡協(xié)議的設計只考慮如何正確有效地完成路由，而忽略了用戶隱私信息暴露的問題。針對社會網(wǎng)絡隱私保護方法主要分為基于數(shù)據(jù)失真技術、基于數(shù)據(jù)限制發(fā)布技術、基于數(shù)據(jù)加密技術等方法[16?17]。在數(shù)據(jù)失真技術方面，Parris等[18]通過采用修改模糊朋友列表的方式保護用戶的隱私，通過加入不實信息模糊隱私列表。為了完全保護隱私信息，需要在機會網(wǎng)絡中引入加密機制，從而大量地研究提出將公鑰加密（public key infrastructure，PKI）機制引入機會網(wǎng)絡中：一種基于關鍵字可搜索的公鑰加密研究[19]、身份密碼學（identity-based cryptography，IBC）的密鑰管理方案[20]等，該類方案通過引入身份密碼學算法中陷門機制，使得交互雙方可以計算加密信息的相似度。但難點在于PKI類密鑰機制需要網(wǎng)絡中存在可信第三方機構提供密鑰的分配和證書的發(fā)放，顯然應用在分布式的機會網(wǎng)絡中很難實現(xiàn)。在之前研究基礎上，Zhou[21]提出分布式的密鑰管理，網(wǎng)絡中每個節(jié)點均平等不存在第三方機構，通過門限算法分配私鑰，但這種機制有一個隱藏的前提：大多數(shù)節(jié)點之間必然存在一條路徑，這顯然與機會網(wǎng)絡基礎意義相背。此外更有許多自組織密鑰管理體系，但是很容易受到破壞，安全隱患很大。

在PKI類加密機制很難實現(xiàn)的前提下，為了簡化加密算法，Nguyen等[22]在提出利用單一哈希運算加密用戶的信息表格完成對用戶隱私的保護。哈希算法的計算開銷較小，對網(wǎng)絡性能影響較小，但此方案中由于單一哈希運算將信息表中信息逐一加密，用戶信息極容易受到字典攻擊。Parris等[23]通過引入多組真實數(shù)據(jù)集分析社會機會網(wǎng)絡，并加入大數(shù)據(jù)集合查找算法Bloom-Filter來處理節(jié)點的朋友列表，建立可靠的隱私保護模型，但Bloom-Filter本質(zhì)也是基于哈希算法的快速查找算法，列表信息逐條加密易遭受逆向攻擊。

本文提出一種保護社會機會網(wǎng)絡中節(jié)點社會關系隱私保護方案?；谀壳吧鐣C會網(wǎng)絡隱私保護方案，并運用于SRSNs（自我報告型社會網(wǎng)絡協(xié)議，self-reported social networks）路由協(xié)議中，解決社會機會網(wǎng)絡中用戶隱私泄露的問題。加密后的社會信息，通過比對簽名數(shù)據(jù)相似性來代替原始數(shù)據(jù)相似性，從而完成路由判決，避免了公鑰機制中密鑰的分發(fā)困難和簡單哈希運算易被字典攻擊破解的問題。最后，通過隱私保護方案在社會機會網(wǎng)絡中的應用，在真實數(shù)據(jù)集SASSY的基礎上完成仿真。

1 局部敏感哈希算法

局部敏感哈希算法本身是一種對數(shù)據(jù)進行快速相似性檢索算法，根據(jù)數(shù)據(jù)位置敏感特性完成哈希運算。

定義1 設距離r2>r1>0，p1、p2為Hash函數(shù)H={h|h:Rd→U}的返回概率，U為映射后的集合。若稱H={h|h:Rd→U}是（r1，r2，p1，p2）敏感的，點p，q∈Rd，則：

1）點D(q,p>r1)，則P[h(q)=h(p)]≥p1;

2）點D(q,p

D(q,p)為2個多維對象的相異程度，當相似性滿足條件時，兩對象可有較大概率放到同一個哈希桶，映射為同一Hash值；而當相似性低時，有極低的概率映射為同一Hash值。

simhash是局部敏感哈希算法實現(xiàn)中的一種。對比單一的Hash加密運算，simhash的主要思想是降維運算，將多維的文檔信息映射成唯一的標識。并且傳統(tǒng)的Hash加密需要保證較低的碰撞率，使得相似內(nèi)容的Hash值不具有任何聯(lián)系，而simhash運算利用哈希碰撞的原理，使得相似的文檔會生成相似的simhash值，可以利用其安全計算數(shù)據(jù)相似度特性設計符合機會網(wǎng)絡的安全隱私算法。simhash算法基礎原理基于局部敏感哈希算法，加入了分詞和權重數(shù)據(jù)處理，使得整個算法更加精確實用。

2 局部敏感哈希隱私保護實現(xiàn)

本文所述的隱私保護方案所應用的社會機會網(wǎng)絡協(xié)議為Parris等所提出的社會機會網(wǎng)絡路由協(xié)議中SRSNs(self-reported social networks)協(xié)議。并在該協(xié)議基礎上，利用上文所述局部敏感哈希算法對網(wǎng)絡中節(jié)點的朋友列表進行加密處理：對于各節(jié)點公開的朋友列表進行加密處理；對不同親密度朋友做權值分配處理。節(jié)點在網(wǎng)絡中公開自身朋友列表simhash值。

2.1 基于朋友列表的SRSNs路由協(xié)議

在社會機會網(wǎng)絡協(xié)議中，若以協(xié)議采用的數(shù)據(jù)是統(tǒng)計數(shù)據(jù)或是真實數(shù)據(jù)，則機會網(wǎng)絡協(xié)議類型分為DSNs(外部信息探測型社會網(wǎng)絡協(xié)議，detected social networks)及SRSNs兩類。

1）DSNs協(xié)議：根據(jù)設備記錄的歷史相遇信息，統(tǒng)計效用值，從而分析節(jié)點的社會關系，也稱接觸網(wǎng)絡，例如Bubble Rap、SimBetS等。

2）SRSNs協(xié)議：由用戶自主記錄社交關系信息，以表明他們的社會關系。例如facebook上記錄的朋友關系，主要利用朋友間比陌生節(jié)點間更有可能相遇的原理。

由于加入了用戶的真實信息，SRSNs相比DSNs更能有效地在仿真中反映現(xiàn)實實際情況。而DSNs中由于不同協(xié)議對收集到的歷史信息利用的算法不同，而達到的效果不一。我們根據(jù)SASSY數(shù)據(jù)集中各用戶facebook中提供的朋友關系構建其m維朋友列表，則節(jié)點A朋友信息表可以定義為：

式中ai∈[1,m]為整數(shù)，表示節(jié)點A的朋友空間中第i維向量的權值。在SASSY數(shù)據(jù)集下，采用SRSNs和DSNs構建的社會關系網(wǎng)會有所不同。相遇的節(jié)點不一定是朋友關系，DSNs根據(jù)相遇歷史信息構建了更復雜的社會關系網(wǎng)。

本文在Parris等所提出基于SASSY數(shù)據(jù)集的SRSNs協(xié)議基礎上進行進一步工作。他們在實驗中只考慮了中繼節(jié)點、目的節(jié)點均為源節(jié)點朋友的情況，整個網(wǎng)絡消息的傳遞也僅限于朋友關系單線傳遞。但在大多數(shù)社會機會網(wǎng)絡中，希望消息的傳遞不限于朋友，而是可以更大范圍的交互傳遞，源節(jié)點產(chǎn)生的消息可以有效地傳輸?shù)骄W(wǎng)絡中任意節(jié)點。因此本文采用文獻[23]中所用的SRSNs協(xié)議，源節(jié)點可以向網(wǎng)絡任意節(jié)點傳輸消息，而消息向與目的節(jié)點相遇概率更大的節(jié)點傳輸。若S為一個消息源節(jié)點，假設S已知目的節(jié)點D及其朋友關系，則S產(chǎn)生的消息M一定要

向集合C中的節(jié)點傳遞。

式中：sim(,)表示2節(jié)點之間朋友列表相似度，相似度越高則代表有更多相同的朋友，即社會關系重合度高；集合C稱為理想中繼節(jié)點集，原則上S節(jié)點無法預先知道該集合的具體信息，判斷任意節(jié)點是否屬于集合C，需要網(wǎng)絡中節(jié)點公開朋友列表從而進行分析判決。

SRSNs協(xié)議中各節(jié)點與相遇節(jié)點分享朋友列表，分別對比與目的節(jié)點朋友列表相似度，完成是否傳輸消息的決策。朋友列表與目的節(jié)點朋友列表相似度越大，則與目的節(jié)點相遇概率越大。

1）節(jié)點ni與節(jié)點nj相遇分享各自朋友列表。

節(jié)點朋友信息表構造如圖1，讀取自facebook數(shù)據(jù)。

圖1 節(jié)點朋友列表

2）在社會網(wǎng)絡規(guī)律中，朋友間接觸比較頻繁而陌生人間的接觸偏少。因此假設目的節(jié)點朋友列表已知的前提下，在社會機會網(wǎng)絡中節(jié)點應將消息向與目的節(jié)點社會關系更密切的節(jié)點傳輸，相同朋友越多則社會關系越密切。

路由決策：當節(jié)點ni與節(jié)點nj相遇時，若nj為目的節(jié)點朋友，ni為非目的節(jié)點朋友（ni此時必為源節(jié)點），則ni將目的節(jié)點消息傳輸給nj；若節(jié)點ni與節(jié)點nj均為目的節(jié)點朋友，則進行社會關系值sim(ni,D)計算。社會關系值為節(jié)點ni與目的節(jié)點朋友列表相似度，相似性可用Jaccard系數(shù)計算：分別計算兩相遇節(jié)點與目的節(jié)點的社會關系值，根據(jù)式（1），消息流向C(ni,nj)集合。

2.2 simhash算法隱私保護方案

對于SRSNs類協(xié)議中用戶隱私保護方案，Parris等[24]提出模糊型隱私保護協(xié)議(obfuscated social network routing，OSRN)及數(shù)據(jù)修改型隱私保護協(xié)議 (statisticulated social network routing，SSRN)這

2種隱私保護方案。本文提出使用simhash算法的simSRN方案來處理朋友列表以達到保護用戶隱私及計算朋友相似度的目的。simhash算法是更加貼近實際應用的一種局部敏感哈希加密算法[25]，對于社會機會網(wǎng)絡中節(jié)點的朋友列表，每個朋友的親密關系均不相同，代表的權值也不同。運用simhash算法可以更全面反映用戶的朋友關系，朋友列表中元素的順序也將影響最終的朋友列表的簽名值。simhash算法可以將信息表整體進行加密運算并且對比兩信息表相似度，解決了對信息表中各元素逐一加密并檢索的繁瑣和易被字典攻擊的問題。

社會機會網(wǎng)絡中，節(jié)點ni的朋友列表可根據(jù)數(shù)據(jù)集中各節(jié)點的facebook通訊錄、手機通訊錄收集。 nm,···,na,···,nx為節(jié)點ni的通訊錄聯(lián)絡人，即為節(jié)點ni朋友。對于本文中朋友的權值為朋友親密程度，基于信息表生成simhash簽名步驟如下：

1）對于節(jié)點ni的m維朋友信息表Fni是按照朋友的關系程度順序排列的，則依序為Fni中的各節(jié)點取權值 {1,2,···,m}。

2）為了保護朋友列表信息隱私，對Fni使用K維哈希函數(shù)，本文使用FNV哈希算法，Hash的位數(shù)采用64位。不同的哈希算法會產(chǎn)生不同位數(shù)的Hash值，位數(shù)越多最后匹配結(jié)果越精確。

V(v1,v2,···,vf)

3）將一個f維的向量 初始化；f位的二進制數(shù)B初始化為0；

通過上述步驟將節(jié)點ni的通訊錄生成為n位的簽名值，將計算通訊錄相似度問題轉(zhuǎn)化為比較2個通訊錄簽名值的問題。

simhash算法由隨機超平面算法原理演變而來，其返回概率與余弦相似度有關，即simhash屬敏感LSH函數(shù)族，

simhash可以定義為

式中w為文檔向量。

本文哈希算法使用FNVhash算法，F(xiàn)NVhash屬于非加密哈希函數(shù)，對比MD5等哈希函數(shù)保持較低的碰撞率，比較適合字符串較短的哈希場景。取初始Hash值Hhash，并設置FNV用于散列的質(zhì)數(shù)Fprime。對初始Hash值Hhash進行n位的取模運算：

哈希函數(shù)一般適用移位和乘除法來實現(xiàn)，函數(shù)一般都比較精簡，算法復雜度比較低。哈希函數(shù)的移位和乘除法可能會導致數(shù)據(jù)丟失，這也是哈希不可逆的原因。將朋友列表中每個分詞分別生成8位數(shù)據(jù)字符串Odata，則每個分詞通過FNVhash算法得到的Hash值Hvalue為

對于朋友列表分詞處理，facebook數(shù)據(jù)中包含了朋友的聯(lián)系頻率。但單獨以頻率計算各分詞的權值無法同等地表述各個節(jié)點的朋友關系，因此對于朋友的權值處理以各節(jié)點朋友列表大小為極限值，降序賦予各分詞的權值

則n維的節(jié)點ni朋友列表可由向量來表示。向量V中各向量累加后可得n位的簽名bf。最終simhash的簽名Hash值B由bf各位比較獲得。

社會機會網(wǎng)絡中每個節(jié)點公開自己的simhash簽名，從而代替自身朋友信息列表。此時sim(i,j)可統(tǒng)計simhash簽名相似度，估計i、j節(jié)點重要朋友相似度。

兩節(jié)點相遇時，對比各自簽名與目的節(jié)點簽名的相似程度，最終消息將根據(jù)式（1）流入流向合。此時中間節(jié)點ni與目的節(jié)點D相似度，即中間節(jié)點與目的節(jié)點社會關系強度可以根據(jù)二進制數(shù)值漢明距d來計算：

2.3 安全性分析

隱私安全方案評價一般注重在信息的損失度和隱私的保密程度。

1）算法可靠性分析

simhash算法在社會機會網(wǎng)絡中將原始數(shù)據(jù)加密成哈希碼及簽名的形式，通過比對簽名的漢明距離從而近似獲得原始數(shù)據(jù)的相似度。

為了分析算法的可靠性，本文采用準確率來說明加密后的數(shù)據(jù)可以獲得與原始數(shù)據(jù)的相同結(jié)果的程度。準確率=正確轉(zhuǎn)發(fā)次數(shù)/轉(zhuǎn)發(fā)總次數(shù)。由于加密后的信息進行相似度計算時會丟失一部分信息量，OSRN方案會產(chǎn)生失誤判決(false positive)，失誤率與列表信息量以及加密位數(shù)有關；simSRN將整體信息表降維處理為哈希碼也會造成信息的部分丟失，從而導致一定的失誤判決。本文同時分析原始數(shù)據(jù)和加密數(shù)據(jù)對同一決策的結(jié)果，若轉(zhuǎn)發(fā)決策結(jié)果一致則為正確轉(zhuǎn)發(fā)。仿真中使用SASSY數(shù)據(jù)集，25個節(jié)點消息，生存時間（time to live，TTL）時間取一周，仿真時間分別取7、14、21 d，分析simSRN及OSRN方案的決策成功率。隱私保護方案準確率曲線如圖2所示。

圖2 simSRN、OSRN方案的決策總次數(shù)及成功率

OSRN方案中Bloom-filter算法中由于存在失誤率導致會存在決策錯誤，失誤率為：

式中：m為數(shù)組大??；k為哈希函數(shù)個數(shù)；n為需要插入元素個數(shù)。simhash算法存在降維操作，損失了一定信息量對決策判決有所影響，在構建的余弦相似度的超平面局部敏感哈希函數(shù)中，2個信息表A，B取同一函數(shù)值的概率分布Pa,b滿足：

2）用戶信息隱私安全性分析

原始用戶背景信息通過simhash算法加密得到simhash值，即指紋簽名。OSRN方案中將朋友列表放入Bloom-filter中進行加密并快速查找計算列表相似度，保護了用戶隱私。但由于元素的逐一加密，暴力字典破解攻擊只需將字典中元素逐一在加密算法中遍歷即可完成破解。而對于simhash降維加密算法，字典攻擊則在每次遍歷運算中需在字典中任選K維元素全排列進行破解，K為任意數(shù)，大大增加了攻擊負擔。對于大小為n個元素的攻擊字典，假設n個元素中包含需被破解的m個朋友列表元素，若Bloom-filter失誤率為f，則字典攻擊產(chǎn)生的符合元素數(shù)為m+nf個，則攻擊Bloom-filter算法加密空間時字典攻擊次數(shù)攻擊simhash加密空間的字典攻擊在實際應用中，字典數(shù)n應遠遠大于m，且對于m數(shù)值較小時失誤率f極小，可以達到0.01%以下，因此Bloom-filter算法加密空間時，字典攻擊的時間復雜度為O(n)，simhash字典攻擊的時間復雜度為O(nm)。

對哈希函數(shù)加密運算采用字典碰撞運算時，對于一個n位的哈希函數(shù)進行碰撞攻擊需要的時間復雜度是O(2n)，隨著位數(shù)增長指數(shù)大小快速增長，對于現(xiàn)有的技術而言很難在實際應用中實現(xiàn)。

simhash算法由于利用哈希碰撞的原理，使得不同順序或權值相似信息表序列通過simhash加密獲得與隱私信息表相同的簽名值，增加了字典攻擊的運算負擔，有效地抑制了字典攻擊。

3 simSRN協(xié)議仿真與性能分析

本文在ONE仿真器下對simSRN、SSRN、OSRN及SRSN算法進行仿真和性能對比，為了考察隱私保護方案對網(wǎng)絡性能的影響，以SRSN算法性能為基準，通過消息到達率和平均時延這2個指標來衡量網(wǎng)絡性能。本次仿真采用SASSY數(shù)據(jù)集，該數(shù)據(jù)集是采集圣安德魯斯大學79d的數(shù)據(jù)，實驗環(huán)境中共有25個節(jié)點，各節(jié)點為學校學生和教職工，21號至25號為學校教職工及研究生，節(jié)點間為藍牙通信模式。本文采用和文獻[21]相同的仿真環(huán)境，取數(shù)據(jù)集中其中30d的數(shù)據(jù)，節(jié)點的朋友列表取自其各自的facebook數(shù)據(jù)。仿真參數(shù)如表1所示。

表1 仿真參數(shù)

根據(jù)表1設置參數(shù)后，分別對simSRN、SSRN、OSRN及SRSN算法進行仿真。其中，SSRN算法中朋友列表采取隨機插入50%節(jié)點的處理方式；OSRN方案中Bloom-filter失誤率f設置為1%。朋友列表完全采用SASSY數(shù)據(jù)集中提供的各用戶facebook朋友列表，數(shù)據(jù)集中朋友列表中朋友個數(shù)為4~14個，為了提高仿真效率，選取的數(shù)據(jù)集中的前30d數(shù)據(jù)進行仿真。

圖3、4中反映出社會機會網(wǎng)絡消息的傳輸?shù)竭_率隨報文生命周期TTL變化情況。SSRN協(xié)議的報文轉(zhuǎn)發(fā)到達率高于其他3種采用隱私保護方案的協(xié)議，網(wǎng)絡中用戶分享各自朋友列表信息作為輔助時，可以優(yōu)化網(wǎng)絡性能。由于simhash算法計算數(shù)據(jù)相似性時將整體信息表進行降維加密處理，損失了一定的信息量，因此simSRN算法的報文轉(zhuǎn)發(fā)到達率略低于OSRN及SSRN算法，但到達率相比SRSN協(xié)議下降不到5%，基本保證了網(wǎng)絡的正常性能。simSRN算法的平均時延隨TTL的增長速度較快。

圖3 SASSY數(shù)據(jù)集下simSRN算法到達率曲線對比

圖4 SASSY數(shù)據(jù)集下simSRN算法平均時延對比

綜上所述，局部敏感哈希機制運用在機會網(wǎng)絡中可以保障網(wǎng)絡的正常性能。同時，simSRN方案可以在加密數(shù)據(jù)后以唯一Hash值來表現(xiàn)原始數(shù)據(jù)的相似度，避免了其他方案中信息表元素逐一加密，易被字典攻擊以及用戶隱私信息暴露的問題，在損失較小的網(wǎng)絡性能同時，可以將用戶隱私信息進行加密，保護用戶隱私。

4 結(jié)論

通過仿真證實了利用simhash算法進行隱私保護的可行性，并保持了良好的網(wǎng)絡性能。

1）simhash算法將隱私信息表進行降維加密處理，與OSRN算法相比更有效的抵制字典攻擊，而且敏感哈希加密后的Hash值可以計算2信息表的相似度，有效利用了加密信息。

2）由于加密后信息仍可以計算信息表相似度，可為網(wǎng)絡提供有效的輔助信息，與不采取隱私保護方案的SRSN協(xié)議相比，消息到達率下降不到5%，保證了網(wǎng)絡的正常性能。

本文方法能有效地加密，保護用戶隱私信息，相比于OSRN算法，提高了對字典攻擊的抵御能力、降低了算法復雜度，更易于應用到實際中。今后的工作應著重于對simhash算法的研究，以提高決策的成功率，提高方案的消息傳輸?shù)竭_率。