Eureka: A General Framework for Black-box Differential Privacy Estimators

Eureka: A General Framework for Black-box Differential Privacy Estimators

Speakers: Yun Lu, PhD Student, Purdue University; Malik Magdon-Ismail, Professor, Rensselaer Polytechnic Institute; Yu Wei, Professor, University of Victoria; Vassilis Zikas, Professor, Purdue University

Conference: IEEE S&P

YouTube: https://www.youtube.com/watch?v=u-yhtQaKVEs

Overview

In the realm of data privacy, ensuring that algorithms do not inadvertently leak sensitive information is paramount. This talk introduces "Eureka," a novel and general framework designed for black-box differential privacy (DP) estimators. Presented by Yun Lu, a PhD student at Purdue University, alongside collaborators Malik Magdon-Ismail, Yu Wei, and his advisor Vassilis Zikas, the work addresses a critical gap: enabling domain experts without specialized privacy knowledge to empirically assess the privacy guarantees of their own machine learning mechanisms.

The core motivation stems from a common scenario: a domain expert develops a machine learning algorithm or mechanism that incorporates randomization techniques, perhaps even explicitly adding noise for efficiency or a nascent attempt at privacy. However, quantifying the formal privacy guarantees, especially under the rigorous framework of differential privacy, remains a significant challenge. Eureka provides an efficient, black-box solution that requires minimal assumptions about the mechanism, offering a tight estimate of its privacy spectrum. This capability is crucial for validating privacy claims, comparing different privacy-preserving mechanisms, and ultimately fostering the broader adoption of differential privacy by making its assessment more accessible.

Background

▶ Watch: Introduction: Black-box privacy estimation problem (0:00)

The foundation of this work lies in Differential Privacy (DP), a robust mathematical definition of privacy for algorithms that operate on datasets. Intuitively, a mechanism satisfies (ε, δ)-DP if, for any two "neighboring" input datasets (differing by a single record), the probability distributions of their outputs are "epsilon-delta close." This formal closeness is captured by an inequality stating that for any output, the ratio of probabilities under the two neighboring datasets is bounded by e^ε and an additive δ probability. DP provides a strong guarantee of deniability, meaning an adversary cannot reliably infer whether an individual's data was included in the input dataset.

While DP is powerful, its practical application and verification can be complex. Domain experts often design algorithms that inherently introduce randomness (e.g., in sampling, optimization, or noise addition) but lack the expertise to formally prove or quantify their DP guarantees. This is where the need for empirical estimation arises. The talk introduces the concept of a Privacy Spectrum, which aims to capture all the "most interesting and incomparable" (ε, δ) pairs that a mechanism satisfies. Rather than just a single (ε, δ) pair, the Privacy Spectrum is conceptualized as a function Δ(ε), representing the smallest δ achievable for a given ε. For instance, the talk illustrates the Privacy Spectrum for common DP mechanisms like Gaussian and Laplacian noise, showing how their Δ(ε) curves differ, with Laplacian often achieving pure DP (δ=0) for certain ε values, while Gaussian mechanisms typically offer better δ for a wider range of ε.

The problem statement for Eureka is clear: given a mechanism M, develop an efficient algorithm A that outputs a good, tight estimate of M's Privacy Spectrum. "Efficient" here means polynomial time. The desired properties for such an algorithm are critical:

1. Black-box access only: The algorithm should only interact with M by providing inputs and observing outputs, without needing internal details. This allows non-privacy experts to use it.
2. Minimal assumptions: Ideally, no assumptions are made about M. However, this is practically impossible. Eureka assumes the mechanism's output distribution has a density, a common and minimal assumption in this line of work.
3. Tight estimate: The estimate should be α-close to the true value with high probability, where α captures the difference.

A significant challenge arises from the definition of DP itself: it considers all neighboring input pairs. For many mechanisms, there can be an infinite number of such pairs, making a truly tight estimate impossible in practice. To circumvent this, the authors propose Relative DP. Instead of considering all neighboring inputs in the mechanism's domain, Relative DP focuses on a chosen set T of neighboring inputs. This relaxation reflects real-world scenarios where an expert might only have a few specific datasets and wants to estimate privacy for those. Crucially, Relative DP does not weaken the privacy guarantees; it still provides global deniability for records within the "record universe" defined by T. The goal then becomes to provide a tight estimate of the Relative DP Spectrum.

This approach distinguishes Eureka from existing work, particularly DP auditing. DP auditing algorithms typically provide only a lower bound on privacy. While useful for identifying faulty implementations or disproving exaggerated privacy claims (e.g., "this mechanism claims (1, 10^-10)-DP, but we found it's at least (1, 1)-DP"), they don't answer "how private is it actually?" Eureka, by aiming for a tight estimate of the Relative DP Spectrum, provides a more comprehensive and actionable assessment of privacy.

Key Findings

▶ Watch: Privacy Spectrum: Gaussian vs. Laplacian comparison (3:54)

The central contribution of the Eureka framework is its innovative approach to estimating differential privacy by reducing the complex problem of privacy quantification to a more tractable binary classification problem. This reduction forms the bedrock of a general framework that can leverage existing machine learning techniques to provide tight estimates of a mechanism's Relative DP Spectrum.

The key findings can be summarized as follows:

1. Reduction to Binary Classification: The most profound insight is the discovery of a formal link between computing the indistinguishability spectrum (which quantifies how difficult it is to distinguish between the outputs of a mechanism on a specific pair of neighboring inputs, M(d) and M(d')) and solving a carefully designed binary classification problem. Specifically, the algorithm that optimally computes this indistinguishability spectrum is also the optimal Bayes classifier for a particular binary classification task.
2. The Indistinguishability Spectrum: The authors define Δ_M(d, d') as the indistinguishability spectrum for a pair of distributions M(d) and M(d'). The overall Relative DP Spectrum is then the maximum of these Δ_M(d, d') over all chosen neighboring input pairs.
3. General Framework for Estimators: Eureka provides a general framework that can convert any binary classifier into a privacy estimator. This means that advances in classification algorithms can be directly applied to improve privacy estimation.
4. Tight Estimates vs. Lower Bounds: Unlike traditional DP auditing methods that only provide lower bounds on privacy (useful for finding bugs but not for precise quantification), Eureka's approach, when coupled with "good universal classifiers," yields tight estimates of the Relative DP Spectrum. This allows for a more accurate understanding of "how private" a mechanism truly is.
5. Empirical Validation: The framework has been empirically validated across various scenarios. It successfully provides estimates that tightly match analytical results for fundamental DP building blocks like the Laplacian mechanism and Gaussian mechanism. Furthermore, it has been applied to more complex machine learning tasks, such as random projection and the approximately square algorithm, demonstrating its versatility and accuracy in practical settings. The framework also successfully performs standard DP auditing tasks, proving its utility in detecting privacy violations.

These findings collectively offer a powerful, accessible tool for assessing differential privacy, lowering the barrier for non-experts and enabling more rigorous validation of privacy-preserving systems.

Technical Deep Dive

▶ Watch: Formal problem statement and desired algorithm properties (5:00)

The core of Eureka's technical innovation lies in its elegant reduction of the privacy estimation problem to a binary classification problem. This section delves into the mathematical underpinnings and the framework's construction.

Recall that the Relative DP Spectrum Δ(ε) for a mechanism M and a chosen set of neighboring datasets T is defined as:

Δ(ε) = max_{ (d, d') ∈ T } { Δ_M(d, d') }

where Δ_M(d, d') is the indistinguishability spectrum for a specific pair of neighboring datasets d and d'. The indistinguishability spectrum Δ_M(d, d') is itself defined by an expression derived from the (ε, δ)-DP inequality, focusing on the maximum probability difference between M(d) and M(d') for any measurable set of outputs. The authors break down Δ_M(d, d') into two parts: an inner component capturing the indistinguishability between the output distributions of M(d) and M(d'), and an outer maximization over all (d, d') pairs in T.

The main observation, which forms the basis of the Eureka framework, is that the problem of computing Δ_M(d, d') for any given pair of distributions M(d) and M(d') is equivalent to solving a specific binary classification problem. Let's denote the output distribution of M(d) as X and M(d') as Y. The carefully designed binary classification problem, denoted P, works as follows:

1. Distribution Selection: Uniformly at random, select one of two distributions.
2. Sampling: Sample a point (output) according to the chosen distribution.
3. Label Prediction: Predict which of the two distributions the point originated from.

More specifically, the distributions involved are not just X and Y, but a constructed mixture distribution X[ε] and Y. The distribution X[ε] is defined as a mixture of X and Y: with probability 1 - e^(-ε), it samples from X; and with probability e^(-ε), it samples from Y. The problem P then asks a classifier to distinguish between samples drawn from X[ε] and Y.

The talk outlines a three-step proof to establish this crucial link:

1. Indistinguishability Δ_M(d, d') is equivalent to the statistical distance between two random variables: The authors show that the expression for Δ_M(d, d') can be directly related to the statistical distance (also known as total variation distance) between the constructed random variable X[ε] and Y. The statistical distance between two probability distributions P and Q is defined as 1/2 * ∫ |p(x) - q(x)| dx, where p(x) and q(x) are their probability density functions. By carefully constructing X[ε] as a mixture distribution, they demonstrate that Δ_M(d, d') can be expressed in terms of the statistical distance D_TV(X[ε], Y).
2. Statistical distance is equivalent to the risk of the optimal Bayes classifier: This step leverages a known result in statistical decision theory. For any two distributions P and Q, the statistical distance D_TV(P, Q) is directly related to the risk (error rate) of the optimal Bayes classifier designed to distinguish between samples drawn from P and Q. The optimal Bayes classifier H* minimizes the probability of misclassification.
3. Putting it all together: By combining these two equivalences, the authors conclude that computing the indistinguishability spectrum Δ_M(d, d') is equivalent to computing the risk of the optimal Bayes classifier H* for the specific binary classification problem P designed to distinguish X[ε] from Y.

This mathematical link is the cornerstone of Eureka. It means that if we can build a good binary classifier for problem P, we can use its performance (specifically, its risk) to estimate the indistinguishability spectrum.

The Eureka framework then proceeds as follows:

• From Classifiers to Estimators: Any binary classifier can be used to estimate Δ_M(d, d'). Even a "not-so-good" classifier will provide a lower bound for the privacy spectrum, which is still useful for DP auditing.
• Achieving Tight Estimates: The key to obtaining tight estimates (i.e., α-close to the true value) lies in using good universal classifiers. These are classifiers whose risk provably converges to the risk of the optimal Bayes classifier as the amount of training data increases. If a classifier's risk approaches that of H*, then the resulting privacy estimator will provide a tight bound.
• Framework Operation: At a high level, for every neighboring input pair (d, d') in the chosen set T, the framework uses the established link to train a binary classifier that distinguishes M(d) outputs from M(d') outputs (or rather, X[ε] from Y). The risk of this classifier is then used to estimate Δ_M(d, d'). Finally, the maximum of these estimated Δ_M(d, d') values over all pairs in T gives the estimate for the Relative DP Spectrum.

The talk mentions that they construct an instantiation of their framework using a K-classifier (likely referring to k-Nearest Neighbors or a similar non-parametric method) and demonstrate that it satisfies all the desired properties: black-box access, minimal assumptions, and providing tight estimates. Further details on this specific instantiation and its formal proofs are available in their full paper.

Demo / Proof of Concept

▶ Watch: Summary of Eureka's black-box estimation approach (8:00)

While the talk did not feature a live, interactive demo in the traditional sense, it presented compelling empirical evaluations that serve as a robust proof of concept for the Eureka framework. The speakers emphasized that their estimators generate empirical results that tightly match analytical privacy claims, a critical validation point for any estimation framework.

The evaluation process involved testing Eureka on a range of well-understood differential privacy mechanisms and more complex machine learning tasks:

1. Fundamental DP Mechanisms:

• Laplacian mechanism: A cornerstone of DP, often used for adding noise to numerical query answers to achieve pure DP (δ=0). Eureka's estimates for its privacy spectrum were shown to align closely with theoretical predictions.
• Gaussian mechanism: Another fundamental DP technique, typically used when outputs are aggregated or when δ > 0 is acceptable. The empirical estimates for the Gaussian mechanism's privacy spectrum also demonstrated strong congruence with its analytical counterparts.

1. Complex Machine Learning Tasks:

• Random projection: A dimensionality reduction technique that can be made differentially private.
• Approximately square algorithm: This likely refers to a privacy-preserving variant of a machine learning algorithm, though specific details were not elaborated in the transcript.

For all these test cases, the empirical estimates generated by Eureka consistently tally matched the logical or analytical results. This consistency across diverse mechanisms, from basic noise addition to more intricate machine learning algorithms, underscores the framework's accuracy and general applicability.

Furthermore, the evaluation confirmed that Eureka can effectively be used for DP auditing tasks. It was shown to "pass the standard test using the DP auditing settings," implying that it can correctly identify instances where a mechanism's claimed privacy guarantees are not met, or at least provide a reliable lower bound on privacy in such scenarios. This dual capability—providing both tight estimates for quantification and lower bounds for auditing—highlights the framework's versatility and practical utility for both privacy developers and auditors.

Defensive Implications

▶ Watch: Eureka's advantages over traditional DP auditing (9:00)

The Eureka framework offers significant defensive implications for various stakeholders involved in developing, deploying, and auditing privacy-preserving systems. By providing a practical, black-box method for estimating differential privacy, it addresses several critical needs:

1. Empowering Domain Experts and Data Scientists: For individuals who are experts in their respective domains (e.g., machine learning, statistics) but lack deep theoretical knowledge of differential privacy, Eureka acts as a powerful verification tool. They can now empirically assess the privacy level of their algorithms, even if those algorithms incorporate randomization for efficiency or other purposes. This lowers the barrier to entry for DP adoption, allowing experts to confidently claim and understand the privacy guarantees of their work without needing to be privacy theoreticians. They can use Eureka to compare different private mechanisms, tune parameters (e.g., noise scales), and choose the best (ε, δ) trade-off for their specific application.

1. Robust Validation for Privacy-Preserving Systems: Developers building privacy-preserving systems can use Eureka to validate that their implementations indeed achieve the intended DP guarantees. Theoretical proofs of DP can be complex and prone to implementation errors. Eureka provides an empirical check, ensuring that the actual privacy properties of the deployed code align with the designed properties. This is crucial for maintaining trust and preventing accidental privacy leaks.

1. Enhanced DP Auditing: While traditional DP auditing provides lower bounds, Eureka significantly enhances this capability. It can still be used to identify faulty implementations or exaggerated privacy claims by demonstrating that a mechanism offers less privacy than advertised. However, by providing a tight estimate of the Relative DP Spectrum, Eureka goes beyond merely flagging issues; it can quantify how much privacy is actually being provided, offering a more complete picture for auditors and aiding in remediation efforts. This allows for more precise verification of compliance with privacy standards and regulations.

1. Facilitating Mechanism Comparison and Selection: With an accurate empirical estimation tool, organizations can objectively compare the privacy-utility trade-offs of different DP mechanisms or even different implementations of the same mechanism. This allows for informed decision-making when selecting the most appropriate privacy-preserving technique for a given task, based on real-world performance rather than just theoretical claims.

1. Reducing Privacy Debt: By making privacy assessment more accessible and empirical, Eureka helps organizations proactively identify and address privacy weaknesses in their systems. This can prevent the accumulation of "privacy debt"—the deferred cost of not adequately addressing privacy concerns early in the development lifecycle—which can lead to costly breaches or compliance issues down the line.

In essence, Eureka bridges the gap between theoretical differential privacy and practical implementation, offering a concrete, verifiable method to measure and understand the privacy offered by black-box mechanisms. This capability is invaluable for building more trustworthy and privacy-aware data ecosystems.

Key Takeaways

• Black-box DP Estimation: Eureka provides a general framework for empirically estimating the differential privacy guarantees of mechanisms, even when only black-box access is available.
• Novel Reduction to Binary Classification: The core innovation is reducing the complex problem of privacy estimation to a solvable binary classification problem, leveraging existing machine learning techniques.
• Relative DP and Privacy Spectrum: The framework introduces Relative DP to address the impossibility of estimating privacy for infinite neighboring inputs, focusing on a chosen set T, and outputs a Privacy Spectrum (Delta as a function of Epsilon).
• Tight Estimates vs. Lower Bounds: Unlike traditional DP auditing which only provides lower bounds, Eureka, when instantiated with good universal classifiers, offers tight estimates of the Relative DP Spectrum, giving a more accurate "how private" answer.
• Empirical Validation: The framework has been rigorously validated against analytical results for fundamental DP mechanisms (Laplacian, Gaussian) and complex ML tasks (random projection, approximately square algorithm), demonstrating high accuracy.
• Empowering Non-Experts: Eureka enables domain experts without deep privacy knowledge to empirically verify and quantify the privacy properties of their algorithms, fostering broader adoption of differential privacy.

About the Speaker(s)

The work "Eureka: A General Framework for Black-box Differential Privacy Estimators" was presented by Yun Lu, who is currently a PhD student at Purdue University. He was the lead presenter for this work.

Yun Lu collaborated with a team of researchers:

• Malik Magdon-Ismail from Rensselaer Polytechnic Institute.
• Yu Wei from the University of Victoria.
• Vassilis Zikas, also from Purdue University, who is Yun Lu's advisor.

Their combined expertise in privacy, machine learning, and theoretical computer science contributed to the development of the Eureka framework.