On the relation between identifiability, differential privacy, and mutual-information privacy

Weina Wang, Lei Ying, Junshan Zhang

Research output: Contribution to journalArticlepeer-review

107 Scopus citations


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 languageEnglish (US)
Article number7498650
Pages (from-to)5018-5029
Number of pages12
JournalIEEE Transactions on Information Theory
Issue number9
StatePublished - Sep 2016


  • Differential privacy
  • Hamming distance
  • identifiability
  • mutual information
  • rate-distortion

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


Dive into the research topics of 'On the relation between identifiability, differential privacy, and mutual-information privacy'. Together they form a unique fingerprint.

Cite this