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

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 notion 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 (but not vice-versa). 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.

30 pages; HAL repository

References in corpus (3)

• Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data
• On the relation between Differential Privacy and Quantitative Information Flow
• Differential Privacy versus Quantitative Information Flow

Cited by in corpus (19)

• Differential Privacy as a Mutual Information Constraint
• Understanding Membership Inferences on Well-Generalized Learning Models
• The Users' Perspective on the Privacy-Utility Trade-offs in Health Recommender Systems
• Utilizing Noise Addition for Data Privacy, an Overview
• Minimax Filter: Learning to Preserve Privacy from Inference Attacks
• Robust Privacy-Utility Tradeoffs under Differential Privacy and Hamming Distortion
• On the relation between Differential Privacy and Quantitative Information Flow
• Privacy Impact on Generalized Nash Equilibrium in Peer-to-Peer Electricity Market
• Information-theoretic metrics for Local Differential Privacy protocols
• Neither Private Nor Fair: Impact of Data Imbalance on Utility and Fairness in Differential Privacy
• Uncertainty-Autoencoder-Based Privacy and Utility Preserving Data Type Conscious Transformation
• VAMS: Verifiable Auditing of Access to Confidential Data
• Task-aware Privacy Preservation for Multi-dimensional Data
• Quantifying Membership Privacy via Information Leakage
• On Generalized Metric Spaces for the Simply Typed Lambda-Calculus (Extended Version)
• Generalised Entropies and Metric-Invariant Optimal Countermeasures for Information Leakage under Symmetric Constraints
• Achieving Transparency Report Privacy in Linear Time
• Corella: A Private Multi Server Learning Approach based on Correlated Queries
• A Graph Symmetrisation Bound on Channel Information Leakage under Blowfish Privacy