Optimal Geo-Indistinguishable Mechanisms for Location Privacy

Nicolás E. Bordenabe 1, 2 Konstantinos Chatzikokolakis 1, 2 Catuscia Palamidessi 1, 2, 3
1 COMETE - Concurrency, Mobility and Transactions
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France, Polytechnique - X, CNRS - Centre National de la Recherche Scientifique : UMR7161
Abstract : With location-based services becoming increasingly more popular, serious concerns are being raised about the potential privacy breaches that the disclosure of location information may induce. We consider two approaches that have been proposed to limit and control the privacy loss: one is the geo-indistinguishability notion of Andrés et al., which is inspired by differential privacy, and like the latter it is independent from the side knowledge of the adversary, and robust with respect to composition of attacks. The other one is the mechanism of Shokri et al., which offers an optimal trade-off between the loss of quality of service and the privacy protection with respect to a given Bayesian adversary. We show that it is possible to combine the advantages of the two approaches: given a minimum threshold for the degree of geo-indistinguishability, we construct a mechanism that offers the maximal utility, as the solution of a linear program. Thanks to the fact that geo-indistinguishability is insensitive to the remapping of a Bayesian adversary, the mechanism so constructed is optimal also 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 (with respect to the number of locations), maintaining the privacy guarantees without affecting significantly the utility of the generated mechanism. This lowers considerably the time required to solve the linear program, thus enlarging significantly the size of location sets for which the optimal trade-off mechanisms can still be computed.
Type de document :
Communication dans un congrès
Gail-Joon Ahn and Moti Yung and Ninghui Li. CCS - 21st ACM Conference on Computer and Communications Security, Nov 2014, Scottsdale, Arizona, United States. ACM, pp.251-262, 2014, Proceedings of the 21st ACM Conference on Computer and Communications Security. 〈10.1145/2660267.2660345〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00950479
Contributeur : Catuscia Palamidessi <>
Soumis le : dimanche 24 août 2014 - 16:09:57
Dernière modification le : jeudi 9 février 2017 - 15:11:24

Identifiants

Collections

Citation

Nicolás E. Bordenabe, Konstantinos Chatzikokolakis, Catuscia Palamidessi. Optimal Geo-Indistinguishable Mechanisms for Location Privacy. Gail-Joon Ahn and Moti Yung and Ninghui Li. CCS - 21st ACM Conference on Computer and Communications Security, Nov 2014, Scottsdale, Arizona, United States. ACM, pp.251-262, 2014, Proceedings of the 21st ACM Conference on Computer and Communications Security. 〈10.1145/2660267.2660345〉. 〈hal-00950479〉

Partager

Métriques

Consultations de la notice

1123