Lower Bounds for Rényi Differential Privacy in a Black-Box Setting

Lower Bounds for Rényi Differential Privacy in a Black-Box Setting

Speakers: Tim Kutta, Önder Askin, Martin Dunsche

Conference: IEEE S&P

YouTube: https://www.youtube.com/watch?v=ECxQDx8G_QY

Overview

This talk, presented by Tim Kutta alongside collaborators Martin Dunsche and Önder Askin, introduces a novel method for statistically assessing Rényi Differential Privacy (RDP) in a black-box setting. Differential privacy (DP) is a crucial concept in data privacy, aiming to protect individual user data while still allowing for meaningful statistical analysis. The challenge lies in verifying whether an algorithm truly adheres to its claimed privacy guarantees, especially when only its outputs are observable without access to its internal code or design – a "black-box" scenario.

The presentation highlights that while several notions of differential privacy exist, RDP offers a "just right" balance, overcoming the limitations of both overly stringent pure differential privacy and overly permissive approximate differential privacy. However, robust black-box assessment tools, prevalent for pure differential privacy, have been lacking for RDP. This work addresses this critical gap by developing a sophisticated statistical framework that can not only estimate RDP parameters but also provide confidence intervals, enabling the debunking of false privacy claims and ensuring the integrity of privacy-preserving algorithms in practice.

The research, supported by the KASTEL Cybersecurity Cluster at WBU University Bochum in Germany, provides a rigorous theoretical foundation and empirical validation for its proposed D_Smooth estimator. By tackling the inherent statistical complexities of estimating Rényi Divergence—a core component of RDP—the speakers offer a practical, statistically sound methodology for auditing and verifying the privacy properties of real-world systems. This advancement is particularly significant given the increasing adoption of RDP in machine learning and other data-intensive applications.

Background

▶ Watch: Introduction and conceptual aim of differential privacy (0:00)

The fundamental premise of Differential Privacy (DP) revolves around safeguarding individual user data within statistical studies. When a database containing sensitive information is queried, there's a risk that an adversary could infer the presence or specific attributes of an individual by observing the query's output. For instance, in a medical database, an adversary might deduce if a specific person has a particular condition. DP aims to prevent such inferences by ensuring that the output of a randomized algorithm remains nearly identical whether an individual's data is included in the database or not. Conceptually, this is achieved by "slapping a little bit of randomness on the outputs" to mask individual contributions.

Formally, this concept is often illustrated by comparing the output distributions of an algorithm run on two adjacent databases. These databases, denoted as X and X', differ by exactly one individual's data point. If the algorithmic outputs A(X) and A(X') have very similar distributions, an adversary cannot reliably determine if the individual in question was part of the database or not, thus achieving privacy.

Over time, various formalizations of differential privacy have emerged, each with its own strengths and weaknesses. The talk specifically focuses on three key notions:

1. Pure Differential Privacy: This was one of the earliest and most popular notions. While widely used, it is often considered "too hot" or too stringent. It excludes many important, practically used algorithms such as the Gaussian mechanism, shuffling, and subsampling, which are crucial for many real-world DP applications, particularly in machine learning.
2. Approximate Differential Privacy: Introduced to address the stringency of pure DP, approximate DP attempts to be more inclusive. However, it proved to be "too cold" or too permissive. It includes pathological examples where an algorithm could publish an entire database with everyone's information with a very low probability, which clearly violates the spirit of privacy.
3. Rényi Differential Privacy (RDP): Introduced more recently, RDP aims to find a "sweet spot" between the two extremes. It successfully incorporates a broader range of algorithms that are excluded by pure DP, such as the Gaussian mechanism and techniques used in noisy gradient descent, while simultaneously avoiding the privacy pathologies inherent in approximate DP. The speakers firmly believe RDP is "just right" for practical applications.

A significant challenge in the deployment of DP is the verification of its guarantees. Typically, assessing differential privacy is a "paper and pencil task" involving mathematical proofs based on an algorithm's pseudocode. However, even a mathematically proven algorithm can suffer from incorrect implementation, or its privacy claims might be false. This highlights the need for black-box methods – techniques that can statistically assess an algorithm's DP properties solely by observing its outputs, without needing access to its internal code. For pure differential privacy, several such black-box methods have been developed, with notable examples including work by Bissl (2021) and Askin et al. (2022). These methods often provide confidence intervals for privacy parameters, which are invaluable tools for debunking false privacy claims. The critical gap that this talk addresses is the absence of comparable robust black-box assessment tools for the more inclusive and increasingly popular Rényi Differential Privacy.

Key Findings

▶ Watch: Rényi DP: The 'just right' notion for privacy (4:40)

The central contribution of this research is the development of a robust statistical methodology for the black-box assessment of Rényi Differential Privacy (RDP). This addresses a significant void in the field, as prior black-box methods were primarily limited to pure differential privacy, which often excludes many practical algorithms. The speakers introduce a novel estimator, dubbed the D_Smooth estimator, designed to accurately and stably estimate the Rényi Divergence between the output distributions of an algorithm operating on adjacent databases.

A key challenge in estimating Rényi Divergence, particularly in a black-box setting, stems from the potential for density estimates in the denominator of the divergence formula to approach zero, leading to extreme instability. The authors demonstrate how a naive plug-in approach using kernel density estimators fails due to this issue. While a standard strategy of "flooring" or truncating the denominator density with a small positive value (tau) stabilizes the estimator, it introduces a new problem: the non-differentiability of the max function. This non-differentiability prevents the application of standard statistical tools like the Delta method, which are essential for deriving the asymptotic distribution of the estimator and, consequently, for constructing confidence intervals.

The innovation lies in replacing the non-differentiable max function with a smooth maximum approximation. This crucial modification renders the entire D_Smooth estimator differentiable, thereby enabling the rigorous application of the Delta method. As a result, the authors are able to derive the asymptotic normality of their estimator, which is the foundational step for constructing statistically valid confidence intervals for the Rényi Divergence. These confidence intervals are the ultimate tool for practitioners, allowing them to statistically verify or debunk claims of RDP satisfaction by an algorithm.

Through extensive simulations, the research validates the effectiveness of the D_Smooth estimator. The experimental results, showcased with algorithms like randomized response and the Gaussian mechanism, demonstrate that the proposed lower bounds for RDP are consistently "tight" – meaning they are close to the true privacy claim – and reliably provide lower bounds. Critically, the probability of "overshooting" (where the estimated lower bound exceeds the true privacy claim) is rigorously controlled to be small, typically less than 5%, aligning with standard statistical confidence levels. This work thus provides a mathematically sound and empirically validated framework for auditing RDP, crucial for ensuring the integrity of privacy-preserving systems.

Technical Deep Dive

▶ Watch: Why black-box methods are needed for DP assessment (6:00)

The core of this research revolves around the statistical estimation of Rényi Divergence, which is the foundational metric for Rényi Differential Privacy (RDP). To understand the technical contributions, it's essential to first grasp these definitions.

The Rényi Divergence of order lambda between two probability distributions (or densities) P and Q, denoted D_lambda(P||Q), is a measure of their dissimilarity. For continuous densities, it is defined as:

D_lambda(P||Q) = (1 / (lambda - 1)) * log ( integral (p(x)^lambda / q(x)^(lambda-1)) dx )

Here, p(x) and q(x) are the probability density functions of P and Q, respectively. The parameter lambda must be greater than 1. This lambda acts as a stringency parameter: as lambda increases, RDP becomes more stringent and approaches pure differential privacy. In practice, lambda values like 2, 5, or 7 are commonly used, balancing inclusivity with privacy strength.

An algorithm A is said to be (lambda, epsilon)-Rényi Differentially Private if, for all pairs of adjacent databases X and X' (databases differing by only one individual record), the Rényi Divergence between their output distributions, A(X) and A(X'), is bounded by epsilon:

D_lambda(A(X)||A(X')) <= epsilon

A smaller epsilon signifies stronger privacy, meaning the output distributions P (from A(X)) and Q (from A(X')) are very similar. The statistical task is to estimate this D_lambda(P||Q) and provide a confidence interval for it in a black-box setting. This means we only have access to replicated outputs from A(X) and A(X') (i.e., independent, identically distributed samples from P and Q), without knowing the internal workings of A.

The natural first approach to estimating D_lambda(P||Q) is a plug-in estimator. This involves first estimating the unknown densities P and Q from the observed samples using methods like Kernel Density Estimators (KDEs), yielding P_hat and Q_hat. Then, these estimated densities are plugged into the Rényi Divergence formula: D_lambda(P_hat||Q_hat).

However, this straightforward approach faces a critical problem. As the formula shows, q(x)^(lambda-1) appears in the denominator. When Q_hat(x) takes values close to zero (which is common for continuous densities at various points in their support), the denominator can become extremely small, causing the entire estimator to become "blown up" and "really, really unstable." This makes the naive plug-in estimator unreliable.

To address this instability, a common strategy in density ratio estimation is truncation or flooring the denominator. Instead of Q_hat(x), one uses max(Q_hat(x), tau), where tau is a small positive constant bounded away from zero. This ensures the denominator never falls below tau, thereby stabilizing the estimator. This "floored estimator" provides a much more stable estimate of the Rényi Divergence.

While the flooring strategy solves the stability issue, it introduces a new, significant problem for statistical inference. To construct confidence intervals, one needs to understand the sampling distribution of the estimator, particularly its asymptotic behavior for large sample sizes. In statistics, the Delta method is a powerful tool for this purpose: if an estimator is asymptotically normally distributed, and it undergoes a differentiable transformation, the transformed estimator will also be asymptotically normally distributed. However, the max function, max(Q_hat(x), tau), is not differentiable. Specifically, it resembles a ReLU function (Rectified Linear Unit), which has a sharp corner at Q_hat(x) = tau. This non-differentiability prevents the direct application of the Delta method, making it impossible to derive the asymptotic distribution and thus to construct confidence intervals in a rigorous manner.

This is where the core innovation of the paper comes in. The authors propose to replace the non-differentiable max function with a smooth maximum approximation. Instead of max(Q_hat(x), tau), they use a differentiable function that smoothly approximates the maximum, such as a softmax or a similar "smooth max" function. This modification leads to their D_Smooth estimator. By ensuring that the transformation is differentiable, the Delta method can now be applied. This allows the derivation of the asymptotic distribution of the D_Smooth estimator, which is shown to be approximately normal.

The ability to prove the asymptotic normality of the D_Smooth estimator is paramount. It provides the theoretical foundation for constructing statistically valid confidence intervals. These intervals give a range of plausible values for the true Rényi Divergence with a specified level of confidence (e.g., 95%). This, in turn, allows for robust statistical hypothesis testing: if an algorithm claims to satisfy (lambda, epsilon)-RDP, one can check if the upper bound of the confidence interval for D_lambda(P||Q) is consistently below epsilon. If not, the claim can be statistically debunked.

The paper provides the "mathematical and formal proofs" for this approach, carefully detailing how to choose the smoothing parameter and truncation threshold (tau) to ensure the method's theoretical guarantees translate to practical effectiveness. This rigorous theoretical backing is what differentiates their intuitive approach from mere heuristic.

Demo / Proof of Concept

▶ Watch: Developing black-box tools for Rényi differential privacy (7:40)

While the talk did not feature a live, interactive demonstration, the speakers presented compelling simulation results that serve as a robust proof of concept for their black-box assessment methodology. These experiments illustrate how the proposed D_Smooth estimator and its derived confidence intervals perform in practice when applied to various privacy-preserving algorithms.

The experimental setup involved a "randomized algorithm," with specific examples mentioned including randomized response and the Gaussian mechanism. These algorithms are commonly used in differential privacy applications and are particularly relevant because they are often excluded by pure differential privacy but are well-covered by Rényi Differential Privacy.

For each algorithm under test, the "true privacy claim" was established, often standardized to a value of one for comparison across different lambda parameters. This true privacy claim is visually represented by a red line in the presented plots. Against this baseline, the research generated violin plots (represented by blue shapes in the presentation). Each violin plot encapsulates the distribution of statistical lower bounds for the Rényi Divergence, obtained from a thousand independent simulation runs. This extensive simulation provides a comprehensive view of the estimator's behavior and reliability.

The results consistently demonstrated the efficacy of their approach:

• The generated lower bounds were "pretty tight," meaning they closely approximated the actual privacy claim. This indicates that the estimator is efficient and provides accurate estimates.
• The lower bounds were "very close to the actual privacy claim," reinforcing the precision of the D_Smooth estimator.
• Crucially, the statistical lower bounds were "usually really lower bounds," meaning they typically fell below the true privacy claim. This is a desirable property for confidence intervals, as it offers a conservative and reliable estimate of privacy.
• The probability of "overshooting," where the lower bound estimate incorrectly exceeds the true privacy claim, was rigorously controlled. The speakers highlighted that this overshooting probability was consistently "smaller than 5%," which aligns with standard statistical confidence levels (e.g., for a 95% confidence interval, we expect the true value to be outside the interval in only 5% of cases). This adherence to statistical guarantees underscores the robustness and trustworthiness of their method.

In essence, these simulation-based "glance[s] of how our experiments look like in reality" provide strong empirical evidence that the D_Smooth estimator effectively provides statistically sound, tight, and reliable lower bounds for Rényi Differential Privacy in a black-box setting, thereby validating the theoretical claims of the paper.

Defensive Implications

▶ Watch: Formal introduction to Rényi Divergence (7:55)

The black-box assessment framework for Rényi Differential Privacy (RDP) presented in this talk carries significant implications for defenders and organizations striving to implement robust privacy safeguards. This work moves beyond theoretical proofs to provide a practical, statistical tool for verifying privacy claims in real-world scenarios.

Firstly, this methodology offers an invaluable tool for auditing and independent verification of privacy-preserving algorithms. In many cases, developers or vendors might claim their systems are RDP-compliant. However, without independent means of verification, these claims can be difficult to trust, especially given the complexity of DP implementations. The D_Smooth estimator, by providing confidence intervals for RDP parameters from observable outputs, allows third-party auditors or internal security teams to statistically assess whether an algorithm's actual behavior aligns with its advertised privacy guarantees. This creates a mechanism for accountability and transparency.

Secondly, the ability to "debunk false privacy claims" is a critical defensive capability. An algorithm might be designed to be RDP, but a flawed implementation, subtle bugs, or incorrect parameter choices could inadvertently leak more information than intended. Existing black-box methods for pure DP have already proven useful in identifying such discrepancies. Extending this capability to RDP means that a wider range of algorithms, particularly those leveraging techniques like the Gaussian mechanism, subsampling, or noisy gradient descent common in machine learning, can now be rigorously checked. This helps prevent the deployment of "patently not private" systems that might deceptively appear to offer RDP.

Furthermore, this research aids in ensuring correct implementation even when theoretical proofs exist. A mathematical proof of RDP applies to the abstract algorithm, not necessarily to its specific code instantiation. An implementation bug, even a minor one, could completely undermine privacy. By analyzing the outputs, defenders can catch these implementation-level flaws that paper-and-pencil proofs might miss. This acts as a crucial safety net for developers and data scientists who are building privacy-preserving systems.

Finally, in an era of increasing data privacy regulations (like GDPR, CCPA), tools that can statistically verify privacy properties are essential for compliance and building trust. Organizations can use this framework to demonstrate, with statistical confidence, that their data processing pipelines adhere to specified RDP levels. This not only mitigates legal and reputational risks but also fosters greater user trust by providing evidence that their data is indeed being protected as claimed. The applicability to machine learning settings, where RDP is gaining traction, is particularly pertinent, as it provides a way to verify the privacy guarantees of increasingly complex ML models.

Key Takeaways

• Rényi Differential Privacy (RDP) is a balanced privacy notion: It addresses the limitations of both overly stringent pure differential privacy and overly permissive approximate differential privacy, making it suitable for a broader range of practical applications, especially in machine learning.
• Black-box assessment is crucial for practical DP: Relying solely on theoretical proofs is insufficient; statistical methods that verify an algorithm's privacy properties from its outputs are essential for auditing, debunking false claims, and ensuring correct implementations.
• Estimating Rényi Divergence is statistically challenging: Naive plug-in estimators are unstable due to denominators approaching zero. Standard truncation methods, while stabilizing, introduce non-differentiability, preventing the use of the Delta method for confidence interval construction.
• The D_Smooth estimator is a key innovation: By employing a smooth maximum approximation, this estimator overcomes the non-differentiability problem, allowing for the rigorous derivation of its asymptotic distribution and the construction of statistically sound confidence intervals for RDP parameters.
• Statistical confidence intervals enable robust verification: The ability to provide tight, reliable lower bounds with controlled overshooting probabilities allows defenders to statistically assess and confirm RDP claims for algorithms like randomized response and the Gaussian mechanism.
• This work empowers practical privacy auditing: It provides a much-needed tool for independent verification of RDP guarantees, enhancing trust, ensuring compliance, and catching implementation flaws in real-world privacy-preserving systems.

About the Speaker(s)

The talk was presented by Tim Kutta, who collaborated with Önder Askin and Martin Dunsche on this research. The project was supported by the KASTEL Cybersecurity Cluster, a collaborative initiative located at WBU University Bochum in Germany. Their collective work focuses on advancing the theoretical and practical aspects of differential privacy, particularly in developing robust statistical methods for assessing privacy guarantees in black-box scenarios. Their contributions aim to bridge the gap between theoretical privacy notions and their verifiable implementation in real-world systems.