分布式在線社會網絡隱私保護機制研究

陳洋榮，邢光林

中南民族大學計算機科學學院，武漢 430074

分布式在線社會網絡隱私保護機制研究

陳洋榮，邢光林

中南民族大學計算機科學學院，武漢 430074

傳統的在線社會網絡都是中央集權式網絡，其服務主要是集中化管理，并不能為用戶提供在多個在線社會網絡之間分享信息的服務[1]。假如一個用戶對很多在線社會網絡都感興趣，就必須要逐一注冊，這樣既會浪費用戶的大量時間，因為用戶不能將一個在線網絡中的好友數據移植到另一個在線網絡；又會導致嚴重的后果，因為用戶的個人信息分布在多個在線社會網絡中，不利于用戶本人對個人信息的管理和保護，從而導致隱私信息泄露，給用戶帶來不同程度的危害。因此，分布式在線社會網絡就成為當前一個熱門的研究方向。

在隱私保護方法上，傳統的基于證書的公鑰加密法PKI（Public Key Infrastructure）廣為人知，它是利用數字證書核實用戶身份的真實性，并分發給用戶密鑰，這些數字證書需要一個權利機構來統一管理，權利機構（通常被假定是可靠的）以一定的規則發布、更新、撤銷密鑰，如果權利機構存在惡意攻擊性，就給證書管理帶來了巨大的挑戰。而在1984年由A.Shamir提出設想[2]，直到2001年才由斯坦福大學和加州大學戴維斯分校的研究人員具體實現的一種基于IBE的隱私保護方案[3]，在一定程度上改進了傳統的公鑰加密方法，它不需要數字證書，但卻需要一條安全通道，這在現實網絡中是很難保證的。

1 相關工作

近年來，IBE加密機制在社會網絡隱私保護方面被廣泛應用，但隨著用戶需求的不斷變化以及攻擊方法的多樣化發展，傳統的IBE隱私保護機制已經不能滿足在線社會網絡的需要。因此，基于IBE的分布式在線社會網絡逐漸被研究者提出，用來解決安全密鑰發布問題，擬實現真正意義上的多網站融合[4]。傳統的IBE隱私保護方案在2001年被設計出后，許多密鑰發布協議被提出，D.Sliva提出了最重要的幾種基于ID的密鑰管理方案，并討論了它們的優勢和劣勢，比較了它們的主要特點[5]。N.P.Smart提出了基于ID的身份驗證密鑰協商協議，并對該協議的屬性進行了討論[6]。

分布式在線社會網絡在近三年才逐漸受到關注，S. Buchegger等人提出了一種分布式的點對點網絡結構，并帶加密方法的隱私保護機制，為了驗證這種機制的靈活性，他們還設計了相關協議實現在線社會網絡的分布化[7]。A.Shakimov在他的研究中給出了三種在線社會網絡的分布機制，網絡中的用戶將個人信息存儲在本地機器上，本地機器自組織成為多個點對點覆蓋網絡，擁有本地機器的用戶有權為自愿分享信息的社交網站建立覆蓋網絡[4]。隨后，一種基于點對點的在線社會網絡結構被提出，避免了惡意網絡服務提供商的集中化控制[8]。

A.Shamir私密共享方案[9]首次提出了私密分片的概念。K.Paterson提出了基于多個KGC（Key Generate Center）發布獨立私鑰，并由用戶將獨立私鑰結合形成完整私鑰的方案[10]。B.Parno等提出了基于路由器級方案，能控制拒絕能力攻擊到指定的區域或鄰居[11]。X.Li為分布式的P2P（Peer-to-Peer）網絡提出的基于信任度模型方案[12]。N.Ryu提出了基于IBE的新的ID分配方案，由于傳統的IBE加密方案執行時間短[13]，該方案的執行成本是很低的，因此相關的身份服務可以擴展到數百萬用戶數量的P2P網絡[14]。

上述研究工作在一定程度上保護了用戶的隱私信息，但也存在一定的缺陷：多數研究方案都需要安全通道，且部分研究中提到的KGC可能模仿網絡中的用戶獲取用戶私鑰。因此，為了在不需要安全通道的情況下，提供安全密鑰發布服務，本文提出了一種基于密鑰隱私機構（KPA）和隱私密友（PC）的密鑰發布方案。其中KPA由專門從事隱私保護的機構擔任，PC由多個在線社會網絡的網絡服務提供商擔任。若是網絡中的PC惡意攻擊，則會引發該網絡中的內部攻擊。為了保證PC的可靠性，本文采用拜占庭容錯協議來對其可靠性[15]進行驗證。實驗結果表明，本文設計的方案具有較強的可行性，并能支持大規模的在線社會網絡，具有較強的適應性。

2 方案設計

針對基于IBE的在線社會網絡，本文提出了基于密鑰隱私機構（KPA）和隱私密友（PC）的密鑰發布方案，該方案具有較強的可行性和適應性。首先給出方案中用到的關鍵實體以及方案的具體實現步驟。

方案中用到的關鍵實體，KPA：可以被認為是一個核心服務器，它由專門的隱私保護公司（機構）來擔任，它的功能相當于IBE加密方案中的KGC。在本方案中，假定KPA始終有效且可靠。PC：PC可以從多個在線社會網絡的網絡服務提供商中選擇組成PC群組，他們不需要像KPA可靠性那么高。因此，惡意攻擊者可能會讓某些網絡服務提供商妥協，執行內部攻擊（Insider-Attack）。用戶：在線社會網絡中注冊的普通用戶，他們很容易受到各種類型的攻擊。

該方案的兩個關鍵技術：（1）它能在不需要安全通道的情況下，提供安全可靠的密鑰發布機制。這樣才能抵抗中間人攻擊、內部攻擊等。（2）由于PC群組成員的可靠性是隨機化的，本方案需要設計一個算法來識別惡意的PC，并將其從PC群組中刪除。

2.1 方案的具體實現

2.1.1 用戶注冊過程

在一個用戶要加入某個在線社會網絡前，要先通過KPA注冊。首先用戶A向KPA發送注冊請求，KPA收到請求后，返回給用戶A相關的注冊信息。在真實的網絡中，KPA和A之間的通信可能會被截獲或篡改，因此本文借鑒A.Shamir的私密共享方案來保護兩者之間的通信，防止注冊信息丟失，具體實現：將用戶A的注冊信息分割為num個分片，利用這個方案即使用戶的注冊信息被篡改或截獲，只要用戶能收集到k個以上不同的分片，就能恢復用戶的注冊信息。用戶注冊的具體步驟如下：用戶A向KPA發送請求注冊的消息，請求消息中附帶用戶A自身的賬號。KPA收到請求消息后，生成用戶A對應的注冊信息Information-A（ID-A，Explanation-A），ID-A是用戶A的身份信息，Explanation-A用來證明用戶A是否已注冊，并將注冊信息分為num個分片(Information-A1，Information-A2，…，Information-Anum)，分發給num個不同的PC。PC將收到的信息分片返回給用戶A。方案的流程圖如圖1所示。

圖1 用戶注冊流程圖

第一步：發送請求的過程中，用戶A可以通過中間人PC或者網站提供的自動服務機制找到KPA，之后發送請求消息給它。

第二步：KPA生成的Explanation-A可以看作是ID-A認證證書，是KPA生成的密鑰和ID-A的映射，即Explanation-A=MAP（ID-A，Key-KPA），如果注冊信息的分片數目num設置恰當，在真實的在線社會網絡中，惡意攻擊者要想獲得用戶注冊信息的k個分片是非常困難的。

第三步：用戶A收到來自一個PC的信息分片后，首先檢查賬號，若賬號信息和發送請求時的賬號相同，用戶A接受這個分片，若不相同，就忽略此消息。只要用戶A在限定的時間段內能收到不同PC發送來的多于k個信息分片，就能獲取注冊信息Information-A（ID-A，Explanation-A）。如果用戶A不能收到多于k個信息分片，用戶A就得返回到注冊過程的第一步，向KPA重新發送注冊請求。

2.1.2 注冊過程中的相關問題

注冊過程中num和k的設定問題：num的值沒有嚴格的限制，因為一個簡單的十六位運算器就能支持有64 000個分片的應用程序。k的值借鑒A.Shamir的閾值方案(k,n)設定：k=[n2]+1，這樣的k值滿足：任意k個分片或更多分片能恢復注冊信息Information-A。任意k-1個分片或更少分泄露，仍可以保證注冊信息Information-A的安全。

注冊信息Information-A恢復：采用多項式插值法，令a0=D=Information-A，將D分為num片，分別是D1,D2,…,Dnum，取多項式：

方程（1）中有k個未知數，若想求出，需要有k個方程。因此若給定k個不同的Di分片，即求出方程中的k個系數，從而得到D=p(0)。少于k個分片就不能得到D。

2.1.3 密鑰發布過程

利用IBE加密方案，結合一個KPA和PC群組為用戶分配私鑰。用戶通過PC這個中間人和KPA通信獲得私鑰，這樣就省去了安全通道。惡意攻擊者想要竊取用戶的私鑰，就要攻破KPA和PC群組成員，這對攻擊者來說是不容易完成的。具體步驟：前期工作：用戶A完成注冊過程，獲得注冊信息。KPA選定私鑰，將其分為m個分片(PK1，PK2，…，PKm)，PC群組成員和KPA協作完成密鑰的生成和發布，任何k個不同的PC協作，就能獲取這個私鑰（利用2.1.2的方案）。用戶A向KPA發送請求消息獲取私鑰，請求消息中附帶用戶A的賬號信息。KPA收到消息后，檢查注冊信息，確認用戶A已經注冊后，生成其私鑰PK-A（Private Key）并分片。KPA隨機選擇PC群組的部分成員，將私鑰分片發送給他們。用戶A向PC群組成員發送請求，請求他們提供密鑰發布服務。PC收到請求核實A已注冊后分配給A私鑰分片。用戶A收到不同的PC發來的至少k個私鑰分片后，將它們結合起來，獲得自己的私鑰，若沒有k個，用戶A就返回到第二步。密鑰發布過程的流程圖如圖2所示。

上述過程中，如果用戶A的隱私信息受到攻擊，只要用戶A重新向PC發送請求，在限定的時間段內PC群組成員返回給用戶k個以上的私鑰分片，用戶A就能恢復自身的完整私鑰。本方案的私鑰發布過程能有效防止中間人攻擊、內部攻擊。

圖2 密鑰發布流程圖

2.2 關鍵技術

2.2.1 PC群組成員選定

方案中的PC群組是從多個在線社會網絡的網絡服務提供商（ISP）中選擇。盡管不要求他們像KPA可靠性那么高，但還是要盡量避免把惡意的ISP選定為PC，這樣能保證網絡免受內部攻擊。因此如何選擇PC對本方案來說是非常關鍵的。本文中采用拜占庭容錯BFT（Byzantine Fault Tolerance）協議解決PC選定問題。KPA想要驗證PC的可靠性，它會發送一個驗證詢問給PC。如果PC是惡意攻擊者，它會向KPA暫時隱藏惡意行為，因此只有PC在不確認發送者是誰，才會達到驗證效果，這就要求KPA必須采取匿名查詢。

本文設計的驗證方案是：在執行選定過程前，KPA首先隨機選定部分用戶作為轉換組成員FG（Forward Group），假定成員數為Number，他們協助KPA完成PC群組成員的選定。

驗證步驟：

（1）KPA首先驗證FG成員是否都有k個以上的私鑰分片。

（2）KPA隨機選擇一個注冊用戶，把他的賬號信息和密鑰(IDi,PKi)發送給FG的一個成員，依次選擇Number個用戶的信息發送給FG的全部成員。

（3）收到(IDi,PKi)后，FG成員Numberi向PCi發送請求，這個階段和用戶注冊過程類似。只要PCi擁有對應的私鑰分片，就可以將其返回給Numberi。最后每個FG成員獲得一個私鑰分片。

（4）FG成員收到私鑰分片后，回應KPA的驗證請求。KPA核實收到的私鑰，是否多于個私鑰被核實正確（floor：向下取整），則PCi是對應私鑰分片的真正擁有者，否則該PCi可能成為惡意攻擊者，將該PCi移出PC群組。

通過上述驗證過程，PC群組成員的數目會降到一個滿足要求的合適值。

2.2.2 閾值num設定

在用戶注冊階段，提出閾值num的設定對保護用戶隱私會起到重要的作用，這里給出閾值num的取值范圍。假定PC群組成員共有N個，網絡結構圖的平均查找路徑（這里特指用戶和PC間的路徑）長度為L，網絡中某個用戶在某一時刻成為惡意攻擊者的概率定義為p。

為了保證本文中設計的方案免受共謀攻擊，閾值num要比帶有危險性的路徑總數目大。帶有危險性的路徑是指并不是所有節點用戶都是惡意攻擊者的路徑。因為網絡中某個用戶成為惡意攻擊者的概率為p，因此一條路徑是危險性路徑的概率為：1-(1-p)L。可得到危險性路徑的總數為：n=N·[1-(1-p)L]。因此：num＞n。為了用戶隱私信息避免遭受拒絕服務攻擊，保證服務質量，應確保網絡用戶能接收到足夠用的信息分片，因此閾值num要比安全路徑的數目小，即：num＜N-n。

假設一個社交網站有10萬個用戶，逐漸增加惡意用戶到網站中，考慮最壞情況，每個惡意用戶能攻擊正常用戶和PC間的所有路徑，手動以0.1%的幅度增加惡意用戶的數量，依據上述閾值num的設定方案，得到一條路徑帶有危險性的概率是在公式中b=5。模擬實驗的結果證實上述方案是可行的。

3 實驗評估

本文主要評估KPA和PC在密鑰發布過程中的性能，表1中的數據給出了IBE加密方案的各個操作的執行時間（機器配置：英特爾四核4 GB內存Win7操作系統）。

表1 IBE加密方案的各個操作的執行時間

本文先從理論模型中得出結果，之后探討本文方案能支持的網絡規模。從密鑰發布過程和A.Saxena的相關研究，可得KPA執行匹配操作1次、乘法操作3次，PC執行匹配操作1次、乘法操作5次，因此，利用表1的數據可計算出密鑰發布過程的執行時間Time(KPA)=15 ms,Time(PC)=17 ms。

為了評估本方案能支持的用戶數量，定義f是一個用戶請求獲取私鑰的頻率，R是用戶的CPU占用率，P是一個PC群組成員被利用的概率，Number-KPA定義為KPA一個時間段能服務的最大用戶數量。Number-PC定義為PC在一個時間段能服務的最大用戶數量。

表2 R=0.6,P=0.8時，KPA和PC在單位時間內服務的用戶數和f的關系

從表2可以看出，如果用戶每一個小時申請一次私鑰，KPA和PC在1秒時間內服務的用戶數量均可達105人，而在現實的社交網絡中，用戶申請私鑰的頻率是非常低的，因此本文的密鑰發布方案能支持較大規模的網絡。

4 結語

為采用基于身份加密（IBE）的分布式在線社會網絡，提出了基于密鑰隱私機構（KPA）和隱私密友（PC）的密鑰發布方案，這是少見的協作解決安全密鑰發布問題的機制。本方案采用KPA和PC協作向用戶發布私鑰。雖然這種密鑰發布機制還在探索中，本文基于理論的證明得出這樣的結論：該方案的核心理念是可行且有效的。在以后的工作中，希望能將本方案逐步擴展到真實的分布式在線社交網絡中，這將是一個重要的研究方向。實驗結果表明，基于密鑰隱私機構（KPA）和隱私密友（PC）的密鑰發布方案執行高效，并能夠支持大規模的在線社交網絡。

[1]羅亦軍，劉強，王宇.社會網絡的隱私保護研究綜述[J].計算機應用研究，2010，27（10）：2601-2604.

[2]Shamir A.Identity-based cryptosystems and signature schemes[C]//Proceedings of International Cryptology Conference，University of California，Santa Barbara，1984：47-53.

[3]Bnoeh D，Franklin M K.Identity-based encryption from the weil pairing[C]//Proceedings of International Cryptology Conference，University of California，Santa Barbara，2001：213-229.

[4]Shakimov A，Varshavsky A，Cox L P，et al.Privacy，cost，and availability tradeoffs in decentralized OSNs[C]//Proceedings of the 2nd ACM Workshop on Online Social Networks.New York：[s.n.]，2009：13-18.

[5]Sliva D.Identity-based key management in mobile ad hoc networks：techniquesandapplications[J].WirelessCommunications，IEEE，2004，15（5）：46-52.

[6]Smart N P.Identity-based authenticated key agreement protocol based on Weil pairing[J].Electronics Letters，2002，38（13）：630-632.

[7]Buchegger S，Schioberg D，Vu L H.PeerSoN：P2P social networking-earlyexperiencesandinsights[C]//Proceedings of the Second ACM EuroSys Workshop on Social Network System，Berlin，Heidelberg，2009：1-10.

[8]Cutillo L A，Molva R，Strufe T.Privacy preserving social networking through decentralization[C]//Proceedings of the 6thInterntionalConferenceonWirelessOn-Demand Network Systems and Services.USA，Piscataway：IEEE，2009：145-152.

[9]A.Shamir.How to share a secret[J].Commun ACM，1979，11（22）：612-613.

[10]Paterson K.Cryptography from Pairings：a snap shot of current research[J].Information Security Technical Report， 2002，7（3）：41-54.

[11]Parno B，Wendlandt D，Shi E，et al.Portcullis：protecting connection setupfrom denial-of-capability attacks[J].ACM SIGCOMM Computer Communication Review，2007，37（4）：289-300.

[12]Li X，Ling L.PeerTrust：supporting reputation-based trust for peer-to-peer electronic communities[J].IEEE Transactions，Knowledge and Data Engineering，2004，16（7）：843-857.

[13]Tao Y，Yong T L，Bo K L，et al.On key issuing privacy in distributed online social networks[C]//Proceedings of Conference on Fuzzy Systems and Knowledge Discovery，2012：2497-2501.

[14]Ryu S，Traynor P，McDaniel P D.Leveraging identity-based cryptography for node ID assignment in structured P2P systems[J].IEEE Transactions on Parallel and Distributed Systems，2009，20（12）：1803-1815.

[15]Dolev D.The byzantine generals strike again[J].ACM Transactions，Programming Languages and Systems，1982，3（1）：14-30.

CHEN Yangrong,XING Guanglin

College of Computer Science,South-Central University for Nationalities,Wuhan 430074,China

This paper proposes a secure key issuing scheme based on Key Privacy Authority（KPA）and Privacy Chum（PC）,for the Distributed Online Social Networks using Identity-based Encryption（IBE）.The scheme resolves secure key issuing without secure channels.In the scheme,KPA and PC can’t imitate users in networks to gain users’key.The results show that this scheme is efficient and strong adaptability,and can support large scale Online Social Networks.

privacy protection;identity-based encryption;key privacy authority;privacy chum;secure key issuing;distributed online social networks

為基于身份加密（IBE）的分布式在線社會網絡，提出了一種基于密鑰隱私機構（KPA）和隱私密友（PC）的密鑰發布方案，該方案解決了在沒有安全通道情況下的安全密鑰發布問題。方案中KPA和PC都不能通過效仿網絡中的用戶獲得用戶密鑰。結果表明該方案高效且適應性強，并能支持大規模的在線社會網絡。

隱私保護；基于身份加密；密鑰隱私機構；隱私密友；安全密鑰發布；分布式在線社會網絡

A

TP309

10.3778/j.issn.1002-8331.1212-0284

CHEN Yangrong,XING Guanglin.Research on privacy protection mechanism in distributed online social networks.Computer Engineering and Applications,2014,50（22）：118-121.

陳洋榮（1989—），女，研究生，研究領域為分布式在線社會網絡安全；邢光林（1972—），男，碩士生導師，副教授，研究領域為訪問控制、安全工作流。E-mail：cyr742877588@sina.com

2012-12-24

2013-02-05

1002-8331（2014）22-0118-04

CNKI網絡優先出版：2013-03-13,http://www.cnki.net/kcms/detail/11.2127.TP.20130313.1455.028.html