保密社交意愿探测∗

巩林明 , 李顺东 , 窦家维 , 王道顺

1(西安工程大学 计算机科学学院,陕西 西安 710048)

2(陕西师范大学 计算机科学学院,陕西 西安 710119)

3(陕西师范大学 数学与信息科学学院,陕西 西安 710119)

4(清华大学 计算机科学与技术系,北京 100084)

近年来,随着基于位置的服务在移动智能设备上的广泛应用,保密探测问题已经成为移动、社交网络中保护隐私的一个研究热点.保密近感探测,是保密探测问题的一个重要分支.保密近感探测问题研究的是移动网络中任意两个用户如何协同计算出他们的实时位置是否彼此临近而不泄漏各方的具体位置.时至今日,保密近感探测问题已取得了一些可喜的成果[1-21],但这些成果中除了Mu 等人[1]取得的以外,其他协议[2-21]都是采用格栅分解技术(如果参与方在相同的格栅内,即同在一个预先设定大小的圆形区域内,则认为参与各方毗邻)实现保密近感探测的.然而,这种方法不满足移动或社交网络用户的个性化需求,如:Alice 正在颐和园度周末,她想知道她的业余划船搭档Bob 是否也在颐和园内,是否可以和Bob 一起参加公园里正在举办的双人划船比赛.采用格栅分解技术的近感探测只能探测到Bob 是否处在以Alice 为中心、预先设定半径值的圆域内.2016 年,Mu 等人[1]综合运用安全多方计算、Paillier[22]和ElGamal[23]同态加密方案设计了一个保密探测区域为任意凸多边形的协议.该协议满足了用户个性化的需求(用户不再预先设定保密探测区域阈值的大小,保密探测区域可以是任意的多边形),非常方便用户表示保密探测区域.

但文献[1]的协议仍然存在以下两个方面的不足.

(1)文献[1]的协议除了用Paillier 加密系统保密计算符号外,还需要调用K(凸多边形的顶点数)次高计算复杂度的、由ElGamal 加密方案实现的保密比较大小运算.

(2)文献[1]的协议并未彻底解决保密近感探测问题,只适用于解决用户参与计算区域的临近两点坐标分量差大于0 的情形,当用户参与计算区域的临近两点坐标分量差值小于0 时,该协议会输出错误的结果.原因是文献[1]的协议用Paillier 加密方案直接加密负数,并在加密负数的结果上实施同态运算.

事实上,Paillier 加密方案不能直接用于加密负数,加密负数以及在加密的负数上进行同态操作需要做额外的比特密文同态运算.关于Paillier 加密方案不能直接用于加密负数,并在加密负数的结果上实施同态运算方面的具体阐述如下.

命题1.Paillier 加密方案不能直接用于加密负数.

设a∈Zn,,-a表示负数,并假定Paillier 加密方案能够直接加密一个负数,则由其加密算法的正确性可知:由加密运算生成的密文Enc(-a),经过解密运算Dec(Enc(-a)),一定能正确恢复出消息-a.

事实上,由解密运算:

得到消息-a的概率很小,因为要等于-a,则需1≡(1+λkan)modn2成立.即n|λka因为gcd(λ,n)=1,所以n|λka则必有n|ka.而为安全起见,系统参数k是不会取κp或者κq的,所以只有当a≡0 modn,解密算法才能正确恢复出消息-a.因此,Paillier 加密算法能够加密负数的假设不成立.

同理,已知a∈Zn在Paillier 加密体制下的密文ca=garnmodn2a∈Zn无法直接通过同态计算得到c-ab=g-ab(r′)nmodn2a∈Zn,其中,b∈Zn.□

用Paillier 通过特殊处理可以实现对一个负数的加密,但难以实现对若干个正、负数对应密文实施若干次同态运算.目前所采用的特殊处理方法大致可以分为3 类.

(1)明文的符号由明文所处的区间隐式地确定,用这种方法能够加密明文的范围是.通常是将整型区间[0,n]划分成两个等长的区间,并事先规定哪个区间内的数代表负数.例如,可以事先规定处在内表示负数,如果解密结果,则解密方需要在解密的基础上执行额外计算:m′=m-n.

(2)用加密加法逆元的方法实现对[-n,0]内整数的加密:用-a表示负数,则在Zn群上可将-a视为a的逆元n-a,进而可以通过加密运算生成的密文Enc(n-a),经过解密运算Dec(Enc(n-a)),一定能够正确恢复出消息n-a.而后再做运算(n-a)-n,可以得到-a.

(3)明文的符号由加密额外的比特信息标识,用此种方法能够解决[-n,n]内的问题.通信双方需要事先商定符号的数字标识,通常规定“0”代表“+”,“1”代表“-”.由运算μ∈{0,1}计算出的密文(Enc(a),Enc(sμ)),通过解密运算:

即可恢复出消息-a.

但是,上述加密负数的方法在需要对差商对应的密文实施若干次同态运算的环境下将变得异常复杂:一方面,多次同态运算会导致明文运算结果所处区间的变换,这会影响多方保密计算结果的准确性;另一方面,在保密多方计算中,各参与方都不想泄露自己的、哪怕是1 比特的信息(在涉及坐标运算的保密计算中,坐标符号的泄露有可能造成相对位置信息的泄露),又有哪个无私钥的参与方愿意对外透露自己的符号信息呢?

由上述分析可得,现有的基于位置服务的保密探测方法绝大多数只能解决保密探测区域在预先设定半径阈值的圆形内的情形,这不能满足用户个性化的需求(用户不再预先设定保密探测区域阈值的大小,保密探测区域可以是任意的多边形).文献[1]的协议提出了一种解决探测区域为任意凸多边形情形的很好的方法.它虽然能够满足用户个性化的需求(无需将探测区域设定为带阈值的圆形区域),但是并未彻底解决保密探测计算中保密坐标符号计算问题.因此,对于涉及到保密计算(正、负)符号的、利用同态加密实现的由多方协同参与的安全/保密几何计算问题以及基于位置服务的移动、社交网络隐私保护问题则需要另辟新径.

如今,社交网络用户又对保密地探测提出了新的个性化需求:保密社交意愿筹划,即保密社交意愿探测.保密社交意愿探测已经成为基于位置服务的社交网络用户的一个新的个性化需求.我们将如下一类问题称为保密意愿探测问题:拥有便携智能设备的用户间可以事先保密地探测他们的社交意愿——Alice 由她的便携智能设备秘密地获取Bob 是否处在自己愿意与Bob 约会(如果Bob 愿意赴约的话)的“理想区域内”,Bob 由自己的便携智能设备保密地表达自己是否愿意赴约的意愿,但双方都不想泄露各自的位置信息(Alice 既不想泄露自己的位置,也不想泄露自己的“理想区域”;Bob 不想泄露自己的位置信息).

保密意愿探测可以视作保密近感探测协议[1]在移动、社交网络用户个性化需求方面的深度拓展.虽然二者都是基于位置服务的移动、社交网络用户隐私保护问题,但它们有明显的区别:保密近感探测问题研究的是两个用户如何计算他们的实时位置是否在预先设定的距离阈值内而不泄漏双方各自的具体位置;保密意愿探测问题研究的则是参与双方如何计算出他们是否可以在某一区域内共事而不泄漏具体的共事区域与双方计划共事的具体位置,即保密社交筹划.

为了解决移动、社交网络用户在社交筹划方面隐私保护的个性化需求问题,同时也为了解决基于同态加密方案与安全多方计算的保密近感探测(如文献[1]的协议)中未能彻底解决的问题(当用户参与计算区域的临近两点坐标分量差值小于0 时,文献[1]的协议会输出错误的结果),本文首先提出了一个基于位置服务的移动、社交网络隐私保护问题:保密社交意愿探测.然后综合采用安全多方几何计算[24-26]、保密计算分数(一种新的保密比较大小方法)、同态加密以及云外包计算等技术设计了一个高效的社交网络保密意愿探测协议.

本文的主要贡献如下:

(1)构造了一个由云辅助计算的新型同态加密方案,该方案在预处理阶段由云服务器提前完成复杂的自模乘运算加密阶段的另一复杂运算gmmodn2由等价的简单模乘运算m⋅(g-1)modn2代替,因此只通过几次简单的模乘运算,就可以实现一次加密.

(2)提出了一种新的保密符号计算方法,并利用该方法和新构造的基于云计算的同态加密方案,设计了一个新的保密意愿探测协议.该协议对于半诚实参与者是安全的.

(3)提出了一种新的加密思想:由加密一方自主确定一次加密需要执行多少次模乘运算.

1 预备知识

1.1 关于加密方案的安全性定义

定义1(不可区分安全游戏).“加密语义安全”通常利用一个(由敌手和加密系统产生者)两方进行的思维游戏进行刻画.本文将引用文献[27]中对于文献[28]中关于公钥加密方案的选择明文攻击不可区分性(indistinguishability under chosen-plaintext attack,简称IND-CPA)游戏的翻译表述(其中,E为任意一个公钥加密方案,A为任意一个概率多项式时间的敌手,为A在攻击E的不可区分游戏中的成功优势).

(1)输入系统安全参数1k,生成密钥对(Kpub,Kpri).

(2)A获得公钥Kpub,并且它能够访问加密谕言机Enc(⋅),经过一些加密问询后输出两个相同长度的明文m0和m1.

(3)系统搭建者随机选择b∈{0,1},然后输出一个挑战密文c=Enc(mb).

(4)A继续调用Enc(⋅),输出一个比特位b′作为对b的猜测结果.

(5)若b′=b,则游戏输出否则,输出

如果存在一个可忽略的函数δ,满足:

则方案E在选择明文攻击下具有不可区分安全性.

1.2 关于安全多方计算的安全性定义[27]

要证明一个安全多方计算协议的安全性,需要用到定义:理想保密计算协议、半诚实参与者、协议π可被用于保密计算函数f(a,b).本文将引用文献[27]中对于学者Goldreich 关于这3 个定义的翻译描述.

定义2(理想保密计算协议)[27].假设TTP 是网络中存在的一个绝对可信的第三方,作为协议的参与方,Alice与Bob 在TTP 协助下,可以按照如下方式协作完成一次安全计算:Alice 与Bob 各自将他们的秘密信息a和b分别秘密地发送给TTP,由TTP 独立计算完函数f(a,b)后,再将计算出的函数值分别秘密地发送给Alice 和Bob.其中规定函数f满足:已知a与b之一以及函数值f(a,b)时,不能计算出a与b中的另一个.显然,网络中这样一个简单的协议是保密程度最高的安全两方计算协议,除此之外,再也找不到一个用于计算f(a,b)的实际安全两方计算协议在安全性上可以超越该协议.

定义3(半诚实参与者)[27].不严格地说,作为某安全多方计算协议的半诚实参与者,在其执行协议的过程中绝对会按照协议规定,执行安全计算协议的每一步,但其可能会在协议执行过程中记录所有中间结果,并试图利用这些记录数据去计算安全多方计算协议之外的有关其他参与者的隐私信息.

将计算概率多项式函数f=(f1,f2):{0,1}*×{0,1}*→{0,1}*×{0,1}*的协议记作π.给π输入(a,b),在协议执行过程中,Alice 和Bob 的视图(view)分别记作其中,d∈{1,2},rd是Alice 或Bob 自己选择的随机数,是Alice 或Bob 收到的第i个消息;将Alice 和Bob 协同执行完协议得到的结果分别记作

定义4(协议π可被用于保密计算函数f(a,b))[27].Goldreich 如下定义一个安全两方计算协议的安全性:如果存在概率多项式时间模拟算法S1与S2,使得

成立,则称协议π可被用于保密计算函数f(a,b).其中,表示计算不可区分.

Goldreich 利用比特承诺和零知识证明理论设计了一个编译器.向该编译器输入一个在半诚实参模型下安全计算f的协议π时,编译器会自动为我们编译输出一个安全协议π′,该协议在有恶意参与者参与协同计算情况下也能安全计算f.考虑到工程实际,本文规定本文构造协议中的参与者皆为半诚实类型.

1.3 Paillier同态加密方案[22]

Paillier 构造的方案(如图1 所示)可以利用密文的运算在明文空间Zn上实现同态加运算:E(x+y)=E(x)⋅E(y).该方案具有第1.1 节中定义1 定义的安全性:将等长的两个消息m0和m1加密,并将它们的密文分别记作C0与C1,对于任何实施选择明文攻击的敌手而言,计算上无法区分C0与C1,即

Fig.1 Paillier’s encryption scheme图1 Paillier 加密方案

1.4 高阶剩余类判定性问题

定义5(高阶剩余类判定性问题).该问题在文献[11]中被称作“decisional composite residuosity problem”,简称为DCR).简单地讲,如果给定两个等长大素数的乘积n=pq(其中p与q保密)和一个与n互素的整数z,对于敌手而言,判定事件“是否存在一个y,满足”成功的概率可以表述为一个忽略的函数[11].

文献[27]从可证明安全的需求出发,将其用形式化语言描述为如下形式:

设D是一种区分任意两个分布的算法,以系统安全参数τ为自变量的函数AdvD(τ)表示敌手利用区分算法D能够区分出Dran与DE的优势函数.

DCR 一直是在现代密码学中一个被公认的难解问题,关于DCR 难解性证明或阐述请参阅Paillier[22].所以,对于任意的敌手而言,利用任意多项式时间的概率算法D区分分布(n,R)的优势函数AdvD(τ)是一个可忽略的量,即存在一个关于安全参数τ的可忽略函数δ(τ),使得AdvD(τ)满足:

2 带云辅助计算的同态加密方案

对于Paillier 加密方案而言,主要的计算开销包括gmmodn2,rnmodn2和cλmodn2,其中,g=1+kn,.本节基于Paillier 加密方案和云外包计算,并采下述思想1 和思想2 设计了一个高效的同态加密方案.

思想1.在执行加密算法的过程中,将运算复杂度高的模指数运算gmmodn2(或gλmodn2)用与之运算结果等价的、运算高效的模乘运算1+m⋅(g-1)(modn2)(或1+λ⋅(g-1)(modn2))替代,从而实现快速而正确的加密.

思想2.将计算开销大的模指数运算rnmodn2委托给云服务器.

2.1 具体方案

此同态加密系统由4 种随机算法组成:云外包随机数模指数运算算法(COR)、密钥生成算法(KGen)、加密算法(Enc)和解密算法(Dec),其中,云外包随机数模指数运算可以在预处理阶段完成,也可以与密钥生成算法并行执行.在此,我们将该加密方案记作E=(COR,Kgen,Enc,Dec).

•KGen:产生长度相等的两个大素数p,q,并计算二者的乘积(n=pq)与二者分别减1 后的最小公倍数(λ=lcm(p-1,q-1)),为加密方案输出公钥(Kpub=(n,1+kn),其中,与私钥

•Enc:加密一方按照如下方式执行加密计算:

(1)从云服务器上下载集合R.

(2)自由确定适量的自模乘运算次数(θ),并从R上随机选择ℓ(ℓ＜＜n)个数(记作R1,R2,...,Rℓ∈R),随机选择χ1,χ2,...,χℓ∈{0,...,ℓ},其中,2≤θ≤ℓ(为了表述简单,在此约定文中此后的加密运算将以两个数为例:Ri,Rj∈R,i,j∈{0,…,ℓ}).

(3)对于m＜n,计算其中,

•Dec:解密方执行解密运算:

2.2 正确性验证

(1)加密运算中引入的随机变量可以在解密运算中被成功消除.

R虽然是公开的,但都是加密者在加密运算中随机选择的,因此,以为随机种子,由随机函数计算得到的Rx与计算(其中,是随机选择的)是等效的,因此,任何敌手由R计算Rx的困难性与破解Paillier加密方案的困难性是等价的.

2.2.2 替换运算的正确性

定理1.1+m⋅(g-1)(modn2)的结果与模指数运算gmmodn2的结果是等价的,即

又由二项式展开定理得:

综上可得:1+m⋅(g-1)(modn2)⇔gmmodn2.□

2.2.3 解密正确性

因为

所以有:

2.3 安全性分析

定理2.如果DCR 是难解问题,则E=(COR,Kgen,Enc,Dec)具有第1.1 节中定义1 所定义的不可区分安全性.

证明:在此先回忆一下DCR 问题挑战者的工作方式.

•在安全时间1k内,通过执行算法G(1k)算法产生两个大素数p和q,以及它们的乘积n.

•在Zn上随机选取一个数r,并从{0,1}中均匀选取一个数f.

•若f为0,则将R置为rnmodn2;若f为1,则将R置成R.

设E=(COR,Kgen,Enc,Dec)是2.1 节中构造的方案,将攻击E=(COR,Kgen,Enc,Dec)时,敌手使用的多项式时间算法记作A,下面利用算法A构造一个算法B,用于解决DCR 问题.该算法的具体工作方式如下.

(1)接收DCR 挑战者发来的(n,(n,R));

(2)令pk=(n,1+kn);

(3)将1n和pk发送给A;

(4)接收A发来的消息m0和m1;

(5)均匀地选取d∈{0,1};

(7)用d′表示敌手A对d的猜测结果;

(8)输出f′(如果d=d′,则置f′=0;如果d≠d′,则置f′=1).

因为算法B只通过调用算法A实现且只调用了3 次,而作为构成算法B的子算法A是在多项式时间内可被完成的算法,所以通过3 次调用算法A而实现的算法B是一种在多项式时间内可被完成的算法.因此,G(1k)也是一种在多项式时间内完成的算法.于是,构造算法B在DCR 安全游戏中获胜的概率可以表示成贝叶斯公式形式:

当f=0 时,DCR 挑战者置R=rnmodn2.这样,由算法A构造的算法B呈现给掌握算法A的敌手的视图与掌握算法A的敌手在实际攻击E=(COR,Kgen,Enc,Dec)的安全游戏中获取的视图相同.因此,掌握算法A的敌手在攻击E=(COR,Kgen,Enc,Dec)的安全游戏中获胜的概率等于d=d′在条件f=0 下的条件概率,即

当f=1 时,DCR 挑战者将R置成R.因为是均匀选取的,所以,执行运算后的结果在群Z/n2Z上是均匀分布的;又因为3 个随机变量m0,m1,d相互独立,因此,pk和C*没有暴露关于d的任何消息,这意味着掌握算法A的敌手对于d的猜测结果d′与d相互独立.若在{0,1}上随机选取d,则d=0 或d=1的概率各为,故有:

成立.联立公式(3)～公式(5),我们可以得到:

因此,算法B在DCR 安全游戏中获胜的优势为

由第1.1 节中定义1 可知,在DCR 安全性游戏中,利用算法A构造的算法B获胜的优势是一个可忽略的量,所以是一个可忽略的值.这意味δ也是一个可忽略的量.所以利用算法A的敌手在攻击方案E的IND-CPA 安全游戏中获胜的优势是一个可忽略的量,即E=(COR,Kgen,Enc,Dec)具有IND-CPA 安全性.□

2.4 加密方案的效率分析

Table 1 Comparative analysis on the efficiency of encryption and decryption表1 加、解密效率对比分析

3 保密社交意愿探测协议

3.1 保密社交意愿应用背景描述及其形式化

Alice(需求者)是保险公司的职员,某天在某一个城市推销保险产品,她只想约谈现在正好在某个区域内的客户(可能住在该区域,也可能正在该区域且有空闲时间),她与不想向不在该区域且不愿约谈的用户透露自己的活动区域,例如她想约谈客户Bob,但Bob 只想让Alice 知道他是否可被约谈而不想透露自己的具体位置.Bob和Alice 怎样做才能同时实现他们的各自的目的呢?然而,安全多方几何计算为解决这种问题提供了一种可行的方法.我们将Bob 和Alice 采用安全多方几何计算思路实现保密测试社交意愿的问题称为保密社交意愿探测问题,其形式化描述如下:

Alice 拥有一个有K个顶点构成的私有凸多边形P,表示她现在利益最大的活动范围.其中,该多边形的边是按逆时针方向标注的,如图2 所示(以K=7 为例).

Fig.2 Abstract geometrical figure of private social-willing testing图2 保密社交意愿探测几何抽象图

Bob 拥有一个私有点pb=(bx,by),表示他现在所处的位置.Alice 想知道Bob 是否处在自己的想活动的范围内,Bob 不想透露自己的具体位置.我们设计一个这样的安全多方计算协议要实现对Alice 与Bob 的隐私保护.

•协议结束时,Alice 只得到一个意愿探测的结果(一个布尔值),而Bob 的具体位置信息对于Alice 仍然是一个秘密.

•协议结束时,最多只得到Alice 多边形的边数K-1(Bob 没有得到意愿探测的结果),而Alice 的活动区域的形状、位置与活动区域的大小对于Bob 仍然是一个秘密.

3.2 保密社交意愿探测协议

3.2.1 判定凸多边形与一个点位置关系

非保密的近感探测问题实际上就是判定某个凸多边形P(有K个顶点)是否包含一个点pb=(bx,by)的问题.可以通过K次计算有向线段与点pb=(bx,by)的位置关系来实现[24-26,29].对于点pi,pb,pi+1构成的有序元组〈pi,pb,pi+1〉在平面上可能对应着3 种位置关系(如图3 所示).

•正向:3 个点构成的方向角∠pi,pb,pi+1为逆时针走向(如图3(a)所示).

•反向:3 个点构成的方向角∠pi,pb,pi+1为顺时针走向(如图3(b)所示).

•零向:3 个点构成的方向角∠pi,pb,pi+1=180°,即pi,pb,pi+1共线(如图3(c)所示).

Fig.3 Position relations between a point and a line segment图3 点与线段的位置关系

假设点pi,pb,pi+1的坐标分别为,则3 点构成的方向角∠pi,pb,pi+1的方向可以通过计算下列行列式来确立:

其中,Di＞0,Di＜0,Di=0 分别对应着图3(a)～图3(c).

因此,下面的算法可以正确计算出近感探测的结果.

凸多边形与点的关系判定算法.

输入:由K个按逆时针顺序访问的顶点构成的凸多边形P,点pb.

输出:“1”,如果pb在P内;“0”,否则pb不在P内.

(1)对于i∈{1,2,…,K-1}计算点pb与有向线段两个端点所构成的方向角∠pi,pb,pi+1的方向Di.

(2)如果对于∀i∈{1,2,…,K-1}都有Di≤0,则返回“1”;否则,返回“0”.

3.2.2 保密社交意愿探测协议

利用上述凸多边形与点的位置关系判定方法、第2.1 节中设计的带云辅助计算的同态加密方案以及一种新的保密符号计算方法,设计了一个保密社交意愿探测协议.

保密社交意愿探测协议.

输入:Alice 输入由K个按逆时针顺序访问的顶点构成的凸多边形P,Bob 输入点pb.

输出:“1”,如果pb在P内;“0”,否则pb不在P内.

2.Alice 运行加密系统E=(COR,Kgen,Enc,Dec)的密钥生成算法Kgen,生成公钥Kpub=(n,1+kn)和私钥Kpri=λ;

3.Alice 首先从云服务器上下载集合R并随机选取,然后按照如下方式操作:

(1)对于j∈{1,2,…,K-1}计算(假设Alice 将χ1,χ2取作χ1=χ2=1,并置ℓ=2):

4.对于i∈{1,2,…,K-1},Bob 收到后,按照如下方式进行:

(2)从云服务器上下载集合R后,随机选择个数:,其中,ℓ是一个比1 大一些的小整数.并计算:

5.对于i∈{1,2,…,K-1},收到以后,Alice计算:

6.通过判断θi与“1”的关系,确定Di的符号:

其中,Sign(⋅)为符号函数.

7.如果对于∀i∈{1,2,…,K-1}都有Di≤0,则返回“D=1”;否则,返回“D=0”.

3.3 保密社交意愿探测协议保密性分析

定理3.保密社交意愿探测协议可以安全地实现Alice,Bob 两方的社交意愿探测.

证明:该协议安全与否的关键是协议执行后有没有造成参与者私有信息的泄露.接下来,我们将证明保密意愿探测协议在安全计算约谈意愿的过程中,Alice(持有凸多边形的活动区域P,由顶点构成)、Bob(持有位置pb)两方除了得到“是否约谈”外,都无法获得有关对方私有数据的其他任何信息,即协议未给Alice、Bob 两方造成信息泄露.

•对于Alice 数据的安全性

我们首先构造一个模拟保密探测协议执行的模拟器SB.该模拟器的输入为:Alice 随机选择一个凸的活动区域,Bob 的私有位置pb,那么由模拟器SB产生的视图为,其中,1≤i≤k;而保密社交意愿探测协议的实际执行产生的视图为,其中1≤i≤k.因为Alice 传输给Bob 的信息是用自己的公钥(n,n+1)对自己的私有信息加密后的密文,又因方案E已被证明在选择明文攻击下具有语义不可区分安全,所以由加密方案E产生的密文是语义不可区分的,可得是不可区分的.从而可得与真实视图是不可区分的,也就是说,满足定义关系式(2).

•对于Bob 位置信息的私密性

我们构造一个Bob,输入其私有位置信息以及由其随机选择的就能模拟Alice 视图的模拟器SA.于是,由模拟器SA产生的视图为

综上所述,Alice 和Bob 的私密性满足安全定义的形式化等式(1)和等式(2).所以,保密社交意愿探测协议可以安全地实现Alice、Bob 两方社交意愿的探测.□

4 保密社交意愿探测协议效率分析

不失一般性,我们假定Alice 和Bob 为文献[1]的协议和本文协议的参与者,并假定Bob 的坐标为(bx,by),Alice提供的意愿区域为K个顶点构成的凸多边形.为了进行公平比较,此处将执行协议时花费的总开销统一用一次自模乘运算()作为统计的基本单位.

Alice和Bob 在执行文献[1]的协议时,总共至少需要K(8n+bx+by+2λ)次自模乘运算().因为基于云外包计算的同态加密方案E中的计算可以在预处理阶段由云服务器完成,并且Alice 和Bob 在预处理阶段可以随时随地地从云服务器下载集合,所以得到集合的时间可以忽略不计;又因为Alice 和Bob 在得到集合后,利用集合中的元素,通过执行有限次的模乘运算(),即可秘密地得到,不再需要做n次自模乘运算().因此,基于同态加密方案E的保密社交意愿探测协议时,Alice 和Bob 总计需要花费K(18+2bx+2by+2kb+2(ℓ+2)+2λ)次自模乘运算().显然,本文的协议比文献[1]的协议在运算效率上有了质变性的提升.

基于同态加密方案E的保密社交意愿探测协议可以解决Alice 出具的K个顶点相邻顶点坐标差小于0 的情形;而对于文献[1]的协议而言,当Alice 出具的K个顶点相邻顶点坐标差小于0 时,它无法正确运行.此外,文献[1]的协议只能用于解决实时位置的近感探测问题,已经不能满足社交网络用户新的个性化需求;而本协议不仅可以用于彻底解决文献[1]的协议提出的近感探测问题,还能满足社交网络用户日益增长的个性化需求:保密社交筹划,即保密社交意愿探测,解决的是保密探测领域中的新问题.下表是保密社交探测协议和协议在效率(用执行协议时各参与方在加密和解密算法中花费的计算开销总和体现)、解决问题的能力(从能否解决保密探测区域相邻两点坐标差商小于0 的情形体现)以及能够解决的问题这3 个方面的对比.保密探测协议与文献[1]的协议的对比分析见表2.

Table 2 Comparative analysis on private social-willing test and the protocol of Ref.[1]表2 保密探测协议与文献[1]的协议的对比分析

5 结束语

本文对保密意愿探测问题进行了研究.为了高效地解决这一问题,首先设计了一个带云辅助计算的同态加密方案;然后,利用该加密方案设计了一个高效的保密意愿探测协议.分析结果表明,此协议在效率和安全性方面都优于先前的类似协议,并且其安全性是在标准的ideal/real 模型下实现的.