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

劉軒甫，劉玉梅

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

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

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

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

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

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

1 局部敏感哈希算法

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

定義1 設距離r2>r1>0，p1、p2為Hash函數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是局部敏感哈希算法實現中的一種。對比單一的Hash加密運算，simhash的主要思想是降維運算，將多維的文檔信息映射成唯一的標識。并且傳統的Hash加密需要保證較低的碰撞率，使得相似內容的Hash值不具有任何聯系，而simhash運算利用哈希碰撞的原理，使得相似的文檔會生成相似的simhash值，可以利用其安全計算數據相似度特性設計符合機會網絡的安全隱私算法。simhash算法基礎原理基于局部敏感哈希算法，加入了分詞和權重數據處理，使得整個算法更加精確實用。

2 局部敏感哈希隱私保護實現

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

2.1 基于朋友列表的SRSNs路由協議

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

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

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

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

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

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

向集合C中的節點傳遞。

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

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

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

節點朋友信息表構造如圖1，讀取自facebook數據。

圖1 節點朋友列表

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

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

2.2 simhash算法隱私保護方案

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

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

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

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

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

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

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

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

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

simhash可以定義為

式中w為文檔向量。

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

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

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

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

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

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

2.3 安全性分析

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

1）算法可靠性分析

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

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

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

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

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

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

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

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

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

3 simSRN協議仿真與性能分析

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

表1 仿真參數

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

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

圖3 SASSY數據集下simSRN算法到達率曲線對比

圖4 SASSY數據集下simSRN算法平均時延對比

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

4 結論

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

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

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

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