论文标题：DPPS: A novel dual privacy-preserving scheme for enhancing query privacy in continuous location-based services（DPPS——用于增强连续位置查询隐私的双重隐私保护方案）

期刊：Frontiers of Computer Science

作者：Long LI, Jianbo HUANG, Liang CHANG, Jian WENG, Jia CHEN, Jingjing LI

发表时间：15 Oct 2023

DOI：10.1007/s11704-022-2155-9

微信链接：点击此处阅读微信文章

原文信息

标 题：

DPPS: A novel dual privacy-preserving scheme for enhancing query privacy in continuous location-based services

原文链接：

https://journal.hep.com.cn/fcs/EN/10.1007/s11704-022-2155-9

引用格式：

Long LI, Jianbo HUANG, Liang CHANG, Jian WENG, Jia CHEN, Jingjing LI. DPPS: A novel dual privacy-preserving scheme for enhancing query privacy in continuous location-based services. Front. Comput. Sci., 2023, 17(5): 175814

公众号推文链接：

文章精要 | DPPS：用于增强连续位置查询隐私的双重隐私保护方案

01

导读

随着嵌入定位系统和数字地图的智能手机的广泛使用，基于位置的服务(IBSs)迅速普及，为人们的日常生活提供了前所未有的便利，然而，它们也引起了人们对隐私泄露的极大关注。特别地，位置查询可用于推断用户的敏感私人信息，如家庭地址、工作地点和约会地点。因此，研究者们提出了许多提供查询匿名的方案，但这些方案通常忽略了攻击者可以从连续LBS中连续位置之间的相关性推断出真实位置的事实。为了解决这一挑战，本文提出了一种新的双重隐私保护方案(DPPS)，该方案包含两种隐私保护机制。首先，为了防止位置之间的相关性导致隐私泄露，提出了一种基于隐马尔可夫模型(HMM)的关联模型来模拟用户的移动性和对手的预测概率。其次，为了提供每个单个位置的查询概率匿名性，提出了一种先进的-匿名算法来构建隐形区域，在隐形区域中生成真实且不可区分的虚拟位置。为了验证DPPS的有效性和效率，本文在微软发布的现实数据集GeoLife数据集上进行了进一步的理论分析和实验验证。

02

问题陈述和证明

P2P架构下的WTA问题定义

图1显示了一个简单的社会网络地图，该地图被划分为21*21个网格单元，其中每个网格单元都有自己的查询概率。本文利用DLS生成5个虚拟位置，形成一个6匿名集，保护用户的位置隐私。图1中绿色虚线表示考虑的时间间隔内可行驶的最远距离，近似计算如下:

，

其中是用户在处的速度。

图1 一个社会网络的例子

从图1中可以发现在处，真实位置附近生成了三个虚拟位置，这使得攻击者很容易识别真实位置。此外，在处选择的一个虚拟位置不在查询范围内并且超过了最大距离，因此攻击者可以根据两个位置集之间的相关性直接将其识别为假位置。

图2给出了两个连续位置集的示例，A和B表示用户访问的两个相邻的真实位置，A'和B'表示虚拟位置，每个箭头上的数字表示了查询数量。基于用户所采取的轨迹历史，攻击者有可能猜测用户当前所采取的真实路径。例如，从图2可知，在A和A'之后，B被查询了70次，而在A和A'之后，B被查询了330次。由于330>>70，攻击者极有可能推断出B是真实位置，从而导致用户位置隐私泄露。简而言之，如果攻击者拥有关于连续位置之间的相关性的信息，则用户的位置信息可能在连续查询中受到损害。

图2 两个连续位置集的例子

定理1：连续位置之间的关联可以泄露用户隐私。

证明：假设匿名集的熵为，表示的熵。用来描述用户拥有的平均私人信息量和隐私来源的隐私不确定程度。越大，隐私泄露的可能性越小，故其也可用来衡量隐私保护的程度。

根据信息论的知识，给出如下公式来表示连续位置之间的相关性的边信息：

其中，和分别表示和的任意一个元素；和分别为和的边际概率分布函数；为和的联合概率分布函数。

进一步执行以下数学运算:

从上面的分析可以看出，如果攻击者了解到上的一些信息，这些信息代表了连续位置之间的关联的侧信息，那么用户的位置隐私就会被泄露。

基于HMM的相关模型

为了增强连续查询中位置隐私的保护，使用隐马尔可夫模型(HMM)对相邻位置和对手预测概率之间的相关性进行建模。图3描绘了基于HMM的关联模型的示意图，其中表示对手猜测中真实位置的概率，并且表示之后已经被查询了次。

图3 基于HMM的相关模型示意图

为了衡量当前位置的隐私程度，引入了转移熵，就两个连续位置之间的相关性而言，其充分考虑了查询概率，因此可以更有效地表达位置隐私保护的程度。转移熵的计算公式如下:

其中可以由下式计算：

其中表示位置的归一化查询概率，表示从位置到位置的查询次数与集合到位置中所有位置的查询次数之比。和的值分别由下面两个公式计算：

高级-匿名算法(AKA)

DPPS的目的是生成真实且难以区分的虚拟位置。在DPPS中，建议AKA生成虚拟位置，同时主要关注以下几个方面来提高隐私保护水平:

（1）匿名集中的虚拟位置应该合理地分布在真实位置周围。与真实位置的距离不应超过，以防止对手从用户的移动中识别出虚拟位置。

（2）选择的假人位置必须在用户的查询半径之内，防止对手根据直接识别假人位置。

不仅基于单一位置的位置隐私保护应当被考虑，也应根据连续位置之间的相关性选择合适的虚拟位置。表1显示了AKA的详细步骤。

表1 AKA的详细步骤

算法1的核心功能如下:

（1）确定了的值与用户的隐私要求有关，越大，隐私程度越高。

（2）构造了一个由和范围内的候选虚拟位置组成的位置池。之所以选择虚拟位置，是因为基数越大，形成的匿名集的转移熵越大，从而保证了更高的隐私保护程度。此外，在和内选择一个虚拟位置，并消除对手根据或识别虚拟位置的可能性。

（3）利用线性加权法得到的多目标优化解，既考虑两个连续位置之间的转移概率，又考虑每个虚拟位置与真实位置之间的距离，选择最优虚拟位置。算法中，和表示线性加权法的系数，表示第个候选虚拟位置与真实位置在处的距离。

（4）根据它们的权重选择个最优假人位置。

03

实验结果总结

（1）DPPS通过同时考虑单个位置的匿名性和连续位置之间的相关性，实现了位置隐私的双重保护。

（2）为了有效捕获隐藏在连续位置关联中的侧信息，利用隐马尔可夫模型(HMM)根据用户的移动性对这些关联进行模拟，从而评估对手对连续匿名关联的预测概率。

（3）为了提供查询概率匿名性，提出了一种高级匿名算法(AKA)来构造隐藏区域。AKA通过同时考虑虚拟位置的分布、用户的查询半径和相邻位置之间的相关性，提高了隐私保护的效果。

（4）为了验证所提出方案的有效性，基于GeoLife数据集进行了进一步的数值分析和实证评估，该数据集是微软GeoLife项目中182个用户在超过5年的时间内收集的全球定位系统(GPS)轨迹数据集。

04

实验结果的简单总结

在实验中，DPPS与几种现有的解决方案进行了比较，包括随机方案、DLS、DLP、贪婪算法和EXA。

1.熵与

根据熵的变化对算法的隐私保护性能进行评价。

从图4可以清楚地看出，随着值的增大，位置隐私保护的程度增大，算法的熵也随之增大。DPPS、DLS和DLP都能使熵最大化，说明这些方案都能实现高效的隐私保护。当和时，随机方案的熵值相同，这是因为随机算法可能会选择带有查询概率为0的位置，比如湖泊和河流等。由于EXA和贪心算法不涉及与熵相关的内容，所以这里不对它们进行比较。

图4 熵的比较

2.转移熵与

图5显示了随着值的变化，不同算法的转移熵的比较。对于用户来说，较低的转移熵表示较低的隐私保护水平，这意味着攻击者可以更容易地识别真实位置。图5(a)为两个连续位置集的实验结果，图5(b)为三个连续位置集的实验结果。

如图5所示，该随机方案具有最低的转移熵，这是因为随机方案随机选择哑点位置，因此忽略了侧面信息，这也意味着对手可以很容易地识别连续查询中的大多数哑点位置。DLS和DLP的性能优于随机方案，这是因为这两种算法都使用了固定查询位置的侧信息，然而，它们没有考虑连续位置之间的关系，这限制了它们保护位置隐私的能力。EXA在转移熵方面表现良好，因为它考虑了连续位置之间的相关性。显然，贪婪算法的性能最好，因为贪婪算法选择的虚拟位置的转移概率与真实位置的转移概率尽可能接近。最后，DPPS算法的性能仅次于贪心算法，明显优于其他算法，由于DPPS额外考虑了虚拟位置的分布，导致转移熵性能略有下降。

图5 转移熵比较 (a) 2个连续的位置集;(b) 3个连续的位置集

3.转变熵对的方差

为了衡量真实位置的过渡概率与每个算法选择的假人之间的偏差程度，计算过渡概率的方差，结果如图6所示。从图6中可以看出，贪心算法的转移熵方差接近于0，说明它可以选择与真实位置非常相似的虚拟位置。DPPS的性能再次与贪心算法相似，并且远远优于其他算法，从而证明了DPPS的合理性和有效性。此外，从曲线的波动可以看出，DPPS的方差分布均匀，说明其性能相对稳定。

图6 根据过渡熵的方差进行比较

4.距离方差与

由于对手很可能根据隐身区域内的位置分布来识别假人，因此匿名集中所有位置之间的距离方差应该是合理的。距离方差越小，位置分布越合理。图7描述了时不同方案的距离方差。从图7可以看出，随机方案的距离方差最大，这反映了它完全忽略了匿名集中的位置分布。DLS和DLP的距离方差也很大，说明匿名集中的位置分布不够合理。贪心算法和EXA的距离方差相对较小，但其值随的变化波动较大，说明其在匿名集中的位置分布不稳定。相比之下，DPPS就衡量标准来说表现最好，表明该方案可以有效地构造合理的匿名集来防御攻击，从而保护位置隐私。

图7 距离方差比较 (a)k = 10;(b) k =20;(c) k =30

05

与其他相关研究对比

为了有效地保护位置隐私，基于各种隐私保护技术提出了许多方案，在这些技术中，基于虚拟生成算法的匿名受到了相当大的关注。为了在有限的时间间隔内隐藏用户的真实位置，虚拟生成算法必须围绕真实位置生成个虚拟位置，然后将所有个位置组合并传输给LBS服务器。通过以这种方式增加用户的位置不确定性，虚拟生成算法降低了对手发起成功推理攻击的可能性。

现有的相关研究中，Kido等人提出了一种以随机概率生成虚拟位置的方法，该方法忽略了对手掌握的背景信息。Niu等人提出了虚拟位置选择(DLS)算法来实现LBSs中用户的匿名。与现有方法不同，DLS仔细选择虚拟位置，考虑到侧信息也可能被对手利用，然而，所选择的虚拟位置离真实位置太远，因此很容易区分。为了解决DLS的缺点，Sun等人提出了一种新的攻击模型，并设计了一种新颖的攻击模型虚拟位置隐私保护算法，然而，该算法只考虑查询概率与真实位置相似的虚拟位置，而忽略了这些假位置和真实位置构成的匿名空间内的位置分布问题。Sun等提出了一种基于划分兴趣区域的位置隐私保护算法。与传统方法不同，该方法在生成虚拟位置时独特地考虑了语义信息，从而降低了真实位置的暴露概率。

显然，上述研究工作只考虑了单个位置的隐私保护，而忽略了连续位置之间的实际相关性，如位置关联和时间可达性。通过使用这些相关性，攻击者可以很容易地计算出每个位置的查询概率，然后过滤掉假人，最终识别出真实的位置。其结果是，用户的位置隐私受到极大的损害。而本文提出的双重隐私保护方案(DPPS)，可以很好地解决这些潜在的隐私问题。

解读：戴西件 南昌大学第二附属医院

审核：张 琨 合肥工业大学

Frontiers of Computer Science

Frontiers of Computer Science （FCS）是由教育部主管、高等教育出版社和北京航空航天大学共同主办、SpringerNature 公司海外发行的英文学术期刊。本刊于 2007 年创刊，双月刊，全球发行。主要刊登计算机科学领域具有创新性的综述论文、研究论文等。本刊主编为周志华教授，共同主编为熊璋教授。编委会及青年 AE 团队由国内外知名学者及优秀青年学者组成。本刊被 SCI、Ei、DBLP、INSPEC、SCOPUS 和中国科学引文数据库（CSCD）核心库等收录，为 CCF 推荐期刊；两次入选“中国科技期刊国际影响力提升计划”；入选“第4届中国国际化精品科技期刊”；入选“中国科技期刊卓越行动计划项目”。

《前沿》系列英文学术期刊

由教育部主管、高等教育出版社主办的《前沿》（Frontiers）系列英文学术期刊，于2006年正式创刊，以网络版和印刷版向全球发行。系列期刊包括基础科学、 、工程技术和人文社会科学四个主题，是我国覆盖学科最广泛的英文学术期刊群，其中12种被SCI收录，其他也被A&HCI、Ei、MEDLINE或相应学科国际权威检索系统收录，具有一定的国际学术影响力。系列期刊采用在线优先出版方式，保证文章以最快速度发表。

中国学术前沿期刊网

http://journal.hep.com.cn