基于非可信用户协作的位置隐私保护机制*

王 辉， 朱国宇， 申自浩， 田可可

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

0 引 言

近年来，随着无线通信技术以及定位技术[1]的发展，基于位置的服务(location-based service，LBS)与人们关系日益密切。在移动互联网中基于位置服务的应用程序日益增加，人们的生活也更加便捷[2]。基于位置服务的应用程序通过将用户的兴趣点和位置信息发送到LBS服务器，用户就可以获得各种各样的基于位置的服务。如“美团”根据用户提供的位置信息进行个性化的服务。用户搜索“小吃”，“美团”时，就会将兴趣点“小吃”和用户位置等信息发送给美团的LBS服务器，”美团”就会将用户附近的小吃商户展示给用户。

然而，若在生成、存储和使用位置信息的过程中没有科学的保护措施，用户的健康状况、财务信息、社会关系、兴趣爱好和情绪状态等敏感信息可能被泄露，攻击者能够根据这些信息散播恶意广告和窃取用户财物。因此，在满足用户基于位置服务的前提下，保护用户的隐私信息不被泄露成为了亟待解决的问题。

近年来，国内外研究学者提出了多种位置隐私保护方法，其中K匿名模型[3]是最常用的方法之一。其基本思想[4]是：用一个包含目标用户在内的k个用户的匿名区域代替用户的真实位置,从而使攻击者无法区分出目标用户的真实位置。如图1(a)所示。该模型系统结构主要有三种:客户端服务器结构、集中式结构和分布式结构。

在客户端服务器结构[5]中，用户利用历史信息(包括历史位置信息和历史查询信息等)通过算法对真实的查询请求进行匿名处理，进而达到保护用户位置隐私的目的。但是此结构的系统对客户端要求较高，需要一定的存储能力和计算能力，优势为不需要其他实体参与。集中式结构[6]，一般需要引入第三方匿名服务器，负责处理用户的查询请求，代替真实用户发送请求信息，并将服务器返回结果发送给用户。缺点是易产生单点故障和瓶颈问题，优点是降低了对客户端的性能要求。

分布式结构[7,8]，各个移动用户之间相互协作，分享部分位置信息，并形成匿名空间，达到K匿名效果，经过处理达到保护位置隐私的目的。缺点为易产生通信延迟和易受串通攻击，优点为有效避免了单点故障和瓶颈问题。

随着数据挖掘技术[9]的发展，K匿名模型的算法易受到攻击者的语义攻击，且在抵抗串通攻击和推理攻击的能力上较弱。针对这些问题，本文提出了多跳传输(multi-hop transmission,MHT)模型,该模型不仅适用于快照查询，还能应用在连续查询中，并且能够在抵抗攻击者串通攻击、推理攻击和语义攻击下提供精确的位置服务。在相同资源下，该模型的隐私保护强度强于K匿名模型。

1 系统结构与相关定义

1.1 系统结构

MHT机制系统由用户、可信云计算中心、LBS服务器三部分组成，如图1(b)。

用户：通常是智能终端(如手机、平板等)，需具有以下功能：1)定位功能(如GPS,北斗等),能够获得用户的当前位置;2)与位置服务提供商进行通信，可以通过蜂窝网络(如4 G、5 G等)传输信息;3)能够和其他用户短距离的通信(如WiFi，蓝牙等)。当用户发送自身查询请求时为目标用户，参与其他用户的查询请求时为邻居用户。目标用户是能够发送经过处理的查询请求信息，具备一定的计算能力，具有加解密能力。邻居用户是辅助目标用户进行查询，具有转发能力、存储能力和与LBS服务器交互能力。

可信云计算中心(trusted cloud computing center，TC3)：将每个进入网络的用户或者已在网络的用户周期发出的请求，根据各自位置隐私保护需求选择下一跳邻居用户，并将可选的下一跳邻居用户的集合返回给相应用户。

LBS服务器：能够根据请求信息进行检索，并将结果打包反馈给发送该请求的用户。具有加解密处理能力。

图1 K匿名机制与MHT机制示意

图1中空心小圆圈和实心点均为实际存在的用户，实心五角星为目标用户。图1(a)中虚框为形成匿名区域。图1(b)为MHT机制示意图。

1.2 相关定义

定义1信息传输轨迹:目标用户发送请求到LBS服务器的信息传输轨迹。表示为

MQ={u0,u1,u2,…uh,S}

式中h(h∈N+)为用户隐私保护强度,即跳数;u0为目标用户，u1到uh为邻居用户，分别称为一跳邻居用户，二跳邻居用户，……，h跳邻居用户;S为LBS服务器。如图 1(b)中实线和虚线箭头所连接的用户及LBS服务器分别形成一条信息传输轨迹。

定义2函数向量积：定义⊗和⊕两种函数和向量的运算关系。表示为

(1)

式中 [pmin,pmax]为最优价值范围，r为价值评估的范围扩展容忍度，使得rpmin为无法容忍的下限，(1+r)pmax为无法容忍的上限。表示为

(2)

定义3竞拍底价Price:目标用户寻找邻居用户时，欲参与目标用户请求过程的用户能够提供的条件量化值。

1)任意用户i竞拍底价满足下式

Pricei(disti,θi,Cnti)=[f(disti)f(θi)f(Cnti)]⊗M·Wi

=[f(disti)⊗M*1f(θi)⊗M*2f(Cnti)⊗M*3]·Wi

(3)

式中Cnti为用户i当前时刻同时参与信息传输轨迹的个数。M为缺省属性参数矩阵

式中Rmin，Rmax;θminθmax;Cntmin,Cntmax分别为距离、弧度、辅助轨迹个数最优价值范围最小值与最大值；λR,λθ,λCnt分别为不同价值评估的范围扩展容忍度。

2)对于n个用户的竞争底价组成的3×n矩阵U,其竞拍底价满足下式

φ=Price⊕U

=[Price⊕U*1Price⊕U*2…Price⊕U*n]

(4)

式中U*i(i=1,2,…,n)为矩阵U的第i列向量，且U*i=[distiθiCnti]T。

定义4云计算信息MSGU2C用户发送给TC3的数据格式，满足下式

MSGU2C={LOCu,Wu,Mu,ADRu,NUMQ}

式中LOCu为用户u的所在位置；Wu为用户的权重向量；Mu为用户u的缺省属性参数矩阵；ADRu为用户u的通信地址；NUMQ为TC3返回的用户的个数。

定义5请求信息MSGU2S目标用户的请求信息格式，满足下式

MSGU2S={h,Nrdm,EPKS(POI,Loc,r,PKU)}

式中Nrdm为随机值，E为非对称加密函数；POI为目标用户的兴趣点信息；Loc为目标用户的经纬度坐标；r为查询半径；PKS,PKU分别为LBS服务器和目标用户的公钥。

定义6请求返回信息MSGS2ULBS服务器处理请求信息之后的返回信息，满足下式

MSGS2U={Nrdm,EPKU(Result)}

式中Result为LBS服务器处理用户请求信息的结果。

定义7路由表Li记录信息传输轨迹中的用户i的上一跳路由，满足下式

Li={Nrdm,ADR}

当用户i参与多条信息传输轨迹时，Nrdm区分不同的信息传输轨迹。

2 MHT机制

2.1 竞拍机制

不同用户参与目标用户的查询请求时，提供的隐私保护帮助也有差异。当用户参与信息传输轨迹越多，其本身的查询请求的安全性越高，所以用户会竞争参与其他用户的查询请求过程，假设不会拒绝其他用户的辅助请求。因此在用户选择下一跳邻居用户时引入竞拍机制，将用户的各个属性信息进行量化，并加权处理，最后得到的量化值为该用户的竞拍底价，用于和其他用户竞争参与目标用户查询请求。

2.2 寻找下一跳邻居用户集合

2.3 查询实现过程

目标用户根据算法构造信息传输轨迹，并将查询信息正向沿着信息传输轨迹传输查询请求，当LBS服务器收到查询请求后，在数据库检索符合条件记录，并将查询结果沿着信息传输轨迹逆向传输，直到返回给目标用户。

3)循环执行步骤(2)，直到MSGU2S发送到LBS服务器。

4)LBS服务器收到MSGU2S后，先进行解密处理，根据目标用户查询请求搜索本地数据库，并构造结果集，然后用目标用户的公钥PKU进行加密处理，构造查询请求返回信息MSGS2U,发送给信息传输轨迹中的跳邻居用户。

5)信息传输轨迹MQ中的用户收到MSGS2U后，按照本地路由中地址发送给上一跳邻居用户。

6)循环执行步骤(5)，直到目标用户收到信息MSGS2U。最后用私钥进行解密得到查询结果。

3 性能分析

对于时间开销。h跳邻居用户发送给LBS服务器时，会在网络中的多个路由节点进行转发，最终由服务器接收并处理。查询请求在信息传输轨迹传输完成后，再由h跳邻居用户进行数据包转发，相当于目标用户直接向LBS服务器发送请求时多进行h次转发处理。由于邻居用户仅做转发处理，相比于K匿名机制，MHT机制的处理时间多出了h跳转发的时间，实际中该时间是毫秒(ms)级的，所以,MHT机制并不会明显增加时间开销。

4 安全分析

4.1 抵抗串通攻击

假设攻击者集合为Adv={v1,v2,…,vm}，并分4种情况进行说明。

1)∃ui(i∈[1,h])使得ui∈Adv，即存在恶意的邻居用户。ui根据收到的MSGU2S，无法分析加密部分。ui仅知道上一跳邻居用户和下一跳邻居用户的信息，除目标用户外的任何用户不可能获得完整的MQ。

3)LBS∈Adv，即LBS服务器不可信。LBS服务器不能完整的获得信息传输轨迹MQ，且MSGU2S中不包含任何目标用户的相关信息。

4)∃ui(i∈[1,h])且TC3,LBS∈Adv。由于跳数h只有目标用户知道，即使是第一跳邻居用户，也仅知道其上一跳用户的得到该请求信息时的跳数，并不能确定上一跳邻居用户就是目标用户。攻击者不能确定信息传输轨迹中的全部用户。

4.2 抵抗推理攻击

假设Ns表示整个网络集合，PE(Event)代表Event成功时的概率。对于信息传输轨迹上的用户ui和uj且∀(0≤i≠j≤h)，若判断目标用户是ui或uj的概率相等，就说明能够抵抗推理攻击。即当下式成立时完成证明

PE(ui∈MQ|MQ∈Ns)=PE(uj∈MQ|MQ∈Ns)

(5)

因为PE(ui∈MQ|MQ∈Ns)=PE(ui∈MQ∩MQ∈Ns)/PE(MQ∈Ns)=PE(ui∈Ns)/PE(MQ∈Ns)，同理有PE(uj∈MQ|MQ∈Ns)=PE(uj∈Ns)/PE(MQ∈Ns)，不论PE(MQ∈Ns)的值为多少，式(5)化简结果为PE(ui∈Ns)=PE(uj∈Ns)，显然成立，故式(5)得证。

4.3 被识别概率

根据4.2节分析，理论上用户被识别的概率趋近于零。对于信息传输轨迹MQ中的用户ui(i∈[0,h])，其参与的信息传输轨迹个数为ci，从中识别出MQ的概率为1/ci，即为p(ui)=1/ci。根据乘法原理，当攻击者不知道跳数h(假设h为何值的概率均为1/h)时的被识别概率为

(6)

当攻击者获得h的值时，其被识别概率为

(7)

图2为用户u0使用不同的位置隐私保护模型的理想状态下被识别概率对比。辅助用户为n代表K匿名机制的k为n+1,MHT机制的跳数为n,c=2和c=3分别代表MHT机制的邻居用户均同时参与2条和3条信息传输轨迹。

图2 K匿名机制和MHT机制被识别概率对比

5 结束语

本文分析了LBS常见的系统结构模型的优缺点，在非可信实体参与真实用户位置服务的情况下，对用户的查询请求进行加密处理，经过h个邻居用户的辅助，发送到LBS服务器，LBS服务器处理后，将查询结果进行加密，并沿信息传输轨迹逆向反馈给目标用户。并通过性能分析和安全分析，突出了MHT机制的优势。