位置隐私保护是为了防止用户的历史位置以及现在的位置被不法分子或不可信的机构在未经用户允许的情况下获取，也是为了阻止不法分子或不可信的机构根据用户位置信息，结合相应的背景知识推测出用户的其他个人隐私情况，如用户的家庭住址、工作场所、工作内容、个人的身体状况和生活习惯等。下面介绍几种常用的位置隐私保护技术。

01 基于干扰的位置隐私保护技术

基于干扰的隐私保护技术主要使用虚假信息和冗余信息来干扰攻击者对查询用户信息的窃取。根据查询用户信息（身份信息和位置信息）的不同，基于干扰的隐私保护技术大致可以分为假名技术和假位置技术两种。

（1）假名技术

假名是基于干扰的位置隐私保护技术中干扰身份信息的技术之一。用户使用假名来隐藏真实的身份信息，如用户小张所处的位置是（X,Y），要查询他附近的KTV，用户小张的查询请求包括：小张，位置（X,Y），“离我最近的KTV”。当攻击者截获了这个请求后，可以很轻易地识别出用户的所有信息。而采用假名技术，用户小张使用假名小李，他的查询请求就变成了：小李，位置（X,Y），“离我最近的KTV”。这样攻击者就认为处于位置（X,Y）的人是小李，用户成功地隐藏了自己的真实身份。

假名技术通过分配给用户一个不可追踪的标志符来隐藏用户的真实身份，用户使用该标志符代替自己的身份信息进行查询。在假名技术中，用户需要有一系列的假名，而且为了获得更高的安全性，用户不能长时间使用同一个假名。假名技术通常使用独立结构和集中式结构，当在独立结构中使用时，用户何时何地更换假名只能通过自己的计算和推测来确定，这样就可能在同一时刻有两个名字相同的用户定位在不同地点，令服务器和攻击者很轻易地知道用户使用了假名。而在集中式结构中使用时，用户把更换假名的权利交给匿名服务器，匿名服务器通过周围环境和其他用户的信息，能够更好地完成假名的使用。

为了使攻击者无法通过追踪用户的历史位置信息和生活习惯将假名与真实用户相关联，假名也需要以一定的频率定期交换。通常使用假名技术时需要在空间中定义若干混合区（Mix Zone），用户可在混合区内进行假名交换，但是不能发送位置信息。

如图1所示，进入混合区前的假名组合为（user1 user2 user3），在混合区内进行假名交换，将会产生6种可能的假名组合。由于用户在进入混合区前后的假名不同，并且用户的名字为假名的可能性会随着进入混合区的用户数目成指数增长，因此，在混合区模式下，攻击者很难通过追踪的方式将用户与假名关联，进而即可起到位置隐私保护的效果。

图1  混合区内的假名交换

混合区的大小设置与空间部署是假名技术的关键所在，因为在混合区内要求不能提交位置信息，所以混合区过大会将导致服务质量下降，混合区过小会将导致同一时刻区内的用户较少，进行假名交换的效率较低。当混合区内只有一个用户时，将不会发生假名更换，从而增大了被攻击的可能性。

（2）假位置技术

假位置技术是在用户提交查询信息中，使用虚假位置或者加入冗余位置信息对用户的位置信息进行干扰。假位置技术按照对位置信息的处理结果可分为孤立点假位置和地址集两种。

孤立点假位置是指用户向SP提交当前位置时，不发送自己的真实位置，而是用一个真实位置附近的虚假位置代替。例如，用户小张所在的位置是（X,Y），要查询他附近离他最近的KTV，用户小张发送的查询请求并不是：小张，位置（X,Y），“离我最近的KTV”，而是会采用虚假位置（M,N）代替真实位置，此时他的查询请求就变成了：小张，位置（M,N），“离我最近的KTV”。这样，攻击者就会认为处于位置（M,N）处的人是小张，用户小张也就成功地隐藏了自己的真实位置。

地址集则是在发送真实位置的同时，加入了冗余的虚假位置信息形成的。将用户真实的位置隐藏在地址集中，通过干扰攻击者对用户真实位置的判断，达到保护用户位置信息的目的。例如，用户小张所在的位置是（X,Y），要查询附近离他最近的KTV，这次用户小张发送的查询请求中，由一个包含真实位置（X,Y）的集合代替用户所在的位置。因此，他的查询请求就变成了：小张，地址集{（X,Y），（X,Y），（X1,Y1），（X2,Y2），（X3,Y3）,…}，“离我最近的KTV”。这样就可以使攻击者很难从地址集中寻找到用户的真实位置。但地址集的选择非常重要，地址数量过少可能会达不到要求的匿名度，而地址数量过多则会增加网络传输的负载。采用随机方式生成假位置的算法，能够保证多次查询中生成的假位置带有轨迹性。

（3）哑元位置技术

哑元位置技术也是一种假位置技术，通过添加假位置的方式同样可以实现k-匿名。哑元位置技术要求在查询过程中，除真实位置外还须加入额外的若干个假位置信息。服务器不仅响应真实位置的请求，还响应假位置的请求，以使攻击者无法从中区分出哪个是用户的真实位置。

假设用户的初始查询信息为（user_id locreal），locreal为用户的当前位置，那么使用假位置技术后用户的查询信息将变为q*=（user_id,locreal,dummy_loc1,dummy_loc2），其中dummy_loc1和dummy_loc2为生成的假位置。

哑元位置技术的关键在于如何生成无法被区分的假位置信息，若假位置出现在湖泊或人烟稀少的大山中，则攻击者可以对其进行排除。假位置可以直接由客户端产生（但客户端通常缺少全局的环境上下文等信息），也可以由可信第三方服务器产生。

02 基于泛化的位置隐私保护技术

泛化技术是指将用户所在的位置模糊成一个包含用户位置的区域，最常用的基于泛化的位置隐私保护技术就是k-匿名技术。k-匿名是指在泛化形成的区域中，包含查询用户及其他k-1个用户。SP不能把查询用户的位置与区域中其他用户的位置区分开来。因此，匿名区域的形成是决定k-匿名技术好坏的重要因素，常用集中式结构和P2P结构来实现。

k-匿名技术要求发布的数据中包含k个不可区分的标志符，使特定个体被发现的概率为1/k。在位置隐私保护中，k-匿名通常要求生成一组包含k个用户的查询集，随后用户即可使用查询集所构成的一个共同的匿名区域。图2展示了用户User1、User2和User3所构成的匿名区域（（Xl，Yl），（Xr，Yr））。

图2  混合区内的假名交换

k-匿名技术中通常要求的若干参数介绍如下。

① 匿名度k：定义匿名集中的用户数量。匿名度k的大小决定了位置隐私保护的程度，更大的k值意味着匿名集包含更多的用户，这会使攻击者更难进行区分。

② 最小匿名区域Amin：定义要求k个用户位置组成空间的最小值。当用户分布较密集时将导致组成的匿名区域过小，即使攻击者无法准确地从匿名集中区分用户，匿名区域也可能将用户的位置暴露给攻击者。

③ 最大延迟时间Tmax：定义用户可接受的最长匿名等待时间。

k-匿名技术在某些场景下仍可能导致用户的隐私信息暴露。例如，当匿名集中用户的位置经纬度信息都可以映射到某一具体的物理场所（如医院）时。对此，增强的l-多样性、t-closeness等技术被提出，要求匿名集中用户的位置要相隔得足够远以致不会处于同一物理场所内。

k-匿名技术可以通过匿名服务器来完成匿名集的收集与查询的发送，也可以通过分布式点对点的技术由若干客户端组成对等网络来完成。

（1）集中式k-匿名

典型的集中式k-匿名是间隔匿名。间隔匿名算法的基本思想为：匿名服务器构建一个四叉树的数据结构，将平面空间递归地用十字分成4个面积相等的正方形区间，直到所得到的最小正方形区间的面积为系统要求的允许用户所采用的最小匿名区面积为止，每个正方形区间对应四叉树中的一个节点。系统中的用户每隔一定的时间就将自己的位置坐标上报给匿名服务器，匿名服务器更新并统计每个节点对应区间内的用户数量。当用户U进行匿名查询时，匿名器会通过检索四叉树为用户U生成一个匿名区ASR，间隔匿名算法从包含用户U的四叉树的叶子节点开始向四叉树根的方向搜索，直至找到包含不少于K个用户（包括用户U）的节点，进而即可将该节点所对应的区域作为用户U的一个匿名区。如图3所示，如果用户U1发起K=2的匿名查询，则间隔匿名算法将首先搜索到象限区间[（0,0），（4,4）]，其中包含不少于两个用户，然后，向根的方向上升一级搜索到象限区间[（0,0），（2,2）]，该象限区间包含3个用户，大于要求的两个，算法停止搜索，并将该区间作为用户U1的匿名区。由于该算法所得到的匿名区所包含的用户数量可能远大于K，因此其会加大LBS服务器的查询处理负担和网络流量负荷。

图3  k-匿名实例

Casper匿名算法与间隔匿名算法类似，但不同于间隔匿名算法的是：Casper采用Hash表来识别和访问四叉树的叶子节点，同时当搜索节点用户数小于K时，首先会对其相邻的两个兄弟节点进行搜索，如果该节点与其相邻的两个兄弟节点合并后的总用户数大于K，则将它们合并，并作为匿名区，否则，再对其父节点进行搜索。Casper生成的匿名区面积相比于间隔匿名算法生成的要小，这会减少网络的负载。

Hilbert匿名算法的基本思想是通过Hilbert空间填充曲线将用户的二维坐标位置转换成一维Hilbert值进行匿名，按照曲线通过的顺序对用户进行编号，此编号即为用户的Hilbert值，并把相邻的k个用户放入同一个桶中。匿名集就是包含请求服务的用户所在桶内的所有用户。计算出匿名集的最小绑定矩形并将其作为匿名区。若两个用户在二维空间中相邻，那么映射到一维空间的Hilbert值也有较大的概率会相邻。Hilbert匿名算法可以满足绝对匿名。如图4所示，用户U1的匿名度为3，他和他的相邻用户U3和U4共同组成了匿名区域。

图4  Hilbert匿名实例

（2）P2P结构下的k-匿名

基于P2P结构的k-匿名查询算法的基本思想是：假设所有的节点都是可信的。每个用户都有两个独立的无线网络，一个网络用于与LBS通信，另一个网络用于P2P通信，并且系统中的用户都是安全可信的。一个完整的查询过程包括以下3步。

① 对等点查询。移动用户需要通过单跳或多跳网络查找不少于k-1个对等点邻居。

② 生成匿名区。移动用户与他所查找到的k-1个邻居形成一个组，将他准确地隐藏到一个覆盖整个组内所有用户的区域（即匿名区）中。如果生成的ASR面积小于用户所要求的最小匿名区面积Amin，那么就需要扩大这个匿名区ASR到最小匿名面积Amin。

③ 选择代理并查询。为了防止攻击者通过移动蜂窝定位技术进行攻击，移动用户需要在所形成的组内随机找一个对等点邻居并将其作为代理。通过专门用于P2P通信的网络，将生成的匿名区和查询的参数内容告诉代理，由代理通过另一个网络与LBS服务器联系，发送查询参数和匿名区，并接收候选集，然后代理通过专门用于P2P的网络将候选集传回查询用户。最后查询用户对返回的候选集进行过滤，得到查询结果。

03 基于模糊法的位置隐私保护技术

位置混淆技术的核心思想在于通过降低位置精度来提高隐私保护程度。一种模糊法可将坐标替换为语义位置，即利用带有语义的地标或者参照物代替基于坐标的位置信息，实现模糊化。也有用圆形区域代替用户真实位置的模糊法技术，此时，将用户的初始位置本身视为一个圆形区域（而不是坐标点），并提出3种模糊方法：放大、平移和缩小。利用这3种方法中的一种或两种的组合，可生成一个满足用户隐私度量的圆形区域。

例如，可以将由用户位置的经纬度坐标转换而来的包含该位置的圆形或矩形区域作为用户的位置进行提交。当提交查询时，我们使用圆形区域C1替换用户的真实位置（X,Y）。

此外，还可以采用基于物理场所语义的位置混淆技术，该技术会提交用户所在的场所而不是用户的具体坐标。例如，使用在西安交通大学校园内的语义地点“图书馆”替换我的具体坐标；也可以使用“兴庆公园”内的黑点位置所示用户，发起查询“最近加油站”的位置服务。

混淆技术的关键在于如何生成混淆空间。用户总是在混淆区域的中间位置，或混淆区域中大部分区域是用户无法到达的河流等场所，亦或混淆区域内人口相对稀疏，这些都会增加攻击者发现用户真实位置的可能性。

大多数模糊法技术无须额外信息辅助，即可在用户端直接实现，因此它们多使用独立结构。

与泛化法不同，多数模糊法技术没有能力对LBS返回的结果进行处理，往往会产生比较粗糙的LBS结果。例如，使用图5中兴庆公园模糊化用户请求“最近加油站”时，事实上S1是最近的加油站，当将C1作为其模糊区域时能够寻找到正确结果；但当将隐私程度更高的C2作为模糊区域时，SP将把S2作为结果返回。所以，虽然C2的半径大于C1的半径，这使得隐私程度提高，但此时SP没有最好地满足用户需求。模糊法技术应解决如何在“保证LBS服务质量”和“满足用户隐私需求”之间寻求平衡的问题。解决该问题的一种方式是在SP和用户之间采用迭代询问的方法，不断征求用户是否同意降低其隐私度量，在有限次迭代中尽可能地提高服务质量。

图5  基于模糊法的隐私保护技术

04 基于加密的位置隐私保护技术

在基于位置的服务中，基于加密的位置隐私保护技术将用户的位置、兴趣点加密后，即会在密文空间内进行检索或者计算，而SP则无法获得用户的位置以及查询的具体内容。两种典型的基于加密的位置隐私保护技术分别是基于隐私信息检索（Private Information Retrieval，PIR）的位置隐私保护技术和基于同态加密的位置隐私保护技术。

（1）基于隐私信息检索（PIR）的位置隐私保护技术

PIR是客户端和服务器通信的安全协议，能够保证客户端在向服务器发起数据库查询时，客户端的私有信息不被泄露给服务器的条件下完成查询并返回查询结果。例如，服务器S拥有一个不可信任的数据库DB，用户U想要查询数据库DB[i]中的内容，PIR可以保证用户能以一种高效的通信方式获取到DB[i]，同时又不让服务器知道i的值。

在基于PIR的位置隐私保护技术中，服务器无法知道移动用户的位置以及要查询的具体对象，从而防止了服务器获取用户的位置信息以及根据用户查询的对象来确定用户的兴趣点并推断出用户的隐私信息。其加密思想如图6所示：用户想要获得SP服务器数据库中位置i处的内容，用户自己将查询请求加密得到Q（i），并将其发送给SP，SP在不知道i的情况下找到X，将结果进行加密R（X,Q（i））并返回给用户，用户可以轻易地计算出Xi。包括SP在内的攻击者都无法通过解析得到i，因此无法获得查询用户的位置信息和查询内容。

图6  PIR方案

PIR可以保证用户的请求、信息的检索以及结果的返回都是安全可靠的。但是，PIR要求SP存储整个区域的兴趣点和地图信息，这使存储空间和检索效率受到了极大挑战。如何设计出更合适的存储结构及检索方式是PIR要继续研究的重点。

（2）基于同态加密的位置隐私保护技术

同态加密是一种支持密文计算的加密技术。对同态加密后的数据进行计算等处理，处理的过程不会泄露任何原始内容，处理后的数据用密钥进行解密，得到的结果与没有进行加密时的处理结果相同。基于同态加密的位置隐私保护最常用的场景是邻近用户相对距离的计算，它能够实现在不知道双方确切位置的情况下，计算出双方间的距离，如微信的“摇一摇”功能。Paillier同态加密是基于加密隐私保护技术常用的同态加密算法，最为典型的有Louis协议和Lester协议。Louis协议允许用户A计算其与用户B的距离，Lester协议规定只有当用户A和用户B之间的距离在用户B设置的范围内时，才允许用户A计算两者之间的距离。

05 位置隐私攻击模型

网络中的攻击者是用户位置隐私最大的威胁来源。攻击者针对不同的位置隐私保护技术形成了不同的攻击模型。这些攻击模型根据攻击者的行为主要可分为主动攻击模型和被动攻击模型。

1. 主动攻击模型

攻击者向受害用户或LBS服务器发送恶意的信息，从而获取用户的位置信息或者干扰用户使用LBS服务。主要包括伪装用户攻击和信息洪水攻击。

（1）伪装用户攻击

伪装用户攻击主要针对基于P2P结构的位置隐私保护技术。在P2P结构下，同一网络中的用户相互信任。攻击者可以假扮用户的好友或其他普通用户，也可以在该网络中的用户的移动设备中植入病毒来控制这些设备。这时攻击者会主动向受害者用户提出协助定位申请，由于得到受害用户的信任，攻击者可以轻松地获取用户精确的位置信息。

伪装用户攻击对于基于同态加密的位置隐私保护技术也有很好的攻击效果。当攻击者得到受害用户信任或距离受害用户的距离在受害用户设置的限定范围之内时，攻击者可以计算得知他与受害者的相对距离。根据三角定位原理，攻击者在成功取得3次及以上相对距离的时候，经过简单的计算就可以得知受害用户的精确位置。

目前已有的位置隐私保护算法中还没有能够很好地解决伪装用户攻击的方法。

（2）信息洪水攻击

信息洪水攻击的原理是拒绝服务。在独立结构和集中式结构中，攻击者向LBS服务器发送大量的LBS请求，占用LBS服务器的带宽和流量，以影响LBS服务器对受害用户的服务效率。在P2P结构中，由于用户之间可以发送协助定位申请，因此攻击者可直接向受害用户发送大量的协助定位申请，这些申请会像洪水一样涌向受害用户，受害用户不仅需要接受这些信息，还需要对这些信息进行处理和转发。数量巨大的信息会导致受害用户的移动网络阻塞，甚至会导致移动设备崩溃。

2. 被动攻击模型

被动攻击是指攻击者被动收集受害用户的信息，并通过收集到的信息来推断用户的真实位置。被动攻击主要包括基于历史信息的攻击、基于语义信息的攻击和基于社交关系的攻击。

（1）基于历史信息的攻击

基于历史信息的攻击主要通过收集受害用户相关的历史信息，分析用户对LBS的使用习惯来推测用户的具体位置。其中历史信息包括受害用户之前发起LBS请求的时间、内容、频率等。例如，如果受害用户经常在晚上或者周末在不同的地点使用导航到达同一地点，则该地点很可能是受害用户的家庭住址。同理，如果受害用户经常在工作日查询某一地点附近的餐厅，则该地点很可能是用户的工作地点。

（2）基于语义信息的攻击

基于语义信息的攻击者通过分析受害用户所在位置区域的信息及其周围环境的语义信息，可缩小用户所在区域的范围，增加识别用户位置的概率。例如，攻击者截获了一个受害用户所在的位置区域信息，经过对该信息进行分析，发现该区域包括一片人工湖、几栋高层楼房和一个停车场。由此可以推断用户位于湖面的概率远小于位于楼房内和停车场的概率。如果又知道用户正在使用导航功能查找去往某地的路线，则用户位于停车场的概率就高于位于楼房内的概率。

（3）基于社交关系的攻击

基于社交关系的攻击主要利用了如今发达的社交网络。首先攻击者收集受害用户的社交信息，通过对其社交网络中的其他用户进行攻击以间接地攻击该受害用户。如果用户甲对自己的位置隐私保护非常重视，攻击者很难直接对用户甲进行攻击，而通过社交网络了解到，用户甲和用户乙是同事，则攻击者就可以对用户乙实施攻击，通过获取用户乙的工作地点来推断出用户甲的工作地点。