On the relation between Differential Privacy and Quantitative Information Flow

Mário Alvim 1 Miguel Andrés 1 Konstantinos Chatzikokolakis 1 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 that has emerged in the community of statistical databases, as a response to the problem of protecting the privacy of the database's participants when performing statistical queries. The idea is that a randomized query satisfies differential privacy if the likelihood of obtaining a certain answer for a database $x$ is not too different from the likelihood of obtaining the same answer on adjacent databases, i.e. databases which differ from $x$ for only one individual. Information flow is an area of Security concerned with the problem of controlling the leakage of confidential information in programs and protocols. Nowadays, one of the most established approaches to quantify and to reason about leakage is based on the Rényi min entropy version of information theory. In this paper, we analyze critically the notion of differential privacy in light of the conceptual framework provided by the Rényi min information theory. We show that there is a close relation between differential privacy and leakage, due to the graph symmetries induced by the adjacency relation. Furthermore, we consider the utility of the randomized answer, which measures its expected degree of accuracy. We focus on certain kinds of utility functions called ''binary'', which have a close correspondence with the Rényi min mutual information. Again, it turns out that there can be a tight correspondence between differential privacy and utility, depending on the symmetries induced by the adjacency relation and by the query. Depending on these symmetries we can also build an optimal-utility randomization mechanism while preserving the required level of differential privacy. Our main contribution is a study of the kind of structures that can be induced by the adjacency relation and the query, and how to use them to derive bounds on the leakage and achieve the optimal utility.
Type de document :
Communication dans un congrès
Luca Aceto, Monika Henzinger, Jiri Sgall. 38th International Colloquium on Automata, Languages and Programming - ICALP 2011, 2011, Zurich, Switzerland. Springer, 6756, pp.60-76, 2011, Lecture Notes in Computer Science. 〈10.1007/978-3-642-22012-8_4〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00627937
Contributeur : Catuscia Palamidessi <>
Soumis le : vendredi 30 septembre 2011 - 04:46:53
Dernière modification le : jeudi 10 mai 2018 - 02:06:40
Document(s) archivé(s) le : samedi 31 décembre 2011 - 02:22:50

Fichiers

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

Identifiants

Collections

Citation

Mário Alvim, Miguel Andrés, Konstantinos Chatzikokolakis, Catuscia Palamidessi. On the relation between Differential Privacy and Quantitative Information Flow. Luca Aceto, Monika Henzinger, Jiri Sgall. 38th International Colloquium on Automata, Languages and Programming - ICALP 2011, 2011, Zurich, Switzerland. Springer, 6756, pp.60-76, 2011, Lecture Notes in Computer Science. 〈10.1007/978-3-642-22012-8_4〉. 〈inria-00627937〉

Partager

Métriques

Consultations de la notice

494

Téléchargements de fichiers

297