Abstract
Differential Privacy (DP) provides a rigorous framework for data protection, yet users often interact with "black-box" mechanisms where the privacy parameter $\epsilon$ is claimed but not verified. This paper investigates whether a user can estimate $\epsilon$ solely through output sampling. We demonstrate that while general estimation is impossible, it becomes feasible with provable guarantees if the mechanism's noise distribution is Lipschitz continuous. We propose a histogram-based estimation framework and validate its efficacy on standard DP mechanisms.
Introduction
In the real world, Differential Privacy is often implemented as a service where the internal code is opaque to the user. This raises a critical question: can a user verify the service provider's privacy claims? Auditing $\epsilon$ is a "worst-case" problem, requiring the identification of two inputs that produce the most divergent output distributions. If these differences are concentrated in low-probability regions, they may remain undetected by standard sampling, leading to a false sense of security.
The Impossibility of Black-Box Auditing
The authors first prove a fundamental "negative" result: without prior assumptions on the noise distributions, no algorithm can estimate $\epsilon$ with guaranteed precision and confidence. A malicious provider could always hide a privacy leak in a "needle in a haystack" region of the output space. This impossibility result underscores the need for additional constraints on the mechanism's behavior to enable auditing.
The Lipschitz Solution
To make estimation possible, the authors introduce a smoothness constraint: Lipschitz continuity. If the probability density functions of the noise do not change too abruptly, the "needle" cannot be arbitrarily thin, allowing local samples to represent global behavior.
Under this assumption, the authors propose a histogram-based estimator. The output space is partitioned into bins, and the ratios of samples within these bins are used to estimate the divergence between distributions. For Local Differential Privacy (LDP), the input space is also discretized, and the estimator performs exhaustive comparisons across input buckets to find the global maximum divergence.
Experimental Evaluation
The researchers evaluated their estimators using synthetic datasets from two standard DP noise mechanisms: the Truncated Laplace and Truncated Gaussian distributions. These mechanisms were modified to fit within closed intervals to satisfy the requirements of the histogram-based approach.
Key Results
- Practical Efficiency: While the authors provide explicit theoretical bounds on the number of samples ($n$) needed for a given precision and confidence, experiments showed the method is much more efficient in practice. For the Laplace mechanism, the required sample size was roughly 400 times lower than the theoretical worst-case bound.
- Convergence and Precision: In LDP experiments with $\epsilon=1$, the estimator correctly converged to the true value as $n$ increased. The standard deviation of the estimate decreased significantly once the sample size exceeded $10^4$.
Discussion and Insights
- Mandatory Smoothness: The core "aha moment" of the paper is that auditing privacy is impossible without some assumption about the "shape" of the noise. Lipschitzness provides the necessary mathematical bridge.
- Safety Checks: To mitigate the risk of a provider lying about the Lipschitz constant $C$, the authors provide a "safety check" (Theorem 3) that allows users to empirically test if the observed samples are consistent with the claimed constant.
Limitations and Future Work
The primary limitation is the continued reliance on the Lipschitz constant $C$, which still requires a degree of trust or external verification. Additionally, the current mathematical framework assumes closed intervals for both input and output spaces. Future work could extend these methods to infinite domains or high-dimensional data, where the computational cost of exhaustive input discretization becomes a significant challenge.
Summary updated