Measurement of Attack Resilience of Differential Privacy

Differential Privacy (DP) is a leading framework for privacy-preserving data analysis,
offering formal guarantees controlled by the privacy budget parameter 𝜀. In practice,
however, it is up to practitioners to select 𝜀—often without clear guidance on how this
choice impacts protection against privacy attacks such as attribute inference and data
reconstruction. There is a need for metrics that capture the privacy risks posed by concrete
adversaries to support such decisions.
Existing metrics like Reconstruction Robustness (ReRo) aim to quantify this risk but po-
tentially overestimate information leakage, leading to overly conservative noise calibration
and unnecessary utility loss.
A new metric, Unbiased Reconstruction Robustness (U-ReRo), was proposed to address
this issue. It is a refined metric that aims to distinguish true privacy leakage from adversarial
prior knowledge and data correlation. While U-ReRo provides tighter bounds than ReRo in
theory, its practical performance has not yet been evaluated. It is therefore unclear whether
U-ReRo improves over ReRo and whether the provided bounds are tight in practice.
In this work, we conduct empirical evaluations using realistic attacks on DP mechanisms
... mehr
to compare ReRo and U-ReRo. Our results show that ReRo overestimates privacy risk,
especially when attacks exploit background knowledge or imputation, whereas U-ReRo
more accurately reflects actual leakage. We further prove that our bound on U-ReRo under
pure DP and uniform prior is tight in settings without target-specific auxiliary knowledge,
providing practical guidance for DP parameter selection.
Beyond risk estimation, we apply U-ReRo to DP auditing—the task of empirically
estimating the privacy loss 𝜀 from the outputs of a DP mechanism. This task is critical for
validating the correctness of deployed DP mechanisms, as theoretical guarantees may not
capture the true behavior of practical implementations. However, prior auditing methods
have focused predominantly on membership inference attacks. In contrast, U-ReRo extends
auditing beyond this setting, offering a framework for estimating privacy loss more broadly.
In the Local DP setting, U-ReRo furthermore achieves more accurate auditing results than
the state-of-the-art.