Online Location Trace Privacy: An Information Theoretic Approach
Online Location Trace Privacy: An Information Theoretic Approach
复制标题
DOI：
10.1109/tifs.2018.2848659
复制
发表时间：
2019-01
影响因子：
6.8
通讯作者：
Wenjing Zhang;Ming Li;R. Tandon;Hui Li
中科院分区：
文献类型：
--
作者：
Wenjing Zhang;Ming Li;R. Tandon;Hui Li
本文从跟踪层面考虑了个人用户的位置隐私保护问题，并研究了隐私-效用权衡问题，该问题在基于位置服务的隐私保护中具有重要应用。现有的位置隐私保护机制（Location Privacy Protection Mechanisms, LPPMs）的工作主要集中在保护单个位置，而没有考虑轨迹内位置之间的时间相关性，在考虑整个轨迹时可能导致更高的隐私泄露。然而，到目前为止，还没有一个正式的框架来量化痕迹级别的位置隐私泄露，也没有一个实用的机制来以最优的在线方式释放位置痕迹。在本文中，我们尝试用信息论的方法来解决这个问题。首先，我们提出了一种基于离线环境下原始和释放轨迹之间相互信息的位置轨迹隐私度量，并在给定效用约束的情况下，提出了最小化轨迹级隐私泄漏的最优位置轨迹释放问题。我们还提出了一个隐私度量来捕获在线设置中的跟踪级隐私泄漏。由于直接计算这些度量会导致与跟踪长度相关的指数复杂度，因此我们利用时间位置相关性的马尔可夫结构获得跟踪级隐私泄漏的上界和下界，这些上界和下界是可有效计算的。所提出的上界使我们能够通过修改率失真理论中的Blahut-Arimoto算法来获得有效的在线解（即LPPMs）。然后，我们通过在合成和现实世界的位置数据集上进行广泛的实验，验证了建议的上限和下限以及LPPM的实际泄漏。我们的结果表明，在跟踪级别的隐私效用权衡方面，我们的LPPM优于现有的LPPM，当位置跟踪相关性更强时，这一点更加明显。
We consider the problem of protecting individual user’s location privacy at the trace-level and study the privacy-utility trade-off, which has key applications in privacy-preserving location-based service. Existing works on Location Privacy Protection Mechanisms (LPPMs) have mainly focused on protecting single location, without taking into account the temporal correlations among locations within the trace, which can lead to higher privacy leakage when considering the whole trace. However, to date, there lacks a formal framework to quantify the trace-level location privacy leakage, and a practical mechanism to release location traces in an optimal and online manner. In this paper, we endeavor to solve this problem using an information-theoretic approach. We first propose a location trace privacy metric based on the mutual information between the original and released trace in an offline setting, and formulate the optimal location trace release problem that minimizes trace-level privacy leakage given a utility constraint. We also propose a privacy metric to capture trace-level privacy leakage in an online setting. As directly computing these metrics incur exponential complexity w.r.t. the trace length, we obtain upper and lower bounds on the trace-level privacy leakage by exploiting the Markov structure of the temporal location correlations, which are efficiently computable. The proposed upper bounds enable us to derive efficient online solutions (i.e., LPPMs) by modifying Blahut-Arimoto algorithm in rate-distortion theory. Then we validate the proposed upper and lower bounds and the actual leakage of our LPPM through extensive experiments over both synthetic and real-world location data sets. Our results show the superiority of our LPPM over existing LPPMs in terms of trace-level privacy-utility tradeoff, which is more conspicuous when the location trace is more correlated.