Abstract
This paper investigates the relation between three different notions of privacy: identifiability, differential privacy, and mutual-information privacy. Under a unified privacy-distortion framework, where the distortion is defined to be the expected Hamming distance between the input and output databases, we establish some fundamental connections between these three privacy notions. Given a maximum allowable distortion D , we define the privacy-distortion functions \epsilon mathrm{ i}(D) epsilon d (D), and epsilon m(D) to be the smallest (most private/best) identifiability level, differential privacy level, and mutual information between the input and the output, respectively. We characterize \epsilon mathrm{ i}(D) and \epsilon mathrm{ d}(D),and prove that \epsilon i (D)- X\le epsilon mathrm d(D)\le \epsilon mathrm{ i}(D) for D within certain range, where epsilon X is a constant determined by the prior distribution of the original database X and diminishes to zero when X is uniformly distributed. Furthermore, we show that \epsilon mathrm{ i}}(D) and \epsilon mathrm{ m}(D) can be achieved by the same mechanism for D within certain range, i.e., there is a mechanism that simultaneously minimizes the identifiability level and achieves the best mutual-information privacy. Based on these two connections, we prove that this mutual-information optimal mechanism satisfies \epsilon -differential privacy with \epsilon mathrm{ d}(D)\le \epsilon \le \epsilon mathrm{ d}(D)+2\epsilon {X}. The results in this paper reveal some consistency between two worst case notions of privacy, namely, identifiability and differential privacy, and an average notion of privacy, mutual-information privacy.
Original language | English (US) |
---|---|
Article number | 7498650 |
Pages (from-to) | 5018-5029 |
Number of pages | 12 |
Journal | IEEE Transactions on Information Theory |
Volume | 62 |
Issue number | 9 |
DOIs | |
State | Published - Sep 2016 |
Keywords
- Differential privacy
- Hamming distance
- identifiability
- mutual information
- rate-distortion
ASJC Scopus subject areas
- Information Systems
- Computer Science Applications
- Library and Information Sciences