Generalized differential privacy: regions of priors that admit robust optimal mechanisms

Ehab Elsalamouny 1 Konstantinos Chatzikokolakis 2, 3 Catuscia Palamidessi 2, 4
2 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 : Differential privacy is a notion of privacy that was initially designed for statistical databases, and has been recently extended to a more general class of domains. Both differential privacy and its generalized version can be achieved by adding random noise to the reported data. Thus, privacy is obtained at the cost of reducing the data's accuracy, and therefore their utility. In this paper we consider the problem of identifying optimal mechanisms for gen- eralized differential privacy, i.e. mechanisms that maximize the utility for a given level of privacy. The utility usually depends on a prior distribution of the data, and naturally it would be desirable to design mechanisms that are universally optimal, i.e., optimal for all priors. However it is already known that such mechanisms do not exist in general. We then characterize maximal classes of priors for which a mechanism which is optimal for all the priors of the class does exist. We show that such classes can be defined as convex polytopes in the priors space. As an application, we consider the problem of privacy that arises when using, for instance, location-based services, and we show how to define mechanisms that maximize the quality of service while preserving the desired level of geo- indistinguishability.
Type de document :
Chapitre d'ouvrage
van Breugel, Franck and Kashefi, Elham and Palamidessi, Catuscia and Rutten, Jan. Horizons of the Mind. A Tribute to Prakash Panangaden, 8464, Springer International Publishing, pp.292-318, 2014, Lecture Notes in Computer Science, 978-3-319-06879-4. 〈10.1007/978-3-319-06880-0_16〉
Liste complète des métadonnées

Littérature citée [25 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01006380
Contributeur : Catuscia Palamidessi <>
Soumis le : lundi 16 juin 2014 - 02:47:00
Dernière modification le : jeudi 9 février 2017 - 15:05:56
Document(s) archivé(s) le : mardi 16 septembre 2014 - 10:56:36

Fichier

main.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Ehab Elsalamouny, Konstantinos Chatzikokolakis, Catuscia Palamidessi. Generalized differential privacy: regions of priors that admit robust optimal mechanisms. van Breugel, Franck and Kashefi, Elham and Palamidessi, Catuscia and Rutten, Jan. Horizons of the Mind. A Tribute to Prakash Panangaden, 8464, Springer International Publishing, pp.292-318, 2014, Lecture Notes in Computer Science, 978-3-319-06879-4. 〈10.1007/978-3-319-06880-0_16〉. 〈hal-01006380〉

Partager

Métriques

Consultations de
la notice

594

Téléchargements du document

251