On the Tradeoff between Privacy and Distortion in Differential Privacy

Weina Wang, Lei Ying, Junshan ZhangarXiv 2014 · arXiv · OpenReview

Abstract

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.

Introduction

In the realm of privacy-preserving data analysis, a fundamental tension exists between protecting individual privacy and maintaining data utility. Adding noise or randomness to a dataset protects individuals but introduces "distortion," reducing the data's usefulness. To navigate this tradeoff, researchers have proposed various mathematical definitions of privacy, most notably Differential Privacy (DP), Identifiability, and Mutual-Information (MI) Privacy.

Conceptual framework relating Differential Privacy, Identifiability, and Mutual-Information Privacy.

These definitions approach privacy from different angles:

  • Differential Privacy: Provides a relative guarantee, bounding the additional information leakage when an individual's data is included.
  • Identifiability: Offers an absolute guarantee, bounding the posterior probability of an adversary recovering the original data.
  • Mutual-Information Privacy: An information-theoretic measure bounding the average amount of information shared between the original and released databases.

This paper bridges these concepts by analyzing them within a unified privacy-distortion framework.

The Privacy-Distortion Framework

The authors define distortion ($D$) as the expected Hamming distance between the input database and the released synthetic database. By treating privacy as a resource to be minimized for a fixed distortion budget, they formulate optimization problems to find the minimum privacy levels ($\epsilon$) achievable for each notion.

To connect these disparate definitions, the research introduces a "Relaxed Privacy-Distortion" (R-PD) problem that serves as a mathematical lower bound for both identifiability and DP. For MI privacy, the problem is framed as a rate-distortion optimization, allowing for a direct comparison with the pairwise constraints of identifiability.

Key Insights and Results

One of the paper's central findings is the tight relationship between identifiability and differential privacy. The gap between the optimal levels for each is bounded by a constant $\epsilon_X$, which represents the maximum prior probability difference between two neighboring databases.

Visualization of the tight bounds between the optimal identifiability level $\epsilon_i^*(D)$ and differential privacy level $\epsilon_d^*(D)$ as a function of distortion $D$.

Key results include:

  1. Exact Identifiability Function: The optimal identifiability level is derived as $\epsilon_i^*(D) = \ln(\frac{n}{D} - 1) + \ln(m - 1)$, where $n$ is the number of rows and $m$ is the domain size.
  2. Tight Bounds for DP: The optimal DP level $\epsilon_d^*(D)$ is shown to satisfy $\epsilon_i^*(D) - \epsilon_X \le \epsilon_d^*(D) \le \epsilon_i^*(D)$. When the data distribution is uniform ($\epsilon_X = 0$), the two notions become mathematically equivalent.
  3. Dual-Optimality: Surprisingly, the mechanism that minimizes identifiability for a given distortion also achieves the absolute minimum mutual information. This proves that local, pairwise constraints can be consistent with global, average measures.

Conclusion and Future Work

This work provides a theoretical foundation for understanding how different privacy metrics relate to one another under utility constraints. While the current framework assumes a known prior distribution and uses Hamming distance as the utility metric, it opens the door for future research into robust privacy mechanisms that handle unknown priors or more complex utility requirements. Future extensions may also integrate membership privacy or group privacy into this unified framework.

Summary updated

Abstract

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.
BibTeX
@misc{wang2014tradeoff,
  author = {Weina Wang and Lei Ying and Junshan Zhang},
  title = {{On the Tradeoff between Privacy and Distortion in Differential Privacy}},
  year = {2014},
  eprint = {1402.3757},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1402.3757},
}

Loading related content...

Figure