Worst- and Average-Case Privacy Breaches in Randomization Mechanisms

Abstract : In a variety of contexts, randomization is regarded as an effective technique to conceal sensitive information. We model randomization mechanisms as information-theoretic channels. Our starting point is a semantic notion of security that expresses absence of any privacy breach above a given level of seriousness ε, irrespective of any background information, represented as a prior probability on the secret inputs. We first examine this notion according to two dimensions: worst vs. average case, single vs. repeated observations. In each case, we characterize the security level achievable by a mechanism in a simple fashion that only depends on the channel matrix, and specifically on certain measures of “distance” between its rows, like norm-1 distance and Chernoff Information. We next clarify the relation between our worst-case security notion and differential privacy (dp): we show that, while the former is in general stronger, the two coincide if one confines to background information that can be factorised into the product of independent priors over individuals. We finally turn our attention to expected utility, in the sense of Ghosh et al., in the case of repeated independent observations. We characterize the exponential growth rate of any reasonable utility function. In the particular case the mechanism provides ε-dp, we study the relation of the utility rate with ε: we offer either exact expressions or upper-bounds for utility rate that apply to practically interesting cases, such as the (truncated) geometric mechanism.
Type de document :
Communication dans un congrès
Jos C. M. Baeten; Tom Ball; Frank S. Boer. 7th International Conference on Theoretical Computer Science (TCS), Sep 2012, Amsterdam, Netherlands. Springer, Lecture Notes in Computer Science, LNCS-7604, pp.72-86, 2012, Theoretical Computer Science. 〈10.1007/978-3-642-33475-7_6〉
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-01556211
Contributeur : Hal Ifip <>
Soumis le : mardi 4 juillet 2017 - 17:45:36
Dernière modification le : mardi 4 juillet 2017 - 17:47:02
Document(s) archivé(s) le : vendredi 15 décembre 2017 - 02:29:25

Fichier

978-3-642-33475-7_6_Chapter.pd...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Michele Boreale, Michela Paolini. Worst- and Average-Case Privacy Breaches in Randomization Mechanisms. Jos C. M. Baeten; Tom Ball; Frank S. Boer. 7th International Conference on Theoretical Computer Science (TCS), Sep 2012, Amsterdam, Netherlands. Springer, Lecture Notes in Computer Science, LNCS-7604, pp.72-86, 2012, Theoretical Computer Science. 〈10.1007/978-3-642-33475-7_6〉. 〈hal-01556211〉

Partager

Métriques

Consultations de la notice

224

Téléchargements de fichiers

29