位置隐私的最佳地理不可区分机制
摘要：我们考虑了位置隐私的地理不可区分性方法，以及针对效用的权衡。 我们表明，在给定程度的地理不可区分性的情况下，可以使用线性编程技术构建一种将服务质量损失降至最低的机制。 此外，我们证明，在一定条件下，从Shokri等人的角度来看，这种机制也可以提供最佳的隐私。 此外，我们提出了一种方法，可以将线性程序的约束数量从三次减少到二次，保持隐私保证，并且不会显着影响所生成机制的效用。 这大大减少了求解线性程序所需的时间，从而显着扩大了可为其计算最佳机构的位置集。
1.介绍
虽然基于位置的系统(LBSs)已被证明为个人和社会提供了巨大的好处，但这些好处是以用户的隐私为代价的：正如[1、2、3]中所讨论的那样，位置数据可以很容易地与有关个人的各种其他信息联系起来，并暴露出她的私人生活的敏感方面，如她的家庭住址、她的政治观点、她的宗教习俗等。因此，人们对位置隐私保护机制(LPPMs)的发展越来越感兴趣，这种机制允许在使用LBSs的同时为用户提供足够的隐私保证。文献中的大多数方法都是基于扰动报告给LBS提供者的信息，从而防止用户位置的泄露[4，5，6，7，8，9]。
显然，发送给LBS提供商信息的扰动会导致服务质量的下降，因此，用户希望保证的隐私级别和她不得不接受的服务质量损失（QL）之间存在权衡 ， 从Shroki等人的开创性论文开始，对这种交易方式的研究及其优化机制的设计是重要的研究方向。 [10]。
显然，任何此类研究都必须基于有意义的隐私和质量损失概念。 [10]的作者考虑了来自贝叶斯对手的隐私威胁。 更具体地说，他们假设对手知道用户可能位置上的先验概率分布，并且将隐私量化为预期误差，即当对手知道向LBS报告的位置后，真实位置与对手最佳猜测之间的预期距离。 我们把这个量称为AdvError。 对手的猜测考虑到了她已经掌握的信息（先验概率），并且平均而言，它比报告的位置更准确。我们还说，对手可能会重新绘制报告的位置。
在[8]中采用的质量损失概念也是以真实位置和报告位置之间的期望距离来定义的，重要的是，不假定LBS知道用户的先验分布(LBS不为任何特定用户进行调整)，因此它不应用任何重映射。请注意，用于表达QL的距离概念并不需要与用于测量位置隐私的概念相同。当这两个概念重合时，由于对手可以利用先验信息为她带来好处，因此QL始终大于或等于位置隐私。[8]中的最佳机制被定义为在给定QL阈值的情况下最大化隐私的机制，由于这些测量方法是噪声的线性函数(由给定真实位置的每个报告位置的条件概率表征)，这种机制可以通过解决线性优化问题来计算。
在本文中，我们考虑了[9]的地理不可区分性框架，一种基于差分隐私[11]的位置隐私概念，更确切地说，是将其扩展到[12]中提出的任意度量。 直觉上，如果地理位置上接近的两个位置具有相似的概率来生成某个报告的位置，则机制可以提供地理上的不可区分性。 同样，所报告的位置不会增加对手在附近的位置之间区分真实位置的机会。 请注意，此概念可保护位置的准确性：允许对手区分距离较远的位置。 重要的是要注意，地理不可区分的属性不依赖于先验。 这是从差异性隐私继承的功能，它使机制在攻击构成方面具有与差异性隐私相同的鲁棒性。
我们研究优化地理不可区分性与服务质量之间的权衡问题。 更精确地说，给定一定程度的地理不可识别性和先验性，我们的目标是获得使QL最小的机制K。 由于可以通过线性约束来表示地域不可分辨性阈值的特性，因此我们可以将产生此类K的问题简化为线性优化问题，然后可以使用线性编程标准技术解决该问题。
应该指出的是，从某种意义上说，我们的方法是[8]中的一种。后者固定了QL(服务质量损失)的范围并优化了位置隐私。相反，在这里，我们对位置隐私设置了限制，然后优化了QL。另一个重要的区别是，在[8]中，由AdvError度量的最佳机制的隐私度仅针对特定先验进行了保证，而在我们的方法中，最佳机制的隐私保证是基于地理信息。不可区分性，这与先验无关。我们认为，这是当前方法的重要特征，因为很难控制对手的先验知识。例如，考虑一个用户，最佳机制是根据他的平均一天（以及随之而来的先验π）计算出来的，他在上午和下午有非常不同的习惯。通过简单地考虑一天中的时间，对手获得了一些额外的知识，并且当对手使用与π的先验差异时，会严重违反[8]最优机制的隐私保证。
但是，当用于测量QL的距离的概念与根据AdvError表示隐私度的距离的概念相吻合时，那么令人惊讶的是，我们的最优机制K在AdvError方面也是最优的，在某种意义上得到了两种方法的最佳效果。 直觉上，这是由于以下事实：地理不可区分的属性不受重新映射的影响。 因此，对手的预期错误必须与QL一致，即，对手无法通过任何重新映射H获得任何收益，否则KH仍在地理上无法区分,并提供更好的QL。 由于隐私与QL同时存在，因此它也必须是最佳的。 总之，我们得到了一个具有最小QL和最大隐私度(对于该QL)的地缘不区分K。
注意，最优机制不是唯一的，我们的通常与[8]算法产生的机制不一致。 特别是，[8]中的一般不会提供地理上的可区分性，而我们的则通过设计来提供。 地理不可区分性的鲁棒性似乎也会对其他隐私概念产生有利影响：我们已经用[8]的隐私定义在两个真实数据集上评估了这两种机制，并观察到，虽然[8]的机制在定义上提供了计算它的先验的最佳可靠性，但当我们考虑不同的先验时，我们的机制可以表现得更好。
现在，我们将注意力转移到效率问题上。由于通过解决线性优化问题而获得了最佳机制，因此效率的高低主要取决于用于表达地理不可区分性的约束的数量。我们注意到，相对于所考虑的位置数量，此数字通常是立方的。我们证明了，我们能够基于构造位置集合的合适跨度图的近似技术，将这个数字从三次减少到二次。这个想法是，我们不考虑每对位置的地理不可区分性约束，而只考虑跨度图中每个边的约束。根据实验结果，我们还表明，相对于Shokri等人的方法，我们的方法在合理合理地近似的情况下，可以改善运行时间。但是，我们必须注意，以这种方式获得的机制相对于原始指标而言不再是最优的，而仅相对于图所诱导的指标而言，因此该机制的QL可能更高，尽管我们的实验也表明这种增加并不明显。
请注意，在本文中，我们专注于零星位置披露的情况，也就是说，我们假设用户报告的连续位置之间有足够的时间，因此它们可以被认为是独立的。地理上的不可区分性也可以应用于连续点之间的相关情况，但必须额外注意避免隐私的降低，当连续位置的数量较多时，隐私的降低可能是非常明显的。相关性的问题与本文的目标是正交的。我们可以参考[13]对这个问题的研究。
贡献：
•我们提出一种基于线性优化的方法，以生成在地理上无法区分并实现最佳效用的机制。 此外，当用于QL的距离概念与用于地理不可区分的距离概念一致时，则该机制对于对手的预期误差也是最佳的。
•我们在不同的先验条件下（从两个广泛使用的数据集的真实痕迹生成）评估了我们的方法，并表明它优于其他考虑的机制。
•我们基于跨度图提出了一种近似技术，该技术可用于减少优化问题的约束数量，并且仍能获得地理上无法区分的机制。
•我们测量了近似对效用和约束数量的影响，并分析了整个方法的运行时间，获得了满意的结果。
本文件的计划：
本文的其余部分组织如下。下一节回顾一些初步的概念。在第3节中，我们说明了产生线性不可分的最佳机制作为线性优化问题的解决方案的方法，并提出了一种减少问题中使用的约束数量的技术。在第4节中，我们对我们的机制与文献中的其他机制进行了评价。最后，在第5节中，我们讨论了相关的工作并得出结论。
缺少的证明可以在本文的报告版本中找到[14]。
2.准备工作
2.1位置混淆、质量损失和敌方错误(adversary’s error)。
实现位置隐私的一种常见方法是应用位置混淆机制，即概率函数K：X→P（X），其中X是可能的位置集合，而P（X）表示X上的概率分布集合。K将位置 x 作为输入，并生成报告的位置 z，该位置 z 被传达给服务提供商。 在本文中，我们通常认为X是有限的，在这种情况下K可以由一个随机矩阵表示，其中 kxz 是从位置 x 报告 z 的概率。
可以将位置集合上的先验分布π∈P（X）视为对用户（用户配置文件）的行为进行建模，或者作为捕获有关用户的对手方信息的方式。 给定先验 π 和 X 的度量d，实际位置和报告位置之间的期望距离为：
从用户的角度来看，我们想对机制 K 产生的服务质量损失（QL）进行量化。给定位置上的质量度量dQ，例如dQ（x，z）通过报告z 实际位置是x（欧氏度量d2是典型选择），我们可以自然地将质量损失定义为实际位置和报告位置之间的预期距离，即QL（K，π，dQ）= ExpDist（K， π，dQ）。 QL也可以看作是该机制的（逆）效用。
类似地，我们要量化 K 所提供的隐私。[10]中引入的自然方法是考虑具有一些先验信息 π 的贝叶斯对手，试图将 z 重新映射回猜测的位置 xˆ 。 重映射策略可以用随机矩阵H建模，其中hzxˆ是将 z 映射到 xˆ 的概率。 然后，可以将机制的隐私定义为最佳重新映射条件下对手的预期错误：
注意，K和H的组成KH本身是一种机制。 与dQ相似，度量标准dA(x，xˆ) 捕获了对手在真实位置为x时猜测xˆ的损失。 请注意，dQ和dA可以不同，但是典型的选择是对两者都使用欧式距离。
那么，自然的问题是，在给定QL约束的情况下，构建一种实现最佳隐私的机制。
定义1.给定一个先验π，一个质量度量dQ，一个质量边界 q 和一个对抗度量dA，机制K为q-OptPriv（π，dA，dQ）i ff
换句话说，q-OptPriv机制在QL最多为q的所有机制中提供了最佳的隐私（以AdvError表示）。 在[8]中研究了这个问题，提供了一种通过解决适当构造的线性程序来构造任何q，π，dA，dQ的这种机制的方法。
2.2差分隐私
差异隐私最初是在统计数据库的上下文中引入的，要求将查询应用于相邻数据库（即，按单行分布的数据库）时，应产生相似的结果。 邻接的概念与汉明度量dh（x，x‘）有关，后者定义为x，x’的行数。 差异性隐私要求x，x'之间的汉明距离越大，则允许它们越可区分。
这个概念可以自然地扩展到任何配备公制dX [15，12]的秘密X的集合。 距离dX（x，x‘）表示 x 和 x’ 之间的可区分性级别：如果距离很小，则秘密应该保持不可区分，而彼此相距较远的秘密将被对手区分。 应该根据手头的应用和我们试图实现的隐私概念的语义来选择度量。
按照[12]的表示法，一种机制是概率函数K：X→P（Z），其中Z是一组重新报告的值（就本文而言，假定为有限值）。 概率分布之间的相似性可以用乘法距离dP来衡量, dP (µ1, µ2) = supz∈Z | ln µ1(z)/µ2(z) | 
如果µ1(z)、µ2(z)都为零，则
= 0，如果其中只有一个为零，则为∞。换句话说，dP(µ1，µ2)小 iff µ1，µ2对每个值 z 赋予相似的概率。
定义2.机制K：X→P（Z）满足dX-privacy iff：
或着说 K(x)(z) ≤ edX(x,x')K(x')(z) 对于所有x，x'∈X，z∈Z. 隐私参数 ε 也可以引入了扩展度规dX（请注意εdX本身是一个指标）。
差异隐私可以表示为“ εdh-privacy”。 此外，不同的度量标准引起了人们对隐私的各种关注。 在[12]中给出了几个例子。
2.3地理不可区分性
在基于位置的系统的上下文中，秘密 X 是位置，我们可以自然使用欧几里得距离d2（由安全参数ε缩放）来获得有用的位置隐私概念。 导致的εd2隐私概念在[9]中称为 ε-地理不可区分性，要求位置混淆机制在应用于地理位置较近的位置时应产生相似的结果。 这样可以防止服务提供商准确推断用户的位置，同时允许他获得提供服务所需的大致信息。 遵循差分隐私的精神，此定义独立于对手的先验信息。
文献[9]对地理不可区分性的描述进一步证明了这一概念。 该描述将对手的结论（后验分布）与他的初始知识（先验分布）进行比较。 由于一些信息是应该被揭示的（即提供商会得知用户在巴黎附近的某个地方），我们不能期望这两个分布会重合。 然而，地理上的不可区分性意味着一个知情的广告商如果已经知道用户位于一个小区域N内，就不能改进他的初始知识，以更高的准确度定位用户。更多的细节，以及第二个特征可以在[9]中找到。
注意，在任何先验条件下，地理上的不可区分性并不能保证在任何先决条件下的小范围泄露。 实际上，没有任何混淆机制在确保某些实用性的同时确保这一点。 例如，考虑到一个对手知道用户在某个机场被劫持，但不知道是哪个机场。除非噪音很大，否则报告一个混淆的位置会让人推断出确切的位置，但这是不可避免的1。
考虑到这一机制，[9]表明通过在用户的二维拉普拉斯分布中添加噪声可以实现地理不可区分性。 可以很容易地在极坐标中通过从伽玛分布中均匀地选择角度和半径来完成。 如果允许有一组受限制的报告位置，那么该机制产生的位置可以被映射到允许的位置中最接近的位置。
虽然Laplace机制提供了一个简单实用的方法来实现地理上的不区分性，不受任何用户先验的影响，但它的效用并不总是最佳的。在下一部分中，我们显示通过针对特定用户配置文件调整先验机制，我们可以在满足地理不可区分性（即与先验独立的隐私保证）的同时，实现针对该先验的更好的实用性。 第4节中的评估结果表明，与拉普拉斯机制相比，最佳机制可以提供实质性的改进。
3.地理不可区分性的最佳利用机制
如引言中所讨论的，我们旨在获得一种机制，可以优化隐私（就地理不可区分性而言）和质量损失（就度量QL而言）之间的权衡。 我们的主要目标是，给定一组具有隐私度量dX（通常是欧几里得距离），隐私级别ε，用户配置文件 π 和质量度量dQ的位置X，以找到εdX-privacy机制，使其QL 尽可能小。
我们从描述强制εdX-privacy的一组线性约束开始，该约束允许获得最佳机制作为线性优化问题。 但是，约束条件的数量可能很大，随着位置数量的增加，该方法在计算上要求很高。 因此，我们提出了一种近似解决方案，该解决方案将dX替换为生成图引起的度量。 我们讨论一种贪婪算法来计算生成图并分析其运行时间。 我们还表明，如果质量指标和对手指标一致，那么就AdvError而言，构造（精确或近似）的机制也可以提供最佳的隐私。 最后，我们讨论了我们方法的一些实际考虑。
3.1构建最优机制
假设所构建的机制具有输入和输出的预先确定的一定数量的位置集X 。例如，可以通过将地图划分为有限数量的区域（任意大小和形状），然后在X中为每个区域选择代表位置来构造X。 我们还假设X之前有一个π，它表示用户 在任何给定时间位于每个位置的概率。
给定隐私度量dX（通常是欧几里得距离）和隐私参数ε，目标是构建εdX-privacy机制K，以使相对于质量度量dQ的服务质量损失最小。 此属性的定义如下：
请注意，εdX -OptQL优化了给定隐私约束的QL，而q-OptPriv（Definition 1）优化了给定QL约束的隐私。
为了使K成为εdX-private，它应满足以下约束：
因此，我们可以通过解决线性优化问题，在满足εdX-privacy的同时将QL（K，π，dQ）最小化来构造最优机制：
可以很容易地看到，机制K先前生成的优化问题是εdX-OptQL（π，dQ）。
3.2 一个更有效的方法-使用扳手
在上一部分的优化问题中，εdX-privacy定义在l线性程序中引入了| X | 3约束。但是，为了能够管理大量位置，我们希望将此数量减少到O（| X | 2）的数量。实现此目的的一种可能方法是使用线性程序的对偶形式（如附录所示）。对偶程序具有与原始程序的变量一样的约束（在这种情况下| X | 2），在主程序中每个约束具有一个变量（在这种情况下O（| X | 3））。由于原始线性程序以有限的步数找到了最优解，因此强大的对偶性定理保证了对偶程序也将这样做。但是，如第4.3节所示，实际上，对偶程序并没有对原始程序进行实质性的改进（可能的解释是，尽管数量较少，但对偶程序中的约束更为复杂，从某种意义上说，每个变量都包含大量变量）。
另一种方法是利用度量dX的结构。 到目前为止，我们尚未对dX进行任何假设，我们需要为每一对位置 x 和 x’ 指定|X|约束。 但是，值得注意的是，如果距离dX是由加权图引起的（即，每对位置之间的距离是图中最小路径的权重），我们只需要考虑图中相邻的每对位置的|X |约束。这方面的一个例子是差异隐私的通常定义:由于数据库之间的邻接关系会引起汉明距离dh，因此我们只需要对汉明图中相邻的每对数据库都要求差分隐私约束（即， 个体差异）。
但是，可能情况是度量dX不受任何图（除了完整图）的诱导，因此约束量保持不变。 实际上，欧几里得度量通常就是这种情况。 因此，我们考虑其中dX可以通过某种图诱导度量近似的情况。
如果G是无向加权图，则用dG表示由G引起的距离函数，即dG（x，x‘）表示G中节点x和x’之间的最小路径的权重。 G的节点是X，其边缘的权重由度量dX给出，我们可以用dG近似dX。 在这种情况下，我们说G是X的生成图或生成器[16，17]。
扳手理论中的一个主要概念是扩张，也称为拉伸因子：
非正式地，X的 δ-spanner 可以认为是度量dX的近似值，其中节点之间的距离“拉伸”了最多 δ 倍。 扳手通常用于估算地理网络中的距离，而无需考虑每对节点之间的距离。 图1中显示了地图中网格的扳手示例。
图1：（a）将巴黎地图划分为7×5正方形网格。 位置X的集合包含区域的中心。 （b）X的扩张度为δ= 1.08的扳手。
命题1：令X为度量为dX的一组位置，令G为X的 δ-spanner。 如果用于X的机制K为
则K为