Ball Differential Privacy: How to Mitigate Data Reconstruction with Less Noise

arXiv:2607.04209 · cs.LG, cs.CR · Submitted 2026-07-05 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Today's paper: "Ball Differential Privacy".

Jane: The gist The proposed Ball-DP mechanism enforces (ε, δ) indistinguishability over single-record substitutions restricted to a ball of radius r in an embedding space,

Tom: First, who's behind it and why it matters.

Paper summary: Tom: So we're looking at this paper called "Ball Differential Privacy: How to Mitigate Data Reconstruction with Less Noise." Basically, the authors are saying that when you use vector embeddings of raw records, even if the model is simple, an attacker can still reconstruct those training records from the released model.

Jane: That sounds a bit scary because we think differential privacy is supposed to be our defense against that kind of thing. So what's the problem they're seeing with standard DP?

Tom: Standard DP calibrates its noise based on this worst-case indistinguishability, which means it hides single-record substitutions that are totally arbitrary. The problem is that this noise ends up being way bigger than what you actually need to stop a reconstruction attack.

Lu: And because of that, the standard DP mechanism degrades your model accuracy without actually giving you any extra security benefit against record reconstruction attacks > Page one > <ref:2607.04209#pg1>

Meng: So what's their idea? They propose something called Ball-DP, which they say enforces (epsilon, delta) indistinguishability only over single-record substitutions that are inside a ball of radius r in the embedding space using a distance metric d > Page one > <ref:2607.04209#pg1,a ball of radius r>

Jane: So the key difference here seems to be introducing this explicit radius r into the privacy guarantee. What does that mean for us?

Tom: It means if you're only facing local reconstruction threats, like someone trying to guess a record near a specific point, you can choose a small radius r. That lets them use less noise and recover more accuracy > Page one > <ref:2607.04209#pg1>

Jane: So it makes the scope of the privacy claim explicit against those reconstruction attacks. But if you want to protect everything, what happens if you make that radius r really big?

Tom: If you set r to cover the entire admissible record domain, then Ball-DP just becomes standard DP again. It’s a trade-off between how much of the data you protect and how much noise you need.

Lu: The paper goes on to derive reconstruction-robustness certificates called Ball-ReRo, which are upper bounds on an attacker's success rate as a function of the oblivious prior and those privacy parameters r, epsilon, delta > Page three > <ref:2607.04209#pg1>

Meng: And they empirically validated these theoretical bounds by comparing Ball-DP against standard DP across seven learning benchmarks. The results show that calibrating noise to Ball-DP improves utility while keeping reconstruction robustness comparable, even when epsilon is small > Page three > <ref:2607.04209#pg1>

Jane: That’s a really interesting finding because it addresses that accuracy-reconstruction robustness trade-off we talked about earlier. Can you tell us a bit more about what this means for deploying these models?

Tom: It means you can tailor the privacy protection to the specific threat you're facing. If your system only needs to be safe against local reconstruction, you don't have to pay the accuracy penalty that standard DP imposes on global settings > Page three > <ref:2607.04209#pg1>

Lu: They also looked at how this works with different convex prediction heads like squared hinge SVMs and softmax logistic regression, showing that they can derive explicit Lz constants for these common models > Page six > <ref:2607.04209#pg1>

Meng: From a deployment standpoint, I'm always worried about what happens when the system breaks at scale. Does this Ball-DP mechanism add significant overhead to the training or inference pipeline?

Tom: It involves Gaussian output perturbation whose noise scales with r, in addition to epsilon and delta parameters, so it adds noise to the output generation > Page three > <ref:2607.04209#pg1>

Jane: So we're talking about a method that seems more practical for real-world scenarios where we only care about local threats. So, what’s the final word on this paper?

Lu: The main contribution is formalizing Ball-DP as a radius-restricted adjacency relation, making the locality of the privacy guarantee an explicit policy choice instead of just a byproduct of noise tuning > Page three > <ref:2607.04209#pg1>

Meng: I see. So it’s about moving from a one-size-fits-all noise calibration to something more targeted based on the specific reconstruction risk we have > Page three > <ref:2607.04209#pg1>

Tom: Exactly. And they showed that this local calibration recovers meaningful accuracy while maintaining those reconstruction robustness guarantees, which is what matters for utility > Page three > <ref:2607.04209#pg1>

Jane: It really shifts the focus from just achieving a certain level of noise to actively choosing the scope of protection, and Ball Differential Privacy provides a principled way to do that > Page one > <ref:2607.04209#pg1>

Conclusion: Tom: So to wrap up, the paper introduces Ball Differential Privacy, which is basically a way to make differential privacy smarter about what it protects by looking at a specific radius in the embedding space > Page one >

Jane: It’s taking standard differential privacy and adding this radius parameter r so that you can specifically limit how much an attacker can substitute records within that ball > Page one >

Tom: Right, and the core idea is you can use less noise than standard DP to achieve a similar level of security if you just focus on local threats > Page three >

Jane: It’s like tuning a radio dial instead of blasting static across the whole spectrum; you find a specific frequency that works for your problem > Page one >

Tom: The authors proved this works by deriving these reconstruction-robustness certificates called Ball-ReRo, which give an upper bound on how successful an attacker can be > Page three >

Jane: And the empirical results show that this calibration actually improves model accuracy compared to just using standard global radius settings when epsilon is small > Page three >

Tom: It means you get better utility while still having a formal guarantee against record reconstruction, which is a big deal for deployment on real data > Page three >

Jane: It shifts the focus from just tuning noise blindly to actively choosing your scope of privacy protection based on what you’re actually worried about > Page one >

Tom: And they showed this works across different convex prediction heads, like those used in SVMs and logistic regression, which means it’s not just a toy problem > Page six >

Jane: So the big picture here is that we can get more accurate AI models while keeping reconstruction risks in check by being specific about where the privacy boundary lies > Page one >

University of Copenhagen

cs.LG, cs.CR

Submitted: 2026-07-05

Updated: 2026-07-13

Comments: 44 pages, 4 figures; references standardized

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 89/100

The gist: The gist The proposed Ball-DP mechanism enforces (ε, δ) indistinguishability over single-record substitutions restricted to a ball of radius r in an embedding space, which mitigates data

Key concepts

Ball-DP
Ball-DP enforces (ε, δ) indistinguishability only for single record substitutions that occur within a metric ball of radius 'r' in the embedding space. This makes the privacy scope explicit: smaller 'r' means tighter local protection and less noise, while larger 'r' expands the protected area at a utility cost.
Reconstruction Robustness
This is a measure of how difficult it is for an adversary to reconstruct training records from a released model. The paper derives Ball-ReRo certificates that mathematically upper-bound this success, showing that Ball-DP provides comparable robustness to standard DP while requiring less noise.
Radius (r)
The radius 'r' defines the explicit scope of the privacy claim against reconstruction attacks. By restricting privacy guarantees to substitutions within this ball, Ball-DP allows practitioners to choose a small 'r' for local threats, recovering accuracy that standard DP often sacrifices.
Ball-ReRo
Ball-ReRo are reconstruction-robustness certificates derived from Ball-DP. They provide an upper bound on an attacker's success in reconstructing data. These certificates are crucial because they allow researchers to verify that the privacy mechanism meets a specific security standard.

Terminology

Summary

The gist The proposed Ball-DP mechanism enforces (ε, δ) indistinguishability over single-record substitutions restricted to a ball of radius r in an embedding space, which mitigates data reconstruction threats with less noise than standard differential privacy while recovering higher model accuracy.

Ball-DP Formulation and Relation to Standard DP

The paper introduces Ball-DP as enforcing (ε, δ) indistinguishability over single-record substitutions within a metric ball of radius r as per a distance metric d in the embedding space <ref:2607.04209#pg2> The radius makes the scope of the privacy claim explicit against reconstruction attacks <ref:2607.04209#pg6> Standard DP is recovered when r covers the entire admissible record domain. Ball-DP deploys the usual (ε, δ)-indistinguishability but applies it to only single-record substitutions within the ball of declared radius r The radius becomes an explicit privacy parameter: smaller r efficiently mitigates local reconstruction threats using less noise, while larger r expands the protected set at a corresponding utility cost.

Mechanism Calibration for Convex Learning

For regularized convex prediction heads, Ball-DP is ensured via Gaussian output perturbation whose noise scales with r in addition to the indistinguishability parameters (ε, δ) The key quantity is how much a single record replacement can change the gradient contribution of the loss. Theorem 3.5 shows that for strongly convex ERM, the distance between corresponding ERM solutions is bounded linearly in the radius r, specifically bounding it by Lzλnr. The Gaussian output perturbation can be calibrated to this protected radius r rather than to any arbitrary replacement.

Reconstruction Robustness and Certificates

The paper connects Ball-DP to reconstruction robustness by deriving reconstruction-robustness certificates named Ball-ReRo, which are upper bounds on an attacker’s reconstruction success. Theorem 4.5 states that if M satisfies (r, ε, δ)-Ball-DP, then every reconstructor R with outputs in Au,r satisfies Pr[ρ(Z, R(θ, D−)) ≤ η] ≤ eκ + δ. This is the radius-restricted analogue of the standard observation that DP limits reconstruction attacks. The direct bound for Gaussian Ball-ReRo is given by Theorem 4.9, which states Pr[ρ(Z, R(θ, D−)) ≤ η] ≤ ΦΦ−1(κ) + ∆2(r)σ.

Empirical Validation and Utility Trade-offs

Empirical evidence suggests that calibrating noise to Ball-DP yields improvement in utility, considerably exceeding the dilution of reconstruction robustness in high privacy regimes, i.e., when ε is small. Experiments show that Ball-DP provides comparable reconstruction robustness while requiring less noise. For example, at ε = 2 and δ = 10−6, Ball-DP improves mean accuracy over the standard global-radius DP comparator across all seven embedding benchmarks at the reported local policy radii. The utility cost of protecting a larger local neighborhood is quantified by comparing accuracy across policies like q50, q80, and q95.

Audit Protocols and Exact Identification

The paper formalizes a finite-prior MAP audit where the adversary narrows the target to a small set of plausible candidates inside the declared neighborhood. Proposition 4.1 provides an exact finite-prior MAP attack for Gaussian releases, showing that the attack reduces to constrained least-squares over the candidate set. The final bound derived in Theorem B.2 gives a support-specific finite-Gaussian exact-ID bound, which is sharper than the generic upper bound from Theorem 3.5.

Convex Head Generalization

The analysis extends to additional convex heads like squared hinge SVMs and softmax logistic regression by verifying Assumption 3.4 for each model. Proposition 6.6 provides explicit Lz constants for these common convex heads, such as Lz ≤ √2 + B2λ/2! The empirical results show that Ball-DP has higher mean accuracy than the global-radius comparator at the same reported ReRo certificate across various convex heads.

Summary of Contributions

The paper introduced Ball-DP, a radius-restricted adjacency relation that makes the locality of a privacy guarantee an explicit, auditable policy choice rather than an implicit byproduct of noise tuning. The core finding is that this local calibration recovers meaningful accuracy while empirical exact-identification rates remain below the theorem-backed Ball-ReRo certificates. The method is a convex-ERM calibration principle rather than a prototype-only construction. The current analysis is confined to convex, one-shot Gaussian releases with public calibration metadata. Future work includes extending the Ball-DP accounting to non-convex representation-learning pipelines and multi-step DP-SGD transcripts. The paper concludes by showing that the radius matters because it changes both the protected adjacency scope and the amount of noise needed to reach this certificate.

Improvements for AI systems

  1. Bold header: Localized Noise Calibration for Privacy-Preserving Embeddings

The Ball-DP mechanism allows calibration of noise to local reconstruction threats by enforcing (ε, δ) indistinguishability over single-record substitutions restricted to a ball of radius r, which can be tuned based on the deployment's threat model. This enables deploying models with lower noise and consequently higher accuracy than standard DP, as shown in Our experiments show that calibrating noise to Ball-DP yields improvement in utility.

  1. Bold header: Reconstruction Robustness Certificates (Ball-ReRo)

The paper provides reconstruction robustness certificates (named Ball-ReRo) by formally connecting the radius-restricted indistinguishability to an upper bound on an attacker’s reconstruction success, enabling quantifiable privacy guarantees against informed adversaries.

  1. Bold header: Utility vs. Privacy Trade-off Quantification

The system can precisely quantify the utility cost of protecting a larger local neighborhood by comparing Ball-DP columns use local adjacency radii q50, q80, and q95 against the standard comparator, showing that Smaller local radii generally yield higher utility.

  1. Bold header: Exact Finite-Prior MAP Auditing

The system can perform exact identification audits using a finite-prior MAP audit for Gaussian releases, which determines the most likely hidden record from a set of plausible candidates by maximizing the log posterior probability, providing a rigorous check against reconstruction success.

  1. Bold header: Head-Specific Sensitivity Calibration

The paper provides explicit Lz constants for various convex heads (Squared Hinge, Binary Logistic, Softmax Logistic), allowing the system to select the appropriate sensitivity bound for specific model architectures when calibrating Ball-DP noise.

Sources

Related papers