基于LBS的位置隐私保护方案综述

张源策,尤海鑫,段明月,李丽红*

(1.华北理工大学 理学院,河北 唐山 063210;2.河北省数据科学与应用重点实验室,河北 唐山 063210;3.唐山市工程计算重点实验室,河北 唐山 063210)

0 引言

生活中很多使用场景都是基于位置服务(Location Based Service,LBS)[1]的,在发展LBS的同时,如何保护用户的位置隐私不被泄露,是位置隐私保护所要解决的问题。

1 LBS的隐私保护架构

目前,LBS主要有两种隐私保护架构:集中式结构和P2P架构。

1.1 集中式器结构

此方案由用户端、可信第三方(Trusted Third Party,TTP)和LSP平台(Location Services Platform,LSP)[1]组成,该架构有效应用的前提是TTP完全可信。

集中式结构的优点是:(1)隐私保护效果好;(2)请求效率高;(3)具有较好的服务效用。但同时,该结构的缺点如下:(1)TTP可信问题;(2)成本问题;(3)匿名服务器是整个架构的薄弱环节。

1.2 P2P结构

基于P2P结构的隐私保护方案不需要TTP匿名服务器,仅由用户端和LBS服务平台组成,通过客户端之间形成的匿名区域,相互协作,用匿名区域代替真实位置向LSP发起请求。LSP处理请求并返回请求结果,用户端筛选得到符合的位置记录。

P2P结构的优点:(1)无须考虑可信匿名服务器的安全性;(2)无须部署匿名服务器;(3)匿名区域更有效地保护了用户的位置隐私。

P2P结构的缺点:(1)客户端需要有一定的计算能力;(2)没有考虑匿名用户的可信性;(3)用户数量是否符合匿名区域的匿名要求。

2 LBS隐私保护技术

本文从4个部分对位置隐私保护方案[2]进行介绍。

2.1 基于模糊的位置隐私保护方案

基于模糊的位置保护方案,即通过位置偏移、假位置等技术对LBS查询中的真实位置信息进行模糊化处理。

(1)假名技术[3],核心思想是用没有具体含义的符号消除真实用户的位置与相关信息的关联性,从而达到保护隐私的目的。针对单一假名的技术缺陷,多次修改假名只是治标不治本。

(2)随机化技术,主要应用在P2P结构中,作用是在LBS查询中随机添加哑元,并发起哑元查询。

(3)假位置生成方法,由Shin等[4]提出假位置生成SpaceTwis方案,用随机锚点代替真实位置点。为了解决SpaceTwis方案敏感点选取的问题,周长利等[5]提出了利用相关位置语义信息,提高锚点选取的准确性。

2.2 基于密码学的位置隐私保护方案

基于密码学的位置隐私保护方案一般基于P2P结构,引入加密解密原理,其原理是先将用户发送给LSP的LBS查询信息进行加密处理,即使获得密文也无法获取真实位置数据。

2.3 基于k-匿名技术的位置隐私保护方案

基于k-匿名技术的位置隐私保护方案中,真实用户与其他k-1个用户共同组成一个匿名区域,用匿名区域发起LBS查询请求。

2.3.1 基于欧氏距离的方案

传统的隐私方案大多基于欧式距离,杨洋等[6]提出了一种LBS矩形区域的划分算法,有效提升了匿名性能。考虑到合谋攻击的情况,叶吉祥等[2]引入用户密度,提出了一种基于用户自我感知的USA算法,感知邻居用户分布密度,划分子区域、随机添加哑元位置均衡用户密度后发起LBS查询,最后对结果筛选。

为解决匿名数据集的隐私问题,谢奇爱[7]提出了基于时空k-匿名的隐私保护持续改进的DLP算法,在一定时间和空间范围内产生多个哑元位置。宋成等[8]基于k-匿名思想和双线性对性质,提出一种基于概率的保护方案:随机地生成2k个哑元位置,选取k-1个概率较高的假位置,并分配虚假的用户身份标识。

2.3.2 基于路网环境的方案

基于欧氏空间距离来度量的方案未考虑到敏感位置的情况。因此,倪巍伟等[9]通过引入路网环分布的概念,结合隐匿环的组成结构,提出了隐匿环剪枝方法,有效防御重放攻击、提高位置泛化和近邻查询效率。为了解决路网环境中敏感位置匿名区域的生成问题,戴佳筑等[10]考虑现实中的路网环境和真实区域的敏感度,生成与之相适应的匿名区域。为了优化算法的开销,周长利等[11]提出了基于路网环境的k近邻兴趣点查询算法,利用四叉树索引划分路网节点,计算相应的路网节点,查询k近邻POI点,构造匿名区域并随机添加哑元查询。

2.4 基于差分隐私的位置隐私保护方案

相较于k-匿名技术,差分隐私的应用也十分有前景,是一种不受攻击者背景知识限制、具有较好隐私保护效果的技术。为了解决现有k-means算法初始点敏感等问题,徐启元等人[12]结合了人流密度、差分隐私技术和k-means技术。为了解决加噪过度的问题,张可铧[13]等人提出了基于空间动态划分的差分隐私聚类算法DPQTk-means算法,减少随机噪声后进行k均值聚类。

3 分析与展望

基于差分隐私技术的位置隐私保护方案无须考虑背景知识,也不受某条数据变化的影响,适合与其他多种方案进行结合,有着良好的应用前景;基于密码学的技术虽然有着较好的隐私保护效果,但却对通信和计算能力提出了要求;基于匿名的技术保护效果直接与k值的选取有关,基于模糊的技术虽然能降低通信开销,但不适用于精度较高的LBS查询服务。

下一步研究方向可以包含以下方面。首先,哑元位置选取仍是一个需要继续研究的问题,如何更有效地应对攻击者预测用户位置,抵御差分攻击、中心区域选择攻击等攻击手段,是一个值得研究的方向。其次,本地化差分隐私很好地解决了TTP不可信的问题,但加重了客户端的负担,下一步可以研究如何降低算法开销、提高算法效用。最后,社交网络也是一个很有应用价值的领域,应在确保用户体验的同时保证用户的位置隐私,提出适用于社交网络的LBS隐私保护模型。