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 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 distortion D, let ε*<sub>i</sub>(D) denote the smallest (best) identifiability level, and ε*<sub>d</sub>(D) the smallest differential privacy level. Then we characterize ε*<sub>i</sub>(D) and ε*<sub>d</sub>(D), and prove that ε*<sub>i</sub>(D) - ε<sub>x</sub> ≤ ε*<sub>d</sub>(D) ≤ ε*<sub>i</sub>(D) for D in some range, where ε<sub>x</sub> is a constant depending on the distribution of the original database X, and diminishes to zero when the distribution of X is uniform. Furthermore, we show that identifiability and mutual-information privacy are consistent in the sense that given a maximum distortion D in some range, there is a mechanism that optimizes the identifiability level and also achieves the best mutual-information privacy.