  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 Hamming distance of the input and output databases, we establish some
fundamental connections between these three privacy notions. Given a distortion
level $D$, define $\epsilon_{\mathrm{i}}^*(D)$ to be the smallest (best)
identifiability level, and $\epsilon_{\mathrm{d}}^*(D)$ to be the smallest
differential privacy level. 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$ in some range, where $\epsilon_X$ 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 distortion
level $D$, the mechanism that optimizes the mutual-information privacy also
minimizes the identifiability level.
