Q?
WHY $r$?
The author investegate the $l$-privacy within $r$.
[2013-Andres] paper don’t understand “polar mechanism is discretized and truncated?”
Problem Setting
The goal of location with DP is that the chance of users being mapped to one specific obfuscated location from any of the actual locations is similar. The more similar the probability for each region is, the harder it is to infer users’ original positions, leading to better privacy protection.
Development Traces
[2013-Andres] is the first one to propose geo-indistinguishability to protect locations.
However, the protection of geo-indistinguishability is unifrom in space and generate the same amount of noise independently of the real location on the map, i.e., the same protection is applied in a dense city and in a sparse countryside. Also, multiple uses of geo-indistinguishability will result in the disclosure of true locations. Based on these problems, [2015-Konstantinos Chatzikokolakis] try to solve them.
[2017-Jingyu Hua] try to solve the problem that the privacy level decreases quikly when the number of queries increases.
$d_x$-DP is proposed in [2018-Parameswaran Kamalaruban], [2014-Ehab ElSalamouny]
[2013-Andres]:Geo-indistinguishability
A motivating scenario
A user visiting Paris, currently located at a point $x$ close to the Eiffel Tower, and wishing to discover nearby restaurants with good reviews. To achieve this goal, the user can query a service provider (for instance, an LBS server); however, to maintain his privacy, the user does not wish to disclose his exact location. Instead, he can provide some approximate information that still allows him to obtain a useful service, for instance, a randomly chosen point $z$ close to his location.
We fix a circle of radius $r$ centered at the user’s location, and we reason about the user’s level of privacy within this radius.
Definition
Adversary model
informal one
Geo-indistinguishability-I
A mechanism satisfies $\epsilon$ -geoindistinguishability iff for all priors $P_X$ and all observations $S \subseteq Z:$
This definition considers that after observing $S$, the attacker assigns similar probabilities to the user being located in $x$ or $x’$.
the distance is the Euclidean distance between points.
Remarks:
From (17) to (18), we use inequation $e^ {-\epsilon}\le \frac{f(x’|x)}{f(x’|y)} $
Geo-indistinguishability-II
A mechanism satisfies $\epsilon$-geoindistinguishability iff for all priors $P_X$ and all observations $S \subseteq Z:$
Geo-indistinguishability-III
A mechanism satisfies $\epsilon$-geoindistinguishability iff for all observations $S \subseteq Z:$
- This definition requires that points within distance $l$ produce observations with similar probabilities
In above three definition, the privacy level is $l$ while $\epsilon$ can be considered as unit of distance measurement, where $l=\epsilon r$. For example, the user specifies his desired level of privacy, say $l=ln(4)$ within $r=0.2$km, then the $\frac{In(4)}{0.2}$-geo-indistinguishability ensures the user that by revealing his approximate location, the adversary cannot infer his real location with probability 4 times higher than without revealing his location among all locations within 200 meters.
Mechanism for Geo-indistinguishability
- We explore how to define a geoindistinguishable mechanism on the continuous plane.
- we call this function planar laplacian centered in $x_0$
Random point generation
It will be convenient, therefore, to transform the reference system into a system of polar coordinates with origin in $x_0$.
Since $r$ and $\theta$ are independent, so
[2015-Konstantinos Chatzikokolakis] elastic distinguishability metrics
The problem in geo-indistinguishability
[2014-Nicolas]
Geo-indistinguishability with expected inference error
[2014-Reza Shokri][2014-Nicolás E. Bordenabe][2017-Lei Yu]
All these works combine geo-indistinguishability and expected inference error.
Utility Cost
Inference Attack
Reference
[2013-Andres] Geo-indistinguishability: Differential privacy for location-based systems
[2014-Nicolas] Optimal geo-indistinguishable mechanisms for location privacy
[2017-Lei Yu] Dynamic Differential Location Privacy with Personalized Error Bounds
[2014-Reza Shokri] Privacy Games: Optimal User-Centric Data Obfuscation
[2014-Nicolás E. Bordenabe] Optimal geo-indistinguishable mechanisms for location privacy
[2015-Konstantinos Chatzikokolakis] Constructing elastic distinguishability metrics for location privacy
[2017-Jingyu Hua] A Geo-Indistinguishable Location Perturbation Mechanism for Location-Based Services Supporting Frequent Queries
[2018-Parameswaran Kamalaruban] $d_x$ -Private Mechanisms for Linear Queries
[2014-Ehab ElSalamouny] Generalized Differential Privacy: Regions of Priors That Admit Robust Optimal Mechanisms