PAC Privacy: Automatic Privacy Measurement and Control of Data Processing

Hanshen Xiao, Srinivas Devadas

TL;DR

This paper introduces "PAC Privacy," a novel information-theoretic privacy definition that quantifies the hardness of inferring sensitive data from processed outputs, focusing on instance-based impossibility rather than worst-case adversarial scenarios. They propose an automatic framework for privacy analysis and control, enabling high-confidence privacy guarantees for black-box data processing mechanisms through simulation.

What Problem Does This Paper Address?

Existing privacy definitions, like Differential Privacy (DP), often rely on worst-case adversarial scenarios and input-independent guarantees. While strong, these definitions can be overly conservative, leading to significant utility compromises, especially in complex data processing tasks like deep learning. Furthermore, analytically proving privacy guarantees for these mechanisms is often computationally intractable (e.g., NP-hard sensitivity calculations). The authors identify a need for a more flexible, instance-based privacy metric that can be automatically analyzed and controlled, bridging the gap between theoretical guarantees and practical utility. They aim to quantify reconstruction hardness by considering the adversary's actual inference capabilities based on data priors and specific inference objectives.

Methods

The core of the paper is the introduction of PAC Privacy, defined by $(\delta, \rho, D)$-PAC Privacy. This definition quantifies the impossibility of an adversary successfully reconstructing sensitive data $X$ with probability at least $1-\delta$, given the processed output $M(X)$ and a measure function $\rho$ that defines the success criterion for reconstruction. This is framed as a game between a user and an adversary.

Key techniques include:

  • Instance-based analysis: Unlike worst-case definitions, PAC Privacy considers specific data distributions and inference tasks.
  • Automatic Security Proof: The authors propose a framework that uses Monte-Carlo simulations to estimate mutual information (MI) between the input and output of a mechanism. This estimation allows for automatic determination of necessary perturbations (e.g., adding Gaussian noise) to achieve desired PAC Privacy guarantees, without requiring algorithmic analysis of the mechanism itself.
  • f-Divergence and Mutual Information: The framework leverages f-divergence to quantify the "PAC Advantage Privacy" ($\Delta_{fd}$), which measures the increase in an adversary's success probability. Mutual Information (MI) is used as a key quantity to bound this advantage, particularly through the KL-divergence.
  • Perturbation Algorithms: Algorithms are presented to automatically determine the parameters of Gaussian noise to add to the mechanism's output to control the mutual information and thus ensure PAC Privacy. These algorithms handle both deterministic and randomized mechanisms.

Datasets

Not explicitly discussed in the paper as new benchmarks. However, the authors mention using the "Hospital dataset from Mathworks Sample 2" and the "CIFAR10 dataset" for examples and demonstrations of their framework.

Key Insights and Ideas

  • Instance-based privacy is more practical: By focusing on specific data distributions and inference tasks, PAC Privacy can offer stronger utility guarantees than worst-case definitions for practical scenarios.
  • Automatic analysis is feasible: The proposed simulation-based approach bypasses the need for complex analytical proofs, making privacy analysis accessible for black-box mechanisms.
  • Mutual Information as a privacy metric: MI effectively captures the instance-based information leakage, and controlling it is key to achieving PAC Privacy.
  • Anisotropic noise for better utility: Unlike DP's isotropic noise, PAC Privacy can utilize anisotropic noise (tailored to the data's geometry) to achieve better utility-privacy tradeoffs.
  • Compositionality: PAC Privacy allows for straightforward composition of privacy losses, even with correlated randomness, which is a significant advantage over DP in certain scenarios.

Key Results

  • PAC Privacy Definition: A formal definition of PAC Privacy and its variants (e.g., PAC Membership Privacy, PAC Individual Privacy) are introduced.
  • Automatic Analysis Framework: A simulation-based framework is proposed to automatically determine privacy parameters and necessary perturbations.
  • Perturbation Algorithms: Algorithms are developed to automatically compute Gaussian noise parameters to achieve desired mutual information bounds. For instance, Theorem 4 provides a tradeoff between noise, sampling complexity, and confidence for deterministic mechanisms.
  • Utility Gains: Examples demonstrate that PAC Privacy can require significantly less noise (and thus preserve more utility) compared to adversarial worst-case guarantees, especially in high-dimensional settings. For example, in a private machine learning scenario, the required Gaussian noise was substantially smaller for PAC Privacy than for adversarial worst-case analysis.
  • Composition Bounds: PAC Privacy offers simple composition bounds, even for correlated randomness, which is a notable improvement over DP in such cases.

Limitations and Future Work

  • Simulation Requirement: The automatic analysis relies on simulations, which can be computationally intensive for complex mechanisms or large datasets.
  • Lack of Prior Knowledge: The current framework does not fully quantify inference hardness when the adversary has limited prior knowledge about the data distribution.
  • Optimal Perturbation: While the proposed algorithms provide conservative bounds, finding the truly optimal perturbation remains an open challenge. The gap between proposed and optimal perturbation can be asymptotically large in some cases.
  • Generalization of Algorithms: Extending the composition analysis of Algorithm 1 (for deterministic mechanisms) to handle correlated randomness is left as an open problem.
  • Arbitrary Noise Distributions: Theorem 9 provides a lower bound for Gaussian noise mechanisms; a generic lower bound for arbitrary noise distributions is also an open problem.

Summary updated

BibTeX
@inproceedings{xiao2023pac,
  author = {Hanshen Xiao and Srinivas Devadas},
  title = {{PAC Privacy: Automatic Privacy Measurement and Control of Data Processing}},
  booktitle = {CRYPTO},
  year = {2023},
  doi = {10.1007/978-3-031-38545-2\_20},
}
Figure