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

Vector embeddings of raw records, while not human-readable, do not preserve privacy of records: an adversary can reconstruct training records from a released model. Differential privacy (DP) is the principled defense, but its noise is calibrated to the worst-case indistinguishability; obscuring arbitrary single-record substitutions, including those far outside the set of plausible alternatives relevant to a reconstruction adversary. The result is noise far larger than what reconstruction robustness requires, which degrades accuracy without a corresponding security benefit against reconstruction attacks. To mitigate this limitation of standard DP, we propose Ball-DP: $(\epsilon ,\delta )$ indistinguishability over single-record substitutions restricted to a ball of radius $r$ according to a distance metric $d$ in the embedding space. A deployment facing only local reconstruction threat can choose a small $r$, thereby reduce noise and recover wasted accuracy. The radius makes the scope of the privacy claim explicit against reconstruction attacks; standard DP is recovered when $r$ covers the entire admissible record domain. We provide noise calibrations for regularized convex learning problems for Ball-DP, and derive the corresponding reconstruction-robustness certificates (named Ball-ReRo) – upper-bound on an attacker's reconstruction success. By deriving the optimal finite-prior MAP reconstruction attack, we conduct empirical auditing of Ball-ReRo certificates for several benchmark learning tasks. We observe that calibrating noise to Ball-DP significantly improves utility, with marginal impact on reconstruction robustness.