一种面向移动终端的K匿名位置隐私保护方案

宋 成，金 彤，倪水平，贺军义，杜守恒

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

随着计算机技术、全球定位系统和无线通信网络的发展，基于位置服务(Location Based Service，LBS)技术[1-3]得到日益广泛的应用，如车载导航、网约车、外卖、网上购票等，给用户的生活带来了极大的便利，并不断改变着人们的日常行为模式。在用户对位置服务的依赖性与日俱增的同时，个人位置隐私泄露的风险无处不在。运动的用户在请求位置服务过程中，需要实时向位置服务服务器提交自己当前的位置信息和需要查询的信息，根据时空关联性，可构建用户的位置轨迹数据信息。而根据用户轨迹能够推断出用户在何时去了何地、用户的家庭住址、工作地点等敏感位置，进而可推断用户的健康状况、宗教信仰、生活习惯等隐私信息。如果攻击者获取用户的位置信息，将会给用户造成与位置相关的隐私泄露的风险。因此，位置隐私保护技术是当前移动网络安全领域研究的热点之一。

针对当前位置隐私保护存在的问题，结合K匿名技术和不经意传输协议的思想，提出一种面向移动终端的K匿名位置隐私保护方案。方案中，用户首先将包含真实用户在内的k个身份标识作为注册请求发送给位置服务服务器，位置服务服务器为k个身份标识生成假名和对应的公私钥对；然后，移动终端将生成并选取假位置，基于不经意传输协议与位置服务服务器完成位置服务查询。

1 相关工作

近年来，国内外学者在位置隐私保护技术方面做了大量的工作，并取得一系列的成果。根据位置隐私保护体系结构的不同，这些成果大致可分为两类：一类为基于可信匿名中心的位置隐私保护技术，另一类为基于移动终端的位置隐私保护技术。

基于可信匿名中心的结构又称为基于可信第三方结构，由GEDIK和LIU[4]首次提出。基于可信匿名中心结构的位置隐私保护方案通过在用户和位置服务服务器之间引入可信匿名中心；可信匿名中心通常结合一些隐私保护技术[5-8]对用户服务请求消息匿名化，同时负责完成用户与位置服务服务器之间的消息转发，进而实现对用户位置隐私的保护，并降低用户端存储开销和计算开销。K匿名技术[9-11]是目前应用最为广泛的一种位置隐私保护技术，其主要思想是形成至少包含其他k-1个不同用户的匿名区域，然后用匿名区域取代真实用户信息向位置服务服务器发送服务请求，从而降低用户位置精度，使攻击者识别匿名区域中真实用户的概率不超过1/k。针对传统K匿名技术只能对预定义的固定属性进行匿名化处理的局限性，OTGONBAYAR等[12]将不同的语义描述数据进行分区，合并语义相似的数据，提出一种合并相近语义数据流的K匿名的方法，降低信息丢失率。K匿名能够阻止身份信息的泄露。但无法阻止属性信息的泄露，为了验证该问题，TU等[13]在轨迹数据发布过程中成功实现了语义攻击，并结合K匿名、L多样性和T相似度这3种数据脱敏方法，提出一种阻止语义和重新识别攻击的隐私保护方案。另一种常用的位置隐私保护技术是混合区域技术[14]，用户进入混合区域时，停止同位置服务服务器的所有通信，离开时通过可信匿名中心更换用户假名，进而防止攻击者根据用户连续提交位置的关联性来跟踪用户。由于大型混合区域会严重影响服务质量，MEMON等[15]根据交通系统和停车位置的相关程度，构建多重混合区域，在确保匿名性的基础上解决了混合区域内的用户多样性问题。

可信匿名中心虽可作为可信第三方结构的核心，但现实生活中完全可信的匿名中心难以存在。即使存在，依旧存在被攻击者破解的风险。一旦可信匿名中心被攻破，所带来的泄露风险更加严重。同时，由于匿名中心负责匿名化的计算以及消息转发存储等功能，可能会成为系统性能的瓶颈。针对单匿名中心的不足，张等[16]引入分布式多匿名服务器，通过位置预测机制和假位置选择机制获取G-1个查询混淆位置，形成匿名域，然后随机选择一个匿名服务器完成服务；但该结构会造成系统整体成本上升。PENG等[17]使用半可信中间实体执行匿名和筛选功能，利用希伯特曲线转换用户位置信息，实现用户位置隐私信息的保护；但半可信中间实体依然会成为系统性能的瓶颈。

随着移动终端性能的不断提升，其计算和存储能力得到了巨大的提高。因此，基于移动终端的隐私保护方案具备了可行性，能够避免传统方案的安全性能对可信匿名中心的依赖和性能瓶颈问题。一些学者已经在这方面做了大量研究工作，如李等[18]提出利用隐马尔科夫转移矩阵模型预测用户的运动轨迹，并将用户下一时刻的预测位置作为前一时刻的查询内容；HAYASHIDA等[19]提出利用旅行推销商贪心算法生成虚假轨迹，通过虚假轨迹与真实轨迹相交来隐藏用户的位置信息；PENG等[20]提出通过生成虚假查询信息混淆真实轨迹，并通过用户间的协作缓存收集消息。毛典辉等[21]提出构建多粒度抽象路网与位置情境模型，根据用户个性化设置，实现自适应选取查询点和查询区域。尽管这些方案避开了对可信匿名中心的依赖，但它们只考虑了用户端的隐私性，而忽视了位置服务服务器端的隐私性。如果单一用户可以通过已获得的部分信息推导出LBS服务器的全部信息，则这将造成其他用户的个人信息外泄和位置服务服务器的失效。因此，位置服务服务器端的隐私性同样需要保护。

2 预备知识

2.1 位置隐私保护系统架构模型

如图1所示，移动终端用户通过卫星定位系统获取自身位置信息并在其周围生成k-1假位置(对应注册的k-1个假身份)及相应的伪查询内容，然后通过附近的基站连接网络，将包含伪查询和真实查询请求的k个请求发送给位置服务服务器。位置服务服务器接收并处理相应的请求，将加密后的兴趣点集通过基站返回给移动终端。移动终端用户对加密结果集进行解密，获得兴趣点的相关信息(如店铺名称、地理位置、交通路线等)。完整系统架构模型由两部分类实体组成：移动终端和位置服务服务器。各部分的作用如下：

(1) 移动终端：负责位置服务服务器发送匿名化处理请求，生成并筛选假位置节点，向位置服务服务器发送位置查询服务请求，并接收来自位置服务服务器的查询服务结果。

(2) LBS服务器：负责用户的注册，位置服务查询及查询结果的响应。

图1 位置隐私保护系统架构

2.2 双线性映射

设q是一个大素数，G1和G2分别为两个阶均为q的加法群和乘法群，G1到G2的双线性映射e：G1×G2→G2满足以下性质：

(1) 双线性：任意P，Q，R∈G1，a，b∈Z*q，满足e(aP，bQ)=e(P，Q)ab，e(P+Q，R)=e(P，R)e(Q，R)和e(P，Q+R)=e(P，Q)e(P，R)。

(2) 非退化性：存在P，Q∈G1，使得e(P，Q)≠1G1，其中1G1为群G1的单位元。

(3) 可计算性：任意P，Q∈G1，都存在一个有效算法计算e(P，Q)。

(4) 对称性：任意P，Q∈G1，满足e(P，Q)=e(Q，P)。

2.3 位置熵

假设某匿名区域R内有k个候选位置节点，k个位置节点被查询概率分别为Yi(i=1，2，…，k)，那么每个位置成为真实位置的概率为

(1)

给定一个包含k个候选位置的匿名区域R，每个位置在匿名区域R内成为真实位置的概率记为Pr(i)，那么它的位置熵值为

(2)

利用式(1)和(2)可得节点位置熵，候选位置节点熵值越高，隐私保护水平越高。

3 面向终端的K匿名隐私保护方案

3.1 系统初始化阶段

步骤1 选择2个阶为q的循环群G1，G2；其中，G1为加法循环群，G2为乘法循环群，q是一个大素数。e：G1×G2→G2表示一个双线性映射。

步骤2 定义3个哈希函数H1，H2和H3。其中，H1：{0，1}*→G*1，H2：G2→{0，1}n，H3为SHA256的哈希函数，n表示一个整数，{0，1}*表示任意长度的二进制串。

步骤3 位置服务服务器选取一随机数s∈Z*q作为系统私钥，计算其公钥：PK=sP，其中，P为G1的生成元。

步骤4 位置服务服务器保存系统私钥s并公开系统公共参数：{G1，G2，e，n，q，P，PK，H1，H2}。

3.2 用户注册阶段

步骤1 移动终端将k个身份信息{ID1，ID2，…，IDk}作为注册请求发送给位置服务服务器，其中用户身份IDu位于请求消息的第u个位置，u∈{1，2，…，k}，u由用户选择。

步骤2 位置服务服务器使用伪随机生成器生成盐值IDsalty，分别计算对应的假名PIDi=H3(IDi+IDsalty)，对应的公钥UiPK=H1(IDi)和私钥UisK=sUiPK，然后生成信息{(PID1，U1PK，U1SK)，(PID2，U2PK，U2SK)，…，(PIDk，UkPK，UkSK)}并通过安全信道反馈给用户。

步骤3 用户收到消息后计算UPK=H1(IDu)，并判断等式e(USK，P)=e(UPK，PK)是否成立。若等式成立，则用户得到正确的假身份、公钥和私钥；否则，用户所得消息失效，返回步骤1。

3.3 假位置生成与选取阶段

步骤1 移动终端以用户B的位置LB为中心点，采用矩形区域内均匀分布随机点算法生成一个假位置Li，假设矩形区域为：[a，b]×[e，f]，独立生成D(0，1)内均匀随机数αi和βi，计算xi=(b-a)βi+a和yi=(f-e)αi+e，分别得到[a，b]和[e，f]内均匀生成的随机点Li=(xi，yi)。再根据地图的背景信息判断该位置的合理性；若为山川、河流等位置，则放弃该位置重新生成；否则，计算该点相对于点LB=(xB，yB)的欧几里得距离dis(LB，Li)=((xB-xi)2-(yB-yi)2)1/2。

步骤2 移动终端判断不等式Rmin≤dis(LB，Li)≤Rmax是否成立，其中Rmin和Rmax分别表示中心点到新生成假位置的最短距离和最远距离。如果满足，则让ci=Li，并将其加入位置集合C={c1，c2，c3，…，ci-1}中，即C={c1，c2，c3，…，ci-1}∪{ci}；如果不满足，则重新返回步骤1。

步骤3 若得到的假位置数量不足2k个，则返回步骤1继续生成；否则，执行下一步。

步骤4 根据式(1)计算每个假位置成为真实位置概率Pr(i)，然后从2k个假位置中选取成为真实位置概率Pr(i)较高的k-1个假位置{L1，L2，…，Lk-1}组成较优假位置集合CEnd。

步骤5 移动终端为包括自身在内的k个位置节点分配虚假身份标识。

3.4 位置服务请求阶段

步骤1 位置服务服务器随机选取d1，d2，…，dn∈Z*q，其中，n≥k，分别计算P1=d1PK，P2=d2PK，…，Pn=dnPK，并将其作为选择基点公布。

步骤2 用户B随机选择a1，a2，…，ak∈Z*q，计算vi=aiPi，其中i=1，2，…，k。

步骤3 用户B结合生成的假身份，位置节点信息和伪查询内容组成查询集合：Msg={(PID1，L1，Q1，v1)，(PID2，L2，Q2，v2)，…，(PIDu，Lu，Qu，vu)，…，(PIDk，Lk，Qk，vk)}，发送给位置服务服务器，其中，Lu表示真实节点位置，Qu表示真实查询请求。

步骤4 位置服务服务器接收到位置服务请求后，获取k个查询结果{m1，m2，…，mu，…，mk}，然后选取随机数r∈Z*q，计算Y0=rPK，Yi=rvi和ci=mi⊕H2(e(Pi+sPK，UBPK)r)，并将{Y0，(Y1，Y2，…，Yu，…，Yk)，(c1，c2，…，cu，…，ck)}发送给用户B，其中，UBPK，UBSK分别表示用户B的公私钥对。

步骤5 用户B收到消息后，判断等式e(vu，Y0)=e(Yu，PK)是否成立。若成立，则用户B计算au的乘法逆元a-1u∈Z*q，解密密钥Vu=a-1uYu，mu=cu⊕H2(e(Vu，UBPK)e(Y0，UBSK))，从而获取查询结果(若是多个服务请求，则计算多个查询结果)；若不成立，则用户B放弃该查询结果，返回步骤1，重新服务请求。

4 方案分析

4.1 安全性分析

4.1.1 匿名性

定义1匿名游戏。

步骤1 攻击者A发起询问获取系统公开参数{G1，G2，e，n，q，P，PK，H1，H2}，LBS服务器公开的选择基点P1，P2，…，Pn以及Y0，Y1，Y2，…，Yk；

步骤2 攻击者A选取k个完全不同的信息m1，m2，…，mk，作为用户B的候选查询结果；

步骤3 用户B选取随机位u∈{1，2，…，k}，然后将{m1，m2，…，mu，…，mk}发送给LBS服务器，其中u对攻击者A保密；

步骤4 位置服务服务器对{m1，m2，…，mu，…，mk}进行加密并返回结果{c1，c2，…，cu，…，ck}给用户B；

步骤5 若用户B收到的密文结果{c1，c2，…，cu，…，ck}与{m1，m2，…，mu，…，mk}相对应，则将密文按照随机顺序发送给攻击者A；否则，终止游戏；

步骤6 若攻击者A通过对密文结果的解密能够输出mu=mu，则攻击者A赢得这场游戏。

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

4.1.2 抗重放攻击

定义2攻击者A通过重新发送LBS服务器已处理的用户注册请求消息和位置服务请求消息，试图获得与用户B相同的结果。攻击者A能够知晓的信息包括：系统公开参数{G1，G2，e，n，q，P，PK，H1，H2}，用户B的注册请求消息{ID1，ID2，…，IDk}，位置服务请求消息Msg，LBS服务器公开的选择基点P1，P2，…，Pn。

定理2如果攻击者A以可忽略的概率获得与用户B相同的注册结果和位置请求服务结果，那么方案可抗重放攻击。

4.1.3 不可伪造性

(1) 初始化阶段。挑战者C产生公开的系统参数{G1，G2，e，n，q，P，PK，H1，H2}和保密的主密钥s。

(2) 训练阶段。攻击者A向挑战者C发送身份信息IDi，请求预言机H1的应答，挑战者C运行密钥生成器算法，生成相应的公私钥对并返回给攻击者A。这一过程可重复训练，多项式有界次。

定理3方案的随机预言模型中，如果攻击者A无法在多项式时间内求解LBS服务器的私钥s和临时会话私钥r，则本方案满足不可伪造性。

证明：系统初始化阶段，挑战者C向攻击者A公开参数{G1，G2，e，n，q，P，PK，H1，H2}和用户与LBS服务器间的通信消息，其中PK=sP，s为系统生成的随机数，对攻击者A保密。

用户注册阶段，攻击者A向随机预言机H1进行适应性询问，查询获取相应的哈希值。具体过程如下：

攻击者A向挑战者C请求身份信息IDi的哈希值H1(IDi)，挑战者C检测请求-应答列表中是否存在：

(1) 如果存在，则将相应的应答发送给攻击者A；

(2) 如果不存在，则随机生成wi∈∈Z*q，并计算H1(IDi)，然后将{wi，H1(IDi)}发送给攻击者A，再把该请求-应答存储到列表中。

攻击者A在询问的过程中始终无法获取系统私钥s，无法使得等式e(U’SK，P)=e(UPK，PK)成立。若攻击者预通过系统公开参数{P，PK}和PK=sP推导系统私钥s，则将面临求解椭圆曲线离散对数难题。同理，位置服务请求阶段，系统选择的临时会话密钥r对攻击者A保密，因此攻击者A无法伪造正确的Y′u使等式e(vu，Y0)=e(Y′u，PK)成立。如果攻击者A预通过Y0=rPK推导r，则将面临求解椭圆曲线离散对数难题。

5 仿真实验

图2 匿名度K与通信开销的关系

基于位置隐私保护系统架构模型，从系统性能和隐私度两方面对方案进行仿真实验。仿真实验在64位的Windows10操作系统、2.80 GHz 英特尔i7 CPU、8 GB内存的PC机和Matlab仿真软件的环境下进行。实验选取5 km×5 km的真实地理地图，以给定的用户真实位置为中心，生成矩形区域[a，b]×[e，f]，大小为100 m×100 m。实验中的主要影响参数为匿名度K，表示单次位置服务过程中移动终端向LBS服务器发送的服务请求数量。

5.1 系统性能

5.1.1 通信开销

系统的通信开销影响移动终端的流量成本。一次完整的位置服务请求过程，通信开销主要发生在用户注册阶段和位置服务请求阶段，主要通信数据包括：用户注册请求消息、用户注册结果、位置服务请求消息和加密结果集合。通信开销的大小由数据包的大小和与匿名度K决定。仿真实验参数K的选取范围为[5，20]，如图2所示，该方案和对比方案的通信开销与匿名度K均呈线性关系。由于文献[16]是基于第三方匿名中心的方案，其通信需经过匿名中心，其通信开销随着匿名度K的增加，相对于其他两个比较方案明显增长的快。尽管文献[18]也是基于终端的方案，由于需要频繁调用GPS服务来完成地图分割算法，在相同的匿名度K的情况下，其通信开销略高于本方案。即该方案能够减少现阶段K匿名技术的通信开销，降低移动终端的流量成本，并具有一定的优势。

5.1.2 效率

图3 匿名度K与执行时间的关系

系统效率指用户从发起查询请求到获得兴趣点相关信息所执行的时间。该方案与对比方案算法执行时间主要由假位置生成和选取阶段贡献；由于匿名度K值决定了生成假位置的数量以及最优假位置的数量，因此执行时间随着匿名度K的变化而变化；仿真实验参数K选取范围设为[10，80]。仿真结果如图3所示。

在匿名度K值较小时，该方案的执行时间与方案[18]的相近，无明显优势，但随着K逐渐增大，由于方案[18]构造维诺多边形，其执行时间增速明显加快，当匿名度K>73时，其执行时间超过方案[16]。该方案与方案[16]执行时间随着K的增大，基本呈线性稳定增长，但方案[16]算法的复杂性和执行效率较低。

图4 匿名度K与位置熵的关系

5.2 隐私度

方案的隐私安全与假位置的选取有关，通过在用户周围生成假位置，隐藏真实用户位置。位置隐私度通常通过位置熵进行度量，衡量假位置生成和选取阶段所选取的候选节点质量标准，熵值越高，隐私保护水平越高。在包括真实位置在内的所有位置点发生概率均相等的情况下，位置熵达到理想最大值。匿名度K越大，对用户真实位置的混淆效果会越好；但是匿名度K过大，会给方案的通信开销和效率造成影响；本仿真中匿名度K值取[10，100]。仿真结果如图4所示，3种方案的隐私度均随着匿名度K的增加而增加，当匿名度K值到达一定数值后，其增长速度越来越趋于平缓，这是因为匿名区域内的假位置过于密集，其混淆能力趋于饱和，再增加假位置数量，对隐私保护效果收效甚微。由于随机方案没有考虑到地图信息和假位置的合理性，因此其隐私效果最不理想，尽管文献[18]的方案在随机选取k-1个假位置时考虑了其合理性，但该方案从2k个合理假位置中选取较优的k-1个假位置，其隐私效果优于文献[18]的方案。

6 结束语

笔者提出了一种面向移动终端的K匿名位置隐私保护方案，采用安全高效的不经意传输协议，避免了传统方案对可信匿名中心的依赖，并且提高了方案的执行效率，降低了通信开销。通过在匿名区域随机选取2k个合理假位置，然后根据位置熵，从中选取较优的k-1个假位置，提高了方案的位置隐私度。通过安全性分析，方案满足匿名性，抗重放攻击和不可伪造性等安全特性；通过对方案通信开销、执行效率和隐私度进行仿真实验，结果显示文中方案优于其它方案。因此，笔者所提出的方案对位置隐私保护相关安全领域的研究具有一定的理论意义和应用价值。