Technical Summary: A Unified Framework for Adversary-Aware Differential Privacy Bounds

Problem Statement

Differential Privacy (DP) provides rigorous guarantees against worst-case membership inference (MI) attacks, bounding the probability that an adversary can distinguish between outputs generated by datasets differing in a single user's record. However, the precise trade-off between complex adversarial models and DP protections remains poorly understood. Practitioners often face a dilemma: standard DP bounds (e.g., $\epsilon=1$) may appear to offer weak guarantees against worst-case MI (success probability $\approx 0.73$), yet these bounds provide little insight into context-specific risks, such as the total number of users whose data could be partially reconstructed or the leakage of non-uniform secrets (e.g., common passwords or PII).

Current approaches to assessing risk rely heavily on empirical attacks. These methods suffer from significant limitations: they establish only lower bounds on privacy leakage, are often highly tuned to specific mechanisms or data distributions, and fail to generalize. Furthermore, many relevant attack settings—such as targeting multiple individuals simultaneously or exploiting non-uniform priors for approximate reconstruction—have not been theoretically characterized. There is a lack of a unified framework that can translate privacy parameters into actionable risk assessments across diverse attack goals (MI, attribute inference, reconstruction) and settings (single vs. multiple targets, uniform vs. non-uniform priors).

Methodology

The authors propose a unified framework that generalizes existing bounds across membership inference, attribute inference, and data reconstruction attacks. The core of the methodology is a Generic Attack Game (Algorithm 1) and a set of high-probability upper bounds derived from the mechanism's privacy parameters and the adversary's baseline success rate.

The Generic Attack Game

The framework models an attack where:

1. Targets: $n$ targets $X$ are sampled from a product distribution $D = D_1 \otimes \dots \otimes D_n$. $D_i$ represents the adversary's prior knowledge for target $i$.
2. Mechanism: A randomized mechanism $M$ produces an output $a$.
3. Adversary: The adversary $A$ uses $a$, $D$, and $M$ to generate $k$ attack attempts $z$.
4. Success Metric: A decomposable metric $L$ measures the number of successfully "attacked" targets. $L$ is decomposable if $L(x, z) = \sum \ell_i(x_i, z_i)$, allowing for arbitrary success criteria (exact match, approximate distance, etc.).

Theoretical Bounds

The framework derives bounds for the probability that the attack success $L(X, A(a))$ exceeds a threshold $v$.

• Pure DP ($\epsilon$-DP): For a mechanism satisfying $(\epsilon, 0)$-DP, the posterior success probability for each target is bounded by a function of the prior success probability and $\epsilon$. Specifically, for a fixed mechanism output $a$ and attack attempt $z$, the number of successful attacks is stochastically dominated by a sum of independent Bernoulli variables $S_i$. The success probability $\beta_i$ for each $S_i$ is:
  $$\beta_i(z, \epsilon) = \frac{e^\epsilon}{e^\epsilon - 1 + \frac{1}{\Pr_{X \sim D_i}[\ell_i(X, z)=1]}}$$
  This formulation captures the intuition that if an attack is easy based on prior knowledge (high prior probability), the DP mechanism adds less relative protection compared to a difficult attack.

• Approximate DP ($f$-DP and $(\epsilon, \delta)$-DP): The framework extends to approximate DP by introducing an additive term $n \cdot \delta_f(\epsilon)$ (or $n \cdot \delta$ for $(\epsilon, \delta)$-DP) to the bound. This accounts for the unbounded privacy loss potential in approximate DP mechanisms. The authors provide versions of the bound that depend on the mechanism output (requiring multiple runs for estimation) and versions that use a worst-case prior to avoid dependence on specific outputs.

Encoding Specific Attacks

The framework encodes various attack scenarios by adjusting the prior distribution $D_i$ and the success metric $\ell_i$:

• Membership Inference (MI): $D_i$ is a Bernoulli distribution over membership bits.
• Attribute Inference (AI): $D_i$ is conditioned on known attributes.
• Reconstruction: $D_i$ represents the data-generating distribution. The metric $\ell_i$ can be an exact match or a thresholded distance (e.g., $L_2$ or $L_1$ error).
• Non-Uniform Priors: The framework explicitly handles arbitrary, non-uniform priors, allowing for the modeling of realistic scenarios where certain secrets (e.g., "123456789") are far more probable than others.

Key Contributions

1. Unification of Existing Bounds: The framework mathematically bridges isolated paradigms of MI, AI, and reconstruction. It strictly generalizes prior work (e.g., Balle et al., Hayes et al., Steinke et al.) and provides tighter bounds for settings involving non-uniform priors.
2. Novel Attack Settings: It is the first framework to evaluate attacks targeting multiple individuals simultaneously and to measure success via complex metrics (approximate reconstruction) under a single cohesive bound.
3. Adversary-Awareness: The bounds depend solely on privacy parameters and the adversary's baseline success rate (prior). This allows practitioners to quantify risk based on the specific difficulty of the attack and the nature of the data distribution, rather than relying on worst-case heuristics.
4. Empirical Validation: The authors validate the framework in two novel settings:
   • Data Extraction from LLMs: Extracting non-uniform secrets (passwords, PII) from DP-finetuned language models.
   • Tabular Data Reconstruction: Reconstructing data from noisy marginals using multi-attribute inference (M-AI).

Results

The paper presents numerical comparisons and empirical case studies demonstrating the framework's utility:

• Tightness: In numerical experiments (Figure 1), the proposed bounds are substantially tighter than state-of-the-art bounds (KGK+, MMC) for non-uniform priors and align closely with MMC for uniform priors.
• Impact of Non-Uniform Priors: In LLM data extraction experiments (Figure 2), the framework reveals that non-uniform priors drastically increase risk. For example, at $\epsilon=1$, the advantage bound for extracting a median password is negligible, but jumps to 0.24 for the most probable password. At $\epsilon=10$, the most probable PII and password canaries reach an advantage bound of $\approx 1.0$, whereas uniform canaries remain negligible. This suggests that protecting naturally occurring secrets may require significantly smaller $\epsilon$ values than protecting uniform canaries.
• Gap Between Theory and Practice: Comparisons with concrete attacks (Figure 3) show that while the theoretical bounds are tight for uniform distributions, a gap persists for non-uniform priors. Furthermore, concrete model attacks often fall significantly short of the theoretical Bayes-optimal baseline, particularly in medium-privacy regimes, highlighting limitations in current black-box auditing techniques.
• Tabular Reconstruction: In the reconstruction of tabular data from noisy marginals (Appendix E), the framework successfully models multi-target attacks. The results show that while theoretical bounds can be vacuous for simple tasks with large priors, the framework provides meaningful population-level bounds and accommodates complex success metrics (approximate reconstruction) that prior work could not simultaneously capture.

Significance and Claims

The paper claims to provide a rigorous theoretical foundation for investigating the risk landscape of DP algorithms in new adversarial settings. Its primary significance lies in enabling practitioners to:

• Interpret DP parameters contextually: Translate abstract privacy parameters into concrete risk assessments for specific deployment scenarios (e.g., "What $\epsilon$ is needed to protect PII with a given prior distribution?").
• Calibrate privacy protections: Move beyond "worst-case heuristics" (like the rule of thumb $\epsilon \le 10$) to calibrate parameters against specific, context-dependent risks.
• Evaluate novel threats: Systematically analyze attacks that were previously uncharacterized, such as simultaneous multi-target attacks and those exploiting non-uniform data distributions.

The authors modestly note that their bounds rely on decomposable success metrics and assume independent priors. They acknowledge that current empirical attacks may not be optimal for DP mechanisms, leading to gaps between theoretical bounds and observed attack success. They also caution that while the framework can demonstrate lower empirical risks than worst-case guarantees, it should not be used as a blanket justification to degrade privacy safeguards, as the bounds rely on strict structural assumptions that may not hold in all use cases.