On the Relation Between Identifiability, Differential Privacy, and Mutual-Information Privacy
Weina Wang, Lei Ying, Junshan Zhang · IEEE Transactions on Information Theory · 2016
This paper investigates the relation between three different notions of privacy: identifiability, differential privacy, and mutual-information privacy. Under a unified privacydistortion 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 ∈i* (D), ∈d*(D), and ∈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 ∈i* (D) and ∈d*(D), and prove that ∈i* (D) - ∈X≤ ∈d*(D) ≤ ∈i* (D) for D within certain range, where ∈Xis 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 ∈i* (D) and ∈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 ∈-differential privacy with ∈d*(D) ≤ ∈ ≤ ∈d*(D)+2∈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.