Within-Dataset Disclosure Risk for Differential Privacy

Zhi-ru Zhu, Raul Castro FernandezarXiv 2023 · DOI · arXiv

TL;DR

This paper introduces the Relative Disclosure Risk Indicator (RDR), a new metric that helps data controllers understand how choosing a specific privacy parameter ($\epsilon$) affects the actual individuals in their dataset. By moving from abstract global bounds to concrete, data-dependent risk distributions, the authors provide a framework to automatically derive $\epsilon$ values that align with a controller's specific privacy preferences.

What Problem Does This Paper Address?

In Differential Privacy (DP), the parameter $\epsilon$ (epsilon) acts as a "privacy knob." A smaller $\epsilon$ means more noise and better privacy, while a larger $\epsilon$ means less noise and better data utility. However, for practitioners, picking the "right" $\epsilon$ is notoriously difficult.

The core issue is that $\epsilon$ is a global, worst-case mathematical bound. It tells you the maximum risk for any possible individual in any possible dataset. It doesn't tell a data controller how much risk is actually being incurred by the specific people in their current dataset. Without this context, controllers often pick $\epsilon$ values arbitrarily. This paper aims to bridge the gap between abstract theory and practical decision-making by providing a "within-dataset" measure of risk.

Methods

The authors propose a three-part solution:

  1. The RDR Metric: Derived from "ex-post per-instance privacy loss," the RDR quantifies the relative risk of a specific individual compared to others in the same dataset for a given query. Intuitively, it combines the per-instance sensitivity (how much one person's data changes the query result) with the noise scale of the DP mechanism (Laplace or Gaussian).
  2. Preference-Based Epsilon Selection: Instead of picking $\epsilon$ directly, a controller defines a preference function based on RDRs. For example, a controller might specify that the most at-risk person should not have a risk score more than 10% higher than the least at-risk person. The Find-ε-from-RDR algorithm then finds the largest (most useful) $\epsilon$ that satisfies this rule.
  3. Private Epsilon Release: Since RDR is calculated using raw data, the chosen $\epsilon$ itself could leak information. The authors introduce Find-and-release-ε-from-RDR, which uses the Sparse Vector Technique (SVT) to select and release $\epsilon$ while maintaining formal DP guarantees.
  4. Privacy Odometer: To handle multiple queries, they use a "privacy odometer" that tracks cumulative privacy loss, allowing the system to dynamically allow or deny queries without requiring a pre-set total budget.

Datasets

The authors evaluated their approach using:

  • UCI Adult Dataset: A standard benchmark containing census data (48,842 records).
  • Synthetic Scaling: They replicated and added noise to the Adult dataset to create versions with up to 1 million records to test the scalability of their algorithms.

Key Insights and Ideas

  • Risk is not distributed equally: In many datasets, a few "outlier" individuals are much more distinguishable than others. RDR makes this visible, allowing controllers to decide if they want to protect the "most vulnerable" or ensure a "tight distribution" of risk.
  • Interpretability through Comparison: A single RDR value is meaningless on its own. Its power comes from comparing it to other RDRs in the same dataset. This "relative" view is much more intuitive for humans than absolute probability bounds.
  • Visualizations Matter: The user study found that simple range plots (showing min-to-max risk) led to more consistent decision-making than complex histograms. Sometimes, less information is more effective for human controllers.

Key Results

  • User Study: In an IRB-approved study with 56 participants, those shown RDR information made significantly more consistent choices for $\epsilon$ compared to a control group. 100% of the treatment group reported using the RDR values to make their decisions.
  • Efficiency: The algorithms are highly practical. Even with 1 million records, the system could derive and release a private $\epsilon$ in under 5 minutes. The runtime scales linearly with the number of records.
  • Sensitivity to Policy: Ablation studies showed that the algorithms correctly respond to stricter privacy preferences (e.g., requiring a smaller gap between the most and least at-risk individuals) by choosing smaller $\epsilon$ values.

Limitations and Future Work

  • Relative vs. Absolute: RDR is a relative indicator. While it helps with "fairness" and "distribution" of risk, it doesn't provide an absolute probability of a successful re-identification attack (though it can complement absolute measures like those proposed by Lee & Clifton).
  • Analyst Utility: The current framework focuses heavily on the controller's privacy needs. The authors suggest that future work could better incorporate analyst preferences (e.g., priority scores for specific queries) to balance the privacy-utility tradeoff more effectively.
  • Complex Queries: The evaluation focused on standard SQL-style queries (COUNT, AVG, SUM). Applying RDR to more complex machine learning models remains an open area for exploration.

Summary updated

Abstract

Differential privacy (DP) enables private data analysis. In a typical DP deployment, controllers manage individuals' sensitive data and are responsible for answering analysts' queries while protecting individuals' privacy. They do so by choosing the privacy parameter $ε$, which controls the degree of privacy for all individuals in all possible datasets. However, it is challenging for controllers to choose $ε$ because of the difficulty of interpreting the privacy implications of such a choice on the within-dataset individuals. To address this challenge, we first derive a relative disclosure risk indicator (RDR) that indicates the impact of choosing $ε$ on the within-dataset individuals' disclosure risk. We then design an algorithm to find $ε$ based on controllers' privacy preferences expressed as a function of the within-dataset individuals' RDRs, and an alternative algorithm that finds and releases $ε$ while satisfying DP. Lastly, we propose a solution that bounds the total privacy leakage when using the algorithm to answer multiple queries without requiring controllers to set the total privacy budget. We evaluate our contributions through an IRB-approved user study that shows the RDR is useful for helping controllers choose $ε$, and experimental evaluations showing our algorithms are efficient and scalable.
BibTeX
@misc{zhu2023within,
  author = {Zhi-ru Zhu and Raul Castro Fernandez},
  title = {{Within-Dataset Disclosure Risk for Differential Privacy}},
  year = {2023},
  eprint = {2310.13104},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2310.13104},
}
Figure