基于隐私匹配的服务代理发现方法

耿魁，万盛，李凤华,，何媛媛，王瀚仪

(1. 西安电子科技大学综合业务网理论与关键技术国家重点实验室，陕西 西安 710071；2. 中国科学院信息工程研究所信息安全国家重点实验室，北京 100093)

基于隐私匹配的服务代理发现方法

耿魁1，万盛1，李凤华1,2，何媛媛2，王瀚仪2

(1. 西安电子科技大学综合业务网理论与关键技术国家重点实验室，陕西 西安 710071；2. 中国科学院信息工程研究所信息安全国家重点实验室，北京 100093)

针对代理发现中用户对代理的性能、成本和安全性等方面的需求，以及需求匹配过程中的隐私保护问题，基于 Paillier同态加密算法，提出一种新的综合考虑代理和用户属性及其偏好的私有数据信息匹配算法，包括建立基于欧氏距离的相似度函数、利用加密算法进行匹配、计算相似度和确定匹配的代理链4个步骤。该算法引入半可信主代理从全局层面管理所有子代理的业务类型和连接状况，并承担主要的计算开销，同时将欧氏距离与Paillier同态加密算法有机结合，支持具有偏好信息的多元属性数据匹配，能够有效保障用户和子代理的安全性。最终，通过安全性分析与性能仿真，证明所提出方案的安全性和有效性。

代理；服务代理发现；隐私匹配；同态加密

1 引言

随着网络技术的快速发展和信息共享系统的大量应用，泛在网络中局域网、互联网、物联网和移动网等多种网络广泛互连互通，信息呈爆炸式增长，出现了过载现象，服务数量的大规模性、服务描述的异构性以及设备服务的资源高度受限性和移动性等特征日益凸显，为了向用户准确地提供所需的信息和服务，朋友发现、代理发现和服务发现等基于匹配的应用应运而生，成为泛在网络的重要应用，已受到了学术界和工业界的广泛关注。用户与活跃在邻近区域的代理及时通信，找到在性能、成本和安全性等方面最优的路径，更快速、更准确地获取信息和服务。然而，用户和代理通过交换服务属性集合优化访问路径的同时，用户和代理的处理能力、时延、能耗、服务费用和抗攻击能力等敏感信息将暴露给对方，从而为双方的数据安全和隐私信息带来潜在威胁。因此，对用户个人隐私和代理敏感数据的保护刻不容缓。

针对私有数据匹配问题，近年来大量文献提出了解决方法。大多数方法假设每个匹配参与方拥有一个属性集合，采用匹配参与双方共同属性的个数为相似度，共同属性越多，用户越匹配，整个匹配过程不泄露双方个人敏感信息，但是，这些方案存在一定的局限性。匹配函数只考虑了共同属性的个数，忽视了每个用户对各个属性偏好程度的差异；基于交换加密、同态加密等加密方法的隐私信息匹配方案安全性较高，但是，计算开销较大，难以在移动终端上运行；基于布隆过滤器、混淆等非加密方法的隐私信息匹配方案计算开销较小，但是，大量随机数导致通信量大幅增加，并且安全性较弱。因此，将复杂的计算工作交由第三方代理来完成是一种常见的解决思路。

为了解决上述问题，本文提出一种与属性偏好相关的私有数据信息匹配算法，其主要贡献如下。

1)将Paillier同态加密应用于代理发现算法的设计中，针对用户的个性化服务请求提供最匹配的作业代理链。

2)引入主代理从全局层面管理所有子代理的业务类型和连接状况，并在利用Paillier同态加密方法的语义安全性保证算法安全性的前提下，由主代理承担主要的计算开销，以缓解用户终端的计算压力。

3)支持具有偏好信息的多元属性数据匹配，更细粒度地满足用户及代理在服务性能和隐私保护方面的需求。同时，执行加密运算前将属性的偏好程度转化为二元值，有助于降低计算开销。

2 相关工作

本文涉及的代理发现这一概念，是建立在第三方不可信的基础上进行的，因而本文方案的主要工作是在隐私保护的前提下实现代理发现。能够保障信息不被泄露的算法有很多种，大体分为加密算法和非加密算法，本文采用的是同态加密算法中的Paillier算法，在方案中起到了隐私保护的关键作用。

有不少学者会通过非加密的算法实现隐私保护，以便减轻执行过程中的消耗。Zheng等[1]提出了一个基于位置隐私保护的握手协议，利用布隆过滤器进行一对多的匹配，构建时空位置标记，从无线电在设备的周围环境中捕获的信号（Wi-Fi等）来标记位置，以防止位置欺骗。Sun等[2]也根据布隆过滤器进行基于共同兴趣爱好的朋友隐私匹配，虽然上述方案均未采用加密算法，使整体方案的消耗很小，但是却有匹配精确度的偏差。Lu等[3]针对移动医疗急救场景提出SPOC协议，并在方案中引入随机数，通过混淆来保证隐私安全，然而利用穷举法，还是有信息被破解的可能。

出于对安全性的考虑，更多学者会利用加密算法来实现高强度的隐私保护。例如，Agrawal等[4]提出了基于交换加密的双方秘密共享方案，Vaidya等[5]提出了 N方秘密共享方案，Niu等[6]提出P-match，利用交换加密进行基于邻近的朋友发现，并考虑到用户的兴趣权重因素。而在各种加密方案中，同态加密方法更是不胜枚举，Li等[7]利用同态加密和二维多项式，实现多方匹配的语义安全。Kerschbaum等[8]也利用同态加密，在双方不泄露个人信息的前提下求出集合交集。Li等[9]基于邻近的移动社交网络，提出了分布式的保护隐私信息匹配方案FindU，建立3个不同的隐私级别，利用Shamir秘密共享方法结合同态加密，进行安全多方计算，实现多方匹配，可以抵抗多方同谋的情形。Zhang等[10]利用 Paillier同态加密方法，根据不同的隐私需求设计不同的方案，并考虑到了用户对不同兴趣的偏好程度，由此建立了基于邻近的隐私信息匹配协议。Thapa等[11]针对在线社交网络，利用Paillier加密算法设计了3个不同隐私级别的非对称的基于邻近的隐私信息匹配方案，其社交网络中的用户不仅通过朋友关系彼此相连，还按社会团体进行分类，并提出新的相似度函数。Chu等[12]提出了隐私保护的二部匹配框架，基于二部图结构中的匈牙利方法和Paillier同态加密方法，来寻找最佳匹配，在保障用户隐私的前提下，利用服务器的计算能力对多媒体进行分析研究。文献[13]提出了一对一基于社交网络隐私信息匹配的方案，运用 ElGamal和Paillier加密算法，使用户双方可以不同时在线进行匹配。Wang等[14]针对社交网络中的群组隐私匹配，利用Paillier加密算法，选出与用户的兴趣集合最匹配的群组。Niu等[15]同样基于Paillier算法，考虑到用户属性的权重来进行朋友发现。上述在不同场景下的文献，均采用了Paillier加密算法，可见该算法的实用性与安全性。

3 隐私匹配机制

3.1 预备知识

本文采用同态加密算法——Paillier加密算法，来保护用户和各个子代理的隐私信息，由于Paillier算法对数据加密后，具有同态性质，所以可直接通过对加密后的信息进行操作，而不需要已知明文，这样保障了在交换信息过程中的安全性。下面介绍Paillier算法的具体操作。

1)密钥生成。任意选取 2个大素数 p、q，使GCD(pq,(p−1)(q−1))=1。记选取随机整数使其中则用户U的公钥为数对lt;N,g＞，私钥为λ。

3.2 参数设置

用户在请求服务时，请求信息交给第三方代理后（主代理），主代理将对服务请求信息进行分解，服务请求将被多个不同类型、不同级别的子代理进行处理，形成一个作业代理链。根据不同下级子代理的类型、级别、业务能力以及代理之间的连通性，实际上可选的下级子代理有多种方案，为完成用户请求作业的下级代理所组成的作业代理链也存在多条。

在具体执行时，主代理可通过子代理之间的业务属性连通性，发现多条可完成用户服务请求的作业代理链。主代理需要根据用户提出的服务要求（例如时延、费用、安全等级等），以及各个子代理的服务属性值，找出一条最符合用户需求的作业代理链。

对 任 意 x∈ [0,w − 1],定 义 函 数 h( x)=其中，当时， xl=1；当时， xl=0。定义用户U的服务属性权重向量为每个子代理 Vi的服务属性权重向量为由定义可知，对均为 0 或 1。

本文将用户 U与子代理 Vi的服务属性权重向量，在不泄露具体信息的情况下,借助主代理进行匹配，使用户得到评价值 f( U,Vi)，算出用户与整条作业代理链的整体评价值，并与其他作业代理链进行比较。评价值越小，表示该作业代理链与用户的服务越接近。本文中选取作为衡量评价值的函数。

在本方案中，忽略通信信道的安全问题，着重考虑来自内部参与者的攻击。假定内部参与信息交换传输的三方：用户、主代理、多个子代理，是诚实但好奇（HBC,honest but curious)，即参与者能诚实的执行既定方案，不会对信息进行伪造，但却会尽可能分析方案执行过程中所有获得的信息，试图获取其他参与者的隐私信息。

基于上述攻击模型，当本文方案执行结束，用户、主代理、多个子代理，不能知道关于其他参与者服务属性的任何信息。

3.3 系统架构

本文提出基于 Paillier同态加密算法的作业代理链发现方法，其系统架构如图1所示。以用户通过一个不完全可信的第三方代理来完成餐饮、医疗等服务，下面举例对系统中相关背景进行介绍。

图1 系统架构

2)主代理通过广播方式，将其需要交通类和餐饮类的信息发送给其邻近的子代理，各个子代理根据自身的业务类型和连通性，将确认信息反馈给主代理。

3)主代理根据接收的信息，综合出可选的作业代理链，然后根据同态加密算法，对用户和子代理的密文信息进行处理，并根据用户最终反馈的结果选择最合适的作业代理链来完成用户的请求作业。

3.4 匹配算法

由于用户与每个子代理的匹配过程都是相同的，所以为了简便，下面以子代理Vi为例，来对匹配过程进行说明。设子代理Vi的整体服务属性值为服务属性权重向量为

显然，

为保护用户和各个子代理的隐私信息，本文通过同态加密，用户使用自身的加密公钥对服务要求进行加密，同时，各个作业代理链上的子代理也使用用户的加密公钥加密自身的服务属性值。用户U和子代理Vi分别已知和为了让用户知道只需要在保证隐私的前提下，让用户计算的数值即可，由此衍生出本文的具体方案，操作如下。

1)用户U首先用Paillier加密算法给自己的服务属性权重向量加密。U的服务属性权重向量为由定义可知，对任意成立，而当时，

脑瘫是小儿常见的神经系统疾病，是指患儿出生后1个月内因非进行性脑受损所致，临床表现存在多样性，现如今小儿脑瘫发病率呈明显上升趋势，随着医学技术的不断进步，其存活率已得到改善[8-9]。手术为症状严重者的主要治疗手段，能够有效改善患儿功能，多于全麻下进行，七氟醚为小儿麻醉的诱导药物，其起效快速，对气道刺激较小，能够促进气道平滑肌松弛，对肌松药的强化作用明显优于恩氟醚及异氟醚[10]。但存在恶心呕吐、咽部不适等不足，加之手术疼痛能够引起苏醒期躁动，导致患儿烦躁不安。既往多予以氯胺酮或者阿片类药物镇痛以预防躁动，但其可能导致呼吸抑制，影响患儿清醒质量[11]。

2)在收到用户的服务请求信息 ReqInfo=lt;ReqData,后，主代理根据请求信息ReqInfo以及各个子代理的业务属性、连通性，采用广播方式，获取到多条作业代理链，对于每条代理链上的每个子代理 Vi，进行如下操作。

3)主代理将ReqInfo发送给Vi，Vi对自己的服务属性权重向量进行处理。Vi的服务属性权重向量为其中， vˆi,s=1 对任意成立，而当时，

子代理利用服务请求信息ReqInfo，计算

子代理 Vi选取随机数利用用户公钥lt;N,g＞对进行加密，得到子代理将的值发送给主代理。

在此之后，主代理将每条作业代理链上所有子代理的信息相乘，计算

并将结果发给用户。

5)用户使用自己的私钥，解密

得到

4 安全性分析与性能仿真

4.1 安全性分析

在方案执行之后，用户将会得知每条作业代理链的评价值，子代理和主代理不会得知相关的有效信息。

1)用户U的安全性

2)子代理的安全性

在整个方案中，子代理 Vi将和透露给主代理，如上所述，主代理在不清楚私钥的情况下不能得到子代理和主代理的服务属性信息以及它们之间的共有信息。

根据上述分析，在主代理不一定可信的情况下，用户和主代理得不到子代理的服务属性值，除了用户的加密公钥信息，子代理和主代理也无法拿到用户的服务属性取值。

4.2 结果分析

假设在本文的方案中，通过主代理，从k个子代理中发现了h条服务链，并设用户和子代理均有m个服务要求，每个要求的偏好取值区间为[0,w−1]。在整个方案中，根据 Paillier同态加密算法的特点，取模数N的长度为1 024 bit，则主要涉及到1 024-bit模乘、2 048-bit模乘、1 024-bit模幂和 2 048-bit模幂的运算，分别记为 mul1、mul2、exp1、exp2。考虑到主代理的运行配置远优于用户和子代理的时间，因此将主代理的上述运算记为 mul3、mul4、exp3、exp4，以示区别。本文选取了文献[17]和文献[18]的方案，从离线计算量、在线计算量、通信量和执行时间的角度与本方案来量化对比。由于文献[17]与文献[18]的方案均为两方匹配，所以为使3个方案具有可比性，考虑在加入第三方的条件下使发起方与k个响应者进行匹配，3个方案理论上的计算开销和通信量如表1所示。

本文的仿真运算将以便携式计算机（处理器：Intel Core P8700，2.53 GHz；内存：4 GB RAM；操作系统：Ubuntu 14.04）作为用户和子代理的运行配置，以服务器（处理器：Intel Xeon E5-2690，2.9 GHz；内存：32 GB RAM；操作系统：CentOS 6.3）作为主代理的运行配置。在便携式计算机上执行mul1、mul2、exp1、exp2运算，以及在服务器上执行 mul3、mul4、exp3、exp4运算的最大时间、最小时间、平均时间、中位数以及标准差如表2和表3所示。

根据实际情况，取w=10。图2(a)表示的是方案离线的计算量，根据理论值可以看出，离线计算量只与m有关，并且本文方案与文献[18]方案计算量相同，略小于文献[17]方案。由于在整个过程中，只有用户进行了离线计算，所以该取值只与服务要求个数m有关，使m在20到100之间变化，从图中可以看出，随着 m值的增大，整个方案的计算量也在不断增加，但是 3个方案的时间差别并不大，通过计算可以知道，当m=100时，离线计算时间低于5.2 s。

图2(b)表示的是3种方案在线的计算量与子代理个数k的关系，本文使k值在1 000到6 000之间变动。显然，k值增加，在线的计算时间也增长，尽管在线计算开销很大，但是本文方案中主代理相应的承担了绝大部分的计算，减轻了子代理和用户的负担，因此从图中可以明显的看出本文方案的计算量小于文献[17,18]方案的计算开销。当 k=6 000时,本方案在线计算时间约为2.3 s，文献[17,18]方案在线时间分别约为3.1 s和3 s。

表1 计算开销与通信量

表2 便携式计算机运算执行时间

表3 服务器运算执行时间

图2 不同参数取值下的不同方案间性能比较

图2(c)表示的是3种方案的通信开销与k的关系图，k在1 000到6 000之间变动，随着k的增加，传输消耗不断增加，从图中难以分辨3种方案的差别，利用理论数据计算，当k=6 000时，本方案、文献[17]和文献[18]的方案通信量分别为 2.219 3×109bit、2.224 5×109bit和2.231 6×109bit，显然，本文方案的通信量小于其他两者。

图2(d)表示3种方案执行时间随k的变化，图像趋势同样为递增，虽然对比方案与本文方案执行时间处于同一量级，但是具体数值还是有所差别，同样通过理论数值计算，得到当k=6 000时，本文方案、文献[17]和文献[18]的方案的执行时间分别约为3.798 2 s、3.819 2 s和3.829 8 s。并且尽管基于大传输量的条件，总体的执行时间仍然在可控范围内。

根据对理论值与图像的分析，方案消耗与服务要求的个数和子代理的个数均为正相关。本文方案通过增加第三方主代理，转移了用户和子代理的消耗，可以使整体的消耗和执行时间均有所减少，并与其他方案比较，本文方案在在线计算量方面有较明显的优越性。

5 结束语

本文针对代理发现中用户对代理的性能、成本和安全性等方面的需求，以及需求匹配过程中的隐私保护问题，基于Paillier同态加密算法，提出一种新的综合考虑代理和用户属性及其偏好的私有数据信息匹配算法，该算法引入半可信主代理，从全局层面管理所有子代理的业务类型和连接状况，并承担主要的计算开销，同时将欧氏距离与 Paillier同态加密算法有机结合，支持具有偏好信息的多元属性数据匹配，能够有效保障用户和子代理的安全性。通过安全性分析，表明了方案的正确性和安全性，并通过性能仿真进一步验证方案的有效性和高效性。

[1]ZHENG Y,LI M,LOU W,et al. Location based handshake and private proximity test with location tags[J]. IEEE Transactions on Dependable and Secure Computing,2015:1.

[2]SUN J,ZHANG R,ZHANG Y. Privacy-preserving spatiotemporal matching[C]//32th IEEE International Conference on Computer Communications. c2013: 800-808.

[3]LU R,LIN X,SHEN X. SPOC: a secure and privacy-preserving opportunistic computing framework for mobile-healthcare emergency[J].IEEE Transactions on Parallel and Distributed Systems,2013,24(3):614-623.

[4]AGRAWAL R,EVFIMIEVSKI A,SRIKANT R. Information sharing across private databases[C]//30th ACM SIGMOD International Conference on Management of Data. c2003: 86-97.

[5]VAIDYA J,CLIFTON C. Secure set intersection cardinality with application to association rule mining[J]. Journal of Computer Security,2005,1(13): 593-622.

[6]NIU B,ZHU X,ZHANG T,et al. P-match: priority-aware friend discovery for proximity-based mobile social networks[C]//10th IEEE International Conference on Mobile Ad-Hoc and Sensor Systems.c2013: 351-355.

[7]LI R,WU C. An unconditionally secure protocol for multi-party set intersection[M]. 5th Springer Applied Cryptography and Network Security,c2007: 226-236.

[8]KERSCHBAUM F. Outsourced private set intersection using homomorphicencryption[C]//7th ACM Symposium on Information,Computer and Communications Security. c2012: 85-86.

[9]LI M,YU S,CAO N,et al. Privacy-preserving distributed profile matching in proximity-based mobile social networks[J]. IEEE Transactions on Wireless Communications,2013,12(5): 2024-2033.

[10]ZHANG R,ZHANG J,ZHANG Y,et al. Privacy-preserving profile matching for proximity-based mobile social networking[J]. IEEE Journal on Selected Areas in Communications,2013,31(9): 656-668.

[11]THAPA A,LI M,SALINAS S,et al. Asymmetric social proximity based private matching protocols for online social networks[J]. IEEE Transactions on Parallel and Distributed Systems,2015,26(6):1547-1559.

[12]CHU W T,CHANG F C. A privacy-preserving bipartite graph matching framework for multimedia analysis and retrieval[C]//5th ACM International Conference on Multimedia Retrieval,c2015: 243-250.

[13]JECKMANS A,TANG Q,HARTEL P. Poster: privacy-preserving profile similarity computation in online social networks[C]//18th ACM Conference on Computer and Communications Security. c2011:793-796.

[14]WANG B,LI B,LI H. Gmatch: secure and privacy-preserving group matching in social networks[C]//55th IEEE Global Communications Conference. c2012: 726-731.

[15]NIU B,HE Y,LI F,et al. Achieving secure friend discovery in social strength-aware PMSNs[C]//34th IEEE Military Communications Conference,c2015: 947-953.

[16]PAILLIER P. Public-key cryptosystems based on composite degree residuosity classes[J]. Springer Cryptology-EUROCRYPT,1999,547(1):223-238.

[17]RANE S,SUN W,VETRO A. Privacy-preserving approximation of L1 distance for multimedia applications[C]//Multimedia and Expo(ICME). c2010: 492-497.

[18]ZHANG R,ZHANG R,SUN J,et al. Fine-grained private matching for proximity-based mobile social networking[C]//INFOCOM. c2012:1969-1977.

Privacy matching-based service proxy discovery scheme

GENG Kui1,WAN Sheng1,LI Feng-hua1,2,HE Yuan-yuan2,WANG Han-yi2

(1.State Key Laboratory of Integrated Service Networks,Xidian University,Xi’an 710071,China;2.State Key Laboratory of Information Security,Institute of Information Engineering,CAS,Beijing 100093,China)

According to user’s requirements on the proxy performance,cost and safety in proxy discovery,and the privacy-preserving issue during the process of the demand private matching,a new private matching algorithm was presented based on Paillier homomorphic encryption,comprehensively considered the attributes of user and agents and their priority. It included four steps: building the similarity function based on Euclidean distance,carrying on the private matching by encryption algorithm,calculating the similarity and screening the proxy chain. Proposed scheme introduced semi trusted primary proxy from the global level,which is to manage all the sub proxy’s business type and the connection status,and do the main computational overhead.At the same time,Euclidean distance and Paillier homomorphic encryption algorithm were combined to support the multivariate attributes with priority to match,which can effectively protect the privacy of user and sub proxy. Finally,security analysis and evaluation results show the effectiveness and safety of proposed scheme.

proxy,service proxy discovery,privacy matching,homomorphic encryption

s:The Key Program of the National Natural Science Foundation of China-Guangdong Union Foundation(No.U1401251),The National High Technology Research and Development Program of China (863 Program)(No.2015AA016007),The National Natural Science Foundation of China (No.61502489)

TP393

A

2016-03-04；

2016-07-28

李凤华，lfh@iie.ac.cn

国家自然科学基金委—广东联合基金资助项目（No.U1401251）；国家高技术研究发展计划（“863”计划）基金资助项目（No.2015AA016007）；国家自然科学基金资助项目（No.61502489）

10.11959/j.issn.1000-436x.2016164

耿魁（1989-），男，湖北红安人，西安电子科技大学博士生，主要研究方向为网络安全。

万盛（1987-），男，江苏南通人，西安电子科技大学博士生，主要研究方向为网络安全与隐私保护。

李凤华（1966-），男，湖北浠水人，博士，中国科学院信息工程研究所副总工、研究员、博士生导师，主要研究方向为网络与系统安全、信息保护、隐私计算。

何媛媛（1985-），女，湖北松滋人，中国科学院信息工程研究所博士生，主要研究方向为信息安全、隐私保护。

王瀚仪（1994-），女，吉林省吉林市人，中国科学院信息工程研究所博士生，主要研究方向为网络安全。