Differential Privacy: on the trade-off between Utility and Information Leakage

Mário Alvim 1 Miguel Andrés 1 Konstantinos Chatzikokolakis 1 Pierpaolo Degano 2 Catuscia Palamidessi 1
1 COMETE - Concurrency, Mobility and Transactions
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR7161
Abstract : Differential privacy is a notion of privacy that has become very popular in the database community. Roughly, the idea is that a randomized query mechanism provides sufficient privacy protection if the ratio between the probabilities that two adjacent datasets give the same answer is bound by $e^\epsilon$. In the field of information flow there is a similar concern for controlling information leakage, i.e. limiting the possibility of inferring the secret information from the observables. In recent years, researchers have proposed to quantify the leakage in terms of Rényi min mutual information, a concept strictly related to the Bayes risk. In this paper, we show how to model the query system in terms of an information-theoretic channel, and we compare the notion of differential privacy with that of mutual information. We show that differential privacy implies a bound on the mutual information. Furthermore, we show that our bound is tight. Then, we consider the utility of the randomization mechanism, which represents how close the randomized answers are, in average, to the real ones. We show that the notion of differential privacy implies a bound on utility, also tight, and we propose a method that under certain conditions builds an optimal randomization mechanism, i.e. a mechanism which provides the best utility while guaranteeing differential privacy.
Type de document :
Communication dans un congrès
Gilles Barthe and Anupam Datta and Sandro Etalle. The 8th International Workshop on Formal Aspects of Security & Trust (FAST), Sep 2011, Leuven, Belgium. Springer, 7140, pp.39--54, 2012, Lecture Notes in Computer Science. 〈10.1007/978-3-642-29420-4_3〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00580122
Contributeur : Catuscia Palamidessi <>
Soumis le : vendredi 30 septembre 2011 - 03:47:42
Dernière modification le : mercredi 25 avril 2018 - 10:45:27
Document(s) archivé(s) le : samedi 31 décembre 2011 - 02:22:45

Fichier

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

Identifiants

Collections

Citation

Mário Alvim, Miguel Andrés, Konstantinos Chatzikokolakis, Pierpaolo Degano, Catuscia Palamidessi. Differential Privacy: on the trade-off between Utility and Information Leakage. Gilles Barthe and Anupam Datta and Sandro Etalle. The 8th International Workshop on Formal Aspects of Security & Trust (FAST), Sep 2011, Leuven, Belgium. Springer, 7140, pp.39--54, 2012, Lecture Notes in Computer Science. 〈10.1007/978-3-642-29420-4_3〉. 〈inria-00580122v5〉

Partager

Métriques

Consultations de la notice

456

Téléchargements de fichiers

300