论文标题
地理图形 - 独立性：基于差异隐私的道路网络上的位置隐私
Geo-Graph-Indistinguishability: Location Privacy on Road Networks Based on Differential Privacy
论文作者
论文摘要
近年来，随着基于位置服务（LBSS）的传播，对位置隐私的担忧正在增加。在过去的几十年中，已经提出了许多保护位置隐私的方法。尤其是，基于地理难以区分性（GEO-I）的扰动方法随机地将真实位置扰动到伪定位，因此由于其强大的隐私保证从差异隐私中继承而引起了人们的注意。但是，Geo-I基于欧几里得飞机，即使许多LBS基于道路网络（例如，共享服务）。这会导致不必要的噪音，因此在道路网络上的LBSS效用和隐私之间的权衡不足。为了解决这个问题，我们提出了一个新的隐私概念，地理图 - 独立性（GG-I），以在道路网络上的位置，以实现更好的权衡。我们提出了满足GG-I的图形指数机制（GEM）。此外，我们正式化了优化问题，以在权衡方面找到最佳的宝石。但是，找到最佳解决方案的幼稚方法的计算复杂性是令人望而却步的，因此我们提出了一种贪婪的算法，以在可接受的时间内找到近似解决方案。最后，我们的实验表明，我们提出的机制在权衡方面优于地理-I的机制。
In recent years, concerns about location privacy are increasing with the spread of location-based services (LBSs). Many methods to protect location privacy have been proposed in the past decades. Especially, perturbation methods based on Geo-Indistinguishability (Geo-I), which randomly perturb a true location to a pseudolocation, are getting attention due to its strong privacy guarantee inherited from differential privacy. However, Geo-I is based on the Euclidean plane even though many LBSs are based on road networks (e.g. ride-sharing services). This causes unnecessary noise and thus an insufficient tradeoff between utility and privacy for LBSs on road networks. To address this issue, we propose a new privacy notion, Geo-Graph-Indistinguishability (GG-I), for locations on a road network to achieve a better tradeoff. We propose Graph-Exponential Mechanism (GEM), which satisfies GG-I. Moreover, we formalize the optimization problem to find the optimal GEM in terms of the tradeoff. However, the computational complexity of a naive method to find the optimal solution is prohibitive, so we propose a greedy algorithm to find an approximate solution in an acceptable amount of time. Finally, our experiments show that our proposed mechanism outperforms a Geo-I's mechanism with respect to the tradeoff.
