劉軒甫，劉玉梅

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

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

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

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

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

本文提出一種保護(hù)社會(huì)機(jī)會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)社會(huì)關(guān)系隱私保護(hù)方案。基于目前社會(huì)機(jī)會(huì)網(wǎng)絡(luò)隱私保護(hù)方案，并運(yùn)用于SRSNs（自我報(bào)告型社會(huì)網(wǎng)絡(luò)協(xié)議，self-reported social networks）路由協(xié)議中，解決社會(huì)機(jī)會(huì)網(wǎng)絡(luò)中用戶隱私泄露的問(wèn)題。加密后的社會(huì)信息，通過(guò)比對(duì)簽名數(shù)據(jù)相似性來(lái)代替原始數(shù)據(jù)相似性，從而完成路由判決，避免了公鑰機(jī)制中密鑰的分發(fā)困難和簡(jiǎn)單哈希運(yùn)算易被字典攻擊破解的問(wèn)題。最后，通過(guò)隱私保護(hù)方案在社會(huì)機(jī)會(huì)網(wǎng)絡(luò)中的應(yīng)用，在真實(shí)數(shù)據(jù)集SASSY的基礎(chǔ)上完成仿真。

1 局部敏感哈希算法

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

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

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

2）點(diǎn)D(q,p

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 simhash算法隱私保護(hù)方案

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

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

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

1）對(duì)于節(jié)點(diǎn)ni的m維朋友信息表Fni是按照朋友的關(guān)系程度順序排列的，則依序?yàn)镕ni中的各節(jié)點(diǎn)取權(quán)值 {1,2,···,m}。

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

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

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

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

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

simhash可以定義為

式中w為文檔向量。

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

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

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

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

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

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

2.3 安全性分析

隱私安全方案評(píng)價(jià)一般注重在信息的損失度和隱私的保密程度。

1）算法可靠性分析

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

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

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

OSRN方案中Bloom-filter算法中由于存在失誤率導(dǎo)致會(huì)存在決策錯(cuò)誤，失誤率為：

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

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

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

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

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

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

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

表1 仿真參數(shù)

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

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

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

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

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

4 結(jié)論

通過(guò)仿真證實(shí)了利用simhash算法進(jìn)行隱私保護(hù)的可行性，并保持了良好的網(wǎng)絡(luò)性能。

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

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

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