Exact zCDP Characterizations for Fundamental Differentially Private Mechanisms

• URL: http://arxiv.org/abs/2510.25746v1
• Date: Wed, 29 Oct 2025 17:48:16 GMT
• Title: Exact zCDP Characterizations for Fundamental Differentially Private Mechanisms
• Authors: Charlie Harrison, Pasin Manurangsi,
• Abstract summary: We derive tight zCDP characterizations for several fundamental mechanisms.<n>We prove that the tight zCDP bound for the $epsilon$-DP Laplace mechanism is exactly $epsilon + e-epsilon - 1$.<n>We also provide a tight zCDP bound for the worst case bounded range mechanism.
• Score: 24.85689199092059
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Zero-concentrated differential privacy (zCDP) is a variant of differential privacy (DP) that is widely used partly thanks to its nice composition property. While a tight conversion from $\epsilon$-DP to zCDP exists for the worst-case mechanism, many common algorithms satisfy stronger guarantees. In this work, we derive tight zCDP characterizations for several fundamental mechanisms. We prove that the tight zCDP bound for the $\epsilon$-DP Laplace mechanism is exactly $\epsilon + e^{-\epsilon} - 1$, confirming a recent conjecture by Wang (2022). We further provide tight bounds for the discrete Laplace mechanism, $k$-Randomized Response (for $k \leq 6$), and RAPPOR. Lastly, we also provide a tight zCDP bound for the worst case bounded range mechanism.

Related papers

• Analysis of Shuffling Beyond Pure Local Differential Privacy [2.4264122405649045]
  Shuffling is a powerful way to amplify privacy of a local randomizer in private distributed data analysis.<n>We develop an analysis that applies to a broad class of local randomizers under mild regularity assumptions.<n>We use an FFT-based algorithm for computing the blanket divergence at finite $n$.
  arXiv  Detail & Related papers  (2026-01-27T03:35:03Z)
• Optimality of Staircase Mechanisms for Vector Queries under Differential Privacy [3.7942266369982955]
  We show that for any dimension, any norm, and any norm-monotone cost function, there exists an $$-DP staircase mechanism that is optimal among all additive mechanisms.<n>This result resolves a conjecture of Geng, Kairouz, Oh, and Viswanath, and provides a geometric explanation for the emergence of staircase mechanisms as extremal solutions in differential privacy.
  arXiv  Detail & Related papers  (2026-01-21T02:35:33Z)
• Dobrushin Coefficients of Private Mechanisms Beyond Local Differential Privacy [36.33156483258328]
  We derive achievable bounds on contraction in terms of a kernels PML guarantees.<n>We extend the results to general $f$-divergences by an application of Binette's inequality.
  arXiv  Detail & Related papers  (2026-01-14T14:03:42Z)
• Beyond Laplace and Gaussian: Exploring the Generalized Gaussian Mechanism for Private Machine Learning [49.66162382667325]
  We investigate the Generalized Gaussian mechanism, which samples the additive noise term $x$ with probability proportional to $e-frac| x |sigmabeta $ for some $beta geq 1$.<n>We show that privacy accounting for the GG Mechanism and its variants is independent, which substantially improves computational costs of privacy accounting.
  arXiv  Detail & Related papers  (2025-06-14T15:49:25Z)
• Approximate Differential Privacy of the $\ell_2$ Mechanism [52.61055173572399]
  We study the $ell$ mechanism for computing a $d$-dimensional statistic with bounded $ell$ sensitivity under approximate differential privacy.<n>Across a range of privacy parameters, we find that the $ell$ mechanism obtains lower error than the Laplace and Gaussian mechanisms.
  arXiv  Detail & Related papers  (2025-02-21T20:56:34Z)
• Beyond the Calibration Point: Mechanism Comparison in Differential Privacy [29.635987854560828]
  In differentially private (DP) machine learning, the privacy guarantees of DP mechanisms are often reported and compared on the basis of a single $(varepsilon, delta)$-pair.<n>This practice overlooks that DP guarantees can vary substantially even between mechanisms sharing a given $(varepsilon, delta)$.
  arXiv  Detail & Related papers  (2024-06-13T08:30:29Z)
• Privacy Amplification for the Gaussian Mechanism via Bounded Support [64.86780616066575]
  Data-dependent privacy accounting frameworks such as per-instance differential privacy (pDP) and Fisher information loss (FIL) confer fine-grained privacy guarantees for individuals in a fixed training dataset. We propose simple modifications of the Gaussian mechanism with bounded support, showing that they amplify privacy guarantees under data-dependent accounting.
  arXiv  Detail & Related papers  (2024-03-07T21:22:07Z)
• Fixed-Budget Differentially Private Best Arm Identification [62.36929749450298]
  We study best arm identification (BAI) in linear bandits in the fixed-budget regime under differential privacy constraints. We derive a minimax lower bound on the error probability, and demonstrate that the lower and the upper bounds decay exponentially in $T$.
  arXiv  Detail & Related papers  (2024-01-17T09:23:25Z)
• Truncated Laplace and Gaussian mechanisms of RDP [28.227024132603123]
  The Laplace mechanism and the Gaussian mechanism are primary mechanisms in differential privacy. Due to the infinite-range random variables they generate, the Laplace and Gaussian mechanisms may return values that are semantically impossible, such as negative numbers.
  arXiv  Detail & Related papers  (2023-09-22T06:37:45Z)
• Breaking the Communication-Privacy-Accuracy Tradeoff with $f$-Differential Privacy [51.11280118806893]
  We consider a federated data analytics problem in which a server coordinates the collaborative data analysis of multiple users with privacy concerns and limited communication capability. We study the local differential privacy guarantees of discrete-valued mechanisms with finite output space through the lens of $f$-differential privacy (DP) More specifically, we advance the existing literature by deriving tight $f$-DP guarantees for a variety of discrete-valued mechanisms.
  arXiv  Detail & Related papers  (2023-02-19T16:58:53Z)
• Connect the Dots: Tighter Discrete Approximations of Privacy Loss Distributions [49.726408540784334]
  Key question in PLD-based accounting is how to approximate any (potentially continuous) PLD with a PLD over any specified discrete support. We show that our pessimistic estimate is the best possible among all pessimistic estimates.
  arXiv  Detail & Related papers  (2022-07-10T04:25:02Z)
• Cactus Mechanisms: Optimal Differential Privacy Mechanisms in the Large-Composition Regime [12.420941209631742]
  We study the design of optimal differential privacy mechanisms in the limit of a large number of compositions. In this regime the best privacy mechanism is the one that minimizes the Kullback-Leibler divergence. We show that our quantization approach can be arbitrarily close to an optimal mechanism.
  arXiv  Detail & Related papers  (2022-06-25T20:05:50Z)
• A unified interpretation of the Gaussian mechanism for differential privacy through the sensitivity index [61.675604648670095]
  We argue that the three prevailing interpretations of the GM, namely $(varepsilon, delta)$-DP, f-DP and R'enyi DP can be expressed by using a single parameter $psi$, which we term the sensitivity index. $psi$ uniquely characterises the GM and its properties by encapsulating its two fundamental quantities: the sensitivity of the query and the magnitude of the noise perturbation.
  arXiv  Detail & Related papers  (2021-09-22T06:20:01Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.