Meeting Utility Constraints in Differential Privacy: A Privacy-Boosting Approach

Bo Jiang, Wanrong Zhang, Donghang Lu, Jian Du, Sagar Sharma, Qiang Yan

TL;DR

Traditional differential privacy often forces a hard trade-off where protecting data destroys its practical utility. This paper introduces a "Privacy-Boosting" framework that reshapes standard DP noise distributions to guarantee that outputs meet specific accuracy constraints (like a maximum relative error) while actually reducing overall privacy leakage.

What Problem Does This Paper Address?

Differential Privacy (DP) typically operates on a "privacy-first" paradigm: you select a privacy budget ($\epsilon$), add the corresponding amount of random noise, and accept whatever data accuracy (utility) remains. In the real world, however, data analysts and regulators often have strict, non-negotiable utility constraints—such as requiring that an anonymized health database report physical activity metrics within a 5% margin of error.

While "utility-first" DP approaches exist, they usually rely on fixed noise distributions that aren't optimized for complex, real-world accuracy requirements. The authors tackle this gap by creating a flexible framework that dynamically balances privacy and utility based on specific target constraints, without requiring a relaxation of worst-case privacy guarantees.

Methods

The core innovation is the Privacy-Boosting DP (PB-DP) framework. Instead of inventing a brand-new noise distribution, it acts as a wrapper around existing standard "kernel" mechanisms (like Gaussian or Laplace noise).

Here is how it works:

  1. Preferred Regions: The user defines a "preferred region" $S(Q(X))$ where the noisy output ought to fall to remain useful, along with a confidence level $\rho$ (the probability that the output lands in this region).
  2. PDF Reweighting: The framework strategically boosts the probability density function (PDF) inside this preferred region by a factor $q$, while flattening and elongating the tails outside of it.
  3. Optimization: The authors introduce an optimization algorithm (using Ternary Search) to find the perfect mathematical split between the base kernel noise and the boosting factor, minimizing the total privacy loss ($\epsilon$).

The paper explores three distinct types of preferred regions, illustrated below:

Figure 1. Illustration of privacy boosting mechanisms for the three special cases studied in this paper. We take one dimensional Gaussian kernel as an example. In each figure, Q(X) and Q(X′) denotes true aggregations from neighboring datasets. Solid vertical lines represent boundaries of preferred regions for each case.
  • Data-dependent (e.g., relative error bounds, where the acceptable error scales with the true value).
  • Fixed/Deterministic (e.g., bounded output support, where outputs must fall within a strict physical range).
  • Data-independent (e.g., absolute error bounds, which depend only on noise magnitude).

The authors also extend this framework to Local DP (PB-LDP) using a modified Generalized Randomized Response mechanism for discrete data categories.

Datasets

To evaluate the Local DP frequency estimation protocol, the authors utilized the UCI Adult Dataset. This standard benchmark contains census information across 45,222 records. The experiments specifically focused on privatizing and reconstructing user age data (preprocessed as integers from 10 to 100) to test the trade-off between category-level and item-level frequency accuracy.

Key Insights and Ideas

  • Counter-Intuitive Variance: To make data more private and more accurate simultaneously, the framework actually increases the overall noise variance in the distribution's tails while boosting the center. This "soft boundary" approach reduces privacy leakage far better than hard-truncating the noise.
  • Decoupling the "Dominating Pair": In data-dependent scenarios (like relative error), the worst-case dataset pair that maximizes privacy leakage for the boosting step isn't necessarily the same as the worst-case pair for the underlying noise kernel. Disentangling these allowed the authors to calculate tighter, more practical privacy upper bounds.
  • Versatility: Because it functions as a framework rather than a single standalone algorithm, it can be applied to almost any standard additive noise mechanism or discrete local DP setting.

Key Results

  • Substantial Privacy Savings: Across both approximate DP and Rényi DP (RDP), the PB-DP framework consistently achieved lower $\epsilon$ values than standard Gaussian mechanisms under identical utility constraints. This advantage becomes massive when query sensitivity is high relative to the true answer.
  • Compounding Benefits Under Composition: When executing sequential queries (tested up to 1,000 compositions), the privacy savings compounded significantly, leading to a much slower accumulation of total privacy loss over time compared to baseline DP.
  • Expanded Feasibility: For fixed output domains, the soft-bounded boosting factor allows the mechanism to achieve tight $(\epsilon, \delta)$ privacy profiles that are mathematically impossible to reach using traditional bounded DP mechanisms.

Limitations and Future Work

The primary limitation of the PB-DP framework is its incompatibility with pure DP ($\delta = 0$). Because the reweighting strategy stretches out the tails of the noise distribution to compensate for the boosted center, the absolute worst-case privacy leakage increases. Consequently, PB-DP is highly effective for approximate DP ($\delta > 0$) and Rényi DP, but less suitable for applications demanding strict pure DP guarantees.

For future work, the authors suggest exploring adaptive online budget recycling and expanding the framework to handle highly complex, multi-dimensional query spaces.

Summary updated

Abstract

Data engineering often requires accuracy (utility) constraints on results, posing significant challenges in designing differentially private (DP) mechanisms, particularly under stringent privacy parameter $ε$. In this paper, we propose a privacy-boosting framework that is compatible with most noise-adding DP mechanisms. Our framework enhances the likelihood of outputs falling within a preferred subset of the support to meet utility requirements while enlarging the overall variance to reduce privacy leakage. We characterize the privacy loss distribution of our framework and present the privacy profile formulation for $(ε,δ)$-DP and Rényi DP (RDP) guarantees. We study special cases involving data-dependent and data-independent utility formulations. Through extensive experiments, we demonstrate that our framework achieves lower privacy loss than standard DP mechanisms under utility constraints. Notably, our approach is particularly effective in reducing privacy loss with large query sensitivity relative to the true answer, offering a more practical and flexible approach to designing differentially private mechanisms that meet specific utility constraints.
BibTeX
@inproceedings{jiang2025meeting,
  author = {Bo Jiang and Wanrong Zhang and Donghang Lu and Jian Du and Sagar Sharma and Qiang Yan},
  title = {{Meeting Utility Constraints in Differential Privacy: A Privacy-Boosting Approach}},
  booktitle = {Sp},
  year = {2025},
  doi = {10.1109/sp61157.2025.00064},
}
Figure