Optimal Geo-Indistinguishable Mechanisms for Location Privacy

By Nicolás Emilio Bordenabe, Konstantinos Chatzikokolakis, Catuscia Palamidessi. Conference on Computer and Communications Security, 2014

300 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Science Applications, Sociology and Political Science

View Paper: https://www.semanticscholar.org/paper/1669fd4dff6ac42bb774abbbb13de87398b0d5f1

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Wei Yang
2. Jun Sakuma
3. Hongli Xu
4. Pengzhan Wang
5. Xinyuan Zhang
6. Liusheng Huang
7. Takao Murakami
8. Shaowei Wang

In Computer Science Applications

1. Jun Sakuma
2. Takao Murakami
3. Hideitsu Hino

In Sociology and Political Science

1. Jun Sakuma
2. Takao Murakami
3. Hideitsu Hino
4. Indrė Žliobaitė

Citations in the corpus

• Toward Distribution Estimation under Local Differential Privacy with Small Samples (2018, background): “In the field of location privacy, a privacy metric called geo-indistiguishability [4, 6, 7, 16] is also widely studied.”
• Local Differential Private Data Aggregation for Discrete Distribution Estimation (2019, background): “, [19], [20], [21], [22]) focus on the utility of a single user report (e.”