基于伪随机置换的朋友发现系统

王凯月+张政宁+杜阿美+崔含笑+胡锦广

摘 要：近年来，随着移动社交软件的迅速发展，便携式移动终端已经渗透到人们生活的方方面面。在这些软件中，人们经常用到其中的一项功能—朋友发现，但是目前这个功能对于用户并不安全，大量隐私信息被云服务商所获取。针对此现象，文章基于目前隐私集合比较的现状，运用伪随机置换和安全多方计算协议并加以改进，设计出基于伪随机置换的朋友发现系统，本系统使用户找到他们集合的交集而且不泄露除交集以外的信息，具有一定推广价值。

关键词：移动社交；伪随机置换；隐私保护；朋友发现

在信息技术和互联网技术日新月异的今天，社交网络服务越来越多地被人们使用，如微信和MSN等，每个人的朋友圈也在日益扩大。朋友的朋友在社会中也发挥着重要作用，不仅体现在就业市场上，还有其他业务，如房地产市场或产品推荐。社交网络的高聚类系数[1]进一步表明，朋友的朋友是我们社会和情感环境的重要组成部分，并且可能成为我们直接的朋友。本文认为，一个共同的朋友至少表明两个人之间存在潜在的“匹配”关系。

假如两个陌生人在街上相遇时，他们想要确定是否有共同的朋友，因此需要比较他们手机的联系人，我们针对此问题进行研究。与此同时，隐私保护受到大家越来越多的关注。如今，市场上开发的移动社交软件都或多或少地存在隐私泄露的问题。据DCCI互联网数据中心和360互联网安全中心联合发布的《2014年下半年Android手机隐私安全报告》数据显示[2]，软件泄漏、系统漏洞泄漏、云端网络泄漏等都是Android手机用户隐私泄露的几大问题。如何在开放的网络环境下保障移动社交软件用户的数据安全存储和计算，成为非常紧迫和严峻的问题。

本文针对移动社交软件在生活中出现的隐私安全问题，设计出了基于安全多方计算（Secure Multi-Party Computation，SMC）和伪随机置换（Pseudo Random Permutation，PRP）的朋友发现系统。该系统在提高效率的基础上，使用了恶意模型以保证用户个人隐私的安全。

1 预备知识

2 基于伪随机置换朋友发现系统模型的建立

2.1 模型介绍

假设Alice和Bob是两个移动终端用户，简单方案如下描述：他们想在自身隐私不被泄露的条件下寻找手机通讯录里的共同好友，并且返回共同的手机联系人。基于伪随机置换朋友发现系统模型如图1所示。

本系统的具体模型如下：本系统由客户端与服务端组成，用Android手机作为客户端，电脑暂时作为一个服务端。在客户端基于PRP和SMC使用恶意服务器模型，对数据进行加密处理，并通过socket通信将加密后的数据传输至服务器。服务器经过密文对比后，返回相同的密文，然后在客户端进行密文解密后，最终得到交集。本文使用手机联系人作为集合，进行集合比较，得到相同的手机联系人信息，实现了上述的模型和方法，保护了隐私信息。

整体系统由3个线程组成，服务端和客户端相对应：（1）服务端创建组播，发送服务端的IP，客户端接收组播信息，得到服务端的IP地址；（2）服务端监控端口号5020，等待客户的密文信息，服务端不断监听5020端口，得到两组客户端集合后，与客户端建立端口号1994的TCP连接，返回交集数据，客户端提取手机联系人信息，进行加密处理；（3）服务端密文对比，返回客户端结果，客户端解密服务端返回信息并显示。

2.2 模型分析

2.2.1 恶意服务器模型

以前的协议只能对半诚实的服务器保证安全，因为服务器可以返回任意结果作为交集，而客户端并不知道这是否为真正的交集。为了克服这一点，本文作了如下改善：

设置和输入：让F：{0，1}k×U→{0，1}≥K为一个PRP和t，λ≥1.P1和P2分别将集合S1?U和S2?U作为输入，而服务器没有输入。

（1）P1选择集，这样，并把P2发送他们；（2）P1检查，构造正确，否，中止；（3）P1和P2使用FCT同意一个随机位键K；（4）对于每一方，发送集合Ti=πi（FK（Siλ+Δi）） 到服务器，πi是一个随机排列?i=D0+Di；（5）服务器返回交集I=T1∩T2；（6）每一方Pi中止，如果：（a）D0 FK-1（I）或Di∩FK-1 （I）≠?；（b）存在x∈Si，x||α∈FK-1（I）和x||β?FK-1 （I）；（7）每一方计算和输出（FK-1 （I）-D0 ）-λ。

2.2.2 洗牌算法

洗牌算法是对一组起始数列中的各个元素的位置进行重新调整，以此得到新的数列。结合本文背景，应用的洗牌算法如下：

已知有N个联系人，在洗牌前将联系人信息放在数组array[N]中。令i=N；对随机数发生器进行初始化，随机取（1～i）之间的一个联系人，与array[i]交换；i减1；如果i>1，则跳到步骤2；完成洗牌。

因为在该算法中，本文将余下的联系人中的最后一张位置调整到刚抽掉的位置上，而不是将抽掉的联系人后面部分全部前移，所以在时间以及空间复杂度上都有较好的表现。

3 结语

针对当前朋友发现系统存在的隐私泄露问题，本文运用伪随机函数、混淆填充、洗牌算法对数据进行处理，保证了用户隐私数据的安全性，使其可以抵御社交网络的各种攻击，使用户之间进行安全的信息匹配，达到了隐私保护的效果。在隐私保护越来越成为热点的趋势下，如何降低隐私保护方法的计算复杂度，提高服务质量，都有待进一步研究。

作者简介：王凯月（1995— ），女，河南新乡，本科。

[参考文献]

[1]LUCIANODA FC，OSVALDO N. OLIVEIRA JR，et al. Analyzing and modeling real-world phenomena with complex networks：a survey of applications[J].Advances in Physics，2011（3）：329-412.

[2]蔡丽华.浅谈如何正确处理群众文化两个效益的关系[J].华章， 2011（1）：210-211.

[3]GOLDWASSER S. Multi party computations：past and present[C].Washington：Proceedings of the 16th annual ACM symposium on principles of distributed computing，1997：21-24.

[4]YAO AC. Protocols for secure computations[C].Washington：Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science，2008：160-164.

[5]EMILIANO D C，GENE T. Experimenting with fast private set intersection[J].Trust and Trustworthy Computing，2012（7）：55-73.

[6]GOLDREICH O， MICALI S， WIGDERSON A. A completeness theorem for protocols with honest majority[C].New York：Proceedings of the 19th Annual ACM Symposium on Theory of Computing，1987：218-229.

[7]GOLDREICH O. Secure multi-party computation [EB/OL].（1998-04-10）[2017-07-10].http：//www.wisdom.weizman.ac.il/oded/pp.html.

[8]RAINER A，RUEPPEL.計算机数据保护—序列密码的分析与设计[M].吕佩尔，译.北京：人民邮电出版社，1988.

[9]WADE T，LAWRENCE CW.密码学概论[M].邹红霞，译.北京：人民邮电出版社，2004.

[10]DAVID S.数据保密与安全[M].蔡建，梁志敏，译.北京：清华大学出版社，2005.

[11]ROGAWAY P，BELLARE M，BLACK J，et al. OCB：a block-cipher mode of operation for efficient authenticated encryption[J].Acm Transactions on Information & System Security，2001（3）：196-205.

Abstract： In recent years， with the rapid development of mobile social software， portable mobile terminals have penetrated into all aspect of peoples lives. In these software， people often use one of these functions——friend find. But this function is insecure for subscribers currently， vast quantities of privacy information is obtained by cloud service providers. Aiming at this phenomenon， the paper based on the current situation of comparison of privacy collections， friend find system based on pseudo random permutation is designed by using pseudo random permutation and secure multi-party computation protocol to improve. The system allows users to find the intersection of their collection and do not disclose information other than the intersection， with a certain value to promote.

Key words： mobile social； pseudo random permutation； privacy protection； friend find