On the Relation Between Identifiability, Differential Privacy, and Mutual-Information Privacy.

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 _{\mathrm{ d}}^{*}(D) , and \epsilon \mathrm{ 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 \mathrm{ i}^{*}(D)-\epsilon 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 . 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. [ABSTRACT FROM PUBLISHER]