Online location trace privacy: An information theoretic approach

Wenjing Zhang, Ming Li, Ravi Tandon, Hui Li

Research output: Contribution to journalArticlepeer-review

42 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)235-250
Number of pages16
JournalIEEE Transactions on Information Forensics and Security
Issue number1
StatePublished - Jan 2019


  • Privacy metric
  • information-theoretic privacy
  • location trace privacy
  • rate-distortion theory
  • temporal correlations

ASJC Scopus subject areas

  • Safety, Risk, Reliability and Quality
  • Computer Networks and Communications


Dive into the research topics of 'Online location trace privacy: An information theoretic approach'. Together they form a unique fingerprint.

Cite this