PaperlayerView exact revision on arXiv

Source-linked AI summary

The Long Road to Computational Location Privacy: A Survey

Primault Vincent, Boutet Antoine, Ben Mokhtar Sonia, Brunie Lionel

arXiv:1810.03568v1cs.CR

TL;DR

Location-based services require users to disclose location, enabling services but exposing mobility data to inference and commercial exploitation. This survey organizes computational location-privacy threats and protections across use cases, algorithmic categories, and evaluation dimensions. It also identifies comparison gaps and open challenges for the field.

  • Problem

    Location disclosure can expose sensitive information, while existing protection mechanisms are numerous and difficult to compare systematically.

  • Method

    The survey reviews threats and LPPMs, organizing mechanisms by online or offline use case and six algorithmic categories, while examining privacy, utility, performance, and architecture.

  • Results

    The survey provides a unified view of online and offline protection mechanisms and reports a lack of standard methods for comparing them.

  • Takeaways & Limitations

    Online and offline mechanisms can use common primitives such as differential privacy while adapting algorithms to their use cases.

Abstract

from arXiv · show

The widespread adoption of continuously connected smartphones and tablets developed the usage of mobile applications, among which many use location to provide geolocated services. These services provide new prospects for users: getting directions to work in the morning, leaving a check-in at a restaurant at noon and checking next day's weather in the evening are possible right from any mobile device embedding a GPS chip. In these location-based applications, the user's location is sent to a server, which uses them to provide contextual and personalised answers. However, nothing prevents the latter from gathering, analysing and possibly sharing the collected information, which opens the door to many privacy threats. Indeed, mobility data can reveal sensitive information about users, among which one's home, work place or even religious and political preferences. For this reason, many privacy-preserving mechanisms have been proposed these last years to enhance location privacy while using geolocated services. This article surveys and organises contributions in this area from classical building blocks to the most recent developments of privacy threats and location privacy-preserving mechanisms. We divide the protection mechanisms between online and offline use cases, and organise them into six categories depending on the nature of their algorithm. Moreover, this article surveys the evaluation metrics used to assess protection mechanisms in terms of privacy, utility and performance. Finally, open challenges and new directions to address the problem of computational location privacy are pointed out and discussed.

I. Introduction

Location-based services rely on users’ disclosed locations to provide contextual services, but retaining and analyzing mobility traces creates privacy risks. The survey organizes computational location-privacy threats, protection mechanisms, use cases, architectures, and evaluation criteria.

  • Mobile devices support location-based services including navigation, weather, venue finding, social games, and crowd-sensing applications.
  • Location disclosure lets services retain users’ mobility traces, from which sensitive places and behavioral information can be inferred.A mobility trace is the sequence of locations associated with one user together with the times of observation.
  • Companies commercially exploit collected mobility data for analysis, profiling, marketing, behavioral targeting, or sharing with external parties.
  • Location privacy protection mechanisms aim to protect users while preserving access to geolocated services, using techniques such as perturbation and encryption.
  • The survey distinguishes real-time, batch, and offline use cases, with protection applied during collection, publication, or both.Real-time services require immediate answers; batch services send data periodically for aggregated results; offline mechanisms protect collected datasets before publication.
  • LPPMs are evaluated through privacy, utility, and performance metrics, reflecting an inherent trade-off between privacy and service quality.
  • The survey organizes LPPMs into six algorithmic categories and reviews attacks, architectures, evaluation, open challenges, and emerging directions.

II. Privacy threats

Location disclosure creates practical privacy threats because mobility data can reveal sensitive facts about users. The survey frames these threats as part of a broader review of attacks and protection mechanisms across multiple use cases.

  • Users may not understand the risks of location disclosure, including inference of whether they are at home and potential exposure to thieves.
  • The survey reviews practical privacy attacks alongside state-of-the-art LPPMs for real-time, batch, and offline protection.

A. Adversary models

The survey models adversaries that access mobility data and examines how mobility traces expose places, relationships, identities, semantics, and future movements. These threats include both direct inference and attacks supported by external data or machine learning.

  • A. Adversary models: Adversaries may be an LBS or a data scientist, often modeled as honest-but-curious entities that exploit received mobility information.
  • A. Adversary models: Adversaries may collude with proxies or other system nodes to learn additional information about users.
  • B. Points of interest & semantics: Points of interest include homes, workplaces, schools, hospitals, religious sites, and political locations, and can be extracted from traces using clustering.
  • C. Social relationships: Mobility traces can reveal social relationships when multiple users repeatedly occupy the same area at the same time.
  • D. Re-identification: Mobility traces can be linked to physical identities through home-address heuristics, white pages, or mobility Markov chains.
  • D. Re-identification: Four spatio-temporal points can almost uniquely identify a user among 1.5 million users, illustrating the high uniqueness of human mobility.
  • D. Re-identification: New re-identification attacks improved re-identification by 17 % over previous state-of-the-art algorithms after accounting for spatio-temporal mismatches.
  • E. Future mobility prediction: Past mobility supports prediction of future locations, with reported accuracy ranging from 50 % to 93 % across prediction settings.

III. Evaluating LPPMs

The survey reviews established privacy models used to evaluate LPPMs, beginning with k-anonymity and extending to ℓ-diversity, t-closeness, and differential privacy. These models provide formal ways to assess protection against identification and disclosure in mobility data.

  • No standard currently exists for evaluating and comparing LPPMs, so the survey reviews quantitative evaluation metrics and classical privacy notions.The survey positions k-anonymity and differential privacy as foundations for subsequent location-privacy work.
  • 1) k-anonymity:: k-anonymity requires each quasi-identifier value sequence to appear at least k times in a dataset.The quasi-identifier is a selected subset of attributes whose repeated combinations reduce unique identification.
  • 1) k-anonymity:: Table I guarantees 2-anonymity because each of its three quasi-identifier triplets occurs in at least two records.The example uses {Birth, Sex, Zip} as the quasi-identifier and Disease as the sensitive attribute.
  • 1) k-anonymity:: k-anonymity can leave records exposed when all members of an anonymity group share the same sensitive value.ℓ-diversity addresses this problem by requiring well-represented sensitive values, while t-closeness also constrains their distribution relative to the full dataset.
  • 2) Differential privacy:: Differential privacy requires aggregate outputs to remain almost unchanged when one dataset element is added or removed, independently of an attacker’s external knowledge.Unlike k-anonymity, its guarantee is defined through the effect of a single-element change on output probabilities.

2) Differential privacy:

Differential privacy protects aggregate analyses by limiting the effect of any one dataset element on query outputs. The survey explains its formal definition, sensitivity, Laplace mechanism, and composition properties.

  • 2) Differential privacy:: Differential privacy compares randomized outputs on datasets differing by at most one element and bounds the probability of outcomes across those datasets.The formal model uses a randomized function K and a privacy parameter ϵ.
  • 2) Differential privacy:: Table II illustrates how differencing two datasets can reveal whether Joe has chronic migraines when the datasets differ only by Joe’s record.The analyst computes Q(D2) − Q(D1) = 3 − 2 = 1, directly exposing Joe’s condition.
  • 2) Differential privacy:: The Laplace mechanism adds random noise whose scale depends on query sensitivity, reducing the direct effect of one record on numerical results.For counting queries, sensitivity is 1 and the mechanism adds noise with scale 1/ϵ.
  • 2) Differential privacy:: Sensitivity depends only on the query function and measures the maximum output change caused by adding or removing one dataset element.For a counting query, ∆Q = 1 because one record changes the count by exactly one.
  • 2) Differential privacy:: Sequential composition combines n independent mechanisms with privacy parameters ϵ1, ..., ϵn into an overall guarantee of (Σiϵi)-differential privacy.This composition accounts for cumulative information leakage under a shared privacy budget.
  • 2) Differential privacy:: The appropriate differential-privacy instantiation at the global or per-user level remains an open question.Recent work addresses this unresolved modeling choice.

B. Privacy metrics

The survey organizes LPPM evaluation around privacy, utility, and performance, using complementary metrics that capture protection, retained analytical value, and computational cost. These dimensions reflect the trade-offs introduced by protecting mobility data.

  • B. Privacy metrics: Privacy evaluation uses formal guarantees, data distortion, and attack correctness metrics.The survey identifies three privacy-metric categories for quantifying LPPM protection.
  • B. Privacy metrics: Formal privacy guarantees include k-anonymity and differential privacy, with location-specific mechanisms often protecting the presence or absence of individual locations.k-anonymity requires at least k users within a time window and area, while differential privacy hides whether a location occurred.
  • B. Privacy metrics: Attack correctness evaluation distinguishes certainty, accuracy, and correctness when measuring adversarial outcomes.Certainty concerns ambiguity, whereas accuracy and correctness account for whether the attacker’s result identifies the right user or location.
  • C. Utility metrics: Utility evaluation measures data distortion and task distortion before and after applying an LPPM.Examples include spatial or temporal imprecision, covered area, data-mining tasks, and analytics queries.
  • D. Performance metrics: Performance evaluation commonly measures execution time, communication overhead, energy overhead, and scalability.Execution time matters especially for real-time services, while energy overhead applies to online LPPMs and scalability depends on workload size or concurrency.
  • C. Utility metrics: A distance-between-locations metric can represent either privacy or utility depending on whether distortion hides locations or harms spatial precision.The interpretation depends on the LBS or downstream task being evaluated.

E. Trade-off between utility and privacy

LPPMs improve privacy by altering mobility data, creating a privacy–utility trade-off that must be configured for each use case. Evaluation also depends strongly on dataset characteristics, while automated parameter selection can help users configure mechanisms.

  • Trade-off between privacy and utility: More information alteration generally reduces the usefulness of protected mobility data, so privacy and utility must be evaluated together.The required balance depends on the application: weather services can use city-level locations, whereas navigation requires street-level precision.
  • Configuration: LPPM parameters can be difficult for end users to understand and configure correctly.Wait for Me uses at least five parameters, while geo-indistinguishability’s ε is expressed in meters^-1 and has an exponential impact.
  • Configuration: Automated approaches such as ALP and PULP select or refine LPPM configurations according to user-defined privacy and utility objectives.ALP iteratively evaluates privacy and utility for online and offline LPPMs, while PULP automatically chooses and configures offline LPPMs.
  • Mobility datasets: Dataset size, sparsity, user population, and collection setting can substantially affect LPPM evaluation results.The survey lists real and synthetic datasets, including taxi, smartphone, social-network, and generated mobility data.
  • Mobility datasets: Synthetic datasets improve scalability testing but may model human mobility and its associated hazards unrealistically.They allow researchers to generate datasets of arbitrary size, including scales that are difficult to obtain from real data.

IV. Architectures of LPPMs

LPPMs use four architectures that determine where protection occurs and which entities participate. Local protection works online and offline, whereas TTP, NTTP, and P2P architectures are limited to online use.

  • Architectures: The survey distinguishes Trusted Third Party, Non-Trusted Third Party, Peer-to-Peer, and Local LPPM architectures.The local architecture supports both online and offline LPPMs; the other three support online LPPMs only.
  • Trusted Third Party: TTP architectures use a trusted proxy server that can access the actual data from all users.The external proxy is therefore an entity with direct access to user data.
  • Non-Trusted Third Party: NTTP architectures split protection between the client and proxy so the proxy need not be trusted, even if malicious or colluding with the LBS.The design aims to prevent the third party from becoming a privacy threat.
  • Peer-to-Peer: P2P architectures avoid an external server by having user devices exchange information through a collaborative privacy protocol.Devices cooperate before sending protected data to the LBS.
  • Local: Local architectures process protection autonomously on the user device or an LBS-operated server without communicating with another party.Any required external databases are expected to be fully available locally.
  • Use cases: The survey distinguishes online protection during collection from offline protection applied to a complete dataset before publication.Online LPPMs protect data on-the-fly or in batches before it reaches the LBS, whereas offline LPPMs protect datasets before release.

A. Mix-zones

Mix-zones protect location privacy by allowing users to change pseudonyms in designated areas, but their effectiveness depends on sufficient participating users and trusted infrastructure. Related generalization approaches use cloaking areas to provide k-anonymity, often with delays or reduced location precision.

  • Mix-zones: Mix-zones originated from mix-network concepts and were refined with formal models, attacker-oriented privacy metrics, and utility-aware placement methods.Mobility models and privacy–utility considerations guide where mix-zones should be placed.
  • Limitations: Mix-zones require a critical mass of users because too few participants are unlikely to meet and change pseudonyms effectively.The survey considers this requirement too demanding for individual users in online settings.
  • Limitations: Mix-zones also require a third party to provide pseudonyms and a trusted party to manage pseudonym swapping.The survey questions the desirability of introducing another trusted party alongside the LBS.
  • Generalization-based mechanisms: Generalization-based methods provide k-anonymity by replacing exact locations with coarser information and forming areas containing at least k users.Spatial cloaking reduces location precision while grouping users into shared cloaking areas.
  • Generalization-based mechanisms: CliqueCloak creates cloaking areas as messages arrive, but insufficient nearby queries can delay or cancel messages.Users specify k, a maximum cloaking-area size, and a maximum transmission delay.
  • Generalization-based mechanisms: Generalization mechanisms include adaptive area enlargement, trajectory grouping and reconstruction, and road-network or grid-based anonymization.These approaches tune spatial or trajectory representations to achieve privacy objectives such as k-anonymity.

2) Offline mechanisms:

Offline mechanisms generalize, synthesize, or inject mobility data to protect released datasets. Their effectiveness and practicality depend on dataset structure, scalability, and the realism of generated traces.

  • Offline mechanisms: Offline generalization methods are well suited to deterministic dataset protection but can reveal information through repeated nondeterministic releases.The survey also identifies scalability problems as dataset size increases.
  • Discussion: Offline generalization can be weakened in online settings by the need for enough users and by outputs that use areas or trajectories instead of GPS coordinates.Such representations may not be directly usable by existing LBSs.
  • Dummies-based mechanisms: Dummies-based mechanisms generate fake users, locations, or trajectories so an attacker cannot identify the user’s actual data exactly.The central challenge is producing realistic fake data that is difficult to distinguish from real data.
  • Dummies-based mechanisms: Fake-trajectory methods generate traces using random endpoints, mobility models, intersections, or preserved trip semantics.SybilQuery preserves properties such as trip length and endpoint-area semantics, while other approaches model individual and aggregate mobility.
  • Offline mechanisms: Offline dummies can provide artificial k-anonymity when no similar user exists, but analysts may see the injected data as an obvious error.Hermes++ injects behaviorally designed dummies into query results and includes auditing mechanisms.

2) Offline mechanisms:

The survey reviews protection mechanisms for collected mobility data, emphasizing attacks on dummy locations, perturbation trade-offs, and privacy-budget challenges.

  • Machine-learning attacks re-identified 93% of users when SybilQuery hid each mobility event among four dummies.The attack used prior mobility data to correlate traces from 85 taxi drivers.
  • Perturbation-based mechanisms must balance privacy from sufficient distortion against utility loss from unusable results.Most mechanisms add random noise to raw data.
  • Geo-indistinguishability bounds the probability of reporting two points for the same real location within a radius, controlled by ε.Lower ε provides higher noise and therefore stronger privacy within the selected area.
  • Location-privacy mechanisms account for temporal correlations through sensitivity measures and hidden Markov models of possible actual locations.These approaches model how successive mobility observations are related over time.
  • Online perturbation mechanisms can operate locally without an external trusted party, but interactive privacy-budget management remains unresolved.The meaning and appropriate value of ε may also be unclear to users, and some mechanisms lack formal guarantees.

3) Discussion:

Protocol-based mechanisms use tailored privacy-preserving protocols and encryption to achieve strong privacy-utility trade-offs, but their specificity, deployment requirements, and computational costs constrain adoption.

  • Privacy protocols support tasks such as proximity checks, aggregate statistics, and nearby-information retrieval without directly exposing all underlying data.Examples include multi-party proximity protocols, encrypted aggregates, and local user collaboration.
  • Protocol-based LPPMs generally provide the best privacy-utility trade-off because they target specific use cases.Their specialization also limits generality and may require replacing existing LBSs.
  • These mechanisms may require new infrastructure because they do not interact with existing LBSs.Replacing established services can slow adoption despite giving designers more freedom.
  • Cryptographic algorithmic complexity can make protocol-based services impractical: outsourced garbled-circuit navigation took about 15 minutes on a 100-vertex road graph.Execution time is affected by the cost of cryptographic primitives.
  • Rule-based mechanisms combine protection methods and use contextual rules to select countermeasures across threats and sensors.ipShield uses a rules engine, while LP-Guardian uses a decision tree with static and user-defined rules.

1) Online mechanisms:

The survey identifies inconsistent evaluation practices and argues for standardized assessment across privacy, utility, and performance while highlighting adaptive and compositional protection strategies.

  • Quantifying location privacy: Heterogeneous metrics make it difficult to fairly evaluate and compare location-privacy protection mechanisms.The survey calls for a common framework using well-defined metrics across privacy, utility, and performance.
  • Quantifying location privacy: Attack-based privacy metrics should complement formal guarantees because guarantees do not always describe practical mechanism behavior.Application-driven utility measures are also needed alongside classical information-theoretic metrics.
  • Towards new protection mechanisms: Differential privacy remains promising, but managing ε in interactive settings remains an open issue.The survey notes continuing interest in differential privacy for geolocated information.
  • Towards new protection mechanisms: Composing heterogeneous LPPMs can cover more use cases, but quantifying the resulting privacy guarantee is challenging.The survey discusses compositions such as combining k-anonymity with l-diversity where l < k.
  • Towards new protection mechanisms: Adaptive mechanisms vary protection levels according to data sensitivity to avoid overprotection and improve utility.The survey suggests incorporating place semantics, such as distinguishing hospital visits from shopping locations.

C. Datasets

The survey finds that real-life mobility datasets are scarce and small, user awareness remains limited, and deployment-ready tools are uncommon despite encouraging privacy-preserving implementations.

  • Public real-life mobility datasets remain small and involve limited numbers of users, restricting evaluation of location-privacy solutions.Platforms and open-data initiatives may help provide larger datasets.
  • Users often lack awareness of the risks and value associated with exploiting mobility data.The survey cites inferences such as whether users are at home from geolocated tweets.
  • Few protection mechanisms are freely downloadable and usable without substantial reimplementation.ipShield is implemented on Android, while geo-indistinguishability has been implemented as a browser extension.
  • Commercial products have implemented privacy-preserving measures, including differential privacy in Apple machine-learning applications and RAPPOR in Chrome.These examples illustrate deployment by large companies rather than broad availability of research mechanisms.
  • The survey presents a unified view of online and offline mechanisms but identifies a lack of standard methods for comparing them.It treats evaluation metrics as first-class elements of the survey.
  • Location privacy still faces technical and social barriers before it can be broadly adopted, despite encouraging theoretical and practical work.The conclusion distinguishes production-quality software from user acceptance.
Loading 1810.03568v1…