CN104507048A - 一种基于l-查询的位置隐私保护方法 - Google Patents

Abstract

本发明涉及一种基于 l -查询的位置隐私保护方法，包括以下步骤：（1）当用户需要位置服务时，向匿名服务器发起查询请求；（2）匿名服务器在位置 k -匿名的基础上，通过合并同一时刻来自同一区域的查询请求以及插入假查询的方法，构造一个包含 k 个用户和 l 个查询主题的匿名查询请求，并提交给位置服务器；（3）位置服务器分别对 l 个查询主题逐一进行查询处理，然后将查询结果合并后的结果集返回给匿名服务器；（4）匿名服务器从结果集中滤掉假查询的结果后，根据不同用户的查询主题进行分拣和二次求精，得到最终的位置查询结果，然后分别返回给各用户。该方法可以提高位置隐私保护机制的安全性。

Description

一种基于l-查询的位置隐私保护方法

技术领域

本发明属于位置信息服务技术领域，特别涉及一种基于l-查询的位置隐私保护方法，可应用于导航、社交和周边查询等各种基于位置的信息服务。

背景技术

基于位置的服务（Location-Based Services，简称LBS）是通过获取移动用户的位置信息为用户提供包括交通引导、兴趣点查询、车辆跟踪、紧急呼叫等众多服务的技术基础，用户在向基于位置的服务器提出服务请求时提供的位置信息越准确，服务器返回给用户的服务信息就越准确。因此人们在享受基于位置的服务所带来的便利的同时，也受到了隐私可能暴露的威胁。

位置k-匿名是目前常见的位置隐私保护方法，其主要思想是通过可信第三方匿名服务器将查询用户及其位置信息分别泛化成一个包含k个用户的匿名组和匿名区域，使得位置服务器无法将真实用户和其他k-1个用户区分，也无法获得匿名组成员所在的精确位置信息，从而实现了用户身份和位置信息的双重隐私保护。但在位置k-匿名机制中，当用户在移动过程中多次请求同一个查询时，匿名服务器将会为该用户构造出多个主题相同但是用户集不同的匿名组，由于这些匿名组都包含真实用户的身份信息，攻击者只要对这些匿名组取交集，就有可能推测出真实用户的身份信息。

发明内容

本发明的目的在于提供一种基于l-查询的位置隐私保护方法，该方法可以提高位置隐私保护机制的安全性。

为实现上述目的，本发明的技术方案是：一种基于l-查询的位置隐私保护方法，包括以下步骤：

（1）当用户需要位置服务时，向匿名服务器发起查询请求；

（2）匿名服务器在位置k-匿名的基础上，通过合并同一时刻来自同一区域的查询请求以及插入假查询的方法，构造一个包含k个用户和l个查询主题的匿名查询请求，并提交给位置服务器；

（3）位置服务器分别对l个查询主题逐一进行查询处理，然后将查询结果合并后的结果集返回给匿名服务器；

（4）匿名服务器从结果集中滤掉假查询的结果后，根据不同用户的查询主题进行分拣和二次求精，得到最终的位置查询结果，然后分别返回给各用户。

进一步的，采用信息熵来确定查询主题个数l：

假设系统共有n个查询主题，1≤l≤n，则l-查询的查询主题个数l的计算公式为：

其中，H为用于度量l-查询的隐私度的信息熵。

进一步的，匿名服务器对整个服务区域进行分簇，划分为若干个区域，以在构造匿名查询请求时将同一时刻来自同一区域的查询请求进行合并。

进一步的，插入假查询的方法为：当合并后的真实查询主题个数不足l时，则随机插入假查询，使总查询主题个数达到l，通过构造l-查询切断用户和查询主题之间的关联。

本发明的有益效果是克服了位置k-匿名机制在连续查询中存在的安全缺陷问题，提供了一种基于l-查询的位置隐私保护方法，该方法通过构造l-查询切断了用户身份信息与查询主题之间的关联，能有效防范攻击者对相同主题的匿名组进行交集运算的攻击，提高了位置隐私保护机制的安全性。此外该方法采用先合并查询再插入假查询的方法，在满足l-查询的基础上，减少了系统资源开销。

附图说明

图1是本发明方法对应的系统结构示意图。

图2是本发明方法的实现过程示意图。

具体实施方式

本发明基于l-查询的位置隐私保护方法，包括以下步骤：

（1）当用户需要位置服务时，向匿名服务器发起查询请求；

（2）匿名服务器在位置k-匿名的基础上，通过合并同一时刻来自同一区域的查询请求以及插入假查询的方法，构造一个包含k个用户和l个查询主题的匿名查询请求，并提交给位置服务器；

（3）位置服务器分别对l个查询主题逐一进行查询处理，然后将查询结果合并后的结果集返回给匿名服务器；

（4）匿名服务器从结果集中滤掉假查询的结果后，根据不同用户的查询主题进行分拣和二次求精，得到最终的位置查询结果，然后分别返回给各用户。

其中，采用信息熵来度量l-查询的隐私度及确定查询主题个数l：

在l-查询中，假设系统共有n个查询主题，1≤l≤n，如果用户的查询主题是随机选取，则一个主题T _i 被选中为l-查询中的真实查询的概率p _i 为：

通过信息熵H来度量l-查询的隐私度：

由此可得l-查询的查询主题个数l为：

表示向下取整。由上式可知，H越大则l越大，其中l为正整数。

合并同一时刻来自同一区域的查询请求前，匿名服务器对整个服务区域进行分簇，划分为若干个区域，以在构造匿名查询请求时将同一时刻来自同一区域的查询请求进行合并。

构造匿名查询请求时，插入假查询的方法为：当合并后的真实查询主题个数不足l时，则随机插入假查询，使总查询主题个数达到l，通过构造l-查询切断用户和查询主题之间的关联。

下面结合图1和图2，具体阐述本发明的具体实现步骤：

步骤1构造系统框架：如图1所示，本发明方法建立了由用户、匿名服务器和位置服务器组成的通信系统；用户利用GPS等定位技术获取自身的地理位置信息；匿名服务器负责对用户的身份和位置信息进行匿名保护；位置服务器负责提供基于位置的服务。

步骤2初始化系统：匿名服务器首先根据语义信息（如兴趣点）对整个服务区域进行分簇，例如将一个小区划分为一个区域；然后根据系统的查询主题总个数n以及熵H值，计算l值：。

步骤3发起查询：如图2所示，当移动用户需要位置服务时，首先向匿名服务器发出查询请求，查询请求定义为M={u，z，k，q}，其中，u表示用户的身份信息；z=(x，y)表示用户u的位置，x表示经度，y表示纬度，z可由GPS定位设备直接获取；k表示用户u对身份的隐私保护需求度；q表示用户u的查询主题。

步骤4构造匿名查询：匿名服务器首先将工作时间进行分时隙；然后在位置k-匿名的基础上，采用合并查询以及插入假查询的方法，构造一个包含k个用户和l个查询主题的匿名请求消息UM，再将UM发送给位置服务器。

定义UM={U，Z，Q}，其中，U为k-匿名组，Z为匿名区域，Q为l-查询主题集。假设某个区域在同一时隙到达的查询消息有i个，则U={u ₁,u ₂,…,ui,u'₁,u'₂,…,u' _k-i }，其中，{u ₁ ,u ₂,…,u _i }为真实用户的身份信息，{u'₁,u'₂,…,u' _k-i }为区域内其他任意用户的身份信息；Z为覆盖U中所有用户的最小矩形框区域；Q={q ₁,q ₂,…,q _j ,q'₁,q'₂,…,q' _l-j }，其中，{q ₁,q ₂,…,q _j }为对i个查询进行合并后的主题集（j≤i），{q'₁,q'₂,…,q' _l-j }为从查询主题库中随机选择的假查询。

步骤5查询处理：位置服务器对l-查询中的每个查询主题逐一进行检索处理，然后将查询结果的并集作为候选结果集CS，返回给匿名服务器。

步骤6信息过滤：匿名服务器首先过滤掉候选结果集中假查询的结果，然后根据不同用户的查询主题进行分拣和二次求精，最后将处理结果集RS分别返回给各查询请求用户。

以上是本发明的较佳实施例，凡依本发明技术方案所作的改变，所产生的功能作用未超出本发明技术方案的范围时，均属于本发明的保护范围。

Claims (4)

1.一种基于l-查询的位置隐私保护方法，其特征在于，包括以下步骤：

（1）当用户需要位置服务时，向匿名服务器发起查询请求；

（2）匿名服务器在位置k-匿名的基础上，通过合并同一时刻来自同一区域的查询请求以及插入假查询的方法，构造一个包含k个用户和l个查询主题的匿名查询请求，并提交给位置服务器；

（3）位置服务器分别对l个查询主题逐一进行查询处理，然后将查询结果合并后的结果集返回给匿名服务器；

（4）匿名服务器从结果集中滤掉假查询的结果后，根据不同用户的查询主题进行分拣和二次求精，得到最终的位置查询结果，然后分别返回给各用户。

2.根据权利要求1所述的一种基于l-查询的位置隐私保护方法，其特征在于，采用信息熵来确定查询主题个数l：

假设系统共有n个查询主题，1≤l≤n，则l-查询的查询主题个数l的计算公式为：

其中，H为用于度量l-查询的隐私度的信息熵。

3.根据权利要求1所述的一种基于l-查询的位置隐私保护方法，其特征在于，匿名服务器对整个服务区域进行分簇，划分为若干个区域，以在构造匿名查询请求时将同一时刻来自同一区域的查询请求进行合并。

4.根据权利要求1所述的一种基于l-查询的位置隐私保护方法，其特征在于，插入假查询的方法为：当合并后的真实查询主题个数不足l时，则随机插入假查询，使总查询主题个数达到l，通过构造l-查询切断用户和查询主题之间的关联。