英语原文共 15 页，剩余内容已隐藏，支付完成后下载完整资料
基于位置变换的位置服务隐私保护
TaoPeng、QinLiu和GuojunWang
中南大学信息科学与工程学院，湖南长沙，中国，410083
摘要。随着移动通信设备的日益普及，带有定位能力(例如GPS)的移动通信设备越来越多地被用于位置服务中(LBSs)。LBSs中的一个重要问题是在与位置服务提供商(LocationServiceProvider，LSP)交互时会暴露用户的真实位置。为了解决这个问题，现有的解决方案通常在用户和LSP之间引入一个可信的匿名器。但是，一个匿名器的引入实际上将安全风险从LSP转移到了匿名器。一旦匿名器被破坏，它可能会使用户信息处于危险之中。本文针对LBS环境，提出了一种增强的位置隐私保护(ELPP)方案。我们的方案使用一个名为函数生成器的实体来分配空间变换参数，用户和LSP可以借助这个实体在实际位置和伪位置之间进行相互转换。该方案的主要优点是：(1)不需要完全可信的实体2)每个用户都能获得准确的兴趣点，同时保持位置隐私。
关键词：基于位置的服务，位置隐私，K-匿名
1 介绍
随着装有定位能力(例如GPS)的移动通信设备的激增，基于位置的服务(LBSs)近年来越来越受欢迎[1][ 2]。由于功能多样，功能齐全，LBSs正在为用户的日常生活提供便利，例如，找到最近的最受欢迎的餐厅，从附近的市场获得优惠券， 在旅游中获取旅游信息和路线指导等。然而，用户在享受LBS之前必须向位置服务提供商(LSP)提供他们的真实位置，这对他们的隐私构成了严重的威胁。让我们考虑以下情况： 用户Bob使用他的全球定位系统启用移动电话向LSP(例如GoogleMaps)发出k近邻(K NN)查询，以查找最近的2家医院。由于LSP可能不值得信任，一个已经破坏了LSP的攻击者可以获得Bob的真实身份、定位、查询，并且可以推断出有关Bob的其他敏感信息，比如他的家乡位置、健康状况，甚至还有其他一些敏感信息如生活习惯、政治/宗教信仰等。尽管LBSs带来了好处，但通过用户位置重传用户个人信息的隐私威胁已经成为阻碍用户使用该服务的关键问题。确保位置隐私，即保护用户的位置信息，对于LBSs的成功至关重要。在过去的几年里，人们提出了许多关于保护位置隐私的有希望的方法。一般来说，它们可以分为两大类[3]：可信第三方(不使用TTP)方案和基于TTP的方案。在不使用TTP的方案中，用户直接与LSP通信。为了保护真实的位置信息不受不可信的LSP的影响，用户向位置添加噪声(例如，扩大用户的位置或在不同的地点生成多个诱饵)，并将“假”诱饵发送到LSP[4]。然而，查询中的噪声越多，LSP会返回的冗余结果越多，并且会给用户带来更高的通信成本。
在基于TTP的方案中，在系统[5][6]中引入了一个称为匿名器的可信实体，作为用户和LSP之间的中间层。为了保证位置隐私，现有的大多数解决方案都采用定位K-匿名原则[7][8]：如果发送到LSP的位置信息与至少K-1其他用户无法区分，则移动用户满足位置K-匿名。因此，K-匿名的基本思想是用至少K个用户所在的匿名区域替换用户的真实位置。
在图1中，用户将他们的kNN查询发送给匿名器，该查询负责删除用户ID并构造隐藏区域，该区域名为“匿名空间区域”(ASR或K-ASR)，且包含至少K个用户。发送ASR后，LSP可以处理查询并返回一组候选兴趣点(POI)，但不能以大于1/K概率识别的任何用户。然后，匿名器过滤候选集，并将准确的结果转发给每个用户。与TTP无关的解决方案相比，基于TTP的解决方案可以防止LBS提供商以高于1/K的概率知道用户的真实位置，同时为用户消耗较低的通信成本。然而，基于TTP的方案需要一个了解所有用户的位置可信的匿名器。因此，整个系统的安全性依赖于匿名器。一旦匿名器遭到攻击者的攻击，它将对用户隐私构成严重威胁，并可能危及用户信息。
图1.Kminus;匿名定位私有框架。k NN表示k-最近邻查询
本文针对LBS环境，提出了一种增强的位置隐私保护(ELPP)方案。我们引入了一个叫做函数生成器的实体，为用户和LSP周期性地分配转换参数，以执行实际位置和伪位置之间的相互转换。没有转换参数，匿名器就无法了解用户的真实位置。然而，有了一组伪定位条件，匿名器仍然能够构造一个正确的K-ASR来实现LSP上的K-匿名，并为每个用户过滤虚假的POI。因此，我们的方案可以为整个系统提供增强的安全性。
我们的贡献有三种：
- 我们提出了一种新的保护位置隐私的框架，其中引入了一个函数生成器以消除任何可信关联的需要。据我们所知，ELPP方案是第一个为LBS环境提供增强的位置隐私的方案。
- 我们利用Hilbert曲线[9]将一个实际位置转化为一个伪位置，这样，匿名器在不影响真实位置下可以为每个用户正确地构造ASR和过滤兴趣点。
- 我们深入分析了ELPP方案的安全性和性能。我们的方案保护位置隐私不受匿名器、LSP、函数生成器和其他用户的影响。
本文的其余部分安排如下：第二节介绍了相关工作，第三节介绍了技术准备，第四节对方案进行了描述，从理论上进行了分析并把它的安全问题放在第5节。最后，我们在第六节中总结了本文的结论。
2相关工作
在与LSP交互时，用户隐私可分为查询隐私和位置隐私[7]。前者与查询中敏感信息或用户相关的兴趣的披露有关。另一方面，后者与披露和滥用用户位置信息有关。我们的工作是在享受LBS的同时保护位置隐私。最近关于位置隐私的工作可分为两大类：可信第三方(不使用TTP)方法[4][10]和基于TTP的方法[3][5]。
在[11]中，不使用TTP的方法分为两个子类别：基于混淆的方法和基于协作的方法。在基于混淆的方案中，用户在不同的位置产生多个诱饵，并将假位置发送到LSP。例如，[4]提出了一个从LSP中逐步检索POI名为SpaceTwist的方案。此过程从与用户实际位置不同的位置(称为锚位置)开始，直到能够报告准确的查询结果为止。该方案的主要缺点是用户与LSP之间的多轮交互可能导致较高的通信成本。
在基于协作的方法中，每个用户都通过联系他的同伴并收集他们的位置数据来隐藏自己的位置。[12]首次提出了LBS中的第一个协作的无TTP方案.用户通过添加零均值高斯噪声来扰乱他的位置，然后向他的邻居广播他的受扰位置，并要求他们提供扰动位置以形成匿名。由于用户只交换受干扰的位置，他们不需要为了隐私而相互信任。这项提议的主要问题是，在查询中加入噪音会降低LSP返回的结果的准确性。因此，无TTP方法的主要缺点是服务质量（QoS）会降低，这是由于低精度的结果引起的通信成本高。
在基于TTP的解决方案中，将匿名器引入到系统中，作为用户和LSP之间的中间层。匿名器可以这样做：(i)在发送给LPS之前，从查询中删除用户的个人信息；(ii)隐藏或修改用户的确切位置；(iii)删除或者过滤LSP中的错误结果。现有的基于TTP的方法通常需要匿名器来构造一个K-匿名ASR。K-匿名的概念首先由Sweeney等人提出[13]用来防止信息丢失和在数据库中披露个人数据。在LBS的隐私中，K-匿名可以被看作是一个用户的位置与K-1其他用户的位置是无法区分的。所以，K-匿名的基本思想是用至少K个用户所在的区域来替换用户的真实位置。在他们工作的启发下，[8][14][15][16]提出了构造K-匿名ASR的一种有效方案。例如，Hilbert匿名[15][16]使用希尔伯特空间填充将二维空间映射为一维值，并将一维排序列表划分为K用户组。在集团匿名中[14]，匿名者执行时空伪装算法来搜索用户的集团，并构造K个用户的最小边界矩形(MBR)。
为了提高基于TTP的解决方案的性能和服务质量，[14]中的工作使用户能够定义其个人隐私要求，例如最小匿名级别和最大时间和空间分辨率。在[5]中，VU等建议在构造K-匿名区域前使用局部敏感散列（LSH）将用户位置划分成组，每个组至少包含k个用户。此外，他们提出了一种基于Voronoi图的高效算法，对任意多边形形状的ASR中的任意点进行K近邻查询。文[17]提出了二维和高维空间中k-神经网络查询的高效内存处理和二次记忆剪枝技术。他们设计了一种辅助解决方案 索引EXO树，以加快任何类型的k近邻查询。
基于TTP的方案的主要优点是使用匿名器保护位置隐私不受不信任的LSP的影响，同时使LSB能够提供更好的服务质量。然而，这种方案将用户的信任从LPS转移到中间实体。一旦匿名器被泄露，这将对用户隐私构成严重威胁，可能会危及用户信息。我们的ELPP方案，通过在系统中使用一个函数生成器，结合了这两种方案的优点，没有完全可信的实体的同时提供了更好的服务质量。
3准备工作
3.1问题表述
我们假设这样的情况：用户u将消息{Location，ID，query}发送给LSP，用于k近邻查询。地图资源和数据库存储在潜在的不可信LSP中。根据这一请求，LSP在其数据库中寻找所需的信息，并将适当的兴趣点返回给u。我们工作的动机是为用户保留位置隐私，同时使LSP能够提供高质量的服务。
在本文中，我们提出了一种新的增强位置隐私保护(ELPP)方案，在基于TTP的模型中引入一个称为函数生成器的实体(图2)。函数生成器的目的是为用户提供空间转换参数(STPs)，并为LSP将二维空间坐标(实际位置)映射为一维空间希尔伯特值(伪位置)。这样，没有STP的匿名器就不知道真正的位置。该方案的工作原理如下：从函数生成器获得STP后，用户将其真实位置编码为伪位置，表示为Lursquo;。通过从用户中聚合足够多的伪位置，匿名器构造了一个转换后的ASR，表示为Rrsquo;，并将其发送给LSP。在LSP方面，转换后的ASR可以由函数生成器的STP解码。在回应匿名器之前，LSP在解码后的ASR中为用户查找候选POI，并将POI的实际位置转换为伪位置，表示为POIlsquo;。对于K个用户的POI，匿名器准确地过滤和转发查询用户的准确结果，表示为POIulsquo;。我们方案的主要优点是ELPP增强了整个系统的安全性，不需要完全可信的实体，每个用户都能获得准确的结果。
图2.增强的位置隐私保护方案
3.2攻击模型
对抗能力。在LBS隐私保护研究常用的威胁模型中，LSP被看作是恶意的观察者，所有其他实体都可以被认为是良性的。攻击者可以是LBS实体的所有者，或者是能够妥协和控制LBS实体的人。在我们的威胁模型中，当查询和信息通过通信网络传输时，假定通信信道是安全的。现有的安全方案(如SSL)和传统的解决方案(如加密和散列)可以通过网络来保护信息的保密性和完整性。因此，有三种类型的攻击者：(i)知道ASR的LSP可能受到攻击者的危害，或可能泄露信息来获取利润。(ii)在用户和LSP之间作为中间层收集所有消息的匿名器，可能成为更大的目标，并可能揭示匿名算法；（iii）少数恶意用户可能想知道其他用户的隐私。所有这些攻击者都被认为，相比于其他信息，他们更感兴趣的是用户的真实位置。
对抗性限制。另一方面，我们也假设匿名器不会与任何其他实体勾结。匿名者与其他实体或恶意用户之间的勾结可能会泄露隐私。这也是其他研究人员在以前的研究中所做的，例如代理再加密。系统[18][19]，其中假定执行代理再加密操作的LSP不与其他实体串通以确保整个系统的安全性。
我们的安全目标是保护用户的位置隐私。如果下列情况属实，我们认为我们的计划失败：
-LSP知道任何用户的真实位置的概率大于1/K的。
-匿名器知道任何用户的真实位置。
-函数生成器知道任何用户的真实位置。
-用户知道其他用户的真实位置。
3.3希尔伯特曲线
用户和LSP利用希尔伯特曲线将实际位置转换为伪位置。希尔伯特曲线是Hilbert[9]首次描述的连续分形空间填充曲线。根据某些算法，希尔伯特曲线在多维空间中一次又一次只按特定的顺序穿过每一点。给定点阵中S点的二维坐标，表示为，则根据Hilbert曲线阶确定相应的一维坐标，表示为H(S)。相反，给定Hilbert曲线上一个点的一维坐标，确定相应的网格坐标，这个过程被定义为编码和解码[21]。
定义1.由Hilbert曲线排列的单元集合定义为：
其中Cij 是网格的lt;x，ygt;坐标，N是一维网格单元格的数目。
定义2.点S的Hilbert值可以定义为：
是空间变换函数，它将二维网格坐标编码为一维Hilbert值。给定函数的参数，对每个网格单元的H值映射进行赋值。参数指的是曲线的起点，曲线阶数N，曲线方向的斜率，曲线的比例因子。我们把这个参数空间变换称为STP，其中。Hilbert曲线的一个重要性质使得它成为我们所提方案的一个非常合适的工具，即当STP不被知道时，函数变成一个单向函数[16]。恶意攻击者不知道密钥，需要通过比较所有单元格的Hilbert值，彻底检查曲线参数的所有组合以找到正确的曲线。穆恩等人提出的显式形式LAS算法[22]可用于生成排序的H值，也可由反向解码希尔伯特值。在不失去通用性的情况下，我们假设用户的位置是一个点，并且是由两个值(如纬度和经度)所确定的。我们定义坐标指移动节点在二维空间中的空间位置(即x轴和y轴)。给定STP，S点的二维坐标可由点阵坐标表示。
这里的U是每个单元的单位长度，该单元长度可以从因子theta;的比例和一个维度2N的网格单元的数目得到，是单元格左下角的真实坐标。请注意，在给定的曲线中，两个或两个以上的点有可能具有相同的格坐标和相同的H值。在高概率[22]中，如果两个点在二维空间中接近，它们在一维变换中也将是接近的。
3.4 Voronoi图
LSP使用Voronoi图(V
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[22613]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
