分布式在线社会网络隐私保护机制研究

陈洋荣，邢光林

中南民族大学计算机科学学院，武汉 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