Exact zCDP Characterizations for Fundamental Differentially Private Mechanisms

Harrison, Charlie; Manurangsi, Pasin

doi:10.4230/LIPIcs.FORC.2026.3

Exact zCDP Characterizations for Fundamental Differentially Private Mechanisms

Charlie Harrison

Google, Austin, TX, USA Pasin Manurangsi

Google Research, Bangkok, Thailand

Abstract

Zero-concentrated differential privacy (zCDP) is a variant of differential privacy (DP) that is widely used partly due to its nice composition property. While a tight conversion from $\varepsilon$ -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 $\varepsilon$ -DP Laplace mechanism is exactly $\varepsilon+e^{-\varepsilon}-1$ , confirming a recent conjecture by Wang [29]. 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.

Keywords and phrases:

Zero-Concentrated Differentially Privacy, Laplace Mechanism, Randomized Response

Copyright and License:

2012 ACM Subject Classification:

Security and privacy

Acknowledgements:

We would like to thank Thomas Steinke for insightful discussions, and for encouraging us to find a tight bound for bounded range mechanisms.

DOI:

10.4230/LIPIcs.FORC.2026.3

Event:

7th Symposium on Foundations of Responsible Computing (FORC 2026)

Editor:

Huijia (Rachel) Lin

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Differential privacy (DP) [8] is a strong, formal notion of privacy which bounds the information revealed by the output of an algorithm. In recent years, various relaxations of $\varepsilon$ -differential privacy (aka pure-DP) have emerged. Most relevant to this work are Rényi differential privacy (RDP) [23] and zero-concentrated differential privacy (zCDP) [11, 1], which have proven useful in regimes where many algorithms are composed together.

Table 1: Our main contributions: tight zCDP bounds for various

\varepsilon

-DP mechanisms, as well as all

\varepsilon

-bounded range mechanisms. Also included are the asymptotics for all tight bounds as

\varepsilon\to 0

, which is common in practice in the large-composition regime. All bounds are plotted in Figure 1.

Mechanism	Tight zCDP bound	$\varepsilon\to 0$	Reference
$\varepsilon$ -DP	$\varepsilon\tanh(\varepsilon/2)$	$\varepsilon^{2}/2$	[27]
$\varepsilon$ -DP Laplace	$\varepsilon+e^{-\varepsilon}-1$	$\varepsilon^{2}/2$	Theorem 12
$\varepsilon$ -DP discrete Laplace	$\varepsilon\left(1-\frac{1}{\Delta}(1-e^{-\varepsilon})\operatorname{csch}(% \varepsilon/\Delta)\right)$	$\varepsilon^{2}/2$	Theorem 13
$\varepsilon$ -DP $k$ -RR	$\frac{\varepsilon(e^{\varepsilon}-1)}{e^{\varepsilon}-1+k}$ for $k\leq 6$	$\varepsilon^{2}/k$ for $k\leq 6$	Theorem 16
$\varepsilon$ -DP RAPPOR	$\varepsilon\tanh(\varepsilon/4)$	$\varepsilon^{2}/4$	Proposition 22
$\varepsilon$ -Bounded Range	$\frac{\varepsilon}{e^{\varepsilon}-1}+\log\left(\frac{e^{\varepsilon}-1}{% \varepsilon}\right)-1$	$\varepsilon^{2}/8$	Theorem 23

Obtaining tight privacy guarantees is of paramount importance in both theoretical and practical applications of differential privacy. Therefore, when the algorithms being composed in this manner are themselves $\varepsilon$ -DP, having tight translations between $\varepsilon$ -DP and zCDP is critical. Bun and Steinke [1] showed that any $\varepsilon$ -DP mechanism also satisfies $(\varepsilon^{2}/2)$ -zCDP, and it is easy to show that any $\varepsilon$ -DP mechanism satisfies $\varepsilon$ -zCDP. Noticeably, there is a gap between these two bounds, as the former is better in the low- $\varepsilon$ regime but the latter is better in the large- $\varepsilon$ regime. This gap was closed in [27] which showed that any $\varepsilon$ -DP mechanism tightly satisfies $\left(\varepsilon\tanh(\varepsilon/2)\right)$ -zCDP and the binary Randomized Response (RR) is the worst-case mechanism. Nevertheless, many fundamental mechanisms enjoy better zCDP guarantees than such a generic formula implies. Our main contributions are tight zCDP bounds of several fundamental $\varepsilon$ -DP mechanisms, including the Laplace mechanism, discrete Laplace mechanism, RAPPOR and $k$ -RR (when $k$ is sufficiently small). The bounds are listed in Table 1 and plotted in Figure 1. In the case of the Laplace mechanism, we confirm a bound conjectured in [29], and formalize the RAPPOR bound first stated in [17]. The bounds for the other mechanisms are novel to the best of our understanding.

We also provide tight zCDP bounds for $\varepsilon$ -bounded range ( $\varepsilon$ -BR) mechanisms. The notion of BR mechanisms was proposed by [7, 6] in an attempt to achieve better composition properties for the exponential mechanism [22]. From this foundation, [2] proved that the exponential mechanism satisfies $(\varepsilon^{2}/8)$ -zCDP, which is only tight asymptotically as $\varepsilon\to 0$ . We show a tight bound for worst-case $\varepsilon$ -BR mechanisms in Theorem 23.

Properties of our bounds.

All our tight zCDP bounds are exactly the same as the KL divergence between output distributions on neighboring datasets. That is, the RDP bound is achieved when the Rényi divergence order approaches one. However, proving such a statement proved challenging and, for each mechanism, we proceed with different parameterization (and differentiation) to prove such an inequality. Another interesting finding is that the zCDP bound for $k$ -RR does not occur at $\alpha\to 1$ for any sufficiently large $k$ (Lemma 17).

Why use zCDP accounting.

For all the mechanisms explored here, privacy accounting with zCDP is lossy with respect to accounting with RDP directly, as zCDP provides upper bounds on the RDP at every $\alpha$ simultaneously. Furthermore, composition with privacy loss distributions (PLDs) [3] will yield tighter guarantees than both zCDP and RDP. This raises the question: “why ever do accounting with zCDP?” The short answer is that zCDP accounting excels in its simplicity, but we elaborate on two further points below:

1.

zCDP vs. PLD. PLD is not known to be compatible with so-called fully adaptive composition using privacy filters, introduced in [26], where both mechanism and privacy parameters can be adapted based on previous queries. Both zCDP and RDP accounting naturally give “free” filters [20, 14], which enable their use in this setting. Furthermore, composition with PLD requires convolution of probability distributions, which is less efficient than zCDP composition which requires the bookkeeping of a single number.
2.

zCDP vs. RDP. While RDP is compatible with the fully adaptive setting, tight accounting with RDP requires tracking many values of $\alpha$ simultaneously. For example, the Google differential-privacy library tracks 156 orders by default [4]. In cases where accounting needs to happen at a more fine-grained level (e.g. with individual differential privacy [12]), this overhead can be substantial compared to zCDP.

2 Preliminaries

Privacy notions.

We recall the various notions of DP considered in this work.

Definition 1 (Differential privacy [8]).

An algorithm $M:\mathcal{X}^{n}\to\mathcal{Y}$ satisfies $\varepsilon$ -differential privacy ( $\varepsilon$ -DP) if, for all neighboring¹¹1For the purpose of our work, the exact definition of neighboring dataset is unimportant. inputs $x,x^{\prime}\in\mathcal{X}^{n}$ and for all $S\subseteq\mathcal{Y}$ , $\log\left(\frac{\mathbb{P}(M(x)\in S)}{\mathbb{P}(M(x^{\prime})\in S)}\right)\leq\varepsilon$ .

Definition 2 (Rényi divergence [24]).

Let $P$ and $Q$ be probability distributions on $\Omega$ . Then the Rényi divergence between $P$ and $Q$ at order $\alpha$ , denoted $\mathrm{D}_{\alpha}\left(P\ \middle\|\ Q\right)$ , is

\mathrm{D}_{\alpha}\left(P\ \middle\|\ Q\right)=\frac{1}{\alpha-1}\log\left(% \int_{\Omega}P(x)^{\alpha}Q(x)^{1-\alpha}\mathrm{d}x\right),

where $P(\cdot),Q(\cdot)$ denote the probability mass/density functions of $P$ and $Q$ , respectively.²²2In this work, $P$ and $Q$ are always absolutely continuous with respect to one another. The Rényi divergence at $\alpha=1$ is defined as

\mathrm{D}_{1}\left(P\ \middle\|\ Q\right)=\lim_{\alpha\to 1}\mathrm{D}_{% \alpha}\left(P\ \middle\|\ Q\right)=D_{KL}(P||Q)=\int_{\Omega}P(x)\log\left(% \frac{P(x)}{Q(x)}\right)\mathrm{d}x.

For notational convenience, we will sometimes write random variables in place of their distributions in $\mathrm{D}_{\alpha}\left(\cdot\ \middle\|\ \cdot\right)$ when there is no ambiguity.

Definition 3 (Rényi DP [23]).

An algorithm $M:\mathcal{X}^{n}\to\mathcal{Y}$ satisfies $(\alpha,\hat{\varepsilon})$ -Rényi differential privacy ( $(\alpha,\hat{\varepsilon})$ -RDP) if, for all neighboring inputs $x,x^{\prime}\in\mathcal{X}^{n}$ , $\mathrm{D}_{\alpha}\left(M(x)\ \middle\|\ M(x^{\prime})\right)\leq\hat{% \varepsilon}.$

$M$ is tightly- $(\alpha,\hat{\varepsilon})$ -RDP if it is $(\alpha,\hat{\varepsilon})$ -RDP and it is not $(\alpha,\hat{\varepsilon}^{\prime})$ -RDP for any $\hat{\varepsilon}^{\prime}<\hat{\varepsilon}$ .

Definition 4 (Concentrated DP [1]).

An algorithm $M:\mathcal{X}^{n}\to\mathcal{Y}$ satisfies $\rho$ -zero concentrated differential privacy ( $\rho$ -zCDP) if it satisfies $(\alpha,\rho\alpha)$ -RDP for all $\alpha\geq 1$ .

$M$ is tightly- $\rho$ -zCDP if it is $\rho$ -zCDP and it is not $\rho^{\prime}$ -zCDP for any $\rho^{\prime}<\rho$ .

Finally, we recall the notion of bounded range mechanisms.

Definition 5 (Bounded range DP [7, 6, 25]).

An algorithm $M:\mathcal{X}^{n}\to\mathcal{Y}$ satisfies $\eta$ -bounded range ( $\eta$ -BR) if, for all neighboring inputs $x,x^{\prime}\in\mathcal{X}^{n}$ differing on a single row and for all $S\subseteq\mathcal{Y}$ , there exists a $t\in\mathbb{R}$ such that $\log\left(\frac{\mathbb{P}(M(x)\in S)}{\mathbb{P}(M(x^{\prime})\in S)}\right)% \in[t,t+\eta].$

It is immediate from the definition that $\eta$ -BR implies $\eta$ -DP, and $\varepsilon$ -DP implies $(2\varepsilon)$ -BR.

Sensitivity.

We will consider mechanisms that simply adds noise to the output of a function. The privacy guarantees of this mechanism depends on the sensitivity of the function, defined as follows.

Definition 6 (Sensitivity).

The sensitivity of a function $g:\mathcal{X}^{n}\to\mathbb{R}$ is $\Delta(g):=\max_{X,X^{\prime}}|g(X)-g(X^{\prime})|$ where the maximum is over all neighboring inputs $X$ and $X^{\prime}$ .

Noise distributions.

$\blacksquare$

The continuous Laplace distribution with scale parameter $\lambda$ is denoted by $\operatorname{Lap}(\lambda)$ and has support on $\mathbb{R}$ . Its probability density function is $f_{\operatorname{Lap}(\lambda)}(x)=\frac{1}{2\lambda}e^{-|x|/\lambda}.$
$\blacksquare$

The discrete Laplace distribution with scale parameter $a$ is denoted by $\operatorname{DLap}(a)$ and has support on $\mathbb{Z}$ . Its probability mass function is $f_{\operatorname{DLap}(a)}(x)=\tanh(a/2)e^{-a|x|}.$

Existing tight bounds.

We will leverage (and extend) the following existing tight bounds.

Proposition 7 (DP to RDP [27]).

If $M$ is $\varepsilon$ -DP, then $M$ satisfies $(\alpha,\hat{\varepsilon}(\alpha))$ -RDP for all $\alpha>1$ where $\hat{\varepsilon}(\alpha)=\frac{1}{\alpha-1}\log\left(\frac{e^{\alpha% \varepsilon}+e^{\varepsilon(1-\alpha)}}{e^{\varepsilon}+1}\right)$ .

Proposition 8 (DP to zCDP [27]).

If $M$ is $\varepsilon$ -DP, then $M$ satisfies $\varepsilon\cdot\tanh(\varepsilon/2)$ -zCDP.

Some Useful Functions and Their Properties.

Recall the hyperbolic functions: $\sinh(x)=\frac{e^{x}-e^{-x}}{2},\cosh(x)=\frac{e^{x}+e^{-x}}{2},$ $\tanh(x)=\frac{\sinh(x)}{\cosh(x)},\coth(x)=\frac{\cosh(x)}{\sinh(x)},% \operatorname{csch}(x)=\frac{1}{\sinh(x)}$ . These functions are related by the identity $\cosh^{2}(x)-\sinh^{2}(x)=1$ . We also note the parity of the basic functions: $\cosh(x)$ is an even function, while $\sinh(x)$ is an odd function.

The function $\frac{\sinh(x)}{x}$ will appear often in the proofs, so we list a few of its properties below. Throughout, we let $\frac{\sinh 0}{0}=\lim_{x\to 0}\frac{\sinh(x)}{x}=1$ for convenience.

Lemma 9.

$\frac{\sinh x}{x}$ is strictly increasing for $x\in[0,\infty)$ .

Proof.

We have $\frac{d\frac{\sinh x}{x}}{dx}=\frac{x\cosh x-\sinh x}{x^{2}}=\frac{\sinh x% \left(\coth x-\frac{1}{x}\right)}{x}$ . It is well known that $\tanh(x)<x$ for all $x>0$ . (See e.g. [30].) Thus, $x,\sinh x$ and $\coth(x)-1/x$ are all positive for $x>0$ . $\hfill\blacktriangleleft$

Lemma 10.

$\phi(x)=\log\left(\frac{\sinh x}{x}\right)$ is strictly convex and superadditive for $x\in[0,\infty)$ .

Proof.

First, we compute the derivatives of $\phi(x)=\log(\sinh x)-\log x$ .

	$\displaystyle\phi^{\prime}(x)$	$\displaystyle=\frac{\cosh x}{\sinh x}-\frac{1}{x}=\coth x-\frac{1}{x}$
	$\displaystyle\phi^{\prime\prime}(x)$	$\displaystyle=-\operatorname{csch}^{2}x+\frac{1}{x^{2}}=\frac{1}{x^{2}}-\frac{% 1}{\sinh^{2}x}$

Since $\sinh x>x$ for all $x>0$ (which follows from Lemma 9), we have $\phi^{\prime\prime}(x)>0$ .

To prove superadditivity, since $\phi$ is convex, $\phi^{\prime}$ is increasing. For $y\geq 0$ , let $H(x)=\phi(x+y)-\phi(x)$ . Then, $H^{\prime}(x)=\phi^{\prime}(x+y)-\phi^{\prime}(x)\geq 0$ , so $H(x)$ is increasing. Thus, for any $x\geq 0$ , $H(x)\geq H(0)$ , which implies that $\phi(x+y)\geq\phi(x)+\phi(y)-\phi(0)=\phi(x)+\phi(y)$ as desired. $\hfill\blacktriangleleft$ What follows is a simple lemma which allows us to leverage concavity of the Rényi curve.

Lemma 11.

Let $f(x)$ be concave and differentiable on the domain $[1,\infty)$ . If $f^{\prime}(1)\leq f(1)$ , then $g(x)=f(x)/x$ is maximized at $x=1$ .

Proof.

It suffices to show $g^{\prime}(x)=\frac{xf^{\prime}(x)-f(x)}{x^{2}}\leq 0\iff h(x)=xf^{\prime}(x)-% f(x)\leq 0$ . This holds, as $h(1)=f^{\prime}(1)-f(1)\leq 0$ by construction, and $h^{\prime}(x)=xf^{\prime\prime}(x)\leq 0$ by concavity. $\hfill\blacktriangleleft$

3 Central DP Mechanisms

In this section, we derive the tight zCDP bounds for Laplace and discrete Laplace mechanisms. In both cases, we show that the tight zCDP bound occurs when $\alpha\to 1^{+}$ .

3.1 Laplace Mechanism

The Laplace mechanism was the first mechanism proposed alongside the definition of differential privacy in [8]. For any function $g:\mathcal{X}^{n}\to\mathbb{R}$ , it simply works by outputting $g(x)+Z$ where $Z\sim\operatorname{Lap}(\Delta(g)/\varepsilon)$ . This mechanism achieves $\varepsilon$ -DP.

In the work proposing RDP [23], Mironov showed that the Laplace mechanism is tightly- $(\alpha,\hat{\varepsilon}(\alpha))$ -RDP for $\alpha>1$ where

\hat{\varepsilon}_{L}(\alpha)=\frac{1}{\alpha-1}\log\left(\frac{\alpha}{2% \alpha-1}e^{(\alpha-1)/\lambda}+\frac{\alpha-1}{2\alpha-1}e^{-\alpha/\lambda}\right)

and $\lambda=\frac{\Delta(g)}{\varepsilon}$ . Given the above bound, it has been conjectured [29] that the tight zCDP bound occurs when $\alpha\to 1$ , which yields $\lim_{\alpha\to 1}\hat{\varepsilon}(\alpha)=\varepsilon+e^{-\varepsilon}-1$ . However, the proof of such a statement has never been published. Below we give a proof of this conjecture.

Theorem 12 (zCDP for Laplace).

The $\varepsilon$ -DP Laplace mechanism is tightly- $(\varepsilon+e^{-\varepsilon}-1)$ -zCDP.

Proof.

We start by showing that the mechanism is $(\varepsilon+e^{-\varepsilon}-1)$ -zCDP. From the aforementioned RDP bound, our goal is to prove that

f(\varepsilon)=(\varepsilon+e^{-\varepsilon}-1)-\frac{1}{\alpha}\cdot\hat{% \varepsilon}_{L}(\alpha)=(\varepsilon+e^{-\varepsilon}-1)-\frac{1}{\alpha(% \alpha-1)}\log\left(\frac{\alpha}{2\alpha-1}e^{(\alpha-1)\varepsilon}+\frac{% \alpha-1}{2\alpha-1}e^{-\alpha\varepsilon}\right)

is non-negative for all $\varepsilon>0$ and $\alpha>1$ . To do this, it suffices to argue that $f(0)=0$ and $f^{\prime}(\varepsilon)\geq 0$ for $x>0$ . Simple calculation confirms that $f(0)=0$ , and that

\displaystyle f^{\prime}(\varepsilon)

\displaystyle=(1-e^{-\varepsilon})-\frac{e^{(\alpha-1)\varepsilon}-e^{-\alpha% \varepsilon}}{\alpha e^{(\alpha-1)\varepsilon}+(\alpha-1)e^{-\alpha\varepsilon}}

\displaystyle=\frac{2e^{\alpha\varepsilon}\alpha(\alpha-1)\varepsilon\left(% \frac{\sinh(\alpha\varepsilon)}{\alpha\varepsilon}-\frac{\sinh((\alpha-1)% \varepsilon)}{(\alpha-1)\varepsilon}\right)}{(\alpha-1)e^{\varepsilon}+\alpha e% ^{2\alpha\varepsilon}},

which is non-negative due to Lemma 9. Finally, the bound is tight as $\lim_{\alpha\to 1}\hat{\varepsilon}(\alpha)=\varepsilon+e^{-\varepsilon}-1$ . $\hfill\blacktriangleleft$

3.2 Discrete Laplace

When the range of $g$ is integers, the Laplace mechanism can be improved by using the discrete Laplace (aka Geometric) mechanism [16]. In particular, for $g:\mathcal{X}^{n}\to\mathbb{Z}$ , the $\varepsilon$ -DP discrete Laplace mechanism outputs $g(x)+Z$ where $Z\sim\operatorname{DLap}(\varepsilon/\Delta(g))$ . The privacy profile of this mechanism depends on the value of the sensitivity, $\Delta(g)$ . Thus, our bound depends on $\Delta:=\Delta(g)$ as well. We state its tight bound for zCDP below.

Theorem 13 (zCDP of discrete Laplace).

The $\varepsilon$ -DP discrete Laplace mechanism for sensitivity $\Delta$ is tightly- $\left(\varepsilon\left(1-\frac{(1-e^{-\varepsilon})\operatorname{csch}(% \varepsilon/\Delta)}{\Delta}\right)\right)$ -zCDP.

Before we prove the above, let us first remark that, when $\Delta=1$ , Theorem 13 yields the bound of $\varepsilon\cdot\tanh(\varepsilon/2)$ , matching the worst case bound for $\varepsilon$ -DP algorithm in Proposition 8. This is as expected, since the privacy loss distribution³³3See e.g. [3] for the definition of privacy loss distributions (PLDs) and derivations of PLDs for discrete Laplace and Randomized Response. of the $\varepsilon$ -DP discrete Laplace mechanism for $\Delta=1$ coincides with the $\varepsilon$ -DP binary Randomized Response, which is known to be the worst case $\varepsilon$ -DP mechanism in terms of its zCDP guarantee.

On the other hand, if we take $\Delta\to\infty$ , then we have $\lim_{\Delta\to\infty}\left(\varepsilon\left(1-\frac{(1-e^{-\varepsilon})% \operatorname{csch}(\varepsilon/\Delta)}{\Delta}\right)\right)=\varepsilon+e^{% -\varepsilon}-1$ , which coincides with the zCDP bound of the Laplace mechanism (Theorem 12). Again, this is expected since the behavior of discrete Laplace mechanism more closely resembles the Laplace mechanism as $\Delta\to\infty$ .

3.2.1 RDP Bound Derivation

We will next prove Lemma 15. We start by directly computing the Rényi divergence between the discrete Laplace distribution and its shift, as stated below.

Proposition 14.

Let $Z\sim\operatorname{DLap}(a)$ and $d\in\mathbb{Z}_{\geq 0}$ , then

	$\displaystyle\mathrm{D}_{\alpha}\left(Z+d\ \middle\\|\ Z\right)=\mathrm{D}_{% \alpha}\left(Z\ \middle\\|\ Z+d\right)$
	$\displaystyle\qquad=\frac{1}{\alpha-1}\log\left(\tanh(a/2)\left(\frac{e^{-a% \alpha d}}{e^{a}-1}+\frac{e^{a-a\alpha d}-e^{a(\alpha(d+2)-d)}}{e^{a}-e^{2a% \alpha}}+\frac{e^{-a(1-\alpha)d}}{e^{a}-1}\right)\right)$

Proof.

We can compute $\mathrm{D}_{\alpha}\left(Z+d\ \middle\|\ Z\right)$ directly as follows.

	$\displaystyle e^{(\alpha-1)\mathrm{D}_{\alpha}\left(Z+d\ \middle\\|\ Z\right)}=% \sum_{x=-\infty}^{\infty}f_{\operatorname{DLap}(a)}(x-d)^{\alpha}\cdot f_{% \operatorname{DLap}(a)}(x)^{1-\alpha}$
	$\displaystyle=\sum_{x=-\infty}^{\infty}(\tanh(a/2)e^{-a\|x-d\|})^{\alpha}\cdot(% \tanh(a/2)e^{-a\|x\|})^{1-\alpha}$
	$\displaystyle=\tanh(a/2)\sum_{x=-\infty}^{\infty}e^{-a(\alpha\|x-d\|+(1-\alpha)\|% x\|)}$
	$\displaystyle=\tanh(a/2)\left(\left(\sum_{x=-\infty}^{-1}e^{a(x-\alpha d)}% \right)+\left(\sum_{x=0}^{d}e^{a((2\alpha-1)x-\alpha d)}\right)+\left(\sum_{x=% d+1}^{\infty}e^{a(\alpha d-x)}\right)\right)$
	$\displaystyle=\tanh(a/2)\left(\frac{e^{-a\alpha d}}{e^{a}-1}+\frac{e^{a-a% \alpha d}-e^{a(\alpha(d+2)-d)}}{e^{a}-e^{2a\alpha}}+\frac{e^{-a(1-\alpha)d}}{e% ^{a}-1}\right).$

Finally, $\mathrm{D}_{\alpha}\left(Z+d\ \middle\|\ Z\right)=\mathrm{D}_{\alpha}\left(Z\ % \middle\|\ Z+d\right)$ is due to the symmetry of $\operatorname{DLap}$ around zero. $\hfill\blacktriangleleft$

We can now prove the RDP bound by showing that the worst case occurs when $d=\Delta$ .

Lemma 15 (RDP of discrete Laplace).

The $\varepsilon$ -DP discrete Laplace mechanism for sensitivity $\Delta$ is tightly- $(\alpha,\hat{\varepsilon}_{D}(\alpha;\Delta))$ -RDP for all $\alpha>1$ where

\displaystyle\hat{\varepsilon}_{D}(\alpha;\Delta)=\frac{1}{\alpha-1}\log\left(% \tanh(a/2)\left(\frac{e^{-a\alpha\Delta}}{e^{a}-1}+\frac{e^{a-a\alpha\Delta}-e% ^{a(\alpha(\Delta+2)-\Delta)}}{e^{a}-e^{2a\alpha}}+\frac{e^{-a(1-\alpha)\Delta% }}{e^{a}-1}\right)\right)

with $a=\varepsilon/\Delta$ .

Proof.

Let $f(d)=\frac{e^{-a\alpha d}}{e^{a}-1}+\frac{e^{a-a\alpha d}-e^{a(\alpha(d+2)-d)}% }{e^{a}-e^{2a\alpha}}+\frac{e^{-a(1-\alpha)d}}{e^{a}-1}$ . Notice that we have

	$\displaystyle f^{\prime}(d)$	$\displaystyle=\frac{-a\alpha e^{-a\alpha d}}{e^{a}-1}+\frac{-a\alpha e^{a-a% \alpha d}-a(\alpha-1)e^{a(\alpha(d+2)-d)}}{e^{a}-e^{2a\alpha}}+\frac{a\alpha e% ^{-a(1-\alpha)d}}{e^{a}-1}$
		$\displaystyle=\frac{a\alpha(e^{a(\alpha-1)d}-e^{-a\alpha d})}{e^{a}-1}+\frac{a% \alpha e^{a-a\alpha d}+a(\alpha-1)e^{a(\alpha(d+2)-d)}}{e^{2a\alpha}-e^{a}},$

which is term-by-term non-negative. Thus, $f$ is an increasing function in $d$ .

Let $Z\sim\operatorname{DLap}(a)$ . For any function $g$ and neighboring inputs $x,x^{\prime}$ , we have

\displaystyle\mathrm{D}_{\alpha}\left(g(x)+Z\ \middle\|\ g(x^{\prime})+Z\right% )=\mathrm{D}_{\alpha}\left(|g(x)-g(x^{\prime})|+Z\ \middle\|\ Z\right)\leq% \mathrm{D}_{\alpha}\left(\Delta+Z\ \middle\|\ Z\right)=\hat{\varepsilon}_{D}(% \alpha;\Delta),

where the inequality holds since $f$ is increasing. Thus, the mechanism is $(\alpha,\hat{\varepsilon}_{D}(\alpha;\Delta))$ -RDP.

The tightness follows from considering any $x,x^{\prime}$ such that $|g(x)-g(x^{\prime})|=\Delta$ . $\hfill\blacktriangleleft$

3.2.2 From RDP to zCDP

Proof of Theorem 13.

Consider the following as a function of $\Delta$ ,

\displaystyle f(\Delta)=a(\Delta+\left(e^{-a\Delta}-1\right)\operatorname{csch% }(a))-\hat{\varepsilon}_{D}(\alpha;\Delta)/\alpha.

The upper bound follows from showing that $f(\Delta)\geq 0$ for all $\Delta\geq 1,a>0,\alpha>1$ . Recall $\hat{\varepsilon}$ from Proposition 7. Observe that $f(1)=\varepsilon\cdot\tanh(\varepsilon/2)-\frac{\hat{\varepsilon}(\alpha)}{\alpha}$ , which is non-negative due to Proposition 8. Thus, to show that $f(\Delta)\geq 0$ for all $\Delta\geq 1$ , it suffices to show that $f^{\prime}(\Delta)$ is non-negative for all $\Delta\geq 1$ .

It will be helpful for us to write out the first and second derivative of $f$ with respect to $\Delta$ :

	$\displaystyle f^{\prime}(\Delta)=\frac{a\left(\frac{(2\alpha-1)\left(e^{2a% \alpha}-1\right)e^{2\alpha a\Delta+a}}{\alpha\left(-e^{a(2\alpha+\Delta)}+e^{2% \alpha a\Delta+a}-e^{2\alpha a(\Delta+1)+a}+e^{a(\Delta+2)}\right)}-a(\alpha-1% )e^{-a\Delta}\operatorname{csch}(a)+\alpha\right)}{\alpha-1},$
	$\displaystyle f^{\prime\prime}(\Delta)=a^{2}\Bigg(-\frac{(1-2\alpha)^{2}\left(% e^{2a\alpha}-e^{2a}\right)\left(e^{2a\alpha}-1\right)e^{a\Delta+a}}{(\alpha-1)% \alpha\left(e^{a(-\alpha\Delta+\Delta+2)}-e^{a(\alpha(-\Delta)+2\alpha+\Delta)% }+e^{\alpha a\Delta+a}-e^{\alpha a(\Delta+2)+a}\right)^{2}}$
	$\displaystyle\qquad\qquad\qquad\qquad+ae^{-a\Delta}\operatorname{csch}(a)\Bigg).$		(1)

To show that $f^{\prime}(\Delta)$ is always non-negative for $\Delta\geq 1$ , we will first show that $f^{\prime}(1)\geq 0$ , and then show $f^{\prime\prime}(\Delta)\geq 0$ for $\Delta\geq 1$ .

Proof of Non-negativity of $f^{\prime}(1)$ .

Note that

f^{\prime}(1)=a\left(-\frac{1}{\alpha}\cdot\frac{(\alpha-1)e^{4a\alpha}+e^{2a}% \alpha+(1-2\alpha)e^{2a\alpha}}{(\alpha-1)\left(e^{4a\alpha}-e^{2a}\right)}+a-% a\coth(a)+1\right).

It is simple to check that $\lim_{\alpha\to 1^{+}}f^{\prime}(1)=0$ . Thus, it suffices for us to show that a $f^{\prime}(1)$ is increasing in $\alpha$ . Since $\frac{1}{\alpha}$ is decreasing in $\alpha$ and $a-a\coth(a)+1$ is a constant (w.r.t. to $\alpha$ ), it in turn suffices for us to prove that $\frac{(\alpha-1)e^{4a\alpha}+e^{2a}\alpha+(1-2\alpha)e^{2a\alpha}}{(\alpha-1)% \left(e^{4a\alpha}-e^{2a}\right)}$ is decreasing in $\alpha$ . We can rearrange this terms as follows:

	$\displaystyle\frac{(\alpha-1)e^{4a\alpha}+e^{2a}\alpha+(1-2\alpha)e^{2a\alpha}% }{(\alpha-1)\left(e^{4a\alpha}-e^{2a}\right)}$	$\displaystyle=1-\frac{(2\alpha-1)\left(e^{2a\alpha}-e^{2a}\right)}{(\alpha-1)% \left(e^{4a\alpha}-e^{2a}\right)}$
		$\displaystyle=1-e^{-a\alpha}\cdot\frac{(2\alpha-1)\sinh(a\cdot\alpha-a)}{(% \alpha-1)\sinh(2a\cdot\alpha-a)}$
		$\displaystyle=1-e^{-a\alpha+\phi(a(\alpha-1))-\phi(a(2\alpha-1))},$

where $\phi$ is defined in Lemma 10 as $\phi(x)=\log\left(\frac{\sinh(x)}{x}\right)$ .

Thus, it suffices to show that $-a\alpha+\phi(a(\alpha-1))-\phi(a(2\alpha-1))$ is decreasing in $\alpha$ . To see this, notice that its derivative (in $\alpha$ ) is

\displaystyle-a+a\phi^{\prime}(a(\alpha-1))-2a\phi^{\prime}(a(2\alpha-1))\leq-% a-a\phi^{\prime}(a(2\alpha-1))\leq 0,

where the first inequality follows from the convexity of $\phi$ (Lemma 10) and the second is from $\phi$ is increasing (Lemma 9). Hence, we have concluded our proof that $f^{\prime}(1)\geq 0$ (for all $\alpha>1,a>0$ ).

Proof of Non-negativity of $f^{\prime\prime}(\Delta)$ .

To show non-negativity of $f^{\prime\prime}(\Delta)$ , we will compare the log ratio of the two terms within the parenthesis in (1). Denote this quantity by

p(\Delta)=\log\frac{ae^{-a\Delta}\operatorname{csch}(a)}{-\frac{(1-2\alpha)^{2% }\left(e^{2a\alpha}-e^{2a}\right)\left(e^{2a\alpha}-1\right)e^{a\Delta+a}}{(% \alpha-1)\alpha\left(e^{a(-\alpha\Delta+\Delta+2)}-e^{a(\alpha(-\Delta)+2% \alpha+\Delta)}+e^{\alpha a\Delta+a}-e^{\alpha a(\Delta+2)+a}\right)^{2}}}.

To prove $f^{\prime\prime}(\Delta)\geq 0$ , it suffices to prove $p(\Delta)\geq 0$ for all $\Delta\geq 1$ . For the latter, it in turn suffices to prove that $p(1)\geq 0$ and $p^{\prime\prime}(\Delta)\geq 0$ for all $\Delta\geq 1$ . To do this, let us first write out the relevant expressions:

	$\displaystyle p(1)$	$\displaystyle=\log\left(\frac{a(\alpha-1)\alpha\operatorname{csch}(a)\sinh^{2}% (a-2a\alpha)\operatorname{csch}(a\alpha)\operatorname{csch}(a\alpha-a)}{(1-2% \alpha)^{2}}\right)$
	$\displaystyle p^{\prime}(\Delta)$	$\displaystyle=\frac{2a(2\alpha-1)\left(e^{2a\alpha}-1\right)e^{2\alpha a\Delta% +a}}{e^{a(2\alpha+\Delta)}-e^{2\alpha a\Delta+a}+e^{2\alpha a(\Delta+1)+a}-e^{% a(\Delta+2)}}-2a\alpha$

We can rewrite $p(1)$ as follows:

$\displaystyle p(1)$	$\displaystyle=\log\left(\frac{a(\alpha-1)\alpha\operatorname{csch}(a)\sinh^{2}% (a-2a\alpha)\operatorname{csch}(a\alpha)\operatorname{csch}(a\alpha-a)}{(1-2% \alpha)^{2}}\right)$
	$\displaystyle=2\phi((2\alpha-1)a)-\phi((\alpha-1)a)-\phi(a\alpha)-\phi(a)$
	$\displaystyle=\left(\phi((2\alpha-1)a)-\phi((\alpha-1)a)-\phi(a\alpha)\right)+% \left(\phi((2\alpha-1)a)-\phi(a)\right)$	$\displaystyle\geq 0,$

where the inequality is from the fact that $\phi$ is super-additive (Lemma 10) and increasing (Lemma 9).

As for $p^{\prime}(\Delta)$ , we have

\displaystyle p^{\prime}(\Delta)

\displaystyle=\frac{2a(2\alpha-1)\left(e^{2a\alpha}-1\right)e^{2\alpha a\Delta% +a}}{e^{a\Delta}(e^{2a\alpha}-e^{2a})+e^{a(2\alpha\Delta+1)}(e^{2a\alpha}-1)}-% 2a\alpha

Dividing this expression by $2a$ and rearranging, we have

	$\displaystyle p^{\prime}(\Delta)\geq 0$	$\displaystyle\iff(\alpha-1)e^{a(2\alpha\Delta+1)}(e^{2a\alpha}-1)\geq\alpha e^% {a\Delta}(e^{2a\alpha}-e^{2a})$
		$\displaystyle\iff e^{a(2\alpha-1)\Delta}\cdot\frac{\sinh(a\alpha)}{a\alpha}% \geq\frac{\sinh((\alpha-1)a)}{(\alpha-1)a},$

which is true because $a(2\alpha-1)\Delta>0$ and $\frac{\sinh x}{x}$ is increasing (Lemma 9).

Altogether, the above argument shows that $f(\Delta)\geq 0$ for all $\Delta\geq 1$ . In other words, the $\varepsilon$ -DP discrete Laplace mechanism is $a(\Delta+\left(e^{-a\Delta}-1\right)\operatorname{csch}(a))$ -zCDP

Tightness of the bound follows from the tightness in Lemma 15 by taking $\alpha\to 1^{+}$ . $\hfill\blacktriangleleft$

4 Local DP Mechanisms

We next move on towards local DP mechanisms [19] where the randomizer is now run on a single data point (i.e. $n=1$ in Definitions 1 and 3). We consider two popular local DP mechanisms: $k$ -Randomized Response and RAPPOR.

5 $𝒌$ -Randomized Response

The $k$ -Randomized Response ( $k$ -RR) mechanism [18] takes as input a number in $[k]:=\{1,\dots,k\}$ outputs its input with probability $p=\frac{e^{\varepsilon}}{e^{\varepsilon}+k-1}$ , and a uniformly random other output symbol with probability $1-p$ . (Note that under the notions of Definitions 1 and 3, both the domain $\mathcal{X}$ and the range $\mathcal{Y}$ are $[k]$ .)

We prove that the tight zCDP bound is obtained at $\alpha\to 1$ for $2\leq k\leq 6$ :

Theorem 16.

The $\varepsilon$ -DP $k$ -RR mechanism is tightly- $\left(\varepsilon\cdot\frac{e^{\varepsilon}-1}{e^{\varepsilon}+k-1}\right)$ -zCDP for $2\leq k\leq 6$ .

Interestingly, the condition on $k$ is necessary, as we show below that for any $\varepsilon>0$ and any sufficiently large $k>k^{*}(\varepsilon)$ , the tight bound is not obtained at $\alpha\to 1$ . The bound $k^{*}(\varepsilon)$ satisfies $\lim_{\varepsilon\to 1}k^{*}(\varepsilon)=6$ ; thus, 6 in Theorem 16 is the best possible value one can hope for.

Lemma 17.

For all $\varepsilon>0$ and $k>k^{*}(\varepsilon):=\frac{2\left(e^{\varepsilon}-1\right)\left(e^{% \varepsilon}-1-\varepsilon\right)}{\varepsilon(e^{\varepsilon}+1)-2e^{% \varepsilon}+2}$ , the $\varepsilon$ -DP $k$ -RR mechanism is not $\left(\varepsilon\cdot\frac{e^{\varepsilon}-1}{e^{\varepsilon}+k-1}\right)$ -zCDP.

Finally, we also obtain zCDP bounds for the case $k>6$ . First, we note that since the RDP curve (see Proposition 20) is clearly decreasing in $k$ , the zCDP bound must too. Thus, we immediately obtain the following as a corollary of Theorem 16.

Corollary 18.

The $\varepsilon$ -DP $k$ -RR mechanism is $\left(\varepsilon\cdot\frac{e^{\varepsilon}-1}{e^{\varepsilon}-1+\min(k,6)}\right)$ -zCDP.

An undesirable aspect of the above corollary is that the bound does not converge to 0 as $k\to\infty$ . As such, we derive a bound with such behavior below. (Note that as $k\to\infty$ , the zCDP bound below becomes $O\left(\frac{\varepsilon^{2}}{\log k}\right)$ .)

Theorem 19.

The $\varepsilon$ -DP $k$ -RR mechanism is $\varepsilon^{2}\cdot\max\left\{\frac{1}{\log\left(\frac{1}{\varepsilon}\sqrt{k% -1+e^{\varepsilon}}\right)},\frac{1}{\sqrt{k-1+e^{\varepsilon}}}\right\}$ -zCDP.

We stress that the bounds in Corollary 18 and Theorem 19 are not tight and it remains an interesting question to obtain tight bounds for these regimes of parameters.

5.1 RDP Bound Derivation

We start by computing the tight bounds for RDP guarantees of $k$ -RR.

Proposition 20.

The $\varepsilon$ -DP $k$ -RR mechanism is tightly- $(\alpha,\hat{\varepsilon}(\alpha))$ -RDP for all $\alpha>1$ where

\displaystyle\hat{\varepsilon}_{RR}(\alpha)

\displaystyle=\frac{1}{\alpha-1}\log\left(\frac{e^{\alpha\varepsilon}+e^{(1-% \alpha)\varepsilon}+k-2}{k-1+e^{\varepsilon}}\right).

Furthermore, we have $\hat{\varepsilon}_{RR}(1):=\lim_{\alpha\to 1}\hat{\varepsilon}_{RR}(\alpha)$ is equal to $\varepsilon\cdot\frac{e^{\varepsilon}-1}{e^{\varepsilon}-1+k}$ .

Proof.

Without loss of generality (due to symmetry), it suffices to consider distributions $P$ and $Q$ , which are the distribution of the mechanism’s output on the first symbol and second symbol, respectively. Let $p=\frac{e^{\varepsilon}}{k-1+e^{\varepsilon}}$ and $q=\frac{1}{k-1+e^{\varepsilon}}$ , then

	$\displaystyle e^{(\alpha-1)\hat{\varepsilon}_{RR}(\alpha)}=e^{(\alpha-1)% \mathrm{D}_{\alpha}\left(P\ \middle\\|\ Q\right)}=\sum_{x\in X}f_{P}(x)^{\alpha% }f_{Q}(x)^{1-\alpha}$	$\displaystyle=p^{\alpha}q^{1-\alpha}+q^{\alpha}p^{1-\alpha}+(k-2)q$
		$\displaystyle=\frac{e^{\alpha\varepsilon}+e^{(1-\alpha)\varepsilon}+k-2}{k-1+e% ^{\varepsilon}}.$

$\hat{\varepsilon}_{RR}(1)$ can be computed by a simple application of L’Hôpital’s Rule. $\hfill\blacktriangleleft$

5.2 From RDP to zCDP

A tight zCDP bound for $k$ -RR is difficult in general, because the RDP curve is not always concave in $\alpha$ . We derive tight bounds in the cases where the curve is concave.

Proof of Theorem 16.

We will show the following two properties of $\hat{\varepsilon}_{RR}$ (assuming that $2\leq k\leq 6$ )⁴⁴4It is straightforward to improve upon Theorem 16 and Corollary 18 with the current proof technique by taking more complex constraints on $k$ . We omit this for sake of presentation, but it allows extending the tightness bound for moderate $k>6$ .: (A) $\lim_{\alpha\to 1^{+}}\hat{\varepsilon}_{RR}(\alpha)=\hat{\varepsilon}(1)$ , and (B), $\hat{\varepsilon}^{\prime\prime}(\alpha)\leq 0$ for all $\alpha>1$ . (i.e. concavity).

From Lemma 11, these two properties imply that $\frac{\hat{\varepsilon}_{RR}(\alpha)}{\alpha}\leq\hat{\varepsilon}_{RR}(1)$ for all $\alpha>1$ . In other words, the mechanism is $\hat{\varepsilon}_{RR}(1)$ -zCDP. The tightness also follow immediately from the tightness of the RDP curve (and taking $\alpha\to 1$ ).

Thus, we are left to prove (A), (B).

Proof of (A).

Define $H(\alpha)=\log(e^{(1-\alpha)\varepsilon}+e^{\alpha\varepsilon}+k-2)$ . The RDP curve for $k$ -RR can be written as $\hat{\varepsilon}_{RR}(\alpha)=\frac{H(\alpha)-H(1)}{\alpha-1}$ . The first derivative of $\hat{\varepsilon}_{RR}$ is

\displaystyle\hat{\varepsilon}^{\prime}(\alpha)

\displaystyle=\frac{(\alpha-1)H^{\prime}(\alpha)-H(\alpha)+H(1)}{(\alpha-1)^{2% }}.

Applying L’Hôpital’s Rule, we get

\displaystyle\lim_{\alpha\to 1}\hat{\varepsilon}^{\prime}_{RR}(\alpha)=\lim_{% \alpha\to 1}\frac{H^{\prime\prime}(\alpha)}{2}

\displaystyle=\frac{\varepsilon^{2}\left((k+2)e^{\varepsilon}+k-2\right)}{2% \left(k+e^{\varepsilon}-1\right)^{2}}.

Thus,

	$\displaystyle\lim_{\alpha\to 1^{+}}\hat{\varepsilon}^{\prime}_{RR}(\alpha)\leq% \hat{\varepsilon}_{RR}(1)$	$\displaystyle\iff\frac{\varepsilon^{2}\left((k+2)e^{\varepsilon}+k-2\right)}{2% \left(k+e^{\varepsilon}-1\right)^{2}}\leq\varepsilon\frac{e^{\varepsilon}-1}{e% ^{\varepsilon}-1+k}$
		$\displaystyle\iff k\leq\frac{2\left(e^{\varepsilon}-1\right)\left(e^{% \varepsilon}-1-\varepsilon\right)}{\varepsilon(e^{\varepsilon}+1)-2e^{% \varepsilon}+2}$		(2)

We conclude by noting this constraint is satisfied when $k\leq 6$ , i.e. the RHS of (2) is at least 6. To see this, consider the Taylor’s expansion of 6 times the denominator, we have

	$\displaystyle 6\left(\varepsilon(e^{\varepsilon}+1)-2e^{\varepsilon}+2\right)$	$\displaystyle=6\left((e^{\varepsilon}-1-\varepsilon)\varepsilon-2\left(e^{% \varepsilon}-1-\varepsilon-\frac{\varepsilon^{2}}{2}\right)\right)$
		$\displaystyle=6\left(\left(\sum_{i=2}^{\infty}\frac{\varepsilon^{i}}{i!}\right% )\cdot\varepsilon-2\left(\sum_{i=3}^{\infty}\frac{\varepsilon^{i}}{i!}\right)\right)$
		$\displaystyle=\left(\varepsilon^{2}\right)\cdot\left(\sum_{i=1}^{\infty}% \varepsilon^{i}\cdot 6\left(\frac{1}{(i+1)!}-\frac{2}{(i+2)!}\right)\right)$
		$\displaystyle=\left(\varepsilon^{2}\right)\cdot\left(\sum_{i=1}^{\infty}\frac{% \varepsilon^{i}}{i!}\cdot\frac{6i}{(i+1)(i+2)}\right)$
		$\displaystyle\leq\left(2\sum_{i=2}^{\infty}\frac{\varepsilon^{i}}{i!}\right)% \left(\sum_{i=1}^{\infty}\frac{\varepsilon^{i}}{i!}\right)\qquad=2\left(e^{% \varepsilon}-1-\varepsilon\right)\left(e^{\varepsilon}-1\right),$

where the inequality is true term-by-term. Thus, (2) always holds for $k\leq 6.$

Proof of (B).

The second derivative of $\hat{\varepsilon}_{RR}$ is

\displaystyle\hat{\varepsilon}^{\prime\prime}_{RR}(\alpha)=\frac{(\alpha-1)^{2% }H^{\prime\prime}(\alpha)-2(\alpha-1)H^{\prime}(\alpha)+2H(\alpha)-2H(1)}{(% \alpha-1)^{3}}.

Let $\psi(\alpha)$ denote the numerator of $\hat{\varepsilon}^{\prime\prime}_{RR}(\alpha)$ above. To show that $\hat{\varepsilon}^{\prime\prime}_{RR}(\alpha)\geq 0$ , it suffices to show that $\psi(\alpha)\geq 0$ for all $\alpha>1$ . Observe that $\lim_{\alpha\to 1^{+}}\psi(\alpha)=0$ . Thus, to prove the non-negativity of $\psi(\alpha)$ , it in turn suffices to show that $\psi^{\prime}(\alpha)\leq 0$ for all $\alpha>1$ .

To show this, note that $\psi^{\prime}(\alpha)=H^{\prime\prime\prime}(\alpha)(\alpha-1)^{2}$ , so the sign of $\psi^{\prime}(\alpha)$ is determined by the sign of

H^{\prime\prime\prime}(\alpha)=\frac{\varepsilon^{3}\left(e^{\varepsilon-% \alpha\varepsilon}-e^{\alpha\varepsilon}\right)\left((k-2)e^{\alpha\varepsilon% }+(k-2)e^{\varepsilon-\alpha\varepsilon}-(k-2)^{2}+8e^{\varepsilon}\right)}{% \left(e^{\alpha\varepsilon}+e^{\varepsilon-\alpha\varepsilon}+k-2\right)^{3}},

which is non-positive if the last term in the numerator is non-negative (since all other terms but $\left(e^{\varepsilon-\alpha\varepsilon}-e^{\alpha\varepsilon}\right)$ are non-negative). It is clear that this last term is increasing in $\varepsilon\in[0,\infty)$ . This means that

\displaystyle(k-2)e^{\alpha\varepsilon}+(k-2)e^{\varepsilon-\alpha\varepsilon}% -(k-2)^{2}+8e^{\varepsilon}\geq(k-2)+(k-2)-(k-2)^{2}+8=k(6-k),

which is non-negative for $k\leq 6$ . Thus, $H^{\prime\prime\prime}(\alpha)\leq 0$ , implying that $\hat{\varepsilon}^{\prime\prime}_{RR}(\alpha)$ is concave. $\hfill\blacktriangleleft$

5.3 Non-Optimality of $\alpha=1$

The above proof also yields a rather simple criterion to certify that $\alpha=1$ is not the optimal for sufficiently large $k$ , as formalized below.

Proof of Lemma 17.

From (2), in this regime $\lim_{\alpha\to 1^{+}}\hat{\varepsilon}^{\prime}_{RR}(\alpha)>\hat{\varepsilon% }_{RR}(1)$ . Since $\frac{\hat{\varepsilon}^{\prime}_{RR}(\alpha)}{2\alpha-1}$ is continuous (in $\alpha$ ), there exists $\alpha_{0}>1$ such that $\frac{\hat{\varepsilon}^{\prime}_{RR}(\alpha)}{2\alpha-1}>\hat{\varepsilon}_{% RR}(1)$ for all $\alpha\in(1,\alpha)$ . Thus,

\displaystyle\hat{\varepsilon}_{RR}(\alpha_{0})-\alpha_{0}\cdot\hat{% \varepsilon}_{RR}(1)=\int_{1}^{\alpha_{0}}(\hat{\varepsilon}^{\prime}_{RR}(% \alpha)-\hat{\varepsilon}_{RR}(1))\mathrm{d}\alpha>0.

Thus, $\frac{\hat{\varepsilon}_{RR}(\alpha_{0})}{\alpha_{0}}>\hat{\varepsilon}_{RR}(1)$ , implying that the mechanism is not $\hat{\varepsilon}_{RR}(1)$ -zCDP. $\hfill\blacktriangleleft$

5.4 Loose zCDP for Large $𝒌$ Regime

Finally, we prove a loose bound that converges to zero as $k\to\infty$ via a commonly used approach of separately considering smaller and larger $\alpha$ .

Proof of Theorem 19.

Let $\rho=\varepsilon^{2}\cdot\max\left\{\frac{1}{\log\left(\varepsilon\sqrt{k-1+e^% {\varepsilon}}\right)},\frac{1}{\sqrt{k-1+e^{\varepsilon}}}\right\}$ and $\alpha^{*}=\frac{\varepsilon}{\rho}$ . Consider two cases based on the value of $\alpha$ :

$\blacksquare$

Case I: $\alpha\geq\alpha^{*}$ . In this case, we simply have $\frac{\hat{\varepsilon}_{RR}(\alpha)}{\alpha}\leq\frac{\varepsilon}{\alpha}\leq\rho$ , where the first inequality follows from the fact that any $\varepsilon$ -DP algorithm is $(\alpha,\varepsilon)$ -DP for all $\alpha>1$ .

\blacksquare

Case II: $\alpha<\alpha^{*}$ . In this case, we have

	$\displaystyle\frac{\hat{\varepsilon}(\alpha)}{\alpha}\leq\hat{\varepsilon}(\alpha)$	$\displaystyle=\frac{1}{\alpha-1}\cdot\log\left(\frac{e^{\alpha\varepsilon}+e^{% (1-\alpha)\varepsilon}+k-2}{k-1+e^{\varepsilon}}\right)$
		$\displaystyle\leq\frac{1}{\alpha-1}\cdot\left(\frac{e^{\alpha\varepsilon}+e^{(% 1-\alpha)\varepsilon}+k-2}{k-1+e^{\varepsilon}}-1\right)$
		$\displaystyle=\frac{1-e^{(1-\alpha)\varepsilon}}{\alpha-1}\cdot\frac{e^{\alpha% \varepsilon}-1}{k-1+e^{\varepsilon}}$
		$\displaystyle\leq\varepsilon\cdot\frac{e^{\alpha^{*}\varepsilon}}{k-1+e^{% \varepsilon}}\qquad=\varepsilon\cdot\frac{e^{\varepsilon^{2}/\rho}}{k-1+e^{% \varepsilon}}\leq\frac{\varepsilon^{2}}{\sqrt{k-1+e^{\varepsilon}}}\leq\rho.$

Thus, the mechanism is $\rho$ -zCDP as claimed. $\hfill\blacktriangleleft$

5.5 RAPPOR

Next, we consider the (basic) RAPPOR mechanism [13]. The mechanism takes input from $[d]$ and outputs a $d$ -bit string (i.e. $\mathcal{X}=[d],\mathcal{Y}=\{0,1\}^{d}$ in Definitions 1 and 3). It first encodes its input as a one-hot vector, and then flips each bit in the vector independently. To satisfy $\varepsilon$ -DP, its output distribution is

Pr[M(X)=x]=\prod_{i=1}^{d}\begin{cases}\frac{e^{\varepsilon/2}}{e^{\varepsilon% /2}+1}&\text{ if $\operatorname{hot}(X)_{i}=x_{i}$}\\ \frac{1}{e^{\varepsilon/2}+1}&\text{ if $\operatorname{hot}(X)_{i}\neq x_{i}$}% \\ \end{cases},

where $\operatorname{hot}(X)$ is the $d$ -length one-hot vector where the $X$ th entry is 1 and the rest are 0.

The tight RDP and zCDP bounds for RAPPOR follows almost immediately from those of Binary RR (from the previous section), as formalized below.

Proposition 21.

The $\varepsilon$ -DP RAPPOR mechanism is tightly- $(\alpha,\hat{\varepsilon}_{RAP}(\alpha))$ -RDP for all $\alpha>1$ where

\hat{\varepsilon}_{RAP}(\alpha)=\frac{2}{\alpha-1}\log\left(\frac{e^{\alpha% \varepsilon/2}+e^{(1-\alpha)\varepsilon/2}}{e^{\varepsilon/2}+1}\right).

Proof.

Without loss of generality (due to symmetry), it suffices to consider distributions $P$ and $Q$ , which are the distribution of the mechanism’s output on the first symbol and second symbol, respectively. Let $P_{i},Q_{i}$ denote the distributions of the $i$ -th coordinate of $P, Q$ respectively. Notice that $P, Q$ are product distributions, and that $P_{i}=Q_{i}$ for all $i\notin\{1,2\}$ . Thus, from additivity of Rényi divergence, we have

\displaystyle\hat{\varepsilon}_{RAP}(\alpha)=\mathrm{D}_{\alpha}\left(P\ % \middle\|\ Q\right)=\mathrm{D}_{\alpha}\left(P_{1}\ \middle\|\ Q_{1}\right)+% \mathrm{D}_{\alpha}\left(P_{2}\ \middle\|\ Q_{2}\right).

Finally, observe that $P_{i},Q_{i}$ for $i\in\{1,2\}$ are exactly the same distribution as that of the $(\varepsilon/2)$ -DP Binary RR. Thus, Proposition 20 implies the claimed bound. $\hfill\blacktriangleleft$

Proposition 22.

The $\varepsilon$ -DP RAPPOR mechanism is tightly- $\left(\varepsilon\cdot\tanh(\varepsilon/4)\right)$ -zCDP.

Proof.

This follows immediately from Theorem 16 since the RDP bound is exactly twice the RDP bound for $(\varepsilon/2)$ -DP Binary RR. $\hfill\blacktriangleleft$

6 $\eta$ -Bounded Range Mechanisms

Finally, we consider $\eta$ -Bounded Range ( $\eta$ -BR) mechanisms, and we prove a tight zCDP bound in this case as well.

Theorem 23.

Any $\eta$ -BR mechanism satisfies $\rho$ -CDP where $\rho=\frac{\eta}{e^{\eta}-1}+\log\left(\frac{e^{\eta}-1}{\eta}\right)-1.$ Furthermore, this is tight⁵⁵5Note that we do not use the terminology tightly- $(\alpha,\rho)$ -zCDP directly here, since “ $\eta$ -BR mechanisms” constitute a class of mechanisms rather than a single mechanism., i.e. there exists an $\eta$ -BR mechanism which is tightly- $\rho(\eta)$ -CDP.

6.1 RDP Bound Derivation

We start by proving the following lemma, which yields a bound for the Rényi divergence when given a parameter $t$ in Definition 5.

Lemma 24.

Let $t,\eta$ be real numbers such that $\eta>0$ and $0\leq t\leq\eta$ , and let $P$ and $Q$ be distributions such that $\log\left(\frac{P(x)}{Q(x)}\right)\in[-t,-t+\eta]$ for all $x\in\operatorname{supp}(P)\cup\operatorname{supp}(Q)$ . Then, for all $\alpha>1$ , we have

\mathrm{D}_{\alpha}\left(P\ \middle\|\ Q\right)\leq\frac{1}{\alpha-1}\log\left% (\frac{e^{\eta}-e^{t}}{e^{\eta}-1}e^{-t\alpha}+\frac{e^{t}-1}{e^{\eta}-1}e^{(-% t+\eta)\alpha}\right)=:\hat{\varepsilon}_{BR}(t;\alpha).

Moreover, there exist a pair of distributions $P, Q$ with $\log\left(\frac{P(x)}{Q(x)}\right)\in\{-t,-t+\eta\}$ for all $x\in\operatorname{supp}(P)\cup\operatorname{supp}(Q)$ such that the above inequality is an equality.

Proof.

We will first show achieveability of the bound by describing a pair of distributions $P$ and $Q$ . Define $P$ and $Q$ as follows:

\displaystyle f_{P}(x)=\begin{cases}\frac{e^{-t}\left(e^{\eta}-e^{t}\right)}{e% ^{\eta}-1}&\text{ if $x=0$}\\ \frac{\left(e^{t}-1\right)e^{\eta-t}}{e^{\eta}-1}&\text{ if $x=1$}\\ \end{cases},\qquad f_{Q}(x)=\begin{cases}\frac{e^{\eta}-e^{t}}{e^{\eta}-1}&% \text{ if $x=0$}\\ \frac{e^{t}-1}{e^{\eta}-1}&\text{ if $x=1$}\\ \end{cases}

It is easy to show that $P, Q$ are valid probability distributions, $\frac{f_{P}(0)}{f_{Q}(0)}=e^{-t}$ and $\frac{f_{P}(1)}{f_{Q}(1)}=e^{-t+\eta}$ as desired, and that the Rényi divergence is exactly equal to the required bound.

We next prove that this is the worst case bound, using a proof technique due to [1, 27]. Define the randomized rounding function $A:[e^{-t},e^{-t+\eta}]\to\{e^{-t},e^{-t+\eta}\}$ such that

\displaystyle\mathbb{P}(A(z)=e^{-t})=\frac{e^{\eta}-ze^{t}}{e^{\eta}-1},\qquad% \mathbb{P}(A(z)=e^{-t+\eta})=\frac{ze^{t}-1}{e^{\eta}-1}

This satisfies $\mathbb{E}[A(z)]=z$ . Thus, by Jensen’s inequality (and by the convexity of $x\mapsto x^{\alpha}$ ),

z^{\alpha}=\mathbb{E}[A(z)]^{\alpha}\leq\mathbb{E}[A(z)^{\alpha}]=\frac{e^{% \eta}-ze^{t}}{e^{\eta}-1}e^{-t\alpha}+\frac{ze^{t}-1}{e^{\eta}-1}e^{(-t+\eta)% \alpha}.

Consider any distributions $P$ and $Q$ such that $\log\left(\frac{P(x)}{Q(x)}\right)\in[-t,-t+\eta]$ for all $x\in\operatorname{supp}(P)\cup\operatorname{supp}(Q)$ . Setting $z=P(x)/Q(x)$ , we have

	$\displaystyle e^{(\alpha-1)\mathrm{D}_{\alpha}\left(P\ \middle\\|\ Q\right)}$	$\displaystyle=\mathbb{E}_{x\sim Q}\left[\left(\frac{P(x)}{Q(x)}\right)^{\alpha% }\right]$
		$\displaystyle\leq\mathbb{E}_{x\sim Q}\left[\frac{e^{\eta}-\frac{P(x)}{Q(x)}e^{% t}}{e^{\eta}-1}e^{-t\alpha}+\frac{\frac{P(x)}{Q(x)}e^{t}-1}{e^{\eta}-1}e^{(-t+% \eta)\alpha}\right]$
		$\displaystyle=\mathbb{E}_{x\sim Q}\left[\frac{e^{\eta}-\frac{P(x)}{Q(x)}e^{t}}% {e^{\eta}-1}e^{-t\alpha}\right]+\mathbb{E}_{x\sim Q}\left[\frac{\frac{P(x)}{Q(% x)}e^{t}-1}{e^{\eta}-1}e^{(-t+\eta)\alpha}\right]$
		$\displaystyle=\frac{e^{\eta}-e^{t}}{e^{\eta}-1}e^{-t\alpha}+\frac{e^{t}-1}{e^{% \eta}-1}e^{(-t+\eta)\alpha}.\$

$\hfill\blacktriangleleft$

The above lemma allows us to easily compute the tight RDP bound for $\eta$ -BR mechanism by optimizing over the value of $t$ .

Theorem 25 (RDP for Bounded Range Mechanisms).

Any $\eta$ -BR mechanism satisfies $(\alpha,\hat{\varepsilon}_{BR}(\alpha))$ -RDP for all $\alpha>1$ where

\displaystyle\hat{\varepsilon}_{BR}(\alpha)

\displaystyle=\frac{1}{\alpha-1}\log\left(\frac{(e^{\alpha\eta}-1)^{\alpha}% \left(\frac{\alpha(e^{\alpha\eta}-e^{\eta})}{\alpha-1}\right)^{1-\alpha}}{% \alpha(e^{\eta}-1)}\right).

Furthermore, the above bound is tight, i.e. there exists an $\eta$ -BR mechanism which is tightly- $(\alpha,\hat{\varepsilon}_{BR}(\alpha))$ -RDP. Moreover, $\hat{\varepsilon}_{BR}(1):=\lim_{\alpha\to 1}\hat{\varepsilon}_{BR}(\alpha)$ is equal to $\frac{\eta}{e^{\eta}-1}+\log\left(\frac{e^{\eta}-1}{\eta}\right)-1$ .

Proof.

From Lemma 24, any $\eta$ -BR mechanism is $(\alpha,\hat{\varepsilon}(\alpha))$ -RDP where $\hat{\varepsilon}_{BR}(\alpha)=\sup_{t\in[0,\eta]}\hat{\varepsilon}_{BR}(t;\alpha)$ . Since $\hat{\varepsilon}_{BR}(t;\alpha)$ is continuous and differentiable, it must achieve a maximum value at some $t=t^{*}\in[0,\eta]$ , and $t^{*}$ must satisfy (i) $t^{*}\in\{0,\eta\}$ , or (ii) its derivative is zero. It is clear that we cannot be in case (i) since $\hat{\varepsilon}_{BR}(0;\alpha)=\hat{\varepsilon}_{BR}(\eta;\alpha)=0$ but $\hat{\varepsilon}_{BR}(t;\alpha)>0$ for $t\in(0,\eta)$ .

The derivative of $\hat{\varepsilon}_{BR}(t;\alpha)$ is

\displaystyle\frac{\mathrm{d}}{\mathrm{d}t}\hat{\varepsilon}_{BR}(t;\alpha)

\displaystyle=\frac{1}{\alpha-1}\left(\frac{e^{\alpha\eta+t}-e^{t}}{e^{\eta}+% \left(e^{t}-1\right)e^{\alpha\eta}-e^{t}}-\alpha\right).

Its only root (in $[0,\eta]$ ) is $t^{*}=\log\left(\frac{\alpha\left(e^{\alpha\eta}-e^{\eta}\right)}{(\alpha-1)% \left(e^{\alpha\eta}-1\right)}\right)$ . Thus, we have

\displaystyle\hat{\varepsilon}_{BR}(\alpha)=\hat{\varepsilon}_{BR}(t^{*};% \alpha)=\frac{1}{\alpha-1}\log\left(\frac{(e^{\alpha\eta}-1)^{\alpha}\left(% \frac{\alpha(e^{\alpha\eta}-e^{\eta})}{\alpha-1}\right)^{1-\alpha}}{\alpha(e^{% \eta}-1)}\right).

The tightness follows from that of Lemma 24 by letting $M:\{0,1\}\to\operatorname{supp}(P)\cup\operatorname{supp}(Q)$ be the mechanism such that $M(0)\sim P$ and $M(1)\sim Q$ where $P, Q$ are the tight example for $t=t^{*}$ from Lemma 24.

It remains to compute

\displaystyle\hat{\varepsilon}_{BR}(1)=\lim_{\alpha\to 1}\hat{\varepsilon}_{BR% }(\alpha)=\lim_{\alpha\to 1}\frac{1}{\alpha-1}\log\left(\frac{(e^{\alpha\eta}-% 1)^{\alpha}\left(\frac{\alpha(e^{\alpha\eta}-e^{\eta})}{\alpha-1}\right)^{1-% \alpha}}{\alpha(e^{\eta}-1)}\right).

This is an indeterminate form 0/0, so we can apply L’Hôpital’s Rule by considering $f(\alpha)=\frac{N(\alpha)}{D(\alpha)}$ with $D(\alpha)=\alpha-1$ . We have $D^{\prime}(\alpha)=1$ , and

	$\displaystyle N^{\prime}(\alpha)$	$\displaystyle=\frac{(\alpha-1)e^{\eta}\eta}{e^{\eta}-e^{\alpha\eta}}+\frac{% \alpha\eta}{e^{\alpha\eta}-1}-\log\left(\frac{\alpha\left(e^{\alpha\eta}-e^{% \eta}\right)}{(\alpha-1)\left(e^{\alpha\eta}-1\right)}\right)+\eta$
	$\displaystyle\lim_{\alpha\to 1}N^{\prime}(\alpha)$	$\displaystyle=-1+\frac{\eta}{e^{\eta}-1}+\eta-\log\left(\lim_{\alpha\to 1}% \frac{\alpha\left(e^{\alpha\eta}-e^{\eta}\right)}{(\alpha-1)\left(e^{\alpha% \eta}-1\right)}\right)$
		$\displaystyle=-1+\frac{\eta}{e^{\eta}-1}+\eta-\log\left(\frac{e^{\eta}\eta}{e^% {\eta}-1}\right)$
		$\displaystyle=\frac{\eta}{e^{\eta}-1}+\log\left(\frac{e^{\eta}-1}{\eta}\right)% -1.\$

$\hfill\blacktriangleleft$

Note that Theorem 25 matches the RDP bound implied by [6, Theorem 5], though their bound does not find the maximal $t$ analytically and therefore relies on a $\sup_{t}$ search.

6.2 From RDP to zCDP

Finally, we show below that any $\eta$ -BR mechanism is $\rho$ -zCDP for $\rho=\hat{\varepsilon}_{BR}(1)$ (Theorem 23).

Proof of Theorem 23.

Let $f(\alpha):=\frac{\hat{\varepsilon}_{BR}(\alpha)}{\alpha}$ where $\hat{\varepsilon}_{BR}(\alpha)$ is from Theorem 25. Our proof will proceed by showing that $f$ is decreasing in $\alpha$ (for $\alpha>1$ ), which implies that any $\eta$ -BR mechanism is $\hat{\varepsilon}_{BR}(1)$ -zCDP. To do this, let

	$\displaystyle g$	$\displaystyle:=\frac{\mathrm{d}}{\mathrm{d}\alpha}f(\alpha)$
		$\displaystyle=\frac{(1-2\alpha)\log\left(e^{\alpha\eta}-e^{\eta}\right)+(2% \alpha-1)\log\left((\alpha-1)\left(e^{\eta}-1\right)\right)}{(\alpha-1)^{2}% \alpha^{2}}$
		$\displaystyle\qquad+\frac{(\alpha-1)\eta+\alpha\log\left(\frac{\alpha\left(e^{% \alpha\eta}-e^{\eta}\right)}{(\alpha-1)\left(e^{\alpha\eta}-1\right)}\right)}{% (\alpha-1)^{2}\alpha}+\frac{\eta}{(\alpha-1)\left(e^{\alpha\eta}-1\right)}+% \frac{e^{\eta}\eta}{\alpha e^{\eta}-\alpha e^{\alpha\eta}}$

Let us view $g$ as function of $\eta$ , i.e. $g=g_{\alpha}(\eta)$ . Recall that we wish to show that $g_{\alpha}(\eta)\leq 0$ for all $\eta>0,\alpha>1$ . Simple calculation verifies that $\lim_{\eta\to 0^{+}}g_{\alpha}(\eta)=0$ for all $\alpha>1$ , so the desired inequality will follow from showing that $g^{\prime}_{\alpha}(\eta)\leq 0$ . For this, first note that

\displaystyle g^{\prime}_{\alpha}(\eta)

\displaystyle=\frac{h_{1}(\alpha,\eta)h_{2}(\alpha,\eta)\text{csch}^{2}\left(% \frac{\alpha\eta}{2}\right)\text{csch}^{2}\left(\frac{1}{2}(\eta-\alpha\eta)% \right)}{8(\alpha-1)^{2}\alpha^{2}}

where

	$\displaystyle h_{1}(\alpha)$	$\displaystyle=\left(-\alpha^{2}\cosh(\eta-\alpha\eta)+(\alpha-1)^{2}\cosh(% \alpha\eta)+2\alpha-1\right)$
	$\displaystyle h_{2}(\alpha)$	$\displaystyle=(\alpha-1)\alpha\eta+\sinh(\alpha\eta)-\coth\left(\frac{\eta}{2}% \right)(\cosh(\alpha\eta)-1).$

Given the rest of the terms are trivially non-negative, it remains to show that $h_{1}$ is positive and $h_{2}$ is negative. To do this, recall the identities $\cosh(2x)=1+2\sinh^{2}x$ and $\sinh(x-y)=\sinh x\cosh y-\cosh x\sinh y$ .

Using the first identity, we can simplify $h_{1}\geq 0$ as follows:

	$\displaystyle h_{1}(\alpha)\geq 0$	$\displaystyle\iff(\alpha-1)^{2}\cosh(\alpha\eta)+\alpha^{2}-(\alpha-1)^{2}\geq% \alpha^{2}\cosh(\eta(\alpha-1))$
		$\displaystyle\iff\frac{\cosh(\alpha\eta)-1}{\alpha^{2}}\geq\frac{\cosh(\eta(% \alpha-1))-1}{(\alpha-1)^{2}}$
		$\displaystyle\iff\frac{\sinh^{2}(\alpha\eta/2)}{\alpha^{2}}\geq\frac{\sinh^{2}% (\eta(\alpha-1)/2)}{(\alpha-1)^{2}}$
		$\displaystyle\iff\frac{\sinh(\alpha\eta/2)}{\alpha\eta/2}\geq\frac{\sinh(\eta(% \alpha-1)/2)}{\eta(\alpha-1)/2},$

and the last inequality is true due to Lemma 9.

Similarly, using the two identities, we can simplify $h_{2}$ as follows:

	$\displaystyle(\alpha-1)\alpha\eta-h_{2}$	$\displaystyle=-2\sinh\left(\frac{\alpha\eta}{2}\right)\cosh\left(\frac{\alpha% \eta}{2}\right)+\coth\left(\frac{\eta}{2}\right)\left(2\sinh^{2}\left(\frac{% \alpha\eta}{2}\right)\right)$
		$\displaystyle=2\sinh\left(\frac{\alpha\eta}{2}\right)\left(\frac{\cosh\left(% \frac{\eta}{2}\right)\sinh\left(\frac{\alpha\eta}{2}\right)-\sinh\left(\frac{% \eta}{2}\right)\cosh\left(\frac{\alpha\eta}{2}\right)}{\sinh\left(\frac{\eta}{% 2}\right)}\right)$
		$\displaystyle=2\sinh\left(\frac{\alpha\eta}{2}\right)\left(\frac{\sinh\left(% \frac{(\alpha-1)\eta}{2}\right)}{\sinh\left(\frac{\eta}{2}\right)}\right)$
		$\displaystyle=\alpha\cdot 2\sinh\left(\frac{(\alpha-1)\eta}{2}\right)\cdot% \left(\frac{\frac{\sinh\left(\frac{\alpha\eta}{2}\right)}{\frac{\alpha\eta}{2}% }}{\frac{\sinh\left(\frac{\eta}{2}\right)}{\frac{\eta}{2}}}\right)$
	$\displaystyle(\text{\lx@cref{creftypecap~refnum}{lem:sinhx-divx-inc}})$	$\displaystyle\geq\alpha\cdot 2\left(\frac{(\alpha-1)\eta}{2}\right)\cdot 1% \qquad\qquad=\alpha(\alpha-1)\eta.$

Thus, $h_{2}\leq 0$ as desired. This concludes the proof that $f$ is decreasing in $\alpha$ . Hence, any $\eta$ -BR mechanism is $\hat{\varepsilon}_{BR}(1)$ -zCDP.

The tightness follows from letting $M:\{0,1\}\to\{0,1\}$ be the mechanism such that

\displaystyle\mathbb{P}(M(0)=y)=\begin{cases}\frac{e^{-t}\left(e^{\eta}-e^{t}% \right)}{e^{\eta}-1}&\text{ if $y=0$}\\ \frac{\left(e^{t}-1\right)e^{\eta-t}}{e^{\eta}-1}&\text{ if $y=1$}\\ \end{cases},\qquad\mathbb{P}(M(1)=1)=\begin{cases}\frac{e^{\eta}-e^{t}}{e^{% \eta}-1}&\text{ if $x=0$}\\ \frac{e^{t}-1}{e^{\eta}-1}&\text{ if $x=1$}\\ \end{cases}

for $t=\eta-\log\left(\frac{e^{\eta}-1}{\eta}\right)$ . It is simple to verify that $M$ is $\eta$ -BR and that $\mathrm{D}_{1}\left(M(0)\ \middle\|\ M(1)\right)=\hat{\varepsilon}_{BR}(1)$ , which implies the claimed tightness. $\hfill\blacktriangleleft$

7 Conclusion

In this work, we continue the direction started by [27] in finding exactly tight zCDP bounds for differentially private mechanisms. In particular, we derive tight zCDP bounds for fundamental mechanisms, including Laplace and Discrete Laplace mechanisms, $k$ -Randomized Response (for sufficiently small $k$ ) and RAPPOR. Given the ubiquity of these mechanisms and the wide adoption of zCDP for privacy accounting, we hope that our precise characterizations provide additional tools for accurate privacy accounting both in theory and practice.

The obvious open problem is to give a precise characterization for zCDP of $k$ -RR when $k$ is large. It is unclear if a closed-form expression can be derived in this setting. Nevertheless, an efficient numerical algorithm for computing a precise bound should still be useful in practice. Finally, there are still many widely used mechanisms for which tight zCDP characterizations are not yet known (e.g. Sparse Vector Technique [9], continuous and discrete staircase mechanism [15], report noisy max / permute and flip [10, 21, 5], or the optimized unary encoding mechanism [28]); it would be interesting to prove tight bounds for them as well.

Figure 1: Tight zCDP bounds for all mechanisms as a function of

\varepsilon

, where each mechanism that satisfies

\varepsilon

-DP tightly satisfies

\rho

-zCDP. All bounds use the formulas listed in Table 1. Note that the topmost blue line in each plot (corresponding to

\varepsilon

-DP, 2-RR, and

\operatorname{DLap}

with

\Delta=1

) all share the exact same curve.

References

[1] Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In TCC, pages 635–658, 2016. doi:10.1007/978-3-662-53641-4_24.
[2] Mark Cesar and Ryan Rogers. Bounding, concentrating, and truncating: Unifying privacy loss composition for data analytics. In ALT, pages 421–457, 2021. URL: https://proceedings.mlr.press/v132/cesar21a.html.
[3] Google Differential Privacy Team. Privacy loss distributions, 2026. URL: https://github.com/google/differential-privacy/blob/main/common_docs/Privacy_Loss_Distributions.pdf.
[4] Google Differential Privacy Team. Privacy loss distributions, 2026. URL: https://github.com/google/differential-privacy/blob/9b03b79908ba4c37437b09f40ff3e1fc9682c7ee/python/dp_accounting/dp_accounting/rdp/rdp_privacy_accountant.py#L973.
[5] Zeyu Ding, Daniel Kifer, Thomas Steinke, Yuxin Wang, Yingtai Xiao, Danfeng Zhang, et al. The permute-and-flip mechanism is identical to report-noisy-max with exponential noise. arXiv preprint, 2021. arXiv:2105.07260.
[6] Jinshuo Dong, David Durfee, and Ryan Rogers. Optimal differential privacy composition for exponential mechanisms. In ICML, pages 2597–2606, 2020. URL: https://proceedings.mlr.press/v119/dong20a.html.
[7] David Durfee and Ryan Rogers. Practical differentially private top-k selection with pay-what-you-get composition. In NeurIPS, pages 3527–3537, 2019. URL: https://proceedings.neurips.cc/paper/2019/hash/b139e104214a08ae3f2ebcce149cdf6e-Abstract.html.
[8] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In TCC, pages 265–284, 2006. doi:10.1007/11681878_14.
[9] Cynthia Dwork, Moni Naor, Omer Reingold, Guy N. Rothblum, and Salil P. Vadhan. On the complexity of differentially private data release: efficient algorithms and hardness results. In STOC, pages 381–390, 2009. doi:10.1145/1536414.1536467.
[10] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9(3–4):211–407, August 2014. doi:10.1561/0400000042.
[11] Cynthia Dwork and Guy N. Rothblum. Concentrated differential privacy. CoRR, abs/1603.01887, 2016. arXiv:1603.01887.
[12] Hamid Ebadi, David Sands, and Gerardo Schneider. Differential privacy: Now it’s getting personal. In Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’15, pages 69–81, New York, NY, USA, 2015. Association for Computing Machinery. doi:10.1145/2676726.2677005.
[13] Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. RAPPOR: randomized aggregatable privacy-preserving ordinal response. In CCS, pages 1054–1067, 2014. doi:10.1145/2660267.2660348.
[14] Vitaly Feldman and Tijana Zrnic. Individual privacy accounting via a rényi filter. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 28080–28091. Curran Associates, Inc., 2021. URL: https://proceedings.neurips.cc/paper_files/paper/2021/file/ec7f346604f518906d35ef0492709f78-Paper.pdf.
[15] Quan Geng and Pramod Viswanath. The optimal mechanism in differential privacy. In ISIT, pages 2371–2375, 2014. doi:10.1109/ISIT.2014.6875258.
[16] Arpita Ghosh, Tim Roughgarden, and Mukund Sundararajan. Universally utility-maximizing privacy mechanisms. SIAM J. Comput., 41(6):1673–1693, 2012. doi:10.1137/09076828X.
[17] Charlie Harrison. Tight rdp and zcdp bounds for rappor. https://charlieharrison.xyz/2024/08/20/rdp-rappor.html, 2025. Accessed: 2025-10-17.
[18] Peter Kairouz, Kallista A. Bonawitz, and Daniel Ramage. Discrete distribution estimation under local privacy. In ICML, volume 48, pages 2436–2444, 2016. URL: http://proceedings.mlr.press/v48/kairouz16.html.
[19] Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith. What can we learn privately? SIAM J. Comput., 40(3):793–826, 2011. doi:10.1137/090756090.
[20] Mathias Lécuyer. Practical privacy filters and odometers with rényi differential privacy and applications to differentially private deep learning, 2021. arXiv:2103.01379.
[21] Ryan McKenna and Daniel R Sheldon. Permute-and-flip: A new mechanism for differentially private selection. Advances in Neural Information Processing Systems, 33:193–203, 2020.
[22] Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In FOCS, pages 94–103, 2007. doi:10.1109/FOCS.2007.66.
[23] Ilya Mironov. Rényi differential privacy. In CSF, pages 263–275, 2017. doi:10.1109/CSF.2017.11.
[24] Alfréd Rényi. On measures of entropy and information. In Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Contributions to the Theory of Statistics, 1961.
[25] Ryan Rogers and Thomas Steinke. A better privacy analysis of the exponential mechanism. DifferentialPrivacy.org, July 2021. URL: https://differentialprivacy.org/exponential-mechanism-bounded-range/.
[26] Ryan M Rogers, Aaron Roth, Jonathan Ullman, and Salil Vadhan. Privacy odometers and filters: Pay-as-you-go composition. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016. URL: https://proceedings.neurips.cc/paper_files/paper/2016/file/58c54802a9fb9526cd0923353a34a7ae-Paper.pdf.
[27] Thomas Steinke. Tight rdp & zcdp bounds from pure dp. DifferentialPrivacy.org, May 2024. URL: https://differentialprivacy.org/pdp-to-zcdp/.
[28] Tianhao Wang, Jeremiah Blocki, Ninghui Li, and Somesh Jha. Locally differentially private protocols for frequency estimation. In USENIX Security, pages 729–745, 2017. URL: https://www.usenix.org/conference/usenixsecurity17/technical-sessions/presentation/wang-tianhao.
[29] Yu-Xiang Wang. For laplace mechanism, $\varepsilon+\exp(-\varepsilon)-1$ is the formula. and for randresp, it is the difference btw. cross-entropy and entropy. what’s in common? they are the kl-div and the derivative of renyidp at $\alpha\to 0$ . @shortstein is this trivial observation published somewhere (or well-known)?, September 2022. Tweet. URL: https://x.com/yuxiangw_cs/status/1565765510872018950.
[30] Proof Wiki. Hyperbolic tangent less than x, 2025. URL: https://proofwiki.org/wiki/Hyperbolic_Tangent_Less_than_X.

[bib.bib1] [1] Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In TCC, pages 635–658, 2016. doi:10.1007/978-3-662-53641-4_24.

[bib.bib2] [2] Mark Cesar and Ryan Rogers. Bounding, concentrating, and truncating: Unifying privacy loss composition for data analytics. In ALT, pages 421–457, 2021. URL: https://proceedings.mlr.press/v132/cesar21a.html.

[bib.bib3] [3] Google Differential Privacy Team. Privacy loss distributions, 2026. URL: https://github.com/google/differential-privacy/blob/main/common_docs/Privacy_Loss_Distributions.pdf.

[bib.bib4] [4] Google Differential Privacy Team. Privacy loss distributions, 2026. URL: https://github.com/google/differential-privacy/blob/9b03b79908ba4c37437b09f40ff3e1fc9682c7ee/python/dp_accounting/dp_accounting/rdp/rdp_privacy_accountant.py#L973.

[bib.bib5] [5] Zeyu Ding, Daniel Kifer, Thomas Steinke, Yuxin Wang, Yingtai Xiao, Danfeng Zhang, et al. The permute-and-flip mechanism is identical to report-noisy-max with exponential noise. arXiv preprint, 2021. arXiv:2105.07260.

[bib.bib6] [6] Jinshuo Dong, David Durfee, and Ryan Rogers. Optimal differential privacy composition for exponential mechanisms. In ICML, pages 2597–2606, 2020. URL: https://proceedings.mlr.press/v119/dong20a.html.

[bib.bib7] [7] David Durfee and Ryan Rogers. Practical differentially private top-k selection with pay-what-you-get composition. In NeurIPS, pages 3527–3537, 2019. URL: https://proceedings.neurips.cc/paper/2019/hash/b139e104214a08ae3f2ebcce149cdf6e-Abstract.html.

[bib.bib8] [8] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In TCC, pages 265–284, 2006. doi:10.1007/11681878_14.

[bib.bib9] [9] Cynthia Dwork, Moni Naor, Omer Reingold, Guy N. Rothblum, and Salil P. Vadhan. On the complexity of differentially private data release: efficient algorithms and hardness results. In STOC, pages 381–390, 2009. doi:10.1145/1536414.1536467.

[bib.bib10] [10] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9(3–4):211–407, August 2014. doi:10.1561/0400000042.

[bib.bib11] [11] Cynthia Dwork and Guy N. Rothblum. Concentrated differential privacy. CoRR, abs/1603.01887, 2016. arXiv:1603.01887.

[bib.bib12] [12] Hamid Ebadi, David Sands, and Gerardo Schneider. Differential privacy: Now it’s getting personal. In Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’15, pages 69–81, New York, NY, USA, 2015. Association for Computing Machinery. doi:10.1145/2676726.2677005.

[bib.bib13] [13] Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. RAPPOR: randomized aggregatable privacy-preserving ordinal response. In CCS, pages 1054–1067, 2014. doi:10.1145/2660267.2660348.

[bib.bib14] [14] Vitaly Feldman and Tijana Zrnic. Individual privacy accounting via a rényi filter. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 28080–28091. Curran Associates, Inc., 2021. URL: https://proceedings.neurips.cc/paper_files/paper/2021/file/ec7f346604f518906d35ef0492709f78-Paper.pdf.

[bib.bib15] [15] Quan Geng and Pramod Viswanath. The optimal mechanism in differential privacy. In ISIT, pages 2371–2375, 2014. doi:10.1109/ISIT.2014.6875258.

[bib.bib16] [16] Arpita Ghosh, Tim Roughgarden, and Mukund Sundararajan. Universally utility-maximizing privacy mechanisms. SIAM J. Comput., 41(6):1673–1693, 2012. doi:10.1137/09076828X.

[bib.bib17] [17] Charlie Harrison. Tight rdp and zcdp bounds for rappor. https://charlieharrison.xyz/2024/08/20/rdp-rappor.html, 2025. Accessed: 2025-10-17.

[bib.bib18] [18] Peter Kairouz, Kallista A. Bonawitz, and Daniel Ramage. Discrete distribution estimation under local privacy. In ICML, volume 48, pages 2436–2444, 2016. URL: http://proceedings.mlr.press/v48/kairouz16.html.

[bib.bib19] [19] Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith. What can we learn privately? SIAM J. Comput., 40(3):793–826, 2011. doi:10.1137/090756090.

[bib.bib20] [20] Mathias Lécuyer. Practical privacy filters and odometers with rényi differential privacy and applications to differentially private deep learning, 2021. arXiv:2103.01379.

[bib.bib21] [21] Ryan McKenna and Daniel R Sheldon. Permute-and-flip: A new mechanism for differentially private selection. Advances in Neural Information Processing Systems, 33:193–203, 2020.

[bib.bib22] [22] Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In FOCS, pages 94–103, 2007. doi:10.1109/FOCS.2007.66.

[bib.bib23] [23] Ilya Mironov. Rényi differential privacy. In CSF, pages 263–275, 2017. doi:10.1109/CSF.2017.11.

[bib.bib24] [24] Alfréd Rényi. On measures of entropy and information. In Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Contributions to the Theory of Statistics, 1961.

[bib.bib25] [25] Ryan Rogers and Thomas Steinke. A better privacy analysis of the exponential mechanism. DifferentialPrivacy.org, July 2021. URL: https://differentialprivacy.org/exponential-mechanism-bounded-range/.

[bib.bib26] [26] Ryan M Rogers, Aaron Roth, Jonathan Ullman, and Salil Vadhan. Privacy odometers and filters: Pay-as-you-go composition. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016. URL: https://proceedings.neurips.cc/paper_files/paper/2016/file/58c54802a9fb9526cd0923353a34a7ae-Paper.pdf.

[bib.bib27] [27] Thomas Steinke. Tight rdp & zcdp bounds from pure dp. DifferentialPrivacy.org, May 2024. URL: https://differentialprivacy.org/pdp-to-zcdp/.

[bib.bib28] [28] Tianhao Wang, Jeremiah Blocki, Ninghui Li, and Somesh Jha. Locally differentially private protocols for frequency estimation. In USENIX Security, pages 729–745, 2017. URL: https://www.usenix.org/conference/usenixsecurity17/technical-sessions/presentation/wang-tianhao.

[bib.bib29] [29] Yu-Xiang Wang. For laplace mechanism, $\varepsilon+\exp(-\varepsilon)-1$ is the formula. and for randresp, it is the difference btw. cross-entropy and entropy. what’s in common? they are the kl-div and the derivative of renyidp at $\alpha\to 0$ . @shortstein is this trivial observation published somewhere (or well-known)?, September 2022. Tweet. URL: https://x.com/yuxiangw_cs/status/1565765510872018950.

[bib.bib30] [30] Proof Wiki. Hyperbolic tangent less than x, 2025. URL: https://proofwiki.org/wiki/Hyperbolic_Tangent_Less_than_X.

	$\displaystyle e^{(\alpha-1)\mathrm{D}_{\alpha}\left(Z+d\ \middle\\|\ Z\right)}=% \sum_{x=-\infty}^{\infty}f_{\operatorname{DLap}(a)}(x-d)^{\alpha}\cdot f_{% \operatorname{DLap}(a)}(x)^{1-\alpha}$
	$\displaystyle=\sum_{x=-\infty}^{\infty}(\tanh(a/2)e^{-a\|x-d\|})^{\alpha}\cdot(% \tanh(a/2)e^{-a\|x\|})^{1-\alpha}$
	$\displaystyle=\tanh(a/2)\sum_{x=-\infty}^{\infty}e^{-a(\alpha\|x-d\|+(1-\alpha)\|% x\|)}$
	$\displaystyle=\tanh(a/2)\left(\left(\sum_{x=-\infty}^{-1}e^{a(x-\alpha d)}% \right)+\left(\sum_{x=0}^{d}e^{a((2\alpha-1)x-\alpha d)}\right)+\left(\sum_{x=% d+1}^{\infty}e^{a(\alpha d-x)}\right)\right)$
	$\displaystyle=\tanh(a/2)\left(\frac{e^{-a\alpha d}}{e^{a}-1}+\frac{e^{a-a% \alpha d}-e^{a(\alpha(d+2)-d)}}{e^{a}-e^{2a\alpha}}+\frac{e^{-a(1-\alpha)d}}{e% ^{a}-1}\right).$

Exact zCDP Characterizations for Fundamental Differentially Private Mechanisms

Abstract

Keywords and phrases:

Copyright and License:

2012 ACM Subject Classification:

Acknowledgements:

DOI:

Event:

Editor:

Series and Publisher:

1 Introduction

Properties of our bounds.

Why use zCDP accounting.

2 Preliminaries

Privacy notions.

Definition 1 (Differential privacy [8]).

Definition 2 (Rényi divergence [24]).

Definition 3 (Rényi DP [23]).

Definition 4 (Concentrated DP [1]).

Definition 5 (Bounded range DP [7, 6, 25]).

Sensitivity.

Definition 6 (Sensitivity).

Noise distributions.

Existing tight bounds.

Proposition 7 (DP to RDP [27]).

Proposition 8 (DP to zCDP [27]).

Some Useful Functions and Their Properties.

Lemma 9.

Proof.

Lemma 10.

Proof.

Lemma 11.

Proof.

3 Central DP Mechanisms

3.1 Laplace Mechanism

Theorem 12 (zCDP for Laplace).

Proof.

3.2 Discrete Laplace

Theorem 13 (zCDP of discrete Laplace).

3.2.1 RDP Bound Derivation

Proposition 14.

Proof.

Lemma 15 (RDP of discrete Laplace).

Proof.

3.2.2 From RDP to zCDP

Proof of Theorem 13.

Proof of Non-negativity of 𝒇′⁢(𝟏).

Proof of Non-negativity of 𝒇′′⁢(𝚫).

4 Local DP Mechanisms

5 𝒌-Randomized Response

Theorem 16.

Lemma 17.

Corollary 18.

Theorem 19.

5.1 RDP Bound Derivation

Proposition 20.

Proof.

5.2 From RDP to zCDP

Proof of Theorem 16.

Proof of (A).

Proof of (B).

5.3 Non-Optimality of 𝜶=𝟏

Proof of Lemma 17.

5.4 Loose zCDP for Large 𝒌 Regime

Proof of Theorem 19.

5.5 RAPPOR

Proposition 21.

Proof.

Proposition 22.

Proof.

6 𝜼-Bounded Range Mechanisms

Theorem 23.

6.1 RDP Bound Derivation

Lemma 24.

Proof.

Theorem 25 (RDP for Bounded Range Mechanisms).

Proof.

6.2 From RDP to zCDP

Proof of Theorem 23.

7 Conclusion

Proof of Non-negativity of $f^{\prime}(1)$ .

Proof of Non-negativity of $f^{\prime\prime}(\Delta)$ .

5 $𝒌$ -Randomized Response

5.3 Non-Optimality of $\alpha=1$

5.4 Loose zCDP for Large $𝒌$ Regime

6 $\eta$ -Bounded Range Mechanisms