K-匿名批量认证的位置隐私保护机制

杨囡囡,宋 成

( 河南理工大学 计算机科学与技术学院,河南 焦作 454003)

0 引 言

随着移动终端设备、通信技术、定位技术及地理信息系统的迅猛发展,用户对位置服务(location based service,LBS)[1]的依赖性大幅增强,如短距离导航[2]、滴滴打车、手机点菜等。但用户在享受位置服务便利的同时,用户的个人兴趣、行踪轨迹等隐私信息也存在泄露的风险。若攻击者获取用户位置信息,或许给用户的人身安全造成威胁。随着人们生活节奏的加快,在确保安全性的基础上,用户对位置实时性要求也越来越高。因此,位置隐私保护技术的安全和效率是当前信息安全领域的热点之一[3-4]。

近年来,学者们针对位置隐私问题展开大量研究,并取得了一系列的成果。文献[5]构建一个包含位置隐私和细粒度访问控制的双服务器体系架构,提出一种基于安全多方计算和同态加密机制的双重位置加密协议和密文位置搜索协议,实现了安全精确的K近邻检索,但同态加密机制算法复杂,计算量较大。文献[6]提出一种双曲线查询解析技术,采用单向转换加密,将用户位置坐标转换成Hilbert序列,该方案在数据转换过程需要额外的处理机制来保证较高准确度,使得处理复杂度、计算量增加。文献[7]在LBS端和用户端使用属性加密算法,实现位置查询服务和反馈中零信息泄露,但通信和计算相对复杂。文献[8]通过n元线性方程组的解实现匿名,若系数矩阵的秩小于n,则有无穷多解,将解和真实身份进行哈希值作为假身份标识,当有用户加入或退出时,对应的数据表需要更新。文献[9]利用模幂运算实现匿名,但在整个过程中匿名认证的空间复杂度高,效率较低。文献[10]利用哈希实现匿名,但攻击者可根据用户与可信第三方的交互信息求解假名和身份标识之间的对应关系。文献[11]使用具有标志性的位置点代替真实用户发起查询,但查询结果依赖于代替位置点信息,其服务质量难以保证。文献[12]在敏感路段进行等级划分,根据位置树的高度分配相应的隐私预算,添加Laplace噪声,尽管数据可用性较高,但服务质量有待提升。文献[13]基于半可信第三方服务的隐私保护系统结构,在网格内使用历史查询概率和位置偏移构建k匿名集,虽然Stackelberg博弈优化隐私保护水平,但系统整体运行效率不高。文献[14]使用服务相似地图,将满足用户服务质量的区域与真实用户所在区域合并构成匿名候选区,在候选区域中使用位置熵构建K-匿名集,并在K-匿名集中使用贪心策略选择一个位置点代替真实用户进行服务请求,但用户的位置隐私信息通过区域连续关联性可被获取。文献[15]提出无可信第三方的K-匿名假位置技术,使用语义差异、查询概率以及位置的分散均匀程度构造假位置集,避免攻击者结合背景知识攻击,但移动用户端计算开销大。文献[16]考虑现在的隐私技术很少关注位置语义信息,结合k-匿名、l-语义多样性、差分隐私等技术来保证匿名区域的隐私性。虽然半可信第三方可平衡计算开销,但需要合理分配隐私预算。

1 预备知识

1.1 位置隐私保护系统架构

位置隐私保护系统架构如图1所示,系统架构由3部分组成：移动用户终端、可信匿名服务器和LBS服务器,各部分的功能如下。

图1 位置隐私保护系统架构Fig.1 Location privacy protection system architecture

1)移动用户终端。向可信匿名服务器发送匿名化请求,筛选出最优的假位置集,向LBS服务器发送查询请求并接收LBS服务器查询结果。

2)可信匿名服务器。处理移动用户端发送的匿名化请求,并将注册结果返回给用户,公布系统参数。

3)LBS服务器。批量认证用户,处理移动用户终端发位置服务请求并将查询结果返回给用户。

1.2 位置熵

位置熵起源于香农熵[17],是一种度量隐私保护方法,熵越大,真实用户不被识别的可能性越大。假设在N×N个位置单元候选区域中有k个候选假位置构成的匿名集合,oi为匿名集合第i个位置的查询概率(i=1,2,…,k),则匿名集合中每个位置单元是真实用户的概率为

(1)

在N×N个位置单元候选区域中有k个候选假位置构成的匿名集合,匿名集合中某一位置单元的查询概率为Oi,那么位置熵为

(2)

2 位置隐私保护方案

2.1 系统初始化阶段

步骤1设Fp表示阶为p的有限域,定义一个椭圆曲线E：y2=x3+ax+bmodp,其中a,b∈Fp,在E上选择一个阶为q,生成元为p的加法群Gp。

步骤4可信匿名服务器公开系统参数(a,b,p,q,Gp,Ppub,P,H1,H2,H3),x作为系统私钥保存。

2.2 注册阶段

步骤3用户终端收到消息后,验证luP=PKu-Ppub是否成立,若成立则计算私钥SKi=ni+li;否则,返回第1步重新请求。假身份、公钥和私钥分别为PIDi、PKi、SKi。

2.3 假位置生成与选取阶段

步骤1以用户所在的位置单元为中心向四周均匀扩展成合适大小的矩形,其长为a个网格,宽为b个网格,在所选矩形区域中均匀使用随机点算法生成假位置li=(xi,yi),结合真实地图背景信息判断假位置是否合理,如果不合理,则重新生成。

步骤3判断假位置集合L中的元素是否小于2k个,若小于则返回第1步继续生成;否则,执行下一步。

步骤4根据(1)式计算位置集L中每个假位置的查询概率Oi,然后从2k个假位置中选择Oi较高的k-1个假位置构成最终假位置集合Lend=(l1,l2,…,lk-1)。

步骤5用户为真实位置和假位置集合Lend分配假身份标识PIDi。

2.4 位置服务请求阶段

3 方案分析

3.1 正确性分析

1)验证luP=PKu-Ppub。

PKu-Ppub=ruP-xP=(ru-x)P=luP

[(a2n2+SK2β2)P-∂2]+…+

[(aknk+SKkβk)P-∂k]=

[(a1n1+(n1+r1-x)β1)P-∂1]+[(a2n2+

(n2+r2-x)β2)P-∂2]+…+[(aknk+

(nk+rk-x)βk)P-∂k]=

[(a1n1P+(n1P+r1P-xP)β1)-∂1]+

[(a2n2P+(n2P+r2P-xP)β2)-∂2]+…+

[(aknkP+(nkP+rkP-xP)βk)-∂k]=

[(a1N1+(N1P+PK1-Ppub)β1)-∂1]+

[(a2N2+(N2P+PK2-Ppub)β2)-∂2]+…+

[(akNk+(NkP+PKk-Ppub)βk)-∂k]=

[∂1+(N1P+PK1-Ppub)β1-∂1]+

[∂2+(N2P+PK2-Ppub)β2-∂2]+…+

[∂k+(NkP+PKk-Ppub)βk-∂k]=

(N1P+PK1-Ppub)β1+(N2P+PK2-Ppub)β2+…+

3)验证zuP-∂u=F+(Nu+PKu-Ppub)βu

zuP-∂u=(f+Bu)P-∂u=

(f+(aunu+SKuβu))P-∂u=

(f+(aunu+(nu+ru-x)βu))P-∂u=

fP+(aunuP+(nuP+ruP-xP)βu)-∂u=

F+(auNu+(Nu+PKu-Ppub)βu)-∂u=

F+(∂u+(Nu+PKu-Ppub)βu)-∂u=

F+∂u+(Nu+PKu-Ppub)βu-∂u=

F+(Nu+PKu-Ppub)βu。

3.2 安全性分析

3.2.1 匿名性

匿名性的验证步骤如下。

步骤1攻击者A发起询问获取系统公开参数{a,b,p,q,Gp,Ppub,P,H1,H2,H3}和相关参数。

步骤2攻击者A选取k个不同的信息m1,m2,…,mk。

步骤3用户U选取随机位u∈{1,2,…,k}(对攻击者A保密),mu为用户的真实查询内容。然后将m1,m2,…,mu,…,mk发送给LBS服务器。

步骤4LBS服务器对接收到的信息m1,m2,…,mk加密得到c1,c2,…,ck并发送给用户U。

步骤5若用户U收到密文c1,c2,…,ck与m1,m2,…,mk相对应,则将c1,c2,…,ck按照随机顺序发送给攻击者A;否则,停止游戏。

攻击者A赢得游戏的优势为：Adv(A)=|Pr(A)|,其中Pr(A)表示攻击者A能够解密获得mu,即解密获得用户真实查询结果的概率。

定理1如果攻击者A能以可忽略的概率赢得该游戏,那么该方案满足匿名性。

证明如果攻击者A得到加密结果c1,c2,…,ck,其中cu=mu⊕H3(BuP+Du),攻击者A尝试以解密密文的方式获取消息mu,需要在猜测正确u的基础上,求解H3(BuP+Du),即需要知道系统秘钥x以及参数nu、au、ru,则必须通过Ppub=xP、Nu=nuP、∂u=auNu、PKu=ruP求解x、nu、au、ru,面临求解椭圆曲线离散对数问题。所以攻击者A能够解密用户U的隐私信息mu的概率Adv(A)=|Pr(A)|可忽略不计,即该方案满足匿名性。

3.2.2 不可伪造性

定理2如果攻击者A在多项式时间内不能假冒可信匿名服务器伪造用户注册信息,那么该方案满足不可伪造性。

证明如果攻击者A可以在多项式时间内以不可忽略的概率注册与用户U相同的注册信息,即攻击者A可以在多项式时间内以不可忽略的概率计算出系统私钥x和参数ru,使等式luP=PKu-Ppub成立。

挑战者C运行并生成系统参数(a,b,p,q,Gp,Ppub,P,H1,H2,H3),并向攻击者A公布,其中Ppub=xP,x为系统私钥,并对攻击者A保密。

在伪造过程中由于攻击者A不能获取系统主密钥x和随机数ru,无法使等式luP=PKu-Ppub成立。若攻击者尝试通过等式Ppub=xP、PKu=ruP获取系统主密钥x和参数ru,则面临求解椭圆曲线离散对数难题。因此,攻击者A在多项式时间内不能以不可忽略的概率解决椭圆曲线离散对数问题,即该方案满足不可伪造性。

3.2.3 抗假冒攻击

定理3在求解椭圆曲线离散对数问题是困难的情况下,如果攻击者A在多项式时间内不能冒充用户发送正确的签名,那么该方案抗假冒攻击。

3.3 仿真实验

本方案从假位置生成效率和隐私保护程度两方面对方案进行仿真实验。仿真实验在1.60 GHz英特尔i5CPU、8 GB内存的PC机和Matlab 2018b仿真软件的环境下进行。实验选取2.5 km×2.5 km的真实地理地图,将地图划分成100个位置单元,实验中的主要影响参数为匿名度k。

3.3.1 效率分析

方案以生成时间作为假位置生成效率,匿名度与假位置集合生成的时间关系如图2所示。图2中,3种方案生成假位置的执行时间都随着k的增大而增大。在匿名度较小时,文献[15]与本方案所需时间相近,随着匿名度的增大,语义差异、查询概率相近及假位置的分布,导致文献[15]假位置集生成时间增大。文献[16]在选取假位置时使用k-匿名、l-多样性、差分隐私来保证匿名区域的隐私性。根据l-语义多样性在道路网上将各部分划分成不同的区域,然后在用户所在的区域结合差分隐私和k-匿名选出最优的假位置集,使得文献[16]方案运行效率低。

图2 匿名度与假位置集合生成的时间关系Fig.2 Relationship between anonymity and the generation time of false location set

本文方案在响应请求服务时不仅效率有所提高,而且减少了信息交互次数。文献[15-16]构建K-匿名后,向LBS服务器发送k个连续的查询请求,LBS在进行查询服务前需逐个认证用户,然后依次进行查询处理。而本方案在构建k-匿名后,用户将k个用户签名消息和查询请求一次性发送给LBS,LBS收到服务请求后,通过批处理的方式一次性对k个用户的匿名身份进行认证,然后处理k个用户的服务请求,最后将k个服务请求结果一次性发送给用户,从而提高认证效率并且减少LBS与用户之间的信息交互次数。

3.3.2 位置熵

位置熵是衡量假位置的重要因素。位置熵越大隐私保护程度越大。匿名度与位置熵关系如图3所示。由图3可知本文方案与文献[15]、随机方案的位置熵随着匿名度的增大而增大。随机方案对假位置的合理性考虑不充分,所以隐私保护效果一般。文献[15]在选取假位置时充分考虑到语义多样化、地理位置尽量分散使得假位置更加合理,但本方案的位置熵始终优于文献[15]。因此,隐私保护效果更好。

图3 匿名度与位置熵关系Fig.3 Relationship between anonymity and position entropy

4 结束语

为了解决移动用户位置隐私泄露问题,本文提出一个基于椭圆曲线密码体制的k匿名批量认证的位置隐私保护方案,采用批处理,减少信息交互次数,提升了执行效率;通过在匿名区域中结合随机位置点生成算法和位置熵筛选最优的k-1个假位置,增强用户隐私保护度。安全性分析表明,本文方案满足匿名性、不可伪造性、抗假冒攻击等安全特性。仿真实验表明,本文方案在效率和隐私保护度方面具有一定的优势。