保护私有信息的社交网络合群判定

第36卷第5期 北京科技大学学报 Vol.36 No.5 2014年5月 Journal of University of Science and Technology Beijing May 2014 保护私有信息的社交网络合群判定 姚亦飞2区，郑榕”，尚伟昌》 1)北京科技大学计算机与通信工程学院，北京1000832)材料领域知识工程北京市重点实验室，北京100083 3)中国人民解放军63961部队，北京100012 ☒通信作者，E-mail:yao_yifei(@126.com 摘要为了解决社交网络中用户申请加入群组的合适性判断问题，将安全多方计算技术中的求和协议与秘密比较协议相 结合提出了保护私有信息的合群判定协议.其中基础协议解决一维线性模型下问题的安全求解，扩展协议对基于圆边界的多 维模型情况进行判定.针对单一申请者与网络群组多用户的特点，将问题转换为两方计算模型可实现的形式，在证明了协议 正确性的基础上分析协议的复杂度，并且利用安全视图的方法逐步验证了在协议执行过程中不会泄露任何个人的隐私数据. 实际使用中协议能够有效地回避盲目的系统推荐和管理员离线所产生的判定时延，同时保护申请者和群组成员的隐私数据 关键词社交网络：数据保密：网络安全；网络协议 分类号TP399 Privacy-preserving join decision in social networks YAO Yi-fei,ZHENG Rong,SHANG Wei-chang 1)School of Computer and Communication Engineering,University of Science and Technology Beijing,Beijing 100083,China 2)Beijing Key Laboratory of Knowledge Engineering for Materials Science,Beijing 100083,China 3)PLA Troops 63961,Beijing 100012,China Corresponding author,E-mail:yao_yifei@126.com ABSTRACT In order to decide the appropriateness of a new user applying to join in a group in the social network,a privacy- preserving protocol was designed by the secure sum protocol and secure comparison protocol.In the privacy-preserving protocol,the secure basis protocol was devised for problems under a one-dimensional linear model,and the advanced protocol for a multi-dimensional model with a circular boundary.For the case of a single applicant and a multi-user group,the solution was converted and realized in a two-party computation model.After the proof of correctness,the complexity was discussed,and there is no leaking message during the process by the analysis of data views in each step.The privacy-preserving protocol avoids not only the blindness of auto recommendation by the net-system but also the decision delay due to the administrators offline.In the meanwhile,the privacy of the applicant and group members can be protected without leaking any information. KEY WORDS social networks:security of data:network security:network protocols 随着信息通讯技术的飞速发展，社交网络在人护日渐获得重视。通过网络进行社交活动正日益普 们的生活中逐渐占据了重要地位.由工作需要或兴 及并飞速发展着，随着它的便捷性和趣味性的增长， 趣导向而联合所产生的群组在网络中正存储着大量 参与其中的用户越来越多，他们在利用网络进行社 的用户隐私信息，然而这种信息共享虽然能够促进 交的同时既希望能够获取所需的信息，为个人及合 成员之间的交流，也可能给生活和工作带来不良后 作群体谋取一定的利益，又要尽量避免将自己的私 果，甚至造成财产和声誉的损失.因此，藉由网络媒 有信息暴露在网络环境之中.这类基于协作问题的 介进行传递信息与合作计算时，个人隐私信息的保 安全解决途径的研究，对构建绿色和谐网络环境影 收稿日期：20130108 DOI:10.13374/j.issn1001-053x.2014.05.019:http://jourals.ustb.edu.cn

第 36 卷 第 5 期 2014 年 5 月 北京科技大学学报 Journal of University of Science and Technology Beijing Vol． 36 No． 5 May 2014 保护私有信息的社交网络合群判定 姚亦飞1，2) ，郑 榕1) ，尚伟昌3) 1) 北京科技大学计算机与通信工程学院，北京 100083 2) 材料领域知识工程北京市重点实验室，北京 100083 3) 中国人民解放军 63961 部队，北京 100012  通信作者，E-mail: yao_yifei@ 126． com 摘 要 为了解决社交网络中用户申请加入群组的合适性判断问题，将安全多方计算技术中的求和协议与秘密比较协议相 结合提出了保护私有信息的合群判定协议． 其中基础协议解决一维线性模型下问题的安全求解，扩展协议对基于圆边界的多 维模型情况进行判定． 针对单一申请者与网络群组多用户的特点，将问题转换为两方计算模型可实现的形式，在证明了协议 正确性的基础上分析协议的复杂度，并且利用安全视图的方法逐步验证了在协议执行过程中不会泄露任何个人的隐私数据． 实际使用中协议能够有效地回避盲目的系统推荐和管理员离线所产生的判定时延，同时保护申请者和群组成员的隐私数据． 关键词 社交网络; 数据保密; 网络安全; 网络协议 分类号 TP 399 Privacy-preserving join decision in social networks YAO Yi-fei1，2)  ，ZHENG Ｒong1) ，SHANG Wei-chang3) 1) School of Computer and Communication Engineering，University of Science and Technology Beijing，Beijing 100083，China 2) Beijing Key Laboratory of Knowledge Engineering for Materials Science，Beijing 100083，China 3) PLA Troops 63961，Beijing 100012，China  Corresponding author，E-mail: yao_yifei@ 126． com ABSTＲACT In order to decide the appropriateness of a new user applying to join in a group in the social network，a privacy￾preserving protocol was designed by the secure sum protocol and secure comparison protocol． In the privacy-preserving protocol，the secure basis protocol was devised for problems under a one-dimensional linear model，and the advanced protocol for a multi-dimensional model with a circular boundary． For the case of a single applicant and a multi-user group，the solution was converted and realized in a two-party computation model． After the proof of correctness，the complexity was discussed，and there is no leaking message during the process by the analysis of data views in each step． The privacy-preserving protocol avoids not only the blindness of auto recommendation by the net-system but also the decision delay due to the administrator＇s offline． In the meanwhile，the privacy of the applicant and group members can be protected without leaking any information． KEY WOＲDS social networks; security of data; network security; network protocols 收稿日期: 2013--01--08 DOI: 10． 13374 /j． issn1001--053x． 2014． 05． 019; http: / /journals． ustb． edu． cn 随着信息通讯技术的飞速发展，社交网络在人 们的生活中逐渐占据了重要地位． 由工作需要或兴 趣导向而联合所产生的群组在网络中正存储着大量 的用户隐私信息，然而这种信息共享虽然能够促进 成员之间的交流，也可能给生活和工作带来不良后 果，甚至造成财产和声誉的损失． 因此，藉由网络媒 介进行传递信息与合作计算时，个人隐私信息的保 护日渐获得重视． 通过网络进行社交活动正日益普 及并飞速发展着，随着它的便捷性和趣味性的增长， 参与其中的用户越来越多，他们在利用网络进行社 交的同时既希望能够获取所需的信息，为个人及合 作群体谋取一定的利益，又要尽量避免将自己的私 有信息暴露在网络环境之中． 这类基于协作问题的 安全解决途径的研究，对构建绿色和谐网络环境影

·696 北京科技大学学报 第36卷 响深远，因此成为了研究团体和科研人员关注的热 3节分析协议的复杂度和安全性，并对应用情况进 点课题. 行了探讨：最后，对全文进行总结和展望. 合群判定问题来源于社交网络的真实需要，虽 1 相关工作 然利用数据挖掘中的离群点检测算法能够得到解 决-习，然而这种算法并不是最优的方案.这是因为 1.1安全模型 社交网络中存在的团体更多的是小型群组，人数并 多用户环境下的参与者P:(i=1,2,…,n)希望 不庞大，并且合群判定通常仅仅发生在当新用户申 共同计算函数f(x1,x2,…,xn),其中x:是P:的私有 请入群的时候.在日常生活中，小型群组的创建通 信息.假设Ⅱ是能够解决问题的安全协议，那么必 常来源于线下的社会组织和团体，同时他们也希望 然能够给P:构造视图模拟器，使得仅从P:获得的中 通过网络来寻找志趣相投用户的加入.然而群组区 间数据和输出数据就可以推断出所有信息61山.形 别于大众的公开组织，前者有着明确的兴趣偏好，却 式化的描述安全协议Ⅱ为：当协议满足下述条件时 通常不会将关键的内部信息公布于众，甚至会刻意 认为协议Ⅱ能够保护私有信息地计算函数∫ 隐藏一些特征信息，这为正确判断陌生人加入群组 S(i=1,2,,n)是一个能够在概率多项式时 造成了一定的障碍.目前采取的方法主要有两种： 间完成计算的模拟器，并且 一种是由想加入群组的用户提出个人申请，并由群 {(S(xt),t1,i2,…,t-1t+1…,tn）}= 组管理员进行判定，这种方法依赖于管理员的主观 {view(x1x2,xn）,ti1,2,,-1+1,…,a}. 判断，不能代表整体的意见，同时也无法实现离线判 式中6与=f(x1,x2,…,xn),:=output(x1,x2,…, 定，如果管理员由于各种原因长期不能上线，那么申 x). 请将长时间无法得到批准：另一种方法来自于网站 对于仅有两方参加的计算，安全协议的模型定 的推荐，但由于推荐系统的不完善，通常无法满足申 义如下： 请者和群组双方的真实需求 参与方A的输入数据记为I4、输出数据记为 安全多方计算(secure multi-party computation, O,参与方B的输入数据记为Ig输出数据记为Og, SMC)技术的提出是为了解决以下问题：网络中的多 用表示双方将要执行的运算过程，则可以形式化 个用户互相不信任，他们希望能够合作执行某项计 地将协议表示为(O4,O)=(I,Is).同时，称协 算任务获得最终的结果，同时尽量不泄漏各自的私 议可安全计算需要满足以下两个条件： 有输入信息.也就是说，在分布式网络环境中的多 (1)存在无限集合D4={(I,0),i=1,2, 个用户，每人持有一些保密的数据，希望在获得基于 …},对任意的(I,0）∈D,必须满足(O,0)= 这些秘密数据进行计算的结果时，保护自己的秘密 (1,Ig): 不被其他用户猜测或推导出来.安全多方计算的概 (2)存在无限集合Dg={(I,0s）,i=1,2, 念由Yao同在1982年提出，经过Goldreich等的进一 …},对任意的(I,Og)∈Dg必须满足(04，O)= 步探讨与研究逐渐形成了为特定问题设计特定求解 (1A,1g). 方案的基本思路，在数据挖掘、信息检索、计算 1.2安全求和协议 几何、科学计算、统计分析等越来越多领域得 安全求和协议(secure sum protocol)是应用最为 到了广泛的关注.保护私有信息的离群点检测0 广泛的SMC基础协议之一，时间代价小且便于部署 是安全多方计算技术能够处理的一般性问题之一， 和执行.安全求和协议所要解决的是多方参与者合 它基于简化的抽象模型进行求解，在私有信息保护 作求加法和值的问题，其加数来源于参与者各自的 计算的应用领域具有重要的地位，也是安全的进行 私有输入，要求协议执行结束时所有人都能够获知 数据挖掘的基础和核心技术 和值结果并且无法获得他人的任何私有输入信 本文将社交网络中的小型群组抽象成简单的几 息四.可形式化地描述为：参与者P:(i=1,2,, 何模型，通过安全多方技术的安全求和与秘密比较 m)进行合作计算，X:是参与者P:持有的私有数据， 方法来实现保护隐私的合群判定.这个协议的判定 结果依赖于更广泛的成员信息，同时不会泄露单个 他们希塑通过安全求和协议获得和值∑X,同时 用户的数据.其中，第1节介绍一些相关性的研究 确保P:无法获知任何有关X:(k=1,2,…,m且k≠ 工作；第2节提出了保护私有信息的合群判定基础 )数据的信息.其中私有数据X,可能是某一个私 协议和扩展协议，并对协议的正确性进行了证明：第 有数据，也可能是参与者P:所持有的n:（n:≥I)个

北 京 科 技 大 学 学 报 第 36 卷 响深远，因此成为了研究团体和科研人员关注的热 点课题． 合群判定问题来源于社交网络的真实需要，虽 然利用数据挖掘中的离群点检测算法能够得到解 决［1--2］，然而这种算法并不是最优的方案． 这是因为 社交网络中存在的团体更多的是小型群组，人数并 不庞大，并且合群判定通常仅仅发生在当新用户申 请入群的时候． 在日常生活中，小型群组的创建通 常来源于线下的社会组织和团体，同时他们也希望 通过网络来寻找志趣相投用户的加入． 然而群组区 别于大众的公开组织，前者有着明确的兴趣偏好，却 通常不会将关键的内部信息公布于众，甚至会刻意 隐藏一些特征信息，这为正确判断陌生人加入群组 造成了一定的障碍． 目前采取的方法主要有两种: 一种是由想加入群组的用户提出个人申请，并由群 组管理员进行判定，这种方法依赖于管理员的主观 判断，不能代表整体的意见，同时也无法实现离线判 定，如果管理员由于各种原因长期不能上线，那么申 请将长时间无法得到批准; 另一种方法来自于网站 的推荐，但由于推荐系统的不完善，通常无法满足申 请者和群组双方的真实需求． 安全多方计算( secure multi-party computation， SMC) 技术的提出是为了解决以下问题: 网络中的多 个用户互相不信任，他们希望能够合作执行某项计 算任务获得最终的结果，同时尽量不泄漏各自的私 有输入信息． 也就是说，在分布式网络环境中的多 个用户，每人持有一些保密的数据，希望在获得基于 这些秘密数据进行计算的结果时，保护自己的秘密 不被其他用户猜测或推导出来． 安全多方计算的概 念由 Yao［3］在1982 年提出，经过 Goldreich 等的进一 步探讨与研究逐渐形成了为特定问题设计特定求解 方案的基本思路，在数据挖掘［4--5］、信息检索、计算 几何［6］、科学计算、统计分析等越来越多领域［7--8］得 到了广泛的关注． 保护私有信息的离群点检测［9--10］ 是安全多方计算技术能够处理的一般性问题之一， 它基于简化的抽象模型进行求解，在私有信息保护 计算的应用领域具有重要的地位，也是安全的进行 数据挖掘的基础和核心技术． 本文将社交网络中的小型群组抽象成简单的几 何模型，通过安全多方技术的安全求和与秘密比较 方法来实现保护隐私的合群判定． 这个协议的判定 结果依赖于更广泛的成员信息，同时不会泄露单个 用户的数据． 其中，第 1 节介绍一些相关性的研究 工作; 第 2 节提出了保护私有信息的合群判定基础 协议和扩展协议，并对协议的正确性进行了证明; 第 3 节分析协议的复杂度和安全性，并对应用情况进 行了探讨; 最后，对全文进行总结和展望． 1 相关工作 1. 1 安全模型 多用户环境下的参与者 pi ( i = 1，2，…，n) 希望 共同计算函数 f( x1，x2，…，xn ) ，其中 xi 是 pi 的私有 信息． 假设 Π 是能够解决问题的安全协议，那么必 然能够给 pi 构造视图模拟器，使得仅从 pi 获得的中 间数据和输出数据就可以推断出所有信息［6，11］． 形 式化的描述安全协议 Π 为: 当协议满足下述条件时 认为协议 Π 能够保护私有信息地计算函数 f． Si ( i = 1，2，…，n) 是一个能够在概率多项式时 间完成计算的模拟器，并且 { ( Si ( xi，ti ) ，t1，t2，…，ti － 1，ti + 1，…，tn ) } ≡ { viewΠ i ( x1，x2，…xn ) ，v1，v2，…，vi － 1，vi + 1，…，vn } ． 式中 ti = fi ( x1，x2，…，xn ) ，vi = outputΠ i ( x1，x2，…， xn ) ． 对于仅有两方参加的计算，安全协议的模型定 义如下: 参与方 A 的输入数据记为 IA、输出数据记为 OA，参与方 B 的输入数据记为 IB、输出数据记为 OB， 用 表示双方将要执行的运算过程，则可以形式化 地将协议表示为( OA，OB ) = ( IA，IB ) ． 同时，称协 议可安全计算 需要满足以下两个条件: ( 1) 存在无限集合 DA = { ( IAi，OAi ) ，i = 1，2， …} ，对任意的( I'A，O'A ) ∈DA 必须满足( O'A，OB ) = ( I'A，IB ) ; ( 2) 存在无限集合 DB = { ( IBi，OBi ) ，i = 1，2， …} ，对任意的( I'B，O'B ) ∈DB 必须满足( OA，O'B ) = ( IA，I'B ) ． 1. 2 安全求和协议 安全求和协议( secure sum protocol) 是应用最为 广泛的 SMC 基础协议之一，时间代价小且便于部署 和执行． 安全求和协议所要解决的是多方参与者合 作求加法和值的问题，其加数来源于参与者各自的 私有输入，要求协议执行结束时所有人都能够获知 和值结果并且无法获得他人的任何私有输入信 息［12］． 可形式化地描述为: 参与者 pi ( i = 1，2，…， m) 进行合作计算，Xi 是参与者 pi 持有的私有数据， 他们希望通过安全求和协议获得和值 ∑ m i = 1 Xi，同时 确保 pi 无法获知任何有关 Xk ( k = 1，2，…，m 且 k≠ i) 数据的信息． 其中私有数据 Xi 可能是某一个私 有数据，也可能是参与者 pi 所持有的 ni ( ni≥1) 个 · 696 ·

第5期 姚亦飞等：保护私有信息的社交网络合群判定 ·697· 隐私数据的集合{x.4lk=1,2,…,n,}内所有数的和 表1点积协议的比较 X=公m Table 1 Comparison of product scalar protocols 协议方案的特点 计算复杂度 通讯复杂度 1.3向量点积协议 借助于不可信第三方 0(1) 0(1) 点积协议(scalar product protocol)是仅有两方 利用可逆矩阵 0(n) 0(1) 参与的计算模型下的典型计算问题，被广泛应用在 通过系数矩阵转置 0(n) 0(1) 隐私保护计算领域中.点积协议帮助两个参与者安 基于茫然传送 m×0(07) 0(1) 全地计算出各自所持有的私有向量的点积，最后使 运用同态加密技术 m×0(C.) 0(1) 双方分享计算结果.其中参与者A拥有n维私有向 量X=(x1x2,…,xn),参与者B拥有n维私有向量 富翁A的财产数额为x,富翁B的财产数额为y,经 Y=(y,y2,…,y).执行协议以后A和B共享计算 过安全的秘密比较二人将知道谁更富有，同时不会 把自己的财产数额具体值泄露给对方知道.姚期智 结果，A持有u=XY+U=∑x:+,B持有，其 博士给出了一个基于域和模幂运算的解决方案，该 中v是B在协议过程中选取的随机数.同时必须保 方案的计算复杂度达到了指数量级，需要引入不可 证A对X·Y、v或者任何y:的值无从得知，B也不知 信第三方的帮助，并且判断结果仅为“大于”或者 道任何关于u或者x:的信息 “小于等于”，即无法区分“小于”和“等于”，且所比 向量点积协议通常用于构造SMC解决方案的 较的数必须是一定范围内的相近的数m. 中间核心过程。目前较常用的向量点积协议的分析 此后，Cachin C博士选择用Φ隐藏技术对秘 与对比情况如表1所示3-0.其中C。表示所采用 密比较协议进行了改良，成功地将计算复杂度降低 的同态加密算法的计算复杂度 到数据二进制表示位数的线性阶：秦静博士和李顺 1.4秘密比较协议 东博士分别采用了同态加密体制和茫然传送技术设 秘密比较协议(secure comparison protocol)是安 计出了无信息泄露的比较协议，并细分为“两个较 全多方计算技术最为重要的基础协议，被广泛地应 小的数的比较”和“任意两个数的比较”两类不同的 用于电子拍卖、在线交易、竞标等新型电子交易模式 解决算法.表2对己提出的其他秘密比较协议进行 中.它起源于姚期智博士所提出的百万富翁问题. 了对比与总结- 表2几种秘密比较协议 Table 2 Several secure comparison protocols 研究者 Rischlin M Blake I F Lin H Y 判断结果类型 >和≤ >和< >和≤ 基本思路 GM-同态加密 Paillier-同态加密 Elgamal--同态加密 通信复杂度 (1 +A)nlgN 4nlgN 6nlgN 计算复杂度 AnlgN +6An +3n 24nlgN+24n 5nlgN+4n-6 于集合{x1,x2,…,xn}的合群点 2保护私有信息的合群判定协议 协议1基础协议 本节设计保护私有信息的合群判定协议，首先 Step 1 群组成员P:(i=1,2,…,n)合作执行安 给出解决一维计算模型的基础协议，进而扩展至 多维 全求和协议，计算X= n x:从而得到隐私数据 2.1合群判定的基础协议 的平均值X; 群组特征通常具有多个属性，用以描述多种兴 Step2组内推选成员p参与下一步的秘密比 趣偏好，通过降维映射可规约成一维逻辑模型.基 较，并发起投票以确定合群阈值△x; 础协议解决以下问题：当前在线的n个群组成员P: Step3p和p'分别以X-△x和x作为私有输 具有隐私数据{x1x2,…,x},其中x:来源于第i个 入执行秘密比较协议： 成员的个人信息.申请者p具有特征数据x,协议将 Step4如果秘密比较的结果是x<X-△x,则 判定p是否适合加入该群组，亦即判断x是否应属 本协议终止并得到结论NO(表示“不合群”，即申请

第 5 期 姚亦飞等: 保护私有信息的社交网络合群判定 隐私数据的集合{ xi，k | k = 1，2，…，ni} 内所有数的和 Xi = ∑ ni k = 1 xi，k ［11］． 1. 3 向量点积协议 点积协议( scalar product protocol) 是仅有两方 参与的计算模型下的典型计算问题，被广泛应用在 隐私保护计算领域中． 点积协议帮助两个参与者安 全地计算出各自所持有的私有向量的点积，最后使 双方分享计算结果． 其中参与者 A 拥有 n 维私有向 量 X = ( x1，x2，…，xn ) ，参与者 B 拥有 n 维私有向量 Y = ( y1，y2，…，yn ) ． 执行协议以后 A 和 B 共享计算 结果，A 持有 u = X·Y + v = ∑ n i = 1 xiyi + v，B 持有 v，其 中 v 是 B 在协议过程中选取的随机数． 同时必须保 证 A 对 X·Y、v 或者任何 yi 的值无从得知，B 也不知 道任何关于 u 或者 xi 的信息［11］． 向量点积协议通常用于构造 SMC 解决方案的 中间核心过程． 目前较常用的向量点积协议的分析 与对比情况如表 1 所示［13--14］． 其中 Ce 表示所采用 的同态加密算法的计算复杂度． 1. 4 秘密比较协议 秘密比较协议( secure comparison protocol) 是安 全多方计算技术最为重要的基础协议，被广泛地应 用于电子拍卖、在线交易、竞标等新型电子交易模式 中． 它起源于姚期智博士所提出的百万富翁问题． 表 1 点积协议的比较 Table 1 Comparison of product scalar protocols 协议方案的特点 计算复杂度 通讯复杂度 借助于不可信第三方 O( 1) O( 1) 利用可逆矩阵 O( n) O( 1) 通过系数矩阵转置 O( n) O( 1) 基于茫然传送 m × O( OT1 2 ) O( 1) 运用同态加密技术 m × O( Ce ) O( 1) 富翁 A 的财产数额为 x，富翁 B 的财产数额为 y，经 过安全的秘密比较二人将知道谁更富有，同时不会 把自己的财产数额具体值泄露给对方知道． 姚期智 博士给出了一个基于域和模幂运算的解决方案，该 方案的计算复杂度达到了指数量级，需要引入不可 信第三方的帮助，并且判断结果仅为“大于”或者 “小于等于”，即无法区分“小于”和“等于”，且所比 较的数必须是一定范围内的相近的数［11］． 此后，Cachin C 博士选择用 Φ-隐藏技术对秘 密比较协议进行了改良，成功地将计算复杂度降低 到数据二进制表示位数的线性阶; 秦静博士和李顺 东博士分别采用了同态加密体制和茫然传送技术设 计出了无信息泄露的比较协议，并细分为“两个较 小的数的比较”和“任意两个数的比较”两类不同的 解决算法． 表 2 对已提出的其他秘密比较协议进行 了对比与总结［15--16］． 表 2 几种秘密比较协议 Table 2 Several secure comparison protocols 研究者 Ｒischlin M Blake I F Lin H Y 判断结果类型 ＞ 和≤ ＞ 和 ＜ ＞ 和≤ 基本思路 GM-同态加密 Paillier-同态加密 Elgamal-同态加密 通信复杂度 ( 1 + λ) nlgN 4nlgN 6nlgN 计算复杂度 λnlgN + 6λn + 3n 24nlgN + 24n 5nlgN + 4n － 6 2 保护私有信息的合群判定协议 本节设计保护私有信息的合群判定协议，首先 给出解决一维计算模型的基础协议，进而扩展至 多维． 2. 1 合群判定的基础协议 群组特征通常具有多个属性，用以描述多种兴 趣偏好，通过降维映射可规约成一维逻辑模型． 基 础协议解决以下问题: 当前在线的 n 个群组成员 pi 具有隐私数据{ x1，x2，…，xn } ，其中 xi 来源于第 i 个 成员的个人信息． 申请者 p'具有特征数据 x，协议将 判定 p'是否适合加入该群组，亦即判断 x 是否应属 于集合{ x1，x2，…，xn } 的合群点． 协议 1 基础协议 Step 1 群组成员 pi ( i = 1，2，…，n) 合作执行安 全求和协议，计算 X = 1 n ∑ n i = 1 xi 从而得到隐私数据 的平均值 X; Step 2 组内推选成员 p 参与下一步的秘密比 较，并发起投票以确定合群阈值 Δx; Step 3 p 和 p'分别以 X － Δx 和 x 作为私有输 入执行秘密比较协议; Step 4 如果秘密比较的结果是 x ＜ X － Δx，则 本协议终止并得到结论 NO( 表示“不合群”，即申请 · 796 ·

·698 北京科技大学学报 第36卷 者p不被允许加入该群组)，否则p和p以X+△x 定理2扩展协议能够正确地判断申请者是否 和x执行第二轮秘密比较协议； 适合加入群组. Step5如果秘密比较的结果为x>X+△x,则 证明：假设协议执行后的结果满足？+2- 本协议终止并得到结论NO,否则得到结论YES(表 (△x)2-2R,>2R2-x2-y2,则(X-x)2+(Y- 示“合群”，即申请者p被允许加入该群组) y)2>(△x)2,其中R1-R2=X×x+Y×y.推导过程 定理1基础协议能够正确地判断申请者是否 如一下. 适合加入群组. /(X-x)2+(Y-y)产>Ax 证明：如图1所示，如果申请者得到的判定结果 曰(X-x)2+(Y-y)2>(△x)2 为YES,则满足X-△x<x<X+△x,表示该申请者 台X2+2-2×(X×x+Y×y)+x2+y2>(△x)2 的兴趣特征属于群组偏好设置的阈值范围，与群组 台X2+2-2×(R1-R2)+x2+y2>(△x)2 团体具有相似的属性特点.其中△x是由在线的所 有参与者共同选定的阈值，因此应满足{Ix:一 台X+2-(△x)2-2R1>2R2-x2-y2 XI1i=1,2,…,n},并且群组在接纳新成员后依然保 如图2所示，此时满足点(x,y)在以(X,)为圆 持原有的兴趣特征未被改变 心、△x为半径的圆内.如果申请者得到的判定结果 为YES,表示此申请者与群组团体具有相似的属性 特点，且群组在接纳新成员后依然保持原有的兴趣 - 特征. 图1基础协议的阈值判定 Fig.1 Threshold decision of the basic protocol ● 2.2合群判定的扩展协议 ● 合群判定的基础协议是一种简约模式，是将群 (X.Y) 组兴趣特征经过降维后归约成单一属性情况下的解 ● 决方法.扩展协议针对具有两类属性的情况进行判 定.扩展协议解决以下问题：{(x,),(x2,2), …,(xnyn)}是当前在线的共n个成员P:的隐私数 据，其中(x,y:)为第i个成员的个人信息.申请者 图2基于圆边界的扩展协议 p'具有特征(x,y),协议判定p'是否适合加入该群 Fig.2 Extensible protocol based on a circular boundary 组，亦即判断(x,y)是否属于集合{(x1,y),(x2, y2),…,(xyn)}的合群点. 3协议分析 协议2扩展协议 Step1在线的n个群组成员合作执行安全求 3.1复杂度分析 和协议，计算兴趣中心(X,),其中X=上∑ 定理3（复杂度）执行基础协议（协议1）或扩 n Xi, 展协议（协议2）的计算复杂度为O(Csc),其中Cscr y=⊥ 为秘密比较协议的复杂度. n 证明：在协议1中，tep1为了计算兴趣属性的 Step2组内推选成员p参与下一步的秘密比 平均值执行了一次安全求和协议，这需要参与者P: 较，并发起投票以确定合群阈值△x; 生成n-1个随机数并进行2n-2次加法运算，同时 Step3p和p分别以(X,)和(x,y)作为私有 需要发送信息和接收信息的次数均为n次，因此 输入，合作执行点积协议计算X×x+Y×y,协议结 Step1总的时间和通讯复杂度为O(n2).Step2进 束后p持有R1=X×x+Y×y+U,p持有R2=U,其 行群内选举和投票需要O(1)时间.Step3执行一 中v是p在执行过程中选取的一个随机数； 次秘密比较协议，若结果满足条件则Step4进行另 Step4p和p执行秘密比较协议判断a=2+ 一次秘密比较协议，因此协议1至多需要进行两次 Y2-(△x)2-2R1和b=2R2-x2-y2的大小，若a> 两方的秘密比较协议即可得出结论.由于计算中心 b则得到结论YES,否则结论为NO,同时p公布判 点和商定偏好阈值的操作可以在空闲时间完成，因 断结果 此合群判定的复杂度取决于秘密比较协议的执行

北 京 科 技 大 学 学 报 第 36 卷 者 p 不被允许加入该群组) ，否则 p 和 p'以 X + Δx 和 x 执行第二轮秘密比较协议; Step 5 如果秘密比较的结果为 x ＞ X + Δx，则 本协议终止并得到结论 NO，否则得到结论 YES( 表 示“合群”，即申请者 p 被允许加入该群组) ． 定理 1 基础协议能够正确地判断申请者是否 适合加入群组． 证明: 如图 1 所示，如果申请者得到的判定结果 为 YES，则满足 X － Δx ＜ x ＜ X + Δx，表示该申请者 的兴趣特征属于群组偏好设置的阈值范围，与群组 团体具有相似的属性特点． 其中 Δx 是由在线的所 有参与者共同选定的阈值，因 此 应 满 足 { | xi － X | | i = 1，2，…，n} ，并且群组在接纳新成员后依然保 持原有的兴趣特征未被改变． 图 1 基础协议的阈值判定 Fig． 1 Threshold decision of the basic protocol 2. 2 合群判定的扩展协议 合群判定的基础协议是一种简约模式，是将群 组兴趣特征经过降维后归约成单一属性情况下的解 决方法． 扩展协议针对具有两类属性的情况进行判 定． 扩展协议解决以下问题: { ( x1，y1 ) ，( x2，y2 ) ， …，( xn，yn ) } 是当前在线的共 n 个成员 pi 的隐私数 据，其中( xi，yi ) 为第 i 个成员的个人信息． 申请者 p'具有特征( x，y) ，协议判定 p'是否适合加入该群 组，亦即判断( x，y) 是否属于集合{ ( x1，y1 ) ，( x2， y2 ) ，…，( xn，yn ) } 的合群点． 协议 2 扩展协议 Step 1 在线的 n 个群组成员合作执行安全求 和协议，计算兴趣中心( X，Y) ，其中 X = 1 n ∑ n i = 1 xi， Y = 1 n ∑ n i = 1 yi ; Step 2 组内推选成员 p 参与下一步的秘密比 较，并发起投票以确定合群阈值 Δx; Step 3 p 和 p'分别以( X，Y) 和( x，y) 作为私有 输入，合作执行点积协议计算 X × x + Y × y，协议结 束后 p 持有 Ｒ1 = X × x + Y × y + v，p'持有 Ｒ2 = v，其 中 v 是 p'在执行过程中选取的一个随机数; Step 4 p 和 p'执行秘密比较协议判断 a = X2 + Y2 － ( Δx) 2 － 2Ｒ1 和 b = 2Ｒ2 － x 2 － y 2 的大小，若 a ＞ b 则得到结论 YES，否则结论为 NO，同时 p 公布判 断结果． 定理 2 扩展协议能够正确地判断申请者是否 适合加入群组． 证明: 假设协议执行后的结果满足 X2 + Y2 － ( Δx) 2 － 2Ｒ1 ＞ 2Ｒ2 － x 2 － y 2 ，则 ( X － x ) 2 + ( Y － y) 2 ＞ ( Δx) 2 ，其中 Ｒ1 － Ｒ2 = X × x + Y × y． 推导过程 如一下． ( X － x) 2 槡 + ( Y － y) 2 ＞ Δx ( X － x) 2 + ( Y － y) 2 ＞ ( Δx) 2 X2 + Y2 － 2 × ( X × x + Y × y) + x 2 + y 2 ＞ ( Δx) 2 X2 + Y2 － 2 × ( Ｒ1 － Ｒ2 ) + x 2 + y 2 ＞ ( Δx) 2 X2 + Y2 － ( Δx) 2 － 2Ｒ1 ＞ 2Ｒ2 － x 2 － y 2 ． 如图 2 所示，此时满足点( x，y) 在以( X，Y) 为圆 心、Δx 为半径的圆内． 如果申请者得到的判定结果 为 YES，表示此申请者与群组团体具有相似的属性 特点，且群组在接纳新成员后依然保持原有的兴趣 特征． 图 2 基于圆边界的扩展协议 Fig． 2 Extensible protocol based on a circular boundary 3 协议分析 3. 1 复杂度分析 定理 3( 复杂度) 执行基础协议( 协议 1) 或扩 展协议( 协议2) 的计算复杂度为 O( CSCP ) ，其中 CSCP 为秘密比较协议的复杂度． 证明: 在协议 1 中，Step 1 为了计算兴趣属性的 平均值执行了一次安全求和协议，这需要参与者 pi 生成 n － 1 个随机数并进行 2n － 2 次加法运算，同时 需要发送信息和接收信息的次数均为 n 次，因此 Step 1 总的时间和通讯复杂度为 O( n2 ) ． Step 2 进 行群内选举和投票需要 O( 1) 时间． Step 3 执行一 次秘密比较协议，若结果满足条件则 Step 4 进行另 一次秘密比较协议，因此协议 1 至多需要进行两次 两方的秘密比较协议即可得出结论． 由于计算中心 点和商定偏好阈值的操作可以在空闲时间完成，因 此合群判定的复杂度取决于秘密比较协议的执行， · 896 ·

第5期 姚亦飞等：保护私有信息的社交网络合群判定 ·699· 即能够在O(1)次秘密比较协议时间内得到合群判 3.3应用分析 定结果.同理，协议2的执行取决于Step3的点积 由于点积协议具有可扩展性，即能够对两方的 协议和Step4的秘密比较协议，其中秘密比较协议 m维向量(x1,x2,…,xm）和（y1,y2,…,yn）计算点 的时间和空间复杂度较大，因此协议2的判定结果 积，因此对协议2进行改进可得到多维情况下的合 需要0(1)次秘密比较协议，即为O(Cp)0. 群判定协议 3.2安全性分析 Step1'n个参与者合作执行安全求和协议， 定理4（安全性）协议1（协议2）能够安全地 计算兴趣中心（X,X2,…,Xm),其中X= 得到合群判定结果. 证明：根据SMC协议的安全模型逐步分析协议 L∑ n台 1中各参与者可能获得的所有信息，并分析这些信 Step2'在线的群组成员投票选取成员p并确 息是否会造成隐私数据泄露) 定合群阈值△x: Step1执行了一次安全求和协议，参与方p:能 Step3’p和p分别以(X1,X2,…,Xm）和(x, 够获得的数据包括 x,…,x)合作参与点积协议的执行，计算结束后p view;= 持有R,=∑Xx'+v,p持有R2=,其中v是p随 {x piece.piece.,sum,,n=1,2,,n}. 其中x:是参与方P:的兴趣特征值，属于P:私有的 机选取的一个数： 保密数据，piece.4是参与方P:向P4发送的中间数 Step4'p和p进行秘密比较，判断a= ∑- 据，sum是执行求和协议得到的结果，且平均值X= sum×(1/n),n为当前在线的参与求和协议的人 (△x)2-2R1和b=2R2- (x22的大小，若a>b 数.分析数据本身代表的信息含义，Stepl阶段pP:能 则得到结论YES,否则结论为NO. 多计算得到的∑piece:其实是由一组无任何价 图3是另一种可选的合群判定模型.在这种情 的随机数所构成的和值，因此单一参与者的隐私信 况下，阈值判定的依据可选用最小二乘法或极大似 然估计，并可通过SMC基础协议实现求解.该模型 息=店 piece.k不会被泄露出去.Step 1结束后 在实际的生产生活中也有一定的适应性 各参与方获得和值sum,同时没有泄露任何个人隐 私信息 Step2的推选p与投票得到△x阶段不需要个 人数据参与计算，因此不会泄露个人隐私 Step3中p和p'参与秘密比较协议，其中p能 够获得的中间数据包括 view =Ax,pieceYES/NO) 其中X和△x来源于群组信息，YES/NO是判断结 果，同时由于秘密比较协议本身的安全性依赖于数 学中的难解问题，从而确定由piecer无法推知他 图3基于最小二乘法的扩展协议（△x为选定的阈值） 人的隐私数据 Fig.3 Extensible protocol based on the least square method (Ax for 同理，p获得的数据为viewapp={x,piecead' the selected threshold) YES/NO}也不会泄露他人的数据信息. 假设Step4需要进行另外一次秘密比较协议， 4结束语 则因为p在前后两次比较中分别选用X-△x和X+ 社交网络的使用中经常需要进行合群判定，利 △x参与计算，所得到的piece是不相同的，因此 用安全多方计算技术构建保护私有信息的解决方 两次比较并不会泄露X或△x的具体信息.所以，除 案，能够正确有效地得到申请者是否适合加入该群 申请者p‘是否适合加入该群组的合群判定结果以 组的判定结果，同时能够很好地保护用户群组中每 外，p和p都无法从协议的执行中获得其他人的隐 个人的个人隐私.该判定协议可替代社交系统的盲 私数据. 目推荐，满足管理员离线时的及时响应需求，在日渐

第 5 期 姚亦飞等: 保护私有信息的社交网络合群判定 即能够在 O( 1) 次秘密比较协议时间内得到合群判 定结果． 同理，协议 2 的执行取决于 Step 3 的点积 协议和 Step 4 的秘密比较协议，其中秘密比较协议 的时间和空间复杂度较大，因此协议 2 的判定结果 需要 O( 1) 次秘密比较协议，即为 O( CSCP ) ［11］． 3. 2 安全性分析 定理 4( 安全性) 协议 1( 协议 2) 能够安全地 得到合群判定结果． 证明: 根据 SMC 协议的安全模型逐步分析协议 1 中各参与者可能获得的所有信息，并分析这些信 息是否会造成隐私数据泄露［11］． Step 1 执行了一次安全求和协议，参与方 pi 能 够获得的数据包括 viewi = { xi，piecei，k，piecek，i，sum，X，n | k = 1，2，…，n} ． 其中 xi 是参与方 pi 的兴趣特征值，属于 pi 私有的 保密数据，piecei，k 是参与方 pi 向 pk 发送的中间数 据，sum 是执行求和协议得到的结果，且平均值 X = sum × ( 1 / n) ，n 为当前在线的参与求和协议的人 数． 分析数据本身代表的信息含义，Step1 阶段 pi 能 够计算得到的 ∑ n k = 1 piecek，i其实是由一组无任何价值 的随机数所构成的和值，因此单一参与者的隐私信 息 xi = ∑ n k = 1 piecei，k不会被泄露出去． Step 1 结束后 各参与方获得和值 sum，同时没有泄露任何个人隐 私信息． Step 2 的推选 p 与投票得到 Δx 阶段不需要个 人数据参与计算，因此不会泄露个人隐私． Step 3 中 p 和 p'参与秘密比较协议，其中 p 能 够获得的中间数据包括 viewtl = { X，Δx，piecerandom，YES /NO} ． 其中 X 和 Δx 来源于群组信息，YES /NO 是判断结 果，同时由于秘密比较协议本身的安全性依赖于数 学中的难解问题，从而确定由piecerandom无法推知他 人的隐私数据． 同理，p'获得的数据为viewapp = { x，piece' random， YES /NO} 也不会泄露他人的数据信息． 假设 Step4 需要进行另外一次秘密比较协议， 则因为 p 在前后两次比较中分别选用 X － Δx 和 X + Δx 参与计算，所得到的 piecerandom是不相同的，因此 两次比较并不会泄露 X 或 Δx 的具体信息． 所以，除 申请者 p'是否适合加入该群组的合群判定结果以 外，p 和 p'都无法从协议的执行中获得其他人的隐 私数据． 3. 3 应用分析 由于点积协议具有可扩展性，即能够对两方的 m 维向量( x1，x2，…，xm ) 和( y1，y2，…，ym ) 计算点 积，因此对协议 2 进行改进可得到多维情况下的合 群判定协议． Step 1’ n 个参与者合作执行安全求和协议， 计算 兴 趣 中 心 ( X1，X2，…，Xm ) ，其 中 Xj = 1 n ∑ n i = 1 xj，i ; Step 2’ 在线的群组成员投票选取成员 p 并确 定合群阈值 Δx; Step 3’ p 和 p'分别以( X1，X2，…，Xm ) 和( x'1， x'2，…，x'm ) 合作参与点积协议的执行，计算结束后 p 持有 Ｒ1 = ∑ m j = 1 Xj x' + v，p'持有 Ｒ2 = v，其中 v 是 p'随 机选取的一个数; Step 4’ p 和 p'进行秘密比较，判断 a = ∑ m j =1 X2 j － ( Δx) 2 － 2Ｒ1 和 b = 2Ｒ2 － ∑ m j = 1 ( x'j ) 2 的大小，若 a ＞ b 则得到结论 YES，否则结论为 NO． 图 3 是另一种可选的合群判定模型． 在这种情 况下，阈值判定的依据可选用最小二乘法或极大似 然估计，并可通过 SMC 基础协议实现求解． 该模型 在实际的生产生活中也有一定的适应性． 图 3 基于最小二乘法的扩展协议( Δx 为选定的阈值) Fig． 3 Extensible protocol based on the least square method ( Δx for the selected threshold) 4 结束语 社交网络的使用中经常需要进行合群判定，利 用安全多方计算技术构建保护私有信息的解决方 案，能够正确有效地得到申请者是否适合加入该群 组的判定结果，同时能够很好地保护用户群组中每 个人的个人隐私． 该判定协议可替代社交系统的盲 目推荐，满足管理员离线时的及时响应需求，在日渐 · 996 ·