Optimal Geo-Indistinguishable Mechanisms for Location Privacy

We consider the geo-indistinguishability approach to location privacy, and the trade-off with respect to utility. We show that, given a desired degree ofgeo-indistinguishability, it is possible to construct a mechanism that minimizes the service quality loss, using linear programming techniques. In addition we show that, under certain conditions, such mechanism also provides optimal privacy in the sense of Shokri et al. Furthermore, we propose a method to reduce the number of constraints of the linear program from cubic to quadratic, maintaining the privacy guarantees and without affecting significantly the utility of the generated mechanism. This reduces considerably the time required to solve the linear program, thus enlarging significantly the location sets for which the optimal mechanisms can be computed.

• Publication year

  2014

• Venue

  Conference on Computer and Communications Security

• Publication date

  2014-02-20

• Fields of study

  Computer Science

• Identifiers
  DOI 10.1145/2660267.2660345arXiv 1402.5029
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Hiding in the Mobile Crowd: LocationPrivacy through Collaboration

  2014cited by this paper
• Optimal sporadic location privacy preserving systems in presence of bandwidth constraints

  2013cited by this paper
• Local Differential Perturbations: Location Privacy under Approximate Knowledge Attackers

  2013cited by this paper
• A Predictive Differentially-Private Mechanism for Mobility Traces

  2013cited by this paper
• Broadening the Scope of Differential Privacy Using Metrics

  2013influential reference
• Geo-indistinguishability: differential privacy for location-based systems

  2012influential reference
• Protecting location privacy: optimal strategy against localization attacks

  2012cited by this paper
• Evaluating the Privacy Risk of Location-Based Services

  2011cited by this paper
• Driving with knowledge from the physical world

  2011influential reference
• Differential privacy for location pattern mining

  2011cited by this paper
• Fairness through awareness

  2011cited by this paper
• T-drive: driving directions based on taxi trajectories

  2010influential reference
• Distance makes the types grow stronger: a calculus for differential privacy

  2010cited by this paper
• GeoLife: A Collaborative Social Networking Service among User, Location and Trajectory

  2010influential reference
• Location Diversity: Enhanced Privacy Protection in Location Based Services

  2009cited by this paper
• On the Anonymity of Home/Work Location Pairs

  2009influential reference
• On the Optimal Placement of Mix Zones

  2009cited by this paper
• Privately querying location-based services with SybilQuery

  2009cited by this paper
• Faking contextual data for fun, profit, and privacy

  2009cited by this paper
• Mining interesting locations and travel sequences from GPS trajectories

  2009influential reference
• Understanding mobility based on GPS data

  2008influential reference
• Location privacy in pervasive computing

  2008cited by this paper
• Supporting anonymous location queries in mobile environments with privacygrid

  2008cited by this paper
• Privacy: Theory meets Practice on the Map

  2008cited by this paper
• Preserving privacy in gps traces via uncertainty-aware path cloaking

  2007cited by this paper
• Inference Attacks on Location Tracks

  2007cited by this paper
• Geometric spanner networks

  2007influential reference
• Computing Geometric Minimum-Dilation Graphs is NP-Hard

  2006influential reference
• Calibrating Noise to Sensitivity in Private Data Analysis

  2006cited by this paper
• The new Casper: query processing for location services without compromising privacy

  2006cited by this paper
• Location Privacy in Mobile Systems: A Personalized Anonymization Model

  2005cited by this paper
• Protection of Location Privacy using Dummies for Location-based Services

  2005cited by this paper
• A Formal Model of Obfuscation and Negotiation for Location Privacy

  2005cited by this paper
• Predictive Resource Management for Wearable Computing

  2003cited by this paper
• Handbook of Computational Geometry

  2000cited by this paper
• 2011 IEEE Symposium on Security and Privacy Quantifying Location Privacy

  year unknowncited by this paper

• Context-aware behavioral authentication and privacy preservation in smartphones: Taxonomy and open research issues

  2026cites this paper
• Interpolation-Based Optimization for Enforcing lp-Norm Metric Differential Privacy in Continuous and Fine-Grained Domains

  2026influential citation
• PAnDA: Rethinking Metric Differential Privacy Optimization at Scale with Anchor-Based Approximation

  2025influential citation
• Road Network-Aware and Differentially Private Framework for Location and Location Histogram

  2025cites this paper
• Differentially Private Target Localization Based on DOA Measurements

  2025cites this paper
• GECKO: Securing Digital Assets Through(out) the Physical World (Extended Technical Report)

  2025cites this paper
• Safeguarding Privacy in Real-Time Trajectory Releases for AI-Driven Consumer Applications

  2025cites this paper
• Location privacy protection method based on social network platform

  2025cites this paper
• PrivAR: Real-Time Privacy Protection for Location-Based Augmented Reality Applications

  2025cites this paper
• A Decade of Metric Differential Privacy: Advancements and Applications

  2025influential citation
• Privacy-Enhanced Sparse Mobile Crowdsensing Leveraging Differential Privacy and Distortion Techniques for Secure Data Aggregation

  2025cites this paper
• Differential Privacy in Geotechnical Engineering

  2025cites this paper
• Semantic-Graph-Indistinguishability: A Novel Approach to Location Privacy Protection Under Road Networks

  2025cites this paper
• Semantics-aware location privacy preserving: A differential privacy approach

  2025cites this paper
• DDLP: Dynamic location data publishing with differential privacy in mobile crowdsensing

  2025cites this paper
• Application of a predictive method to protect privacy of mobility data

  2025cites this paper
• A Personalized Secondary Perturbation Mechanism Based on Local Differential Privacy

  2025cites this paper
• Deploying Privacy-Preserving Mechanisms for Financial Applications: A Comprehensive Survey

  2025cites this paper
• A Location-Privacy-Aware Taxi-Hailing System: Adaptive Differential Privacy-Based Dynamic Incentive Method

  2024cites this paper
• Self-Defense: Optimal QIF Solutions and Application to Website Fingerprinting

  2024cites this paper
• Transparent Decisions: Selective Information Disclosure To Generate Synthetic Data

  2024cites this paper
• Metric Differential Privacy at the User-Level via the Earth-Mover's Distance

  2024cites this paper
• Preserving location privacy against inference attacks in indoor positioning system

  2024cites this paper
• Privacy-preserving generation and publication of synthetic trajectory microdata: A comprehensive survey

  2024cites this paper
• Time-Efficient Locally Relevant Geo-Location Privacy Protection

  2024influential citation
• Differentially private de-identifying textual medical document is compliant with challenging NLP analyses: Example of privacy-preserving ICD-10 code association

  2024cites this paper
• Socially-aware and privacy-preserving multi-objective worker recruitment in mobile crowd sensing

  2024cites this paper
• Improving Data Utility in Privacy-Preserving Location Data Collection via Adaptive Grid Partitioning

  2024cites this paper
• Metric geometry of the privacy-utility tradeoff

  2024cites this paper
• Effective Route Recommendation Leveraging Differentially Private Location Data

  2024cites this paper
• Enhancing Scalability of Metric Differential Privacy via Secret Dataset Partitioning and Benders Decomposition

  2024cites this paper
• Event Retrieval from Mobile Devices with Location Anonymization Satisfying Geo-Indistinguishability Using Real Population Data

  2024cites this paper
• Protecting Vehicle Location Privacy with Contextually-Driven Synthetic Location Generation

  2024influential citation
• Differential Privacy for Time Series: A Survey

  2024cites this paper
• A Framework for Tradeoff Between Location Privacy Preservation and Quality of Experience in Location Based Services

  2024cites this paper
• AAA: an Adaptive Mechanism for Locally Differential Private Mean Estimation

  2024cites this paper
• Adapting Geo-Indistinguishability for Privacy-Preserving Collection of Medical Microdata

  2023cites this paper
• Privacy-preserving mobile crowd sensing task assignment with Stackelberg game

  2023cites this paper
• LPP2KL: Online Location Privacy Protection Against Knowing-and-Learning Attacks for LBSs

  2023cites this paper
• Trajectory Data Collection with Local Differential Privacy

  2023cites this paper
• PrSLoc: Sybil attack detection for localization with private observers using differential privacy

  2023cites this paper
• Location Privacy Protection and Location Verification Mechanism of Vehicle in VANET

  2023cites this paper
• An improved dummy generation approach for infeasible regions

  2023cites this paper
• Dynamic Private Task Assignment under Differential Privacy

  2023cites this paper
• Improving unlinkability in C-ITS: a methodology for optimal obfuscation

  2023cites this paper
• Synthesizing Realistic Trajectory Data With Differential Privacy

  2023cites this paper
• Task Allocation Under Geo-Indistinguishability via Group-Based Noise Addition

  2023cites this paper
• DPTP-LICD: A differential privacy trajectory protection method based on latent interest community detection

  2023cites this paper
• Optimal privacy protection of mobility data: a predictive approach

  2023cites this paper
• CORGI: An interactive framework for Customizable and Robust Location Obfuscation

  2023cites this paper
• FastReach: A system for privacy-preserving reachability queries over location data

  2023cites this paper
• Where Have You Been? A Study of Privacy Risk for Point-of-Interest Recommendation

  2023cites this paper
• Collecting Geospatial Data Under Local Differential Privacy With Improving Frequency Estimation

  2023influential citation
• Geo-indistinguishable masking: enhancing privacy protection in spatial point mapping

  2023cites this paper
• Trajectory Privacy Protection with Pricing Awareness on Ride-on-Demand System

  2023cites this paper
• k-Means Clustering with Distance-Based Privacy

  2023cites this paper
• Location Inference under Temporal Correlation

  2023cites this paper
• Universal optimality and robust utility bounds for metric differential privacy

  2022cites this paper
• Utility-aware and Privacy-preserving Trajectory Synthesis Model that Resists Social Relationship Privacy Attacks

  2022cites this paper
• Constructing Mobile Crowdsourced COVID-19 Vulnerability Map With Geo-Indistinguishability

  2022cites this paper
• A Privacy-Preserving Querying Mechanism with High Utility for Electric Vehicles

  2022cites this paper
• Differentially Private Task Allocation Algorithm under Preference Protection

  2022cites this paper
• Privacy-Utility Trades in Crowdsourced Signal Map Obfuscation

  2022cites this paper
• Differentially Private Tripartite Intelligent Matching Against Inference Attacks in Ride-Sharing Services

  2022cites this paper
• Privacy Preserving Task Allocation with Multi-objectives in Edge Computing Enhanced Mobile Crowdsensing

  2022cites this paper
• Privacy-Aware Compression for Federated Learning Through Numerical Mechanism Design

  2022cites this paper
• Privacy-preserving mechanisms for location privacy in mobile crowdsensing: A survey

  2022cites this paper
• Group privacy for personalized federated learning

  2022cites this paper
• A Run a Day Won't Keep the Hacker Away: Inference Attacks on Endpoint Privacy Zones in Fitness Tracking Social Networks

  2022cites this paper
• An Easy-to-use and Robust Approach for the Differentially Private De-Identification of Clinical Textual Documents

  2022cites this paper
• Perturb and optimize users’ location privacy using geo-indistinguishability and location semantics

  2022cites this paper
• A Privacy-Preserving Crowd Flow Prediction Framework Based on Federated Learning during Epidemics

  2022cites this paper
• PRIVIC: A privacy-preserving method for incremental collection of location data

  2022cites this paper
• User Customizable and Robust Geo-Indistinguishability for Location Privacy

  2022cites this paper
• A Trajectory Released Scheme for the Internet of Vehicles Based on Differential Privacy

  2022cites this paper
• Dimension-aware under spatiotemporal constraints: an efficient privacy-preserving framework with peak density clustering

  2022cites this paper
• A K-anonymity Optimization Algorithm Under Attack Model

  2022cites this paper
• Thwarting Longitudinal Location Exposure Attacks in Advertising Ecosystem via Edge Computing

  2022cites this paper
• Balancing utility and scalability in metric differential privacy

  2022influential citation
• RF-protect: privacy against device-free human tracking

  2022cites this paper
• Context Adaptive Personalized Privacy for Location-based Systems

  2022cites this paper
• Privacy of Autonomous Vehicles: Risks, Protection Methods, and Future Directions

  2022cites this paper
• Location Privacy Protection in Vehicle-Based Spatial Crowdsourcing via Geo-Indistinguishability

  2022influential citation
• TACO: A Tree-based Approach to Customizing Location Obfuscation based on User Policies

  2022cites this paper
• SGTP: A Spatiotemporal Generalized Trajectory Publishing Method With Differential Privacy

  2022influential citation
• Three-way optimization of privacy and utility of location data

  2022cites this paper
• Area coverage-based worker recruitment under geo-indistinguishability

  2022cites this paper
• A Survey Of differential privacy-based techniques and their applicability to location-Based services

  2021cites this paper
• A Closer Look: Evaluating Location Privacy Empirically

  2021cites this paper
• Privacy-Preserving Worker Recruitment Under Variety Requirement in Spatial Crowdsourcing

  2021cites this paper
• Data-Driven Transportation Network Company Vehicle Scheduling With Users’ Location Differential Privacy Preservation

  2021cites this paper
• DPIVE: A Regionalized Location Obfuscation Scheme with Personalized Privacy Levels

  2021influential citation
• Designing a Location Trace Anonymization Contest

  2021influential citation
• Optimized Data Sharing with Differential Privacy: A Game-theoretic Approach

  2021cites this paper
• Privacy-Enhancing k-Nearest Neighbors Search over Mobile Social Networks

  2021influential citation
• Moving without association: an association shifting scheme for protecting destination

  2021cites this paper
• Collecting Geospatial Data with Local Differential Privacy for Personalized Services

  2021influential citation
• KLPPS: A k-Anonymous Location Privacy Protection Scheme via Dummies and Stackelberg Game

  2021cites this paper
• Preserving Privacy for Discrete Location Information

  2021cites this paper
• Security Challenges of Location Privacy in VANETs and State-of-the-Art Solutions: A Survey

  2021cites this paper