基于SpaceTwist的混合式LBS隐私保护方案

职鸣奕 杨明

摘要：基于位置的信息服务（Location Based Services，LBS）在给个人生活带来极大便利的同时，也带来了个人隐私泄露的危险。本文对现有位置隐私保护方案进行梳理，提出一种混合式LBS隐私保护方案。该方法采用混合式系统结构，基于SpaceTwist方案的位置隐私保护算法，以六边形匿名区域中心作为锚点进行K-匿名增量近邻查询，根据用户需求在位置隐私保护度和查询结果准确性之间做到有效调节，从而对查询用户进行个性化的隐私保护。

关键词：LBS;隐私保护;混合式系统结构;SpaceTwist方案;增量查询

中图分类号：TP3       文献标识码：A

文章编号：1009-3044（2021）26-0025-03

开放科学（资源服务）标识码（OSID）：

基于位置的信息服务（Location Based Services，以下简称LBS）是LBS服务提供商根据用户的空间位置，通过移动通信运营商向用户提供的与位置相关的信息资源和增值服务。LBS最初应用于军事领域，现已广泛应用于紧急救援、商业、医疗、工业、物流等民生领域[1]。其典型应用包括：紧急救援服务（美国的“911”，中国的“119”），导航服务（高德地图、百度地图），商场、酒店、餐厅等周边信息查询服务（美团，口碑，大众点评），定位服务（菜鸟物流，京东物流），广告促销，个人安全服务，位置计费等。LBS的广泛应用给人们的生活带来了极大的便利，但是，由此产生的位置大数据也带来了个人隐私泄露的危害，主要包括：位置隐私（家庭住址、工作单位、访问地址等）和查询隐私（兴趣爱好，健康状况，运动模式等）。位置隐私和查询隐私二者密切相关，位置隐私的泄露，可能导致用户被定位跟踪，进而获取用户的查询隐私;另一方面，攻击者根据历史数据来匹配查询隐私，将查询隐私和位置隐私联系起来，从而获得个人隐私信息。因此，LBS隐私保护是位置服务中非常重要的问题。

LBS隐私保护技术仍面临一些挑战：①用户的位置信息是关联的。攻击者知道用户的当前位置和运动模式，可推断出预计到达的位置;②位置服务的及时性，面对海量的数据，连续的服务请求能进行高效率的处理;③隐私保护度、查询结果的准确性和开销三者之间是矛盾的。目前，国内外学者进行了大量的研究，提出各种隐私保护方案，本文将其分为3类：政策法、扭曲法、加密法三种。与政策法、加密法相比，扭曲法能更好地保留用户信息，无须可信第三方以及额外的硬件，因此在LBS隐私保护中得到广泛应用。

1 研究现状综述与分析

1.1  LBS隐私保护技术[1-2]

本文将LBS隐私保护技术分为3类：基于政策法的LBS隐私保护技术、基于扭曲法的LBS隐私保护技术以及基于加密法的LBS隐私保护技术。

1.1.1 基于政策法的LBS隐私保护技术

基于政策法的LBS隐私保护技术，顾名思义就是政府或组织发布隐私管理规定或协议，通过限制LBS服务提供商对用户信息的不正当使用，从而达到保护用户隐私的目的。政策法实现简单，技术难度低，但隐私保护效果无法衡量，无法保证LBS服务提供商的完全可信，即使其声称不会对用户数据进行不正当使用，但仍然无法保证用户的隐私安全。

1.1.2 基于扭曲法的LBS隐私保护技术

基于扭曲法的LBS隐私保护技术，这一技术通过让用户提交对时间、空间、服务属性适当增加、修改等操作后的查询内容，来避免攻击者获取用户的真实信息。采用的技术主要有：随机化（增加随机噪点）、空间模糊化（将查询位置模糊为一片区域）、时间模糊化（增加时间域的不确定性）。扭曲法能在隐私保护度和服务质量之间做到较好的平衡，但是容易受到完全背景攻击。需要在满足用户最低服务质量的前提下，提高隐私保护度，以降低用户隐私泄漏的危险。

1.1.3 基于加密法的LBS隐私保护技术

基于加密法的LBS隐私保护技术，是指利用加密算法对查询内容进行加密并发送发给LBS服务提供商，LBS服务提供商在不解密查询内容的情况下，直接进行位置服务查询处理。加密法能满足较高的隐私需求和完全的服务质量，但是查询过程中需要额外的硬件和计算，查询过程中花费的代价很大，导致效率低下，而高效率的查询又会导致暴露查询数据之间的关系。

1.2 LBS隐私保护技术分析比较

表1從隐私保护度、服务质量和开销三个方面分析比较了现有的隐私保护技术。表2从优缺点和代表技术做了进一步分析。

由此可以看出，当用户对隐私保护度不高且对服务质量要求较高时，政策法更适合。当用户对隐私保护度很高，可以考虑加密法，这时的代价较高。其余情况可以考虑扭曲法，需要在隐私保护度、服务质量和开销之间取得平衡。需要注意的是，不同的LBS隐私保护技术基于不同的隐私保护需求，单一的方案并不能完美解决所有问题。

2 混合式LBS隐私保护方案

2.1 系统结构

本方案采用混合式系统结构[3]，由集中式结构和分布式结构结合而成，具体组成如图1所示：

用户在发起LBS查询前，通过隐私保护通信协议构建所在区域的匿名组。若组内有效用户连接数量满足该用户匿名需求，则将该匿名区域中心位置发送给LBS服务提供商进行LBS查询，并将查询结果返回给用户，由客户端本身对结果进行筛选;若组内有效用户连接数量不满足该用户匿名需求，则用户将实际位置发送给匿名服务器，由匿名服务器实现匿名、查询以及求精处理。具体的时序交互方式如图2所示：

2.2 隐私保护算法

基于SpaceTwist方案的LBS隐私保护算法（如图3所示），用随机生成的锚点q代替用户的真实位置q进行LBS查询。查询过程中，以q为中心的供应空间不断增大，以q为中心的需求空间不断缩小，直到需求空间完全被供应区间覆盖停止检索，并将查询结果返回给用户[4-5]。该方案不需要额外引入第三方可信匿名服务器，但是采用随机生成锚点的方法，导致锚点位置在现实生活中可能不合理，提高锚点生成速率和合理性，能够很好地提高LBS隐私保护度和服务质量。