一种移动终端隐私保护的信息匹配方案

夏　勇， 张明武， 沈　华， 陈泌文

(湖北工业大学计算机学院， 湖北 武汉 430068)



一种移动终端隐私保护的信息匹配方案

夏勇， 张明武， 沈华， 陈泌文

(湖北工业大学计算机学院， 湖北 武汉 430068)

[摘要]移动终端用户在交友通讯过程中可能泄露用户双方的隐私信息，给用户带来安全隐患。针对该问题，提出一种移动终端隐私保护的信息匹配方案：首先利用安全两方计算对用户双方进行预处理，以达到物理位置匹配的目的；然后利用各种算术变换进行用户兴趣爱好的匹配；最后利用权重公式计算用户双方信息的匹配度。通过对方案的正确性、安全性等进行分析，显示本方案可有效地保护用户隐私。

[关键词]隐私保护； 安全两方计算； 正确性； 安全性； 私隐性

近年来安全多方计算(Secure muti-party Computation,SMC)问题成为密码学界的研究热点，SMC最早在文献[1]中提出，随后文献[2]作了进一步的研究。各种问题以及相应的解决方案有：关于隐私信息相似度评估[4]，矩阵相等和特征值[5]，字符串匹配[6]，两圆距离计算[7]，两平行直线间距[8]，线与椭圆相交判定[9]，信息泄露比较[10]，点线关系判定[11]，信息的叉积协议[12]等。

针对目前移动终端交友容易带来安全隐患这一问题，提出一种移动终端隐私保护的信息匹配方案。方案利用两方安全计算用户之间的距离，通过保密的比较来判断所要交友的用户是否在搜寻范围内，实现物理位置的匹配；利用哈希函数 、随机置换及模指数运算来进行两用户的兴趣爱好信息的交互，实现兴趣爱好的匹配；利用权重公式来计算用户信息的匹配度。这样不仅保护了用户的隐私信息不被泄露，而且还为用户交友提供了真实可靠的参考数据，在现实环境下有很高的实用性和可靠性。

1预备知识

1.1半诚实模型

所谓的半诚实参与者会严格执行协议的操作步骤，不会中途退出或恶意输入虚假的数据，但是它可能保留所有的中间数据，试图推导其他参与者的私有输入信息。

1.2保密点积协议

假设有两个参与者Alice和Bob，它们各自拥有秘密输入向量X={x1,…,xn}和Y=(y1,…,yn)，它们进行协作计算并在协议结束后Alice得到值wA=xi·yi+rB(rB是Bob选取的一个随机值)。同时要保证Alice不能从wA中得到有关rB的值，也不能从已知的信息中推出任何有关yi的信息；同理Bob不能得到wA的值，也不能推出有关的xi的信息。

1.3安全两实数和的平方协议

协议描述Alice拥有实数a，Bob拥有实数b，Alice和Bob希望保密计算(a+b)2。计算结束后，Alice得到k1，Bob得到k2，满足k1+k2=(a+b)2。

步骤1Alice计算a2，Bob计算b2；

步骤2Alice和Bob利用安全两方保密点积协议计算a·b：Alice得到K1，Bob得到K2，满足K1+K2=a·b；

步骤3Alice计算k1=a2+2K1，Bob计算k1=a2+2K1；

步骤4k1和k2两数相加得：k1+k2=a2+2K1+b2+2K2=(a+b)2。

1.4两个实数大小的保密比较协议

协议描述Alice拥有实数c，Bob拥有实数d,他们保密比较c,d的大小。利用可交换加密方案E来实现保密比较，假设Alice的密钥为KA，Bob的密钥为KB。

输入： 实数c,d

步骤1Alice加密c得EKA(c)，Bob加密d得EKB(d)；

步骤2Alice将EKA(c)发送给Bob，Bob将EKB(d)发送给Alice；

步骤3Alice计算EKA(EKB(d))，Bob计算EKB(EKA(c))；

步骤4Alice和Bob交换数据，如果EKA(EKB(d))≤EKB(EKA(c))，那么c≥d；否则c

2隐私保护信息匹配方案

方案描述 假设Alice和Bob是两个移动终端用户，方案如下描述：Alice拥有三维坐标保密点P1(x1,y1,z1)及兴趣爱好集合A={a1,…,am}，Bob拥有三维坐标保密点P2(x2,y2,z2)及兴趣爱好集合B={b1,…,bn}，Alice在自身隐私信息不被泄露的条件下寻找有共同兴趣爱好的朋友Bob，并且返回信息匹配度的值(图1)。

图 1　方案示意图

输入Alice输入三维坐标保密点P1(x1,y1,z1)，Bob输入三维坐标保密点P2(x2,y2,z2)，进行物理位置匹配，匹配成功后，Alice再输入兴趣爱好集合A={a1,…,am}，Bob再输入兴趣爱好集合B={b1,…,bn}。

输出两用户信息匹配度的值。

图 2　方案流程附图

本方案的执行过程由四个模块构成(图2)，依次为：1)预处理模块 ；2)物理位置匹配模块；3)兴趣爱好匹配模块；4)信息匹配度计算模块。

2.1预处理模块

Alice和Bob希望在不泄露自己保密点信息的情况下，计算出两用户之间的距离

步骤1.1Alice和Bob利用安全两数x1、-x2和的平方协议，保密计算(x1+(-x2))2；计算完成后，Alice得到d1A，Bob得到d1B，满足d1A+d1B=(x1+(-x2))2；

步骤1.2Alice和Bob利用安全两数y1、-y2和的平方协议，保密计算(y1+(-y2))2；计算完成后，Alice得到d2A，Bob得到d2B，满足d2A+d2B=(y1+(-y2))2；

步骤1.3Alice和Bob利用安全两数z1、-z2和的平方协议，保密计算(z1+(-z2))2；计算完成后，Alice得到d3A，Bob得到d3B，满足d3A+d3B=(z1+(-z2))2；

步骤1.4Alice计算d1=d1A+d2A+d3A，Bob计算d2=d1B+d2B+d3B，此时d1+d2=(x1-x2)2+(y1-y2)2+(z1-z2)2， 可知两点距离为：

步骤1.5系统将两用户间的距离dreal发送给Bob。

2.2物理位置匹配模块

Alice和Bob在不泄露距离信息的情况下，达到两用户物理位置匹配的目的。

假设Alice所能搜寻的最远距离为dmax，它的密钥为KA，Bob的密钥为KB，只要Alice想交友的距离dselect在(0,dmax]范围内都可以实现物理位置的匹配。

步骤2.1Alice随机选取所要搜寻的距离dselect(dselect∈(0,dmax])；

步骤2.2Alice加密dselect得EKA(dselcet)，Bob加密dreal得EKA(dreal)；

步骤2.3Alice将EKA(dselect)发送给Bob，Bob将EKB(dreal)发送给Alice；

步骤2.4Alice计算EKA(EKB(dreal))，Bob计算EKB(EKA(dselect))；

步骤2.5Alice和Bob交换各自数据，如果EKA(EKB(dreal))≤EKB(EKA(dselect))，那么Bob在Alice的距离范围内，则物理位置匹配成功，否则匹配失败。

只有物理位置匹配成功才执行以下的兴趣爱好匹配模块，如果匹配失败的话则提前结束整个方案。

2.3兴趣爱好匹配模块

在不泄露各自兴趣爱好的情况下，得到两用户之间兴趣爱好匹配的个数。

第一轮运算：

步骤3.1Alice将集合A={a1,…,am}中的每个元素依次代入哈希函数H1(·)，记为hai=H1(ai),(1≤i≤m)，得到集合A1：

A1={ha1,…,ham}=

步骤3.2Alice选取随机数r1,?(r1∈Zq)，对集合A1中的每个元素做如下运算：

Alice将集合A2发送给用户Bob；

第二轮运算：

得到集合A3：

步骤3.4Bob将集合A3中的每个元素代入随机置换函数∏1(·)，得到集合A4：

步骤3.5Bob将集合B={b1,…,bn}中的每个元素代入随机置换函数∏2(·)，记为ξj=∏2(bj)，(1≤j≤n,j,n,均为正整数)，得到集合B1：

B1={ξ1,…,ξn}=∏2{b1,…,bn}=

Bob将集合A4和集合B4发送给Alice；

第三轮运算：

2.4信息匹配度计算模块

进行信息匹配计算，得到信息匹配度。

步骤4.1Alice计算自身所想搜寻的距离与两用户之间的实际距离的差，记为

△d=dselcet-dreal=

步骤4.2Alice计算△d占dselect的比例，记为

步骤4.4Alice计算两用户兴趣爱好交集的个数占两用户兴趣爱好集合的最大个数的比例，记为

步骤4.5由上述已知的条件，可以利用权重公式计算信息匹配度：

F(ρ)=η×ρ%+μ×(1-ρ%)，

即

求出的F(ρ)即为两用户的信息匹配度；

3方案的性能分析

3.1正确性

方案中Alice和Bob通过安全两方计算得到两用户的实际距离为dreal，如果该距离小于或者等于dselect，则两用户的物理位置匹配成功；两用户再利用哈希函数，随机置换函数，模指数运算等一系列的变换来实现兴趣爱好的信息匹配；最后通过权重公式计算出相关信息的匹配度。因此，用户Alice一定可以得到关于Bob的物理位置和兴趣爱好匹配的百分比值，信息的匹配度也给Alice交友提供了可供参考的数据。

3.2安全性用户的隐私信息没有泄露。

1)预处理的安全性

预处理主要是两空间三维坐标的点安全计算距离dreal，它依赖的是安全两实数和的平方协议的正确性和安全性。该协议只需使用3 次安全两数和平方计算协议, 即3次一维安全两方点积协议, 其计算复杂性和通信复杂性都依赖使用的一维安全两方点积协议的计算复杂性和通信复杂性，在距离dreal计算完成后，用户双方并不知道对方的三维坐标点。因此，预处理的整个过程没有泄露任何有关用户的坐标信息。

2)物理位置匹配的安全性

物理位置匹配主要利用的是可交换加密方案E来实现两距离dselect和dreal的保密比较，在比较的过程中，Alice和Bob只是在各自密钥加密的情况下，进行了数据交换，因此，用户双方在不知道对方密钥的条件下，是无法知道对方距离信息的。可交换加密方案 执行完成之后，只是得到了两距离的大小关系，并没有泄露相关的距离信息。

3)兴趣爱好匹配的安全性

4)信息匹配度的安全

信息匹配度主要是利用权重公式

(0<ρ<100)

3.3复杂性

计算的复杂性：Alice和Bob在通信过程中用到了点积协议和可交换加密方案E，其他都是一系列算术变换，因此计算的复杂性为O(nlnn)。

通信的复杂性：预处理模块中，Alice和Bob需要相互通信1次；物理位置匹配模块中，Alice和Bob需要相互通信1次；兴趣爱好匹配模块中，Alice和Bob需要相互通信2次；信息匹配模块中，Alice和Bob需要相互通信1次，因此该方案中，两用户总共通信了5次。

4结束语

本文利用两方安全计算和哈希函数等设计了一种移动终端隐私保护的信息匹配方案。该方案有效的解决了现有的移动终端交友过程中隐私信息容易泄露的问题，不需要不可信第三方的参与，只需要参与计算的双方就可以实现用户信息的匹配度计算，且保护了双方的隐私信息。本方案是在半诚实的模型下进行的，如何在恶意的模型下实现同样的效果有待进一步的研究与探索。

[参考文献]

[1]Yao A C. Protocols for secure computations [C] // Proceedings of 23rd Annual IEEE Symposium on Foundations of Computer Science[A]. Los Alamitos: IEEE Computer Society Press, 1982: 160-164.

[2]Goldreich O, Micali S, Wigderson A. How to play any mental game[C] // Proceedings of the19th Annual ACM Conference on Theory of Computing[A]. New York: ACM Press, 1987:218-229.

[3]DU Wen-liang，ATALLAH M J． Secure multi-party computation problems and their applications: a review and open problems[C]// Proc of Workshop on New Security Paradigms[A]．New York: ACM Press，2001:11-20.

[4]Carlo Blundo，Emiliano De Cristofaro, Paolo Gasti. Efficient Privacy-Preserving Evaluation of Sample Set Similarity，DPM 2012.

[5]刘新，李顺东，陈振华，等. 矩阵相等和矩阵特征值的概率多方保密计算协议[J].计算机应用研究，2015,32(02)：524-527.

[6]袁先平，仲红，黄宏升，等. 一种字符串近似匹配的安全查询协议[J]. 计算机工程 ，2011，37(20)：142-144.

[7]刘文，罗守山，杨义先，等. 安全两方圆计算协议[J]. 北京邮电大学学报，2009,32(03)：32-35.

[8]辛欣，郝林，汤瑜. 空间两平行直线间距离的保密计算协议[J]. 计算机应用研究，2013,30(05)：1530-1535.

[9]符祖峰，罗文俊，童玲. 一个保护私有信息的线段与椭圆相交判定协议[J]. 计算机工程与应用，2010,46(17)：77-80.

[10] 秦静，张振峰，冯登国等. 无信息泄露的比较协议[J]. 软件学报，2004,15(3)：421-427.

[11] 刘文，罗守山，陈萍. 保护私有信息的点线关系判定协议及其应用[J]. 北京邮电大学学报，2008,31(2)：72-75.

[12] 罗永龙，黄刘生，荆巍巍,等. 保护私有信息的叉积协议及其应用[J]. 计算机学报，2007,30(2)：248-254.

[责任编校： 张岩芳]

Information Matching Scheme Protecting Mobile Terminal Privacy

XIAYong，ZhangMingwu，SHENHua，CHENMiwen

(SchoolofComputerScience，HubeiUniv.ofTech.，Wuhan430068，China)

Abstract：Mobile terminals may disclose the privacy information when users are communicating with others, which will bring security risks to users. To solve this problem, this paper presents an information matching scheme protecting mobile terminal privacy. First, it used two party security computations to pretreat users, in order to achieve the physical location of matching purposes; then used various arithmetic transforming to match the user's interests; Finally, used weight formula to calculate the information matching degree. Through analysing the correctness and security of the scheme, it shows that this scheme can improve the users’privacy effectively.

Keywords：privacy-preserving; secure two-party computation; correctness; security; privacy

[中图分类号]TP393.08

[文献标识码]：A

[文章编号]1003-4684(2016)01-0076-05

[作者简介]夏勇(1987-)， 男， 湖北钟祥人，湖北工业大学硕士研究生，研究方向为安全多方计算[通讯作者] 张明武(1970—)，男，湖北仙桃人，湖北工业大学教授，研究方向为信息网络安全

[收稿日期]2015-03-20