Concentrated Differential Privacy:
Simplifications, Extensions, and Lower Bounds
arXiv:1605.02065v1 [cs.CR] 6 May 2016

Mark Bun∗

Thomas Steinke†

{mbun,tsteinke}@seas.harvard.edu

Abstract
“Concentrated differential privacy” was recently introduced by Dwork and Rothblum as a relaxation of differential privacy, which permits sharper analyses of many
privacy-preserving computations. We present an alternative formulation of the concept of concentrated differential privacy in terms of the Rényi divergence between the
distributions obtained by running an algorithm on neighboring inputs. With this reformulation in hand, we prove sharper quantitative results, establish lower bounds, and
raise a few new questions. We also unify this approach with approximate differential
privacy by giving an appropriate definition of “approximate concentrated differential
privacy.”
∗
†

Supported by an NDSEG Fellowship and NSF grant CNS-1237235.
Supported by NSF grants CCF-1116616, CCF-1420938, and CNS-1237235.

1

Contents
1 Introduction
1.1 Our Reformulation: Zero-Concentrated Differential Privacy .
1.1.1 Comparison to the Definition of Dwork and Rothblum
1.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2.1 Relationship between zCDP and Differential Privacy .
1.2.2 Gaussian Mechanism . . . . . . . . . . . . . . . . . . .
1.2.3 Basic Properties of zCDP . . . . . . . . . . . . . . . .
1.2.4 Group Privacy . . . . . . . . . . . . . . . . . . . . . .
1.2.5 Lower Bounds . . . . . . . . . . . . . . . . . . . . . .
1.2.6 Approximate zCDP . . . . . . . . . . . . . . . . . . .
1.3 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4 Further Work . . . . . . . . . . . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

3
. 4
. 5
. 6
. 6
. 6
. 7
. 7
. 8
. 9
. 9
. 10

2 Rényi Divergence
11
2.1 Composition and Postprocessing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2 Gaussian Mechanism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3 Relation to Differential Privacy
13
3.1 Pure DP versus zCDP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.2 Approximate DP versus zCDP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4 Zero- versus Mean-Concentrated Differential Privacy

17

5 Group Privacy

18

6 Lower Bounds
20
6.1 Example Applications of the Lower Bound . . . . . . . . . . . . . . . . . . . . . . . . 22
7 Obtaining Pure DP Mechanisms from zCDP

25

8 Approximate zCDP
30
8.1 Approximate DP Implies Approximate zCDP . . . . . . . . . . . . . . . . . . . . . . 31
8.2 Approximate zCDP Implies Approximate DP . . . . . . . . . . . . . . . . . . . . . . 32
8.3 Application of Approximate zCDP . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
Acknowledgements

34

References

34

A Postprocessing and mCDP

37

B Miscellaneous Proofs and Lemmata
39
B.1 Proof of Lemma 2.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
C Privacy versus Sampling

49

2

1

Introduction

Differential privacy [DMNS06] is a formal mathematical standard for protecting individuallevel privacy in statistical data analysis. In its simplest form, (pure) differential privacy is
parameterized by a real number ε > 0, which controls how much “privacy loss”1 an individual
can suffer when a computation (i.e., a statistical data analysis task) is performed involving
his or her data.
One particular hallmark of differential privacy is that it degrades smoothly and predictably under the composition of multiple computations. In particular, if one performs k
computational tasks that are each ε-differentially private and combines the results of those
tasks, then the computation as a whole is kε-differentially private. This property makes differential privacy amenable to the type of modular reasoning used in the design and analysis
of algorithms: When a sophisticated algorithm is comprised of a sequence of differentially
private steps, one can establish that the algorithm as a whole remains differentially private.
A widely-used relaxation of pure differential privacy is approximate or (ε, δ)-differential
privacy [DKM+ 06], which essentially guarantees that the probability that any individual
suffers privacy loss exceeding ε is bounded by δ. For sufficiently small δ, approximate (ε, δ)differential privacy provides a comparable standard of privacy protection as pure ε-differential
privacy, while often permitting substantially more useful analyses to be performed.
Unfortunately, there are situations where, unlike pure differential privacy, approximate
differential privacy is not a very elegant abstraction for mathematical analysis, particularly
the analysis of composition. The “advanced composition theorem” of Dwork, Rothblum,
and Vadhan [DRV10] (subsequently improved by [KOV15, MV16])√shows that the composition of k tasks which are each (ε, δ)-differentially private is (≈ kε, ≈ kδ)-differentially
private. However, these bounds can be unwieldy; computing the tightest possible privacy
guarantee for the composition of k arbitrary mechanisms with differing (εi , δi )-differential
privacy guarantees is #P-hard [MV16]! Furthermore, these bounds are not tight even for
simple and natural privacy-preserving computations. For instance, consider the mechanism
which approximately answers k statistical queries on a given database by adding independent
Gaussian noise to each answer. Even for this basic computation, the advanced composition
theorem does not yield a tight analysis.2
Dwork and Rothblum [DR16] recently put forth a different relaxation of differential privacy called concentrated differential privacy. Roughly, a randomized mechanism satisfies
concentrated differentially privacy if the privacy loss has small mean and is subgaussian.
Concentrated differential privacy behaves in a qualitatively similar way as approximate
1

The privacy loss is a random variable which quantifies how much information is revealed about an
individual by a computation involving their data; it depends on the outcome of the computation, the way
the computation was performed, and the information that the individual wants to hide. We discuss it
informally in this introduction and define it precisely in Definition 1.2 on page 4.
2
In particular, consider answering k statistical queries on a dataset of n individualspby adding noise
drawn from N (0, (σ/n)2 ) independently for each query. Each individual query satisfies (O( log(1/δ)/σ), δ)differential privacy for any δ >
√ 0. Applying the advanced composition theorem shows that the composition
of all k queries satisfies (O( k log(1/δ)/σ), (k + 1)δ)-differential
privacy for any δ > 0. However, it is
p
well-known that this bound can be improved to (O( k log(1/δ)/σ), δ)-differential privacy.

3

(ε, δ)-differential privacy under composition. However, it permits sharper analyses of basic
computational tasks, including a tight analysis of the aforementioned Gaussian mechanism.
Using the work of Dwork and Rothblum [DR16] as a starting point, we introduce an
alternative formulation of the concept of concentrated differential privacy that we call “zeroconcentrated differential privacy” (zCDP for short). To distinguish our definition from that
of Dwork and Rothblum, we refer to their definition as “mean-concentrated differential privacy” (mCDP for short). Our definition uses the Rényi divergence between probability distributions as a different method of capturing the requirement that the privacy loss random
variable is subgaussian.

1.1

Our Reformulation: Zero-Concentrated Differential Privacy

As is typical in the literature, we model a dataset as a multiset or tuple of n elements (or
“rows”) in X n , for some “data universe” X , where each element represents one individual’s
information. A (privacy-preserving) computation is a randomized algorithm M : X n → Y,
where Y represents the space of all possible outcomes of the computation.
Definition 1.1 (Zero-Concentrated Differential Privacy (zCDP)). A randomised mechanism
M : X n → Y is (ξ, ρ)-zero-concentrated differentially private (henceforth (ξ, ρ)-zCDP) if, for
all x, x0 ∈ X n differing on a single entry and all α ∈ (1, ∞),
Dα (M (x)kM (x0 )) ≤ ξ + ρα,

(1)

where Dα (M (x)kM (x0 )) is the α-Rényi divergence3 between the distribution of M (x) and
the distribution of M (x0 ).
We define ρ-zCDP to be (0, ρ)-zCDP.4
Equivalently, we can replace (1) with


E e(α−1)Z ≤ e(α−1)(ξ+ρα) ,

(2)

where Z = PrivLoss (M (x)kM (x0 )) is the privacy loss random variable:
Definition 1.2 (Privacy Loss Random Variable). Let Y and Y 0 be random variables on Ω.
We define the privacy loss random variable between Y and Y 0 – denoted Z = PrivLoss (Y kY 0 )
3

Rényi divergence has a parameter α ∈ (1, ∞) which allows it to interpolate between KL-divergence
(α → 1) and max-divergence (α → ∞). It should be thought of as a measure of dissimilarity between
distributions. We define it formally in Section 2. Throughout, we assume that all logarithms are natural
unless specified otherwise — that is, base e ≈ 2.718. This includes logarithms in information theoretic
quantities like entropy, divergence, and mutual information, whence these quantities are measured in nats
rather than in bits.
4
For clarity of exposition, we consider only ρ-zCDP in the introduction and give more general statements
for (ξ, ρ)-zCDP later. We also believe that having a one-parameter definition is desirable.

4

– as follows. Define a function f : Ω → R by f (y) = log(P [Y = y] /P [Y 0 = y]).5 Then Z is
distributed according to f (Y ).
Intuitively, the value of the privacy loss Z = PrivLoss (M (x)kM (x0 )) represents how well
we can distinguish x from x0 given only the output M (x) or M (x0 ). If Z > 0, then the
observed output of M is more likely to have occurred if the input was x than if x0 was the
input. Moreover, the larger Z is, the bigger this likelihood ratio is. Likewise, Z < 0 indicates
that the output is more likely if x0 is the input. If Z = 0, both x and x0 “explain” the output
of M equally well.
A mechanism M : X n → Y is ε-differentially private if and only if P [Z > ε] = 0, where
Z = PrivLoss (M (x)kM (x0 )) is the privacy loss of M on arbitrary inputs x, x0 ∈ X n differing
in one entry. On the other hand, M being (ε, δ)-differentially private is equivalent, up to a
small loss in parameters, to the requirement that P [Z > ε] ≤ δ.
In contrast, zCDP
entails a bound on the moment generating function of the privacy
 (α−1)Z
loss Z — that is, E e
as a function of α − 1. The bound (2) implies that Z is a
subgaussian random variable6 with small mean. Intuitively, this means that Z resembles a
Gaussian distribution with mean ξ + ρ and variance 2ρ. In particular, we obtain strong tail
bounds on Z. Namely (2) implies that
P [Z > λ + ξ + ρ] ≤ e−λ

2 /4ρ

for all λ > 0.7
Thus zCDP requires that the privacy loss random variable is concentrated around zero
(hence the name). That is, Z is “small” with high probability, with larger deviations from
zero becoming increasingly unlikely. Hence we are unlikely to be able to distinguish x from
x0 given the output of M (x) or M (x0 ). Note that the randomness of the privacy loss random
variable is taken only over the randomnesss of the mechanism M .
1.1.1

Comparison to the Definition of Dwork and Rothblum

For comparison, Dwork and Rothblum [DR16] define (µ, τ )-concentrated differential privacy
for a randomized mechanism M : X n → Y as the requirement that, if Z = PrivLoss (M (x)kM (x0 ))
5

Throughout we abuse notation by letting P [Y = y] represent either the probability mass function or

the probability density function of Y evaluated at y. Formally, P [Y = y] /P [Y 0 = y] denotes the RadonNikodym derivative of the measure Y with respect to the measure Y 0 evaluated at y, where we require Y to
be absolutely continuous with respect to Y 0 , i.e. Y  Y 0 .
6
A randomhvariable X being
is characterised by hthe following
i four 2equivalent conditions
i subgaussian
t(X−E[X])
−Ω(λ2 )
[Riv12]. (i) P |X − E [X] | > λ ≤ e
for all λ > 0. (ii) E e
≤ eO(t ) for all t ∈ R. (iii)


h
i
c(X−E[X])2
E (X − E [X])2k ≤ O(k)k for all k ∈ N. (iv) E e
≤ 2 for some c > 0.
7

We only discuss bounds on the upper tail of Z. We can obtain similar bounds on the lower tail of
Z = PrivLoss (M (x)kM (x0 )) by considering Z 0 = PrivLoss (M (x0 )kM (x)).

5

is the privacy loss for x, x0 ∈ X n differing on one entry, then
h
i
21 2
(α−1)(Z−E[Z])
E [Z] ≤ µ
and
E e
≤ e(α−1) 2 τ
for all α ∈ R. That is, they require both a bound on the mean of the privacy loss and that
the privacy loss is tightly concentrated around its mean. To distinguish our definitions, we
refer to their definition as mean-concentrated differential privacy (or mCDP).
Our definition, zCDP, is a relaxation of mCDP. In particular, a (µ, τ )-mCDP mechanism
is also (µ − τ 2 /2, τ 2 /2)-zCDP (which is tight for the Gaussian mechanism example), whereas
the converse is not true. (However, a partial converse holds; see Lemma 4.3.)

1.2
1.2.1

Results
Relationship between zCDP and Differential Privacy

Like Dwork and Rothblum’s formulation of concentrated differential privacy, zCDP can be
thought of as providing guarantees of (ε, δ)-differential privacy for all values of δ > 0:
p
Proposition 1.3. If M provides ρ-zCDP, then M is (ρ + 2 ρ log(1/δ), δ)-differentially
private for any δ > 0.
We also prove a slight strengthening of this result (Lemma 3.6). Moreover, there is
a partial converse, which shows that, up to a loss in parameters, zCDP is equivalent to
differential privacy with this ∀δ > 0 quantification (see Lemma 3.7).
There is also a direct link from pure differential privacy to zCDP:
Proposition 1.4. If M satisfies ε-differential privacy, then M satisfies ( 21 ε2 )-zCDP.
Dwork and Rothblum [DR16, Theorem 3.5] give a slightly weaker version of Proposition
1.4, which implies that ε-differential privacy yields ( 21 ε(eε − 1))-zCDP; this improves on an
earlier bound [DRV10] by the factor 12 .
We give proofs of these and other properties using properties of Rényi divergence in
Sections 2 and 3.
Propositions 1.3 and 1.4 show that zCDP is an intermediate notion between pure differential privacy and approximate differential privacy. Indeed, many algorithms satisfying
approximate differential privacy do in fact also satisfy zCDP.
1.2.2

Gaussian Mechanism

Just as with mCDP, the prototypical example of a mechanism satisfying zCDP is the Gaussian mechanism, which answers a real-valued query on a database by perturbing the true
answer with Gaussian noise.
Definition 1.5 (Sensitivity). A function q : X n → R has sensitivity ∆ if for all x, x0 ∈ X n
differing in a single entry, we have |q(x) − q(x0 )| ≤ ∆.
6

Proposition 1.6 (Gaussian Mechanism). Let q : X n → R be a sensitivity-∆ query. Consider
the mechanism M : X n → R that on input x, releases a sample from N (q(x), σ 2 ). Then M
satisfies (∆2 /2σ 2 )-zCDP.
We remark that either inequality defining zCDP — (1) or (2) — is exactly tight for the
Gaussian mechanism for all values of α. Thus the definition of zCDP seems tailored to the
Gaussian mechanism.
1.2.3

Basic Properties of zCDP

Our definition of zCDP satisfies the key basic properties of differential privacy. Foremost,
these properties include smooth degradation under composition, and invariance under postprocessing:
Lemma 1.7 (Composition). Let M : X n → Y and M 0 : X n → Z be randomized algorithms.
Suppose M satisfies ρ-zCDP and M 0 satisfies ρ0 -zCDP. Define M 00 : X n → Y ×Z by M 00 (x) =
(M (x), M 0 (x)). Then M 00 satisfies (ρ + ρ0 )-zCDP.
Lemma 1.8 (Postprocessing). Let M : X n → Y and f : Y → Z be randomized algorithms.
Suppose M satisfies ρ-zCDP. Define M 0 : X n → Z by M 0 (x) = f (M (x)). Then M 0 satisfies
ρ-zCDP.
These properties follow immediately from corresponding properties of the Rényi divergence outlined in Lemma 2.2.
We remark that Dwork and Rothblum’s definition of mCDP is not closed under postprocessing; we provide a counterexample in Appendix A. (However, an arbitrary amount of
postprocessing can worsen the guarantees of mCDP by at most constant factors.)
1.2.4

Group Privacy

A mechanism M guarantees group privacy if no small group of individuals has a significant
effect on the outcome of a computation (whereas the definition of zCDP only refers to
individuals, which are groups of size 1). That is, group privacy for groups of size k guarantees
that, if x and x0 are inputs differing on k entries (rather than a single entry), then the outputs
M (x) and M (x0 ) are close.
Dwork and Rothblum [DR16, Theorem 4.1] gave nearly tight bounds on the group privacy
guarantees of concentrated differential privacy, showing that a (µ = τ 2 /2, τ )-concentrated
differentially private mechanism affords (k 2 µ · (1 + o(1)), kτ · (1 + o(1)))-concentrated differential privacy for groups of size k = o(1/τ ). We are able to show a group privacy guarantee
for zCDP that is exactly tight and works for a wider range of parameters:
Proposition 1.9. Let M : X n → Y satisfy ρ-zCDP. Then M guarantees (k 2 ρ)-zCDP for
groups of size k — i.e. for every x, x0 ∈ X n differing in up to k entries and every α ∈ (1, ∞),
we have
Dα (M (x)kM (x0 )) ≤ (k 2 ρ) · α.
In particular, this bound is achieved (simultaneously for all values α) by the Gaussian
mechanism. Our proof is also simpler than that of Dwork and Rothblum; see Section 5.
7

1.2.5

Lower Bounds

The strong group privacy guarantees of zCDP yield, as an unfortunate consequence, strong
lower bounds as well. We show that, as with pure differential privacy, zCDP is susceptible to
information-based lower bounds, as well as to so-called packing arguments [HT10, MMP+ 10,
De12]:
Theorem 1.10. Let M : X n → Y satisfy ρ-zCDP. Let X be a random variable on X n .
Then
I (X; M (X)) ≤ ρ · n2 ,
where I(·; ·) denotes the mutual information between the random variables (in nats, rather
than bits). Furthermore, if the entries of X are independent, then I(X; M (X)) ≤ ρ · n.
Theorem 1.10 yields strong lower bounds for zCDP mechanisms, as we can construct
distributions X such that, for any accurate mechanism M , M (X) reveals a lot of information
about X (i.e. I(X; M (X)) is large for any accurate M ).
In particular, we obtain a strong separation between approximate differential privacy
and zCDP. For example, we can show that releasing an accurate approximate histogram (or,
equivalently, accurately answering
all point queries) on a data domain of size k requires an
√
input with at least n = Θ( log k) entries to satisfy zCDP. In contrast, under approximate
differential privacy, n can be independent of the domain size k [BNS13]! In particular,
our lower bounds show that “stability-based” techniques (such as those in the propose-testrelease framework [DL09]) are not compatible with zCDP.
Our lower bound exploits the strong group privacy guarantee afforded by zCDP. Group
privacy has been used to prove tight lower bounds for pure differential privacy [HT10, De12]
and approximate differential privacy [SU15a]. These results highlight the fact that group
privacy is often the limiting factor for private data analysis. For (ε, δ)-differential privacy,
group privacy becomes vacuous for groups of size k = Θ(log(1/δ)/ε). Indeed, stability-based
techniques exploit precisely this breakdown in group privacy.
As a result of this strong lower bound, we show that any mechanism for answering
statistical queries that satisfies zCDP can be converted into a mechanism satisfying pure
differential privacy with only a quadratic blowup in its sample complexity. More precisely,
the following theorem illustrates a more general result we prove in Section 7.
Theorem 1.11. Let n ∈ N and α ≥ 1/n be arbitrary. Set ε = α and ρ = α2 . Let
q : X → [0, 1]k be an arbitrary family of statistical queries. Suppose M : X n → [0, 1]k
satisfies ρ-zCDP and
E [kM (x) − q(x)k∞ ] ≤ α
M

0

for all x ∈ X . Then there exists M 0 : X n → [0, 1]k for n0 = 5n2 satisfying ε-differential
privacy and
E0 [kM 0 (x) − q(x)k∞ ] ≤ 10α
n

M

n0

for all x ∈ X .
8

For some classes of queries, this reduction is essentially tight. For example,
√ for k oneway marginals, the Gaussian mechanism achieves sample complexity n = Θ( k) subject
to zCDP, whereas the Laplace mechanism achieves sample complexity n = Θ(k) subject to
pure differential privacy, which is known to be optimal.
For more details, see Sections 6 and 7.
1.2.6

Approximate zCDP

To circumvent these strong lower bounds for zCDP, we consider a relaxation of zCDP in the
spirit of approximate differential privacy that permits a small probability δ of (catastrophic)
failure:
Definition 1.12 (Approximate Zero-Concentrated Differential Privacy (Approximate zCDP)).
A randomized mechanism M : X n → Y is δ-approximately (ξ, ρ)-zCDP if, for all x, x0 ∈ X n
differing on a single entry, there exist events E (depending on M (x)) and E 0 (depending on
M (x0 )) such that P [E] ≥ 1 − δ, P [E 0 ] ≥ 1 − δ, and
∀α ∈ (1, ∞)

Dα (M (x)|E kM (x0 )|E 0 ) ≤ ξ+ρ·α

∧

Dα (M (x0 )|E 0 kM (x)|E ) ≤ ξ+ρ·α,

where M (x)|E denotes the distribution of M (x) conditioned on the event E. We further
define δ-approximate ρ-zCDP to be δ-approximate (0, ρ)-zCDP.
In particular, setting δ = 0 gives the original definition of zCDP. However, this definition
unifies zCDP with approximate differential privacy:
Proposition 1.13. If M satisfies (ε, δ)-differential privacy, then M satisfies δ-approximate
1 2
ε -zCDP.
2
Approximate zCDP retains most of the desirable properties of zCDP, but allows us to
incorporate stability-based techniques and bypass the above lower bounds. This also presents
a unified tool to analyse a composition of zCDP with approximate differential privacy; see
Section 8.

1.3

Related Work

Our work builds on the aforementioned prior work of Dwork and Rothblum [DR16].8 We
view our definition of concentrated differential privacy as being “morally equivalent” to their
definition of concentrated differential privacy, in the sense that both definitions formalize the
same concept.9 (The formal relationship between the two definitions is discussed in Section
8

Although Dwork and Rothblum’s work only appeared publicly in March 2016, they shared a preliminary
draft of their paper with us before we commenced this work. As such, our ideas are heavily inspired by
theirs.
9
We refer to our definition as “zero-concentrated differential privacy” (zCDP) and their definition as
“mean-concentrated differential privacy” (mCDP). We use “concentrated differential privacy” (CDP) to
refer to the underlying concept formalized by both definitions.

9

4.) However, the definition of zCDP generally seems to be easier to work with than that of
mCDP. In particular, our formulation in terms of Rényi divergence simplifies many analyses.
Dwork and Rothblum prove several results about concentrated differential privacy that
are similar to ours. Namely, they prove analogous properties of mCDP as we prove for
zCDP (cf. Sections 1.2.1, 1.2.2, 1.2.3, and 1.2.4). However, as noted, some of their bounds
are weaker than ours; also, they do not explore lower bounds.
Several of the ideas underlying concentrated differential privacy are implicit in earlier
works. In particular, the proof of the advanced composition theorem of Dwork, Rothblum,
and Vadhan [DRV10] essentially uses the ideas of concentrated differential privacy. Their
proof contains analogs of Propositions 1.7, 1.3, and 1.4,.
We also remark that Tardos [Tar08] used Rényi divergence to prove lower bounds for cryptographic objects called fingerprinting codes. Fingerprinting codes turn out to be closely related to differential privacy [Ull13, BUV14, SU15b], and Tardos’ lower bound can be (loosely)
viewed as a kind of privacy-preserving algorithm.

1.4

Further Work

We believe that concentrated differential privacy is a useful tool for analysing private computations, as it provides both simpler and tighter bounds. We hope that CDP will be prove
useful in both the theory and practice of differential privacy.
Furthermore, our lower bounds show that CDP can really be a much more stringent
condition than approximate differential privacy. Thus CDP defines a “subclass” of all (ε, δ)differentially private algorithms. This subclass includes most differentially private algorithms
in the literature, but not all — the most notable exceptions being algorithms that use the
propose-test-release approach [DL09] to exploit low local sensitivity.
This “CDP subclass” warrants further exploration. In particular, is there a “complete”
mechanism for this class of algorithms, in the same sense that the exponential mechanism
[MT07, BLR13] is complete for pure differential privacy? Can we obtain a simple characterization of the sample complexity needed to satisfy CDP? The ability to prove stronger
and simpler lower bounds for CDP than for approximate DP may be useful for showing
the limitations of certain algorithmic paradigms. For example, any differentially private algorithm that only uses the Laplace mechanism, the exponential mechanism, the Gaussian
mechanism, and the “sparse vector” technique, along with composition and postprocessing
will be subject to the lower bounds for CDP.
There is also room to examine how to interpret the zCDP privacy guarantee. In particular, we leave it as an open question to understand the extent to which ρ-zCDP provides a
stronger privacy guarantee than the implied (ε, δ)-DP guarantees (cf. Proposition 1.3).
In general, much of the literature on differential privacy can be re-examined through the
lens of CDP, which may yield new insights and results.

10

2

Rényi Divergence

Recall the definition of Rényi divergence:
Definition 2.1 (Rényi Divergence [Rén61, Equation (3.3)]). Let P and Q be probability
distributions on Ω. For α ∈ (1, ∞), we define the Rényi divergence of order α between P
and Q as
Z

1
α
1−α
log
P (x) Q(x) dx
Dα (P kQ) =
α−1
Ω


α 
P (x)
1
log E
=
x∼Q
α−1
Q(x)
"
α−1 #!
1
P (x)
=
log E
,
x∼P
α−1
Q(x)
where P (·) and Q(·) are the probability mass/density functions of P and Q respectively or,
more generally, P (·)/Q(·) is the Radon-Nikodym derivative of P with respect to Q.10 We
also define the KL-divergence


Z
P (x)
P (x) log
dx
D1 (P kQ) = lim Dα (P kQ) =
α→1
Q(x)
Ω
and the max-divergence

D∞ (P kQ) = lim Dα (P kQ) = sup log
α→∞

x∈Ω

P (x)
Q(x)


.

Alternatively, Rényi divergence can be defined in terms of the privacy loss (Definition
1.2) between P and Q:
 (α−1)Z 
e(α−1)Dα (P kQ) =
E
e
Z∼PrivLoss(P kQ)

for all α ∈ (1, ∞). Moreover, D1 (P kQ) =

E

Z∼PrivLoss(P kQ)

[Z].

We record several useful and well-known properties of Rényi divergence. We refer the
reader to [vEH14] for proofs and discussion of these (and many other) properties. Selfcontained proofs are given in Appendix B.1.
Lemma 2.2. Let P and Q be probability distributions and α ∈ [1, ∞].
• Non-negativity: Dα (P kQ) ≥ 0 with equality if and only if P = Q.
10

If P is not absolutely continuous with respect to Q (i.e. it is not the case that P  Q), we define
Dα (P kQ) = ∞ for all α ∈ [1, ∞].

11

• Composition: Suppose P and Q are distributions on Ω × Θ. Let P 0 and Q0 denote the
marginal distributions on Ω induced by P and Q respectively. For x ∈ Ω, let Px0 and
Q0x denote the conditional distributions on Θ induced by P and Q respectively, where
x specifies the first coordinate. Then
Dα (P 0 kQ0 ) + min Dα (Px0 kQ0x ) ≤ Dα (P kQ) ≤ Dα (P 0 kQ0 ) + max Dα (Px0 kQ0x ) .
x∈Ω

x∈Ω

In particular if P and Q are product distributions, then the Rényi divergence between
P and Q is just the sum of the Rényi divergences of the marginals.
• Quasi-Convexity: Let P0 , P1 and Q0 , Q1 be distributions on Ω, and let P = tP0 + (1 −
t)P1 and Q = tQ0 +(1−t)Q1 for t ∈ [0, 1]. Then Dα (P kQ) ≤ max{Dα (P0 kQ0 ) , Dα (P1 kQ1 )}.
Moreover, KL divergence is convex:
D1 (P kQ) ≤ tD1 (P0 kQ0 ) + (1 − t)D1 (P1 kQ1 ) .
• Postprocessing: Let P and Q be distributions on Ω and let f : Ω → Θ be a function.
Let f (P ) and f (Q) denote the distributions on Θ induced by applying f to P or Q
respectively. Then Dα (f (P )kf (Q)) ≤ Dα (P kQ).
Note that quasi-convexity allows us to extend this guarantee to the case where f is a
randomized mapping.
• Monotonicity: For 1 ≤ α ≤ α0 ≤ ∞, Dα (P kQ) ≤ Dα0 (P kQ).

2.1

Composition and Postprocessing

The following lemma gives the postprocessing and (adaptive) composition bounds (extending
Lemmas 1.7 and 1.8).
Lemma 2.3 (Composition & Postprocessing). Let M : X n → Y and M 0 : X n × Y → Z.
Suppose M satisfies (ξ, ρ)-zCDP and M 0 satisfies (ξ 0 , ρ0 )-zCDP (as a function of its first
argument). Define M 00 : X n → Z by M 00 (x) = M 0 (x, M (x)). Then M 00 satisfies (ξ+ξ 0 , ρ+ρ0 )zCDP.
The proof is immediate from Lemma 2.2. Note that, while Lemma 2.3 is only stated for
the composition of two mechanisms, it can be inductively applied to analyse the composition
of arbitrarily many mechanisms.

2.2

Gaussian Mechanism

The following lemma gives the Rényi divergence between two Gaussian distributions with
the same variance.

12

Lemma 2.4. Let µ, ν, σ ∈ R and α ∈ [1, ∞). Then
 α(µ − ν)2
Dα N (µ, σ ) N (ν, σ ) =
2σ 2
Consequently, the Gaussian mechanism,
 2  which answers a sensitivity-∆ query by adding
∆
2
noise drawn from N (0, σ ), satisfies 2σ
2 -zCDP (Proposition 1.6).
2

2

Proof. We calculate


Z

1
(x − ν)2
(x − µ)2
dx
exp (α − 1)Dα N (µ, σ ) N (ν, σ ) = √
− (1 − α)
exp −α
2σ 2
2σ 2
2πσ 2 R


Z
1
(x − (αµ + (1 − α)ν))2 − (αµ + (1 − α)ν)2 + αµ2 + (1 − α)ν 2
=√
dx
exp −
2σ 2
2πσ 2 R



−(αµ + (1 − α)ν)2 + αµ2 + (1 − α)ν 2
=
E
exp −
x∼N (αµ+(1−α)ν,σ 2 )
2σ 2


α(α − 1)(µ − ν)2
= exp
.
2σ 2
2

2

For the multivariate Gaussian mechanism, Lemma 2.4 generalises to the following.
Lemma 2.5. Let µ, ν ∈ Rd , σ ∈ R, and α ∈ [1, ∞). Then
 αkµ − νk22
Dα N (µ, σ 2 Id ) N (ν, σ 2 Id ) =
2σ 2
Thus, if M : X n → Rd is the mechanism that, on input x, releases a sample from
N (q(x), σ 2 Id ) for some function q : X n → Rd , then M satisfies ρ-zCDP for
ρ=

3

1
2σ 2

sup
x,x0 ∈X n
differing in one entry

kq(x) − q(x0 )k22 .

(3)

Relation to Differential Privacy

We now discuss the relationship between zCDP and the traditional definitions of pure and
approximate differential privacy. There is a close relationship between the notions, but not
an exact characterization.
For completeness, we state the definition of differential privacy:
Definition 3.1 (Differential Privacy (DP) [DMNS06, DKM+ 06]). A randomized mechanism
M : X n → Y satisfies (ε, δ)-differential privacy if, for all x, x0 ∈ X differing in a single entry,
we have
P [M (x) ∈ S] ≤ eε P [M (x0 ) ∈ S] + δ
for all (measurable) S ⊂ Y. Further define ε-differential privacy to be (ε, 0)-differential
privacy.
13

3.1

Pure DP versus zCDP

Pure differential privacy is exactly characterized by (ξ, 0)-zCDP:
Lemma 3.2. A mechanism M : X n → Y satisfies ε-DP if and only if it satisfies (ε, 0)-zCDP.
Proof. Let x, x0 ∈ X n be neighbouring. Suppose M satisfies ε-DP. Then D∞ (M (x)kM (x0 )) ≤
ε. By monotonicity,
Dα (M (x)kM (x0 )) ≤ D∞ (M (x)kM (x0 )) ≤ ε = ε + 0 · α
for all α. So M satisfies (ε, 0)-zCDP. Conversely, suppose M satisfies (ε, 0)-zCDP. Then
D∞ (M (x)kM (x0 )) = lim Dα (M (x)kM (x0 )) ≤ lim ε + 0 · α = ε.
α→∞

α→∞

Thus M satisfies ε-DP.
We now show that ε-differential privacy implies ( 21 ε2 )-zCDP (Proposition 1.4).
Proposition 3.3. Let P and Q be probability distributions on Ω satisfying D∞ (P kQ) ≤ ε
and D∞ (QkP ) ≤ ε. Then Dα (P kQ) ≤ 21 ε2 α for all α > 1.
Remark 3.4. In particular, Proposition 3.3 shows that the KL-divergence D1 (P kQ) ≤ 12 ε2 .
A bound on the KL-divergence between random variables in terms of their max-divergence is
an important ingredient in the analysis of the advanced composition theorem [DRV10]. Our
bound sharpens (up to lower order terms) and, in our opinion, simplifies the previous bound
of D1 (P kQ) ≤ 21 ε(eε − 1) proved by Dwork and Rothblum [DR16].
Proof of Proposition 3.3. We may assume 21 εα ≤ 1, as otherwise 12 ε2 α > ε, whence the result
follows from monotonicity. We must show that
α 

1
P (x)
2
(α−1)Dα (P kQ)
≤ e 2 α(α−1)ε .
e
= E
x∼Q
Q(x)
We know that e−ε ≤
E [A(x)] =
A

P (x)
Q(x)

≤ eε for all x. Define a random function A : Ω → {e−ε , eε } by

for all x. By Jensen’s inequality,


E

P (x)
Q(x)

x∼Q

P (x)
Q(x)

α 
= E

x∼Q

h

α i
h
i
α
E [A(x)]
≤ E E [A(x) ] = E [Aα ] ,
A

x∼Q

A

A

where A denotes A(x) for a random x ∼ Q. We also have E [A] = E
A

x∼Q

h

P (x)
Q(x)

equation, we can conclude that


eε − 1
P A = e−ε = ε
A
e − e−ε

and

14

P [A = eε ] =
A

1 − e−ε
.
eε − e−ε

i

= 1. From this

Thus
e(α−1)Dα (P kQ) ≤E [Aα ]
A

eε − 1
1 − e−ε αε
−αε
·
e
+
·e
eε − e−ε
eε − e−ε
(eαε − e−αε ) − (e(α−1)ε − e−(α−1)ε )
=
eε − e−ε
sinh(αε) − sinh((α − 1)ε)
.
=
sinh(ε)
=

The result now follows from the following inequality, which is proved in Lemma B.1.
0 ≤ y < x ≤ 2 =⇒

3.2

1
sinh(x) − sinh(y)
≤ e 2 xy .
sinh(x − y)

Approximate DP versus zCDP

The statements in this section show that, up to some loss in parameters, zCDP is equivalent
to a family of (ε, δ)-DP guarantees for all δ > 0.
Lemma 3.5. Let M : X n → Y satisfy (ξ, ρ)-zCDP. Then M satisfies (ε, δ)-DP for all δ > 0
and
p
ε = ξ + ρ + 4ρ log(1/δ).
Thus to achieve a given (ε, δ)-DP guarantee it suffices to satisfy (ξ, ρ)-zCDP with
p
2
p
(ε − ξ)2
ρ=
.
ε − ξ + log(1/δ) − log(1/δ) ≈
4 log(1/δ)
Proof. Let x, x0 ∈ X n be neighbouring. Define f (y) = log(P [M (x) = y] /P [M (x0 ) = y]). Let
Y ∼ M (x) and Z = f (Y ). That is, Z = PrivLoss (M (x)kM (x0 )) is the privacy loss random
variable. Fix α ∈ (1, ∞) to be chosen later. Then

!α−1 
P
[M
(x)
=
Y
]


 = e(α−1)Dα (M (x)kM (x0 )) ≤ e(α−1)(ξ+ρα) .
E e(α−1)Z = E 
0
Y ∼M (x)
P [M (x ) = Y ]
By Markov’s inequality


E e(α−1)Z
 (α−1)Z

P [Z > ε] = P e
> e(α−1)ε ≤
≤ e(α−1)(ξ+ρα−ε) .
e(α−1)ε
Choosing α = (ε − ξ + ρ)/2ρ > 1 gives
2 /4ρ

P [Z > ε] ≤ e−(ε−ξ−ρ)
15

≤ δ.

Now, for any measurable S ⊂ Y,
P [M (x) ∈ S] =P [Y ∈ S]
≤P [Y ∈ S ∧ Z ≤ ε] + P [Z > ε]
≤P [Y ∈ S ∧ Z ≤ ε] + δ
Z
= P [M (x) = y] · I(y ∈ S) · I(f (y) ≤ ε) dy + δ
ZY
≤ eε P [M (x0 ) = y] · I(y ∈ S) dy + δ
Y
ε

=e P [M (x0 ) ∈ S] + δ.

Lemma 3.5 is not tight. In particular, we have the following refinement of Lemma 3.5,
the proof of which is deferred to the appendix (Lemma B.2).
Lemma 3.6. Let M : X n → Y satisfy (ξ, ρ)-zCDP. Then M satisfies (ε, δ)-DP for all δ > 0
and
q
√
ε = ξ + ρ + 4ρ · log( π · ρ/δ).
Alternatively M satisfies (ε, δ)-DP for all ε ≥ ξ + ρ and
 √
π·ρ



1
2
1+(ε−ξ−ρ)/2ρ
δ = e−(ε−ξ−ρ) /4ρ · min
r 2


 1+ ε−ξ−ρ + (1+ ε−ξ−ρ )2 + 4
2ρ

2ρ

.

πρ

Note that the last of three options in the minimum dominates the first two options. We
have included the first two options as they are simpler.
Now we show a partial converse to Lemma 3.5, which is proved in the appendix (Lemma
B.3).
Lemma 3.7. Let M : X n → Y satisfy (ε, δ)-DP for all δ > 0 and
p
ε = ξˆ + ρ̂ log(1/δ)


1
4
ˆ ρ̂ ∈ [0, 1]. Then M is ξˆ − 1 ρ̂ + 5√
for some constants ξ,
ρ̂,
ρ̂
-zCDP.
4
4

(4)

Thus zCDP and DP are equivalent up to a (potentially substantial) loss in parameters
and the quantification over all δ.

16

4

Zero- versus Mean-Concentrated Differential Privacy

We begin by stating the definition of mean-concentrated differential privacy:
Definition 4.1 (Mean-Concentrated Differential Privacy (mCDP) [DR16]). A randomized
mechanism M : X n → Y satisfies (µ, τ )-mean-concentrated differential privacy if, for all
x, x0 ∈ X n differing in one entry, and letting Z = PrivLoss (M (x)kM (x0 )), we have
E [Z] ≤ µ
and





λ Z−E[Z]

E e

≤ eλ

2 ·τ 2 /2

for all λ ∈ R.


In contrast (ξ, ρ)-zCDP requires that, for all α ∈ (1, ∞), E e(α−1)Z ≤ e(α−1)(ξ+ρα) , where
Z ∼ PrivLoss (M (x)kM (x0 )) is the privacy loss random variable. We now show that these
definitions are equivalent up to a (potentially significant) loss in parameters.
Lemma 4.2. If M : X n → Y satisfies (µ, τ )-mCDP, then M satisfies (µ−τ 2 /2, τ 2 /2)-zCDP.
Proof. For all α ∈ (1, ∞),
h
i
 (α−1)Z 
2 2
2
2
(α−1)(Z−E[Z])
(α−1)E[Z]
E e
=E e
·e
≤ e(α−1) τ /2 · e(α−1)µ = e(α−1)(µ−τ /2+τ /2·α) .

√
Lemma 4.3. If M : X n → Y satisfies (ξ, ρ)-zCDP, then M satisfies (ξ + ρ, O( ξ + 2ρ))mCDP.
The proof of Lemma 4.3 is deferred to the appendix.
p
Thus we can convert (µ, τ )-mCDP into (µ−τ 2 /2, τ 2 /2)-zCDP and then back to (µ, O( µ + τ 2 /2))mCDP. This may result in a large loss in parameters, which is why, for example, pure DP
can be characterised in terms of zCDP, but not in terms of mCDP.
We view zCDP as a relaxation of mCDP; mCDP requires the privacy loss to be “tightly”
concentrated about its mean and that the mean is close to the origin. The triangle inequality
then implies that the privacy loss is “weakly” concentrated about the origin. (The difference
between “tightly” and “weakly” accounts for the use of the triangle inequality.) On the other
hand, zCDP direcly requires that the privacy loss is weakly concentrated about the origin.
That is to say, zCDP gives a subgaussian bound on the privacy loss that is centered at
zero, whereas mCDP gives a subgaussian bound that is centered at the mean and separately
bounds the mean.
There may be some advantage to the stronger requirement of mCDP, either in terms of
what kind of privacy guarantee it affords, or how it can be used as an analytic tool. However,
it seems that for most applications, we only need what zCDP provides.
17

5

Group Privacy

In this section we show that zCDP provides privacy protections to small groups of individuals.
Definition 5.1 (zCDP for Groups). We say that a mechanism M : X n → Y provides
(ξ, ρ)-zCDP for groups of size k if, for every x, x0 ∈ X n differing in at most k entries, we
have
∀α ∈ (1, ∞)
Dα (M (x)kM (x0 )) ≤ ξ + ρ · α.
The usual definition of zCDP only applies to groups of size 1. Here we show that it
implies bounds for all group sizes. We begin with a technical lemma.
Lemma 5.2 (Triangle-like Inequality for Rényi Divergence). Let P , Q, and R be probability
distributions. Then
Dα (P kQ) ≤

kα
D kα−1 (P kR) + Dkα (RkQ)
kα − 1 k−1

(5)

for all k, α ∈ (1, ∞).
Proof. Let p =

kα−1
α(k−1)

and q =

(α−1)Dα (P kQ)

e

kα−1
.
α−1

Z

Then

1
p

1
q

+

=

α(k−1)+(α−1)
kα−1

= 1. By Hölder’s inequality,

P (x)α Q(x)1−α dx

=
ZΩ

P (x)α R(x)−α · R(x)α−1 Q(x)1−α · R(x)dx
Ω
"
α 
α−1 #
P (x)
R(x)
= E
·
x∼R
R(x)
Q(x)
"

pα 1/p
q(α−1) #1/q
R(x)
P (x)
· E
≤ E
x∼R
x∼R
R(x)
Q(x)
=

=e(pα−1)Dpα (P kR)/p · eq(α−1)Dq(α−1)+1 (RkQ)/q .
Taking logarithms and rearranging gives
Dα (P kQ) ≤
Now pα =

kα−1
,
k−1

pα−1
p(α−1)
kα
kα−1

=

pα − 1
Dpα (P kR) + Dq(α−1)+1 (RkQ) .
p(α − 1)

q(α − 1) + 1 = kα, and

pα − 1 kα − 1
·
=
pα
k(α − 1)

kα−1
−
k−1
kα−1
k−1

1

·

kα − 1
kα − 1 − k + 1 kα − 1
=
·
= 1,
k(α − 1)
kα − 1
k(α − 1)

as required.
18

Proposition 5.3. If M : X n → Y satisfies (ξ, ρ)-zCDP, then M gives (ξ · k
zCDP for groups of size k.
Note that

k
X
1
i=1

i

Z
=1+
1

k

1
dx ≤ 1 +
dxe

Z

k

1

Pk

1
i=1 i , ρ

· k 2 )-

1
dx = 1 + log k.
x

Thus (ξ, ρ)-zCDP implies (ξ · O(k log k), ρ · k 2 )-zCDP for groups of size k.
The Gaussian mechanism shows that k 2 ρ is the optimal dependence on ρ. However,
O(k log k)ξ is not the optimal dependence on ξ: (ξ, 0)-zCDP implies (kξ, 0)-zCDP for groups
of size k.
Proof. We show this by induction on k. The statement is clearly true for groups of size 1.
We now assume the statement holds for groups of size k − 1 and will verify it for groups of
size k.
Let x, x0 ∈ X n differ in k entries. Let x̂ ∈ X n be such that x and x̂ differ in k − 1 entries
and x0 and x̂ differ in one entry.
Then, by the induction hypothesis,
Dα (M (x)kM (x̂)) ≤ ξ · (k − 1)

k−1
X
1
i=1

i

+ ρ · (k − 1)2 · α

and, by zCDP,
Dα (M (x̂)kM (x0 )) ≤ ξ + ρ · α
for all α ∈ (1, ∞).
By (5), for any α ∈ (1, ∞),
kα
D kα−1 (M (x)kM (x̂)) + Dkα (M (x̂)kM (x0 ))
kα − 1 k−1
!
k−1
X
1
kα
−
1
kα
ξ · (k − 1)
+ ρ · (k − 1)2 ·
+ ξ + ρ · kα
≤
kα − 1
i
k
−
1
i=1
!


k−1
X
kα
1
kα
2 kα − 1
=ξ · 1 +
(k − 1)
+ρ·
(k − 1)
+ kα
kα − 1
i
kα − 1
k−1
i=1
!
k−1
X
kα
1
=ξ · 1 +
(k − 1)
+ ρ · k2 · α
kα − 1
i
i=1
!
k−1
X1
k
≤ξ · 1 +
(k − 1)
+ ρ · k2 · α
k−1
i
i=1

Dα (M (x)kM (x0 )) ≤

=ξ · k

k
X
1
i=1

i

+ ρ · k 2 · α,

where the last inequality follows from the fact that
α > 1.
19

kα
kα−1

is a decreasing function of α for

6

Lower Bounds

In this section we develop tools to prove lower bounds for zCDP. We will use group privacy to
bound the mutual information between the input and the output of a mechanism satisfying
zCDP. Thus, if we are able to construct a distribution on inputs such that any accurate
mechanism must reveal a high amount of information about its input, we obtain a lower
bound showing that no accurate mechanism satisfying zCDP can be accurate for this data
distribution.
We begin with the simplest form of our mutual information bound, which is an analogue
of the bound of [MMP+ 10] for pure differential privacy:
Proposition 6.1. Let M : X n → Y satisfy (ξ, ρ)-zCDP. Let X be a random variable in X n .
Then
I(X; M (X)) ≤ ξ · n(1 + log n) + ρ · n2 ,
where I denotes mutual information (measured in nats, rather than bits).
P
Proof. By Proposition 5.3, M provides (ξ · n ni=1 1i , ρ · n2 )-zCDP for groups of size n. Thus
0

D1 (M (x)kM (x )) ≤ ξ · n

n
X
1
i=1

i

+ ρ · n2 ≤ ξ · n(1 + log n) + ρ · n2

for all x, x0 ∈ X n . Since KL-divergence is convex,
I(X; M (X)) = E [D1 (M (x)kM (X))]
x←X
h
i
0
≤ E
E [D1 (M (x)kM (x ))]
x←X x0 ←X
h

i
2
≤ E
E
ξ
·
n(1
+
log
n)
+
ρ
·
n
0
x←X

x ←X

=ξ · n(1 + log n) + ρ · n2 .

The reason this lower bound works is the strong group privacy guarantee — even for
groups of size n, we obtain nontrivial privacy guarantees. While this is good for privacy it is
bad for usefulness, as it implies that even information that is “global” (rather than specific
to a individual or a small group) is protected. These lower bounds reinforce the connection
between group privacy and lower bounds [HT10, De12, SU15a].
In contrast, (ε, δ)-DP is not susceptible to such a lower bound because it gives a vacuous
privacy guarantee for groups of size k = O(log(1/δ)/ε). This helps explain the power of the
propose-test-release paradigm.
Furthermore, we obtain even stronger mutual information bounds when the entries of
the distribution are independent:

20

Lemma 6.2. Let M : X m → Y satisfy (ξ, ρ)-zCDP. Let X be a random variable in X m with
independent entries. Then
I (X; M (X)) ≤ (ξ + ρ) · m,
where I denotes mutual information (measured in nats, rather than bits).
Proof. First, by the chain rule for mutual information,
X
I(X; M (X)) =
I(Xi ; M (X)|X1···i−1 ),
i∈[m]

where
I(Xi ; M (X)|X1···i−1 ) =

E

[I(Xi |X1···i−1 = x; M (X)|X1···i−1 = x)]

=

E

[I(Xi ; M (x, Xi···m ))] ,

x←X1···i−1
x←X1···i−1

by independence of the Xi s.
We can define mutual information in terms of KL-divergence:
I(Xi ; M (x, Xi···m )) = E [D1 (M (x, Xi···m )|Xi = ykM (x, Xi···m ))]
y←Xi

= E [D1 (M (x, y, Xi+1···m )kM (x, Xi···m ))] .
y←Xi

By zCDP, we know that for all x ∈ X i−1 , y, y 0 ∈ X , and z ∈ X m−i , we have
D1 (M (x, y, z)kM (x, y 0 , z)) ≤ ξ + ρ.
Thus, by the convexity of KL-divergence,
D1 (M (x, y, Xi+1···m )kM (x, Xi···m )) ≤ ξ + ρ
for all x and y. The result follows.
More generally, we can combine dependent and independent entries as follows.
Theorem 6.3. Let M : X n → Y satisfy (ξ, ρ)-zCDP. Take n = m · `. Let X 1 , · · · , X m be
independent random variables on X ` . Denote X = (X 1 , · · · , X m ) ∈ X n . Then

I (X; M (X)) ≤ m · ξ · `(1 + log `) + ρ · `2 ,
where I denotes the mutual information (measured in nats, rather than bits).

21

Proof. By Proposition 5.3, M provides (ξ · `
D1 (M (x1 , · · · , xi , · · · , xm )kM (x1 , · · ·

P`

1
i=1 i , ρ

, x0i , · · ·

· `2 )-zCDP for groups of size `. Thus

, xm )) ≤ ξ ·`

`
X
1
i=1

i

+ρ·`2 ≤ ξ ·`(1+log `)+ρ·`2
(6)

for all x1 , · · · , xm , x0i ∈ X ` .
By the chain rule for mutual information,
X
I(X; M (X)) =
I(Xi ; M (X)|X1···i−1 ),
i∈[m]

where
I(Xi ; M (X)|X1···i−1 ) =

E

[I(Xi |X1···i−1 = x; M (X)|X1···i−1 = x)]

=

E

[I(Xi ; M (x, Xi···m ))] ,

x←X1···i−1
x←X1···i−1

by independence of the Xi s.
We can define mutual information in terms of KL-divergence:
I(Xi ; M (x, Xi···m )) = E [D1 (M (x, Xi···m )|Xi = ykM (x, Xi···m ))]
y←Xi

= E [D1 (M (x, y, Xi+1···m )kM (x, Xi···m ))] .
y←Xi

By (6) and the convexity of KL-divergence,
D1 (M (x, y, Xi+1···m )kM (x, Xi···m )) ≤ ξ · `(1 + log `) + ρ · `2
for all x and y. The result follows.

6.1

Example Applications of the Lower Bound

We informally discuss a few applications of our information-based lower bounds to some
simple and well-studied problems in differential privacy.
One-Way Marginals Consider M : X n → Y where X = {0, 1}d and Y = [0, 1]d . The
goal of M is to estimate the attribute means, or one-way marginals, of its input database x:
1X
M (x) ≈ x =
xi .
n
i∈[n]

It is known that this is possible subject to ε-DP if andp
only if n = Θ(d/ε) [HT10, SU15a].
This is possible subject to (ε, δ)-DP if and only if n = Θ̃( d log(1/δ)/ε), assuming δ  1/n
[BUV14, SU15a].
22

We now analyze what can be accomplished with zCDP. Adding independent noise drawn
from N (0, d/2n2 ρ) to each
p of the d coordinates of x satisfies ρ-zCDP. This gives accurate
answers as long as n  d/ρ.
For a lower bound, consider sampling X1 ∈ {0, 1}d uniformly at random. Set Xi = X1
for all i ∈ [n]. By Proposition 6.1,
I(X; M (X)) ≤ n2 ρ
for any ρ-zCDP M : ({0, 1}d )n → [0, 1]d . However, if M is accurate, we can recover (most
p of)
X1 from M (X), whence I(X; M (X)) ≥ Ω(d). This yields a lower bound of n ≥ Ω( d/ρ),
which is tight up to constant factors.
Histograms (a.k.a. Point Queries) Consider M : X n → Y, where X = [T ] and Y = RT .
The goal of M is to estimate the histogram of its input:
M (x)t ≈ ht (x) = |{i ∈ [n] : xi = t}|
For ε-DP it is possible to do this if and only if n = Θ(log(T )/ε)); the optimal algorithm
is to independently sample
M (x)t ∼ ht (x) + Laplace(2/ε).
However, for (ε, δ)-DP, it is possible to attain sample complexity n = O(log(1/δ)/ε)
[BNS13,
p
BNS16b, Theorem 3.13]. Interestingly, for zCDP we can show that n = Θ( log(T )/ρ) is
sufficient and necessary:
Sampling
M (x)t ∼ ht (x) + N (0, 1/ρ)
independently for t ∈ [T ] satisfies ρ-zCDP. Moreover,


2
P max |M (x)t − ht (x)| ≥ λ ≤ T · P [|N (0, 1/ρ)| > λ] ≤ T · e−λ ρ/2 .
t∈[T ]

i
h
p
In particular P maxt∈[T ] |M (x)t − ht (x)| ≥ log(T /β)/ρ ≤ β for all β > 0. Thus this
p
algorithm is accurate if n  log(T )/ρ.
On the other hand, if we sample X1 ∈ [T ] uniformly at random and set Xi = X1 for all
i ∈ [n], then I(X; M (X)) ≥ Ω(log T ) for any accurate M , p
as we can recover X1 from M (X)
if M is accurate. Proposition 6.1 thus implies that n ≥ Ω( log(T )/ρ) is necessary to obtain
accuracy.
This gives a strong separation between approximate DP and zCDP.

23

Randomized Response and the Exponential Mechanism Consider M : {±1}n →
{±1}n where the goal is to maximize hx, M (x)i subject to ρ-zCDP.
One solution is randomized response [War65]: Each output bit i of M is chosen independently with
eε
.
P [M (x)i = xi ] = ε
e +1
This satisfies ε-DP and, hence, 12 ε2 -zCDP. And E [hx, M (x)i] = n(eε − 1)/(eε + 1) = Θ(nε).
Alternatively, we can independently choose the output bits i according to


√
M (x)i = sign N (xi , 2/ρ) ,
which satisfies ρ-zCDP.
Turning our attention to lower bounds: Let X ∈ {±1}n be uniformly random. By
Lemma 6.2, since the bits of X are independent, we have I(X; M (X)) ≤ ρ · n for any ρzCDP M . However, if M is accurate, we can recover part of X from M (X) [BSU16], whence
I(X; M (X)) ≥ Ω(n).
Randomized response is a special case of the exponential mechanism [MT07, BLR13].
Consequently this can be interpreted as a lower bound for search problems.
Lower Bounds with Accuracy The above examples can be easily discussed in terms of a
more formal and quantitative definition of accuracy. In particular, we consider the histogram
example again:
Proposition 6.4. If M : [T ]n → RT satisfies ρ-zCDP and


n
∀x ∈ [T ]
E max M (x)t − ht (x) ≤ αn,
M

t∈[T ]

p
then n ≥ Ω( log(α2 T )/ρα2 ).
Proof. Let m = 1/10α and ` = n/m. For simplicity, assume that both m and n are integral.
Let X1 , X2 , · · · , Xm ∈ [T ]` be independent, where each Xi is ` copies of a uniformly
random element of [T ]. By Theorem 6.3,
I(X; M (X)) ≤ ρ · m · `2 = 10ραn2 ,
where X = (X1 , · · · , Xm ) ∈ X n . However,
I(X; M (X)) ≥I(f (X); g(M (X)))
=H(f (X)) − H(f (X)|g(M (X)))
=H(X) − H(X|f (X)) − H(f (X)|g(M (X)))
for any functions f and g, where H is the entropy (in nats). In particular, we let
f (x) = {t ∈ T : ∃i ∈ [n] xi = t}

and
24

g(y) = {t ∈ T : yt ≥ 5αn}.

(7)

Clearly H(X) = m log T . Furthermore, H(X|f (X)) ≤ m log m, since X can be specified by
naming m elements of f (X), which is a set of at most m elements.
If
max M (X)t − ht (X) < 5α,
(8)
t∈[T ]

then g(M (X)) contains exactly all the values in X — i.e. f (X) = g(M (X)). By Markov’s
inequality, (8) holds with probability at least 4/5.
Now we can upper bound H(f (X)|g(M (X))) by giving a scheme for specifying f (X)
given g(M (X)). If (8) holds, we simply need one bit to say so. If (8) does not hold, we need
one bit to say this and m log2 T bits to describe f (X). This gives
H(f (X)|g(M (X))) ≤ log 2 + P [f (X) 6= g(M (X))] · m log T.
Combining these inequalities gives
4
1
I(X; M (X)) ≥ m log T −m log m−log 2− m log T ≥ m log(T m−5/4 )−1 ≥ Ω(log(α1.25 T )/α).
5
5
Combining this with (7) completes the proof.
We remark that our lower bounds for zCDP can be converted to lower bounds for mCDP
using Lemma 4.2.

7

Obtaining Pure DP Mechanisms from zCDP

We now establish limits on what more can be achieved with zCDP over pure differential
privacy. In particular, we will prove that any mechanism satisfying zCDP can be converted
into a mechanism satisfying pure DP with at most a quadratic blowup in sample complexity.
Formally, we show the following theorem.
Theorem 7.1. Fix n ∈ N, n0 ∈ N, k ∈ N α > 0, and ε > 0. Let q : X → Rk and let k · k be
a norm on Rk . Assume maxx∈X kq(x)k ≤ 1.
Suppose there exists a (ξ, ρ)-zCDP mechanism M : X n → Rk such that for all x ∈ X n ,
E [kM (x) − q(x)k] ≤ α.

M

Assume ξ ≤ α2 , ρ ≤ α2 , and

4
ρ · n2 + ξ · n · (1 + log n) + 1 .
n0 ≥
εα
0

Then there exists a (ε, 0)-differentially private M 0 : X n → Rk satisfying
E [kM 0 (x) − q(x)k] ≤ 10α

M0

and

 

1
4
0
≤β
P0 kM (x) − q(x)k > 10α + 0 log
M
εn
β
0

for all x ∈ X n and β > 0.
25

Before discussing the proof of Theorem 7.1, we make some remarks about its statement:
• Unfortunately, the theorem only works for families of statistical queries q : X → Rk .
However, it works equally well for k · k∞ and k · k1 error bounds.
• If ξ = 0, we have n0 = O(n2 ρ/εα). So, if ρ, ε, and α are all constants, we have
n0 = O(n2 ). This justifies our informal statement that we can convert any mechanism satisfying zCDP into one satisfying pure DP with a quadratic blowup in sample
complexity.
• Suppose M : X n → Rk is the Gaussian mechanism scaled to satisfy ρ-zCDP and
k · k = k · k1 /k. Then
s
!
k
α = E [kM (x) − q(x)k] = Θ
.
ρn2
p
0
In particular, n = Θ( k/ρα2 ). The theorem then gives us a ε-DP M 0 : X n → Rk
with E [kM 0 (x) − q(x)k] ≤ O(α) for
0

n =Θ



n2 ρ
εα




=Θ

k
α3 ε


.

However, the Laplace mechanism achieves ε-DP and E [kM 0 (x) − q(x)k] ≤ α with
n = Θ(k/αε).
This example illustrates that the theorem is not tight in terms of α; it loses a 1/α2
factor here. However, the other parameters are tight.
• The requirement that ξ, ρ ≤ α2 is only used to show that
max min kq(x) − q(x̂)k ≤ 2α

n
x∈X n0 x̂∈X

(9)

using Lemma 7.5. However, in many situations (9) holds even when ξ, ρ  α2 . For
example, if n ≥ O(log(k)/α2 ) or even n ≥ O(V C(q)/α2 ) then (9) is automatically
satisfied.
The technical condition (9) is needed to relate the part of the proof with inputs of size
n to the part with inputs of size n0 .
Thus we can restate Theorem 7.1 with the condition ξ, ρ ≤ α2 replaced by (9). This
would be more general, but also more mysterious.
Alas, the proof of Theorem 7.1 is not constructive. Rather than directly constructing a mechanism satisfying pure DP from any mechanism satisfying zCDP, we show the contrapositive
statement: any lower bound for pure DP can be converted into a lower bound for zCDP.
Pure DP is characterized by so-called packing lower bounds and the exponential mechanism.
We begin by giving a technical lemma showing that for any output space and any desired
accuracy we have a “packing” and a “net:”
26

Lemma 7.2. Let (Y, d) be a metric space. Fix α > 0. Then there exists a countable T ⊂ Y
such that both of the following hold.
• (Net:) Either T is infinite or for all y 0 ∈ Y there exists y ∈ T with d(y, y 0 ) ≤ α.
• (Packing:) For all y, y 0 ∈ T , if y 6= y 0 , then d(y, y 0 ) > α.
Proof. Consider the following procedure for producing T .
• Initialize A ← Y and T ← ∅.
• Repeat:
– If A = ∅, terminate.
– Pick some y ∈ A.
– Update T ← T ∪ {y}.
– Update A ← {y 0 ∈ A : d(y 0 , y) > α}.
This procedure either terminates giving a finite T or runs forever enumerating a countably
infinite T .
(Net:) If T is infinite, we immediately can dispense the first condition, so suppose the
procedure terminates and T is finite. Fix y 0 ∈ Y. Since the procedure terminates, A = ∅ at
the end, which means y 0 was removed from A at some point. This means some y ∈ T was
added such that d(y 0 , y) ≤ α, as required.
(Packing:) Fix y 6= y 0 ∈ T . We assume, without loss of generality, that y was added to
T before y 0 . This means y 0 was not removed from A when y was added to T . In particular,
this means d(y 0 , y) > α.
It is well-known that a net yields a pure DP algorithm:
Lemma 7.3 (Exponential Mechanism [MT07, BLR13]). Let ` : X n ×T → R satisfy |`(x, y)−
`(x0 , y)| ≤ ∆ for all x, x0 ∈ X n differing in one entry and all y ∈ T . Then, for all ε > 0,
there exists an ε-differentially private M : X n → T such that
 

|T |
2∆
log
P `(x, M (x)) ≤ min `(x, y) +
≥1−β
M
y∈T
ε
β
and
E [`(x, M (x))] ≤ min `(x, y) +

M

y∈T

2∆
log |T |
ε

n

for all x ∈ X and β > 0.
Proof. The mechanism is defined by
P [M (x) = y] = P

M

e−`(x,y)ε/2∆
.
−`(x,y)ε/2∆
y 0 ∈T e

The analysis can be found in [DR14, Theorems 3.10 and 3.11] and [BNS+ 16a, Lemma 7.1].

27

We also show that a packing yields a lower bound for zCDP:
Lemma 7.4. Let (Y, d) be a metric space and q : X n → Y a function. Let M : X n → Y be
a (ξ, ρ)-zCDP mechanism satisfying
P [d(M (x), q(x)) > α/2] ≤ β

M

for all x ∈ X n . Let T ⊂ Y be such that d(y, y 0 ) > α, for all y, y 0 ∈ T with y 6= y 0 . Assume
that for all y ∈ T there exists x ∈ X n with q(x) = y. Then
(1 − β) log |T | − log 2 ≤ ξ · n(1 + log n) + ρ · n2 .
In particular, if ξ = 0, we have
s
p
(1 − β) log |T | − log 2
n≥
= Ω( log |T |/ρ).
ρ
Proof. Let q −1 : T → X n be a function such that q(q −1 (y)) = y for all y ∈ T . Define
f : Y → T by
f (y) = argmin d(y, y 0 )
y 0 ∈T

(breaking ties arbitrarily). Then


P f (M (q −1 (y))) = y ≥ 1 − β

M

for all y ∈ T , as P [d(M (q −1 (y)), y) > α/2] ≤ β and d(y 0 , y) > α for all y 0 ∈ T \ {y}.
M

Let Y be a uniformly random element of T and let X = q −1 (Y ). By the data processing
inequality and Proposition 6.1,
I(Y ; f (M (q −1 (Y )))) = I(q(X); f (M (X))) ≤ I(X; M (X)) ≤ ξ · n(1 + log n) + ρ · n2 .
However, P [f (M (q −1 (Y ))) = Y ] ≥ 1 − β. Denote Z = f (M (q −1 (Y ))) and let E be the
indicator of the event that Z = Y . We have
I(Y ; Z) = H(Y ) − H(Y |Z) = H(Y ) − H(Y, E|Z) = H(Y ) − H(Y |E, Z) − H(E|Z).
Clearly H(Y ) = log |T | and H(E|Z) ≤ H(E) ≤ log 2. Moreover,
H(Y |E, Z) = E [H(Y |Z, E = e)]
e←E

=P [Y = Z] · 0 + P [Y 6= Z] · H(Y |Z, Y 6= Z)
≤β · H(Y ).
Thus
I(Y ; Z) ≥ log |T | − log 2 − β log |T |.
The result now follows by combining inequalities.
28

We need one final technical lemma:
Lemma 7.5. Let q : X → Rk satisfy maxx∈X kq(x)k ≤ 1, where k · k is some norm. Let
M : X n → Rk satisfy (ξ, ρ)-zCDP and
E [kM (x) − q(x)k] ≤ α

M

for all x ∈ X n . For all n0 ,
max0 minn kq(x̂) − q(x)k ≤ 2α +

x∈X n x̂∈X

p
2(ξ + ρ).

The proof of Lemma 7.5 is deferred to the appendix.
Now we can combine Lemmas 7.2, 7.3, 7.4, and 7.5 to prove Theorem 7.1:
o
n
P
Proof of Theorem 7.1. Apply Lemma 7.2 with Y = q(x) = n1 i∈[n] q(xi ) : x ∈ X n ⊂ Rk
and d being the metric induced by the norm to obtain T ⊂ Y:
• (Net:) Either T is infinite or for all y 0 ∈ {q(x) : x ∈ X n } ⊂ Rk there exists y ∈ T with
ky − y 0 k ≤ 4α.
• (Packing:) For all y, y 0 ∈ T , if y 6= y 0 , then ky − y 0 k > 4α.
By Markov’s inequality
1
P [kM (x) − q(x)k > 2α] ≤ .
M
2
Thus, by Lemma 7.4,
1
log |T | − log 2 ≤ ξ · n(1 + log n) + ρ · n2 .
2
This gives an upper bound on |T |. In particular, T must be finite.
0
Let M 0 : X n → Rk be the exponential mechanism (Lemma 7.3) instantiated with T and
`(x, y) = ky − q(x)k. We have

 
4
|T |
P kM (x) − q(x)k ≤ min ky − q(x)k + 0 log
≥1−β
M
y∈T
εn
β
and

4
log |T |
M
y∈T
εn0
0
0
for all x ∈ X n . For x ∈ X n , by the Net property and Lemma 7.5,
E [kM (x) − q(x)k] ≤ min ky − q(x)k +

min ky − q(x)k ≤ min min
ky − y 0 k + ky 0 − q(x)k
y∈T
y∈T y 0 ∈Y



0
0
= min
min ky − y k + ky − q(x)k
0
y ∈Y

y∈T

≤ min
(4α + ky 0 − q(x)k)
0
y ∈Y

= minn (4α + kq(x̂) − q(x)k)
x̂∈X
p
≤4α + 2α + 2(ξ + ρ).
29

Furthermore,

4
8
log |T | ≤ 0 ξ · n(1 + log n) + ρ · n2 + log 2 ≤ 2α.
0
εn
εn
The theorem now follows by combining inequalities.

8

Approximate zCDP

In the spirit of approximate DP, we propose a relaxation of zCDP:
Definition 8.1 (Approximate zCDP). A randomised mechanism M : X n → Y is δapproximately (ξ, ρ)-zCDP if, for all x, x0 ∈ X n differing on a single entry, there exist events
E = E(M (x)) and E 0 = E 0 (M (x0 )) such that, for all α ∈ (1, ∞),
Dα (M (x)|E kM (x0 )|E 0 ) ≤ ξ + ρ · α
and P [E] ≥ 1 − δ and
M (x)

and

Dα (M (x0 )|E 0 kM (x)|E ) ≤ ξ + ρ · α

P [E 0 ] ≥ 1 − δ.

M (x0 )

Clearly 0-approximate zCDP is simply zCDP. Hence we have a generalization of zCDP.
As we will show later in this section, δ-approximate (ε, 0)-zCDP is equivalent to (ε, δ)-DP.
Thus we have also generalized approximate DP. Hence, this definition unifies both relaxations
of pure DP.
Approximate zCDP is a three-parameter definition which allows us to capture many
different aspects of differential privacy. However, three parameters is quite overwhelming.
We believe that use of the one-parameter ρ-zCDP (or the two-parameter δ-approximate
ρ-zCDP if necessary) is sufficient for most purposes.
It is easy to verify that the definition of approximate zCDP satisfies the following basic
properties.
Lemma 8.2 (Composition & Postprocessing). Let M : X n → Y and M 0 : X n × Y → Z be
randomized algorithms. Suppose M satisfies δ-approximate (ξ, ρ)-zCDP and, for all y ∈ Y,
M 0 (·, y) : X n → Z satisfies δ 0 -approximate (ξ 0 , ρ0 )-zCDP. Define M 00 : X n → Z by M 00 (x) =
M 0 (x, M (x)). Then M 00 satisfies (δ + δ 0 − δ · δ 0 )-approximate (ξ + ξ 0 , ρ + ρ0 )-zCDP.
Lemma 8.3 (Tradeoff). Suppose M : X n → Y satisfies δ-approximate (ξ, 0)-zCDP. Then
M satisfies δ-approximate ξ-zCDP and δ-approximate 21 ξ 2 -zCDP.
However, the strong group privacy guarantees of Section 5 no longer apply to approximate
zCDP and, hence, the strong lower bounds of Section 6 also no longer hold. Circumventing
these lower bounds is part of the motivation for considering approximate zCDP. However,
approximate zCDP is not necessarily the only way to relax zCDP that circumvents our lower
bounds:
Proving the group privacy bound requires “inflating” the parameter α: Suppose M :
n
X → Y satisfies ρ-zCDP and x, x0 ∈ X n differ on k entries. To prove Dα (M (x)kM (x0 )) ≤

30

k 2 ρα, the proof of Proposition 5.3 requires a bound on Dkα (M (x00 )kM (x000 )) for x00 , x000 ∈ X n
differing on a single entry.
Consider relaxing the definition of zCDP to only require the bound (1) or (2) to hold
when α ≤ m:
Definition 8.4 (Bounded zCDP). We say that M : X n → Y satisfies m-bounded (ξ, ρ)zCDP if, for all x, x0 ∈ X n differing in only one entry and all α ∈ (1, m), Dα (M (x)kM (x0 )) ≤
ξ + ρ · α.
This relaxed definition may also be able to circumvent the group privacy-based lower
bounds, as our group privacy proof would no longer work for groups of size larger than m.
We do not know what group privacy guarantees Definition 8.4 provides for groups of size
k  m. This relaxed definition may be worth exploring, but is beyond the scope of our
work.

8.1

Approximate DP Implies Approximate zCDP

We can convert approximate DP to approximate zCDP using the following lemma.
First we define a approximate DP version of the randomized response mechanism:
Definition 8.5. For ε ≥ 0 and δ ∈ [0, 1], define M̃ε,δ : {0, 1} → {0, 1} × {⊥, >} by
h
i
h
i
P M̃ε,δ (b) = (b, >) =δ,
P M̃ε,δ (b) = (1 − b, >) =0,
h
i
h
i
1
eε
,
P
M̃
(b)
=
(1
−
b,
⊥)
=(1
−
δ)
P M̃ε,δ (b) = (b, ⊥) =(1 − δ)
ε,δ
1 + eε
1 + eε
for both b ∈ {0, 1}.
The above mechanism is “complete” for approximate DP:
Lemma 8.6 ([KOV15], [MV16, Lemma 3.2]). For every (ε, δ)-DP M : X n → Y and all
x0 , x1 ∈ X n differing in one entry, there exists a randomized T : {0, 1} × {⊥, >} → Y such
that T (M̃ε,δ (b)) has the same distribution as M (xb ) for both b ∈ {0, 1}.
Corollary 8.7. If M : X n → Y satisfies (ε, δ)-DP, then M satisfies δ-approximate (ε, 0)zCDP, which, in turn, implies δ-approximate (0, 21 ε2 )-zCDP.
Proof. Fix neighbouring x0 , x1 ∈ X n . Let T : {0, 1} × {⊥, >} → Y be as in Lemma 8.6.
Now we can write M (xb ) = T (M̃ε,δ (b)) for b ∈ {0, 1}. Define events E0 and E1 by
h
i
Eb ≡ M̃ε,δ (b) ∈ {0, 1} × {⊥} .
By definition, for both b ∈ {0, 1},

P

[Eb ] = 1 − δ and

M̃ε,δ (b)





M (xb )|Eb = T M̃ε,δ (b)|M̃ε,δ (b)∈{0,1}×{⊥} = T (M̃ε,0 (b)).
31



We have D∞ M̃ε,0 (b) M̃ε,0 (1 − b) ≤ ε for both b ∈ {0, 1}. By postprocessing and
monotonicity, this implies

Dα M (xb )|Eb M (x1−b )|E1−b ≤ ε
for both b ∈ {0, 1} and all α ∈ (1, ∞). Thus we have satisfied the definition of δ-approximate
(ε, 0)-zCDP.
Applying Proposition 3.3 shows that this also implies δ-approximate (0, 12 ε2 )-zCDP.

8.2

Approximate zCDP Implies Approximate DP

Lemma 8.8. Suppose M : X n → Y satisfies δ-approximate (ξ, ρ)-zCDP. If ρ = 0, then M
satisfies (ξ, δ)-DP. In general, M satisfies (ε, δ + (1 − δ)δ 0 )-DP for all ε ≥ ξ + ρ, where

1


√


 π·ρ
2
1
.
δ 0 = e−(ε−ξ−ρ) /4ρ · min
1+(ε−ξ−ρ)/2ρ

2

r


 1+ ε−ξ−ρ + (1+ ε−ξ−ρ )2 + 4
2ρ
2ρ
πρ
Proof. Fix neighbouring x, x0 ∈ X n and let E and E 0 be the events promised by definition
8.1. We can assume, without loss of generality that P [E] = P [E 0 ] = 1 − δ.
Fix S ⊂ Y. Then
P [M (x) ∈ S] =P [M (x) ∈ S | E] · P [E] + P [M (x) ∈ S | ¬E] · P [¬E]
≤P [M (x) ∈ S | E] · (1 − δ) + δ,
P [M (x0 ) ∈ S] =P [M (x0 ) ∈ S | E 0 ] · P [E 0 ] + P [M (x0 ) ∈ S | ¬E 0 ] · P [¬E 0 ]
≥P [M (x0 ) ∈ S | E 0 ] · (1 − δ).
Firstly, if ρ = 0, then
P [M (x) ∈ S | E] ≤ eξ P [M (x0 ) ∈ S | E 0 ]
and
P [M (x) ∈ S] ≤ P [M (x) ∈ S | E]·(1−δ)+δ ≤ eξ P [M (x0 ) ∈ S | E 0 ]·(1−δ)+δ ≤ eξ P [M (x0 ) ∈ S]+δ,
which proves the first half of the lemma.
Secondly, by Lemma B.2 (cf. Lemma 3.5), for all ε ≥ ξ + ρ,

1


√


 π·ρ
2
1
P [M (x) ∈ S | E] ≤ eε P [M (x0 ) ∈ S | E 0 ] + e−(ε−ξ−ρ) /4ρ · min
1+(ε−ξ−ρ)/2ρ


r 2


 1+ ε−ξ−ρ + (1+ ε−ξ−ρ )2 + 4
2ρ

32

2ρ

πρ

.

Thus

2 /4ρ

P [M (x) ∈ S] ≤ eε P [M (x0 ) ∈ S] + δ + (1 − δ) · e−(ε−ξ−ρ)

· min


1


√


 π·ρ






8.3

1
1+(ε−ξ−ρ)/2ρ
r 2
1+ ε−ξ−ρ
+
2ρ

(1+ ε−ξ−ρ
2ρ )

.
2

4
+ πρ

Application of Approximate zCDP

Approximate zCDP subsumes approximate DP. A result of this is that we can apply our
tightened lemmas to give a tighter version of the so-called advanced composition theorem
[DRV10].
Note that the following results are subsumed by the bounds of Kairouz, Oh, and Viswanath
[KOV15] and Murtagh and Vadhan [MV16]. However, these bounds may be extended to analyse the composition of mechanisms satisfying CDP with mechanisms satisfying approximate
DP. We believe that such a “unified” analysis of composition will be useful.
Applying Corollary 8.7, Lemma 8.2, and Lemma 8.8 yields the following result.
Corollary 8.9. Let M1 , · · · , Mk : X n → Y and
let M : X n → Y k be their composition.
P
k
Suppose each Mi satisfies (εi , δi )-DP. Set ρ = 12 i ε2i . Then M satisfies
!
k
Y
ε, 1 − (1 − δ 0 ) (1 − δi ) -DP
i

for all ε ≥ ρ and
2 /4ρ

δ 0 = e−(ε−ρ)

· min


1


√


 π·ρ






1
1+(ε−ρ)/2ρ
r 2
1+ ε−ρ
+
2ρ

.
2

(1+ ε−ρ
2ρ )

4
+ πρ

A slight restatement is the following
n
k
Corollary 8.10. Let M1 , · · · , Mk : X n → Y and
Pklet2 M : X → Y be their composition.
1
2
Suppose each Mi satisfies (εi , δi )-DP. Set ε = 2 i εi . Then M satisfies
!
k
Y
2
0
ε + 2λε, 1 − (1 − δ ) (1 − δi ) -DP
i

for all λ ≥ 0 and
2

δ 0 = e−λ · min


1√



 π·ε





.

1
1+λ/ε

1+ λε +

33

q 2
2
(1+ λε ) +

4
πε2

Finally, by picking the second term in the minimum and using 1 −
we have the following simpler form of the lemma.

Q

i (1

− δi ) ≤

P

i δi ,

Corollary 8.11. Let M1 , · · · , Mk : X n → Y and let M : X n → Y k be their composition.
Suppose each Mi satisfies (εi , δi )-DP. Then M satisfies
r


√
π
1
2
−λ2
kεk2 + 2λkεk2 ,
· kεk2 · e
+ kδk1 -DP
2
2
for all λ ≥ 0. Alternatively M satisfies


q
p
1
2
0
0
kεk2 + 2 log( π/2 · kεk2 /δ ) · kεk2 , δ + kδk1 -DP
2
for all δ 0 ≥ 0.
In comparison to the composition theorem
p of [DRV10], we save modestly by a constant
factor in the first term and, in most cases π/2kεk2 < 1, whence the logarithmic term is an
improvement over the usual advanced composition theorem.
Acknowledgements We thank Cynthia Dwork and Guy Rothblum for sharing a preliminary draft of their work with us. We also thank Ilya Mironov, Kobbi Nissim, Adam Smith,
Salil Vadhan, and the Harvard Differential Privacy Research Group for helpful discussions
and suggestions.

References
[AS64]

Milton
Abramowitz
and
mathematical
functions:
ematical
tables,
volume
http://people.math.sfu.ca/

Irene
A
Stegun.
Handbook of
with
formulas,
graphs,
and
math55.
Courier
Corporation,
1964.
cbm/aands/abramowitz and stegun.pdf.

[BLR13]

Avrim Blum, Katrina Ligett, and Aaron Roth. A learning theory approach to
noninteractive database privacy. J. ACM, 60(2):12, 2013.

[BNS13]

Amos Beimel, Kobbi Nissim, and Uri Stemmer. Private learning and sanitization:
Pure vs. approximate differential privacy. In Approximation, Randomization, and
Combinatorial Optimization. Algorithms and Techniques - 16th International
Workshop, APPROX 2013, and 17th International Workshop, RANDOM 2013,
Berkeley, CA, USA, August 21-23, 2013. Proceedings, pages 363–378, 2013.

[BNS+ 16a] Raef Bassily, Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer, and
Jonathan Ullman. Algorithmic stability for adaptive data analysis. In STOC,
2016.
34

[BNS16b]

Mark Bun, Kobbi Nissim, and Uri Stemmer. Simultaneous private learning of
multiple concepts. In Proceedings of the 2016 ACM Conference on Innovations
in Theoretical Computer Science, ITCS ’16, pages 369–380, New York, NY, USA,
2016. ACM.

[BNSV15] Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil Vadhan. Differentially private
release and learning of threshold functions. In Foundations of Computer Science
(FOCS), 2015 IEEE 56th Annual Symposium on, pages 634–649. IEEE, 2015.
[BSU16]

Mark Bun, Thomas Steinke, and Jonathan Ullman. Make up your mind: The
price of online queries in differential privacy. CoRR, abs/1604.04618, 2016.

[BUV14]

Mark Bun, Jonathan Ullman, and Salil P. Vadhan. Fingerprinting codes and the
price of approximate differential privacy. In Symposium on Theory of Computing,
STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 1–10, 2014.

[Coo09]

John D Cook. Upper and lower bounds for the normal distribution function,
2009.

[De12]

Anindya De. Lower bounds in differential privacy. In Proceedings of the 9th
International Conference on Theory of Cryptography, TCC’12, pages 321–338,
Berlin, Heidelberg, 2012. Springer-Verlag.

[DKM+ 06] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and
Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In
Advances in Cryptology - EUROCRYPT 2006, 25th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg, Russia, May 28 - June 1, 2006, Proceedings, pages 486–503, 2006.
[DL09]

Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC
2009, Bethesda, MD, USA, May 31 - June 2, 2009, pages 371–380, 2009.

[DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating
noise to sensitivity in private data analysis. In Theory of Cryptography, Third
Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March
4-7, 2006, Proceedings, pages 265–284, 2006.
[DR14]

Cynthia Dwork and Aaron Roth. The Algorithmic Foundations of Differential
Privacy, volume 9. Foundations and Trends R in Theoretical Computer Sc, 2014.

[DR16]

Cynthia Dwork and Guy Rothblum. Concentrated differential privacy. CoRR,
abs/1603.01887, 2016.

[DRV10]

Cynthia Dwork, Guy N. Rothblum, and Salil P. Vadhan. Boosting and differential privacy. In IEEE Symposium on Foundations of Computer Science (FOCS
’10), pages 51–60. IEEE, 23–26 October 2010.
35

[DSS+ 15]

Cynthia Dwork, Adam Smith, Thomas Steinke, Jonathan Ullman, and Salil
Vadhan. Robust traceability from trace amounts. In FOCS, 2015.

[Due10]

L. Duembgen. Bounding Standard Gaussian Tail Probabilities. ArXiv e-prints,
December 2010.

[hh]

hbp
(http://math.stackexchange.com/users/131476/hbp).
Hyperbolic
trig
inequality.
Mathematics
Stack
Exchange.
URL:http://math.stackexchange.com/q/1461426 (version: 2015-10-02).

[HT10]

Moritz Hardt and Kunal Talwar. On the geometry of differential privacy. In Proceedings of the Forty-second ACM Symposium on Theory of Computing, STOC
’10, pages 705–714, New York, NY, USA, 2010. ACM.

[KOV15]

Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem
for differential privacy. In Proceedings of the 32nd International Conference on
Machine Learning, ICML 2015, Lille, France, 6-11 July 2015, pages 1376–1385,
2015.

[MMP+ 10] Andrew McGregor, Ilya Mironov, Toniann Pitassi, Omer Reingold, Kunal Talwar, and Salil P. Vadhan. The limits of two-party differential privacy. In 51th
Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010,
October 23-26, 2010, Las Vegas, Nevada, USA, pages 81–90, 2010.
[MT07]

F. McSherry and K. Talwar. Mechanism design via differential privacy. In Foundations of Computer Science, 2007. FOCS ’07. 48th Annual IEEE Symposium
on, pages 94–103, Oct 2007.

[MV16]

Jack Murtagh and Salil P. Vadhan. The complexity of computing the optimal
composition of differential privacy. In Theory of Cryptography - 13th International Conference, TCC 2016-A, Tel Aviv, Israel, January 10-13, 2016, Proceedings, Part I, pages 157–175, 2016.

[Rén61]

Alfréd Ré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, pages 547–561, Berkeley, Calif.,
1961. University of California Press.

[Riv12]

Omar Rivasplata. Subgaussian random variables: An expository note, 2012.
http://www.stat.cmu.edu/ arinaldo/36788/subgaussians.pdf.

[SU15a]

Thomas Steinke and Jonathan Ullman. Between pure and approximate differential privacy. CoRR, abs/1501.06095, 2015.

[SU15b]

Thomas Steinke and Jonathan Ullman.
Interactive fingerprinting codes
and the hardness of preventing false discovery.
In COLT, 2015.
http://arxiv.org/abs/1410.1228.
36

[Tar08]

Gábor Tardos. Optimal probabilistic fingerprint codes. J. ACM, 55(2), 2008.

[Ull13]

Jonathan Ullman. Answering n {2+ o (1)} counting queries with differential
privacy is hard. In Proceedings of the forty-fifth annual ACM symposium on
Theory of computing, pages 361–370. ACM, 2013.

[vEH14]

T. van Erven and P. Harremos. Rényi divergence and Kullback-Leibler divergence. IEEE Transactions on Information Theory, 60(7):3797–3820, July 2014.

[War65]

Stanley L. Warner. Randomized response: A survey technique for eliminating
evasive answer bias. Journal of the American Statistical Association, 60(309):63–
69, 1965. PMID: 12261830.

A

Postprocessing and mCDP

In this appendix we give a family of counterexamples showing that mCDP is not closed
under postprocessing (unlike zCDP).
Fix a parameter σ > 0, and consider the Gaussian mechanism for a single bit M :
{−1, 1} → R, where M (x) samples from N (x, σ 2 ). The mechanism M satisfies (2/σ 2 , 2/σ)mCDP (and also (2/σ 2 )-zCDP).
Now consider the postprocessing function T : R → {−1, 0, 1} defined as follows:


if y > t
1
T (y) = −1 if y < −t


0
if − t ≤ y ≤ t.
We examine the mCDP guarantees of the postprocessed mechanism M 0 : {−1, 1} →
{−1, 0, 1} defined by M 0 (x) = T (M (x)):
Proposition A.1. Let σ ≥ 1 and let t ≥ 6σ 3 + 1. Then while the mechanism M is
(2/σ 2 , 2/σ)-mCDP, the postprocessed mechanism M 0 is not (2/σ 2 , 2/σ)-mCDP.
Proof. For each x ∈ {−1, 1}, let


p = P [M 0 (x) = x] = P N (0, σ 2 ) > t − 1 ,


q = P [M 0 (x) = −x] = P N (0, σ 2 ) > t + 1 .
Note that p > q. Hence, for each x ∈ {−1, 1},


P [M 0 (x) = 0] = P N (0, σ 2 ) ∈ [−t − 1, t − 1] = 1 − p − q.
Let f (y) = log(P [M (1) = y] /P [M (−1) = y]), and observe that
p
f (1) = log ,
q

q
f (−1) = log ,
p
37

f (0) = 0.

Now consider the privacy loss random variable Z = PrivLoss (M (1)kM (−1)) = f (M (1)).
Then Z is distributed according to

p

log q w.p. p
Z = log pq w.p. q
.


0
w.p. 1 − p − q
This gives E [Z] = (p − q) log(p/q) ≥ 0. For λ ∈ R, we have
!  
 λ
 λ
−λ(p−q)
q
p
p
λ(Z−E[Z])
+q
+1−p−q ·
.
E e
= p
q
p
q
h
i
2
2
λ(Z−E[Z])
If M 0 were to satisfy (2/σ 2 , 2/σ)-mCDP, we would have E e
≤ e2λ /σ for all
λ > 0. We will show that this does not hold for any setting of parameters σ ≥ 1 and
t ≥ 6σ 3 + 1, which shows that mCDP is not closed under postprocessing.11
h

i

Lemma A.2. The values p, q satisfy the following inequalities:
q
q
2
2
1
σ
1
−(t−1)2 /2σ 2
·
·
e
≤
p
≤
· σ · e−(t−1) /2σ
1.
2π t+σ−1
2π t−1
2.

p
q

≥ e2t/σ

2

Proof. We have [Coo09, Equation (5)]
q
q
2 −x2 /2
2 −x2 /2
e
·
x
e
π
π
≤
P
[N
(0,
1)
>
x]
≤
x2 + 1
x
for all x ≥ 0. Thus
q
q


2 −(t−1)2 /2σ 2
2 −(t−1)2 /2σ 2
e
·
(t
−
1)
e
·σ
t−1
π
π
≤
p
=
P
N
(0,
1)
>
≤
.
σ · ((t − 1)2 /σ 2 + 1)
σ
t−1
The first part now follows from the fact that σ ≤ t − 1.
To establish the second inequality, we write
Z ∞
1
2
2
p= √
e−x /2σ dx
2
2πσ Zt−1
∞
1
2
2
e−(u−2) /2σ du
=√
2
2πσ Zt+1
∞
1
2
2
2
=√
e(4u−4)/2σ · e−u /2σ du
2
2πσ t+1 Z
∞
1
2
2
2
≥ e2t/σ √
e−u /2σ du
2
2πσ t+1
2t/σ 2
=e
· q.
11

For specific settings of parameters, this can be verified numerically. (For example, with the values σ = 1,
t = 3, and λ = 2.)

38

By Lemma A.2,
h

λ(Z−E[Z])

E e

i

!  
 λ
 λ
−λ(p−q)
p
q
p
= p
+q
+1−p−q ·
q
p
q
 λ(1−(p−q))
p
≥p
q
r
σ
1
2
2
2
·
· e−(t−1) /2σ · (e2t/σ )λ(1−p) .
≥
2π t + σ − 1

Now set λ = 2t . Then this quantity becomes
r

σ
1
2
2
2
2
2
2
·
· e−(t−1) /2σ · et (1−p)/σ = et /2σ ·
2π t + σ − 1

We now examine the term
r
2
2
1 σt2 e−(t−1) /2σ
2
pt ≤
2π
t−1
r
5/2 −(t−1)
1 t e
≤
4π t − 1
1
≤
2

r

σ
1
·
· exp
2π t + σ − 1




t
pt2
1
− 2 − 2 .
σ2
σ
2σ
(10)

by Lemma A.2
for t ≥ 2σ 2 + 1
for t ≥ 3.

We may thus bound (10) from below by
r
r




σ
t−1
t−1
1
1 1
t2 /2σ 2
t2 /2σ 2
e
·
·
· exp
≥e
·
· · exp
2π t + σ − 1
2σ 2
2π 2t
2σ 2

2
The expression
is monotone increasing for t ≥ 2σ 2 . Thus, it is strictly
√ exp((t − 1)/2σ )/2t
larger than 2π as long as t ≥ 6σ 3 + 1.

B

Miscellaneous Proofs and Lemmata

Lemma B.1.
0 ≤ y < x ≤ 2 =⇒

1
sinh(x) − sinh(y)
≤ e 2 xy .
sinh(x − y)
1

This technical lemma may be “verified” numerically by inspecting a plot of z = e 2 xy ·
sinh(x − y) − (sinh(x) − sinh(y)) for (x, y) ∈ [0, 2]2 .
39

For intuition, consider the third-order Taylor approximation to sinh(x) about 0:
1
sinh(x) = x + x3 ± O(x5 ).
6
Then we can approximate
x + 61 x3 − (y + 16 y 3 )
sinh(x) − sinh(y)
≈
sinh(x − y)
(x − y) + 16 (x − y)3
3xy(x − y)
=1+
6(x − y) + (x − y)3
1
≤ 1 + xy
2
1
xy
≤ e2 .
Unfortunately, turning this intuition into an actual proof is quite involved. We instead
provide a proof from [hh]:
Proof. We need the following hyperbolic trigonometric identities.
cosh (w + z) = cosh(w) cosh(z) + sinh(w) sinh(z)
= cosh(w) cosh(z) (1 + tanh(w) tanh(z)) ,

1
sinh(x − y) = ex−y + 1 − 1 − e−(x−y)
2


1 (x−y)/2
= e
− e−(x−y)/2 e(x−y)/2 + e−(x−y)/2
2




x−y
x−y
=2 sinh
cosh
2
2

 
 



x
x−y
−y
−y
x
=2 sinh
cosh
tanh
cosh
1 + tanh
2
2
2
2
2











x
y
x
y
x−y
cosh
cosh
1 − tanh
tanh
,
=2 sinh
2
2
2
2
2

1
sinh(x) − sinh(y) = ex − e−x − ey + e−y
2


1 (x−y)/2
= e
− e−(x−y)/2 e(x+y)/2 + e−(x+y)/2
2




x−y
x+y
=2 sinh
cosh
2
2




y  
x
 y 
x
x−y
=2 sinh
cosh
cosh
1 + tanh
tanh
.
2
2
2
2
2

40

We also use the fact that 0 ≤ tanh(z) < min{z, 1} for all z > 0. Thus


1 + tanh x2 tanh y2
sinh(x) − sinh(y)
1+t


=
,
y =
x
sinh(x − y)
1−t
1 − tanh 2 tanh 2


where t = tanh x2 tanh y2 < 1. Now
1+t
≤ exy/2 ⇐⇒ 1 + t ≤ (1 − t)exy/2 ⇐⇒ (exy/2 + 1)t ≤ exy/2 − 1
1−t
 xy 
exy/4 − e−xy/4
exy/2 − 1
= xy/4
.
⇐⇒ t ≤ xy/2
= tanh
e
+1
e
+ e−xy/4
4



So it only remains to show that tanh x2 tanh y2 ≤ tanh xy
. This is clearly true when
4
y = 0. Now
x
y 
x
y  1
y  x
∂
tanh
tanh
= tanh
cosh−2
≤ cosh−2
∂y
2
2
2
2 2
2 4
and

 xy 
 xy  x
∂
tanh
= cosh−2
.
∂y
4
4 4

Since 0 ≤ y < x ≤ 2, we have 0 ≤ xy/4 ≤ y/2 and, hence, cosh(y/2) ≥ cosh(xy/4). Thus
x
y 
 xy 
∂
∂
tanh
tanh
≤
tanh
.
∂y
2
2
∂y
4
The inequality now follows by integration of the inequality on the derivatives.
The following lemma immediately implies Lemma 3.6 and is also used to prove Lemma
8.8.
Lemma B.2. Let P and Q be probability distributions on Y with Dα (P kQ) ≤ ξ + ρ · α for
all α ∈ (1, ∞). Then, for any ε ≥ ξ + ρ and

1


√


 π·ρ
2
1
δ = e−(ε−ξ−ρ) /4ρ · min
,
1+(ε−ξ−ρ)/2ρ

2

r


 1+ ε−ξ−ρ + (1+ ε−ξ−ρ )2 + 4
2ρ
2ρ
πρ
we have
P (S) ≤ eε Q(S) + δ
for all (measurable) S.

41

Proof. Define f : Y → R by f (y) = log(P (y)/Q(y)). Let Y ∼ P , Y 0 ∼ Q and let Z = f (Y )
be the privacy loss random variable. That is, Z = PrivLoss (P kQ). For any measurable
S ⊂ Y,
P (S) =P [Y ∈ S]
=P [Y ∈ S ∧ f (Y ) ≤ ε] + P [Y ∈ S ∧ f (Y ) > ε]
Z
= P (y)I[f (y) ≤ ε]dy + P [Y ∈ S ∧ f (Y ) > ε]
ZS
= P (y)I[P (y) ≤ eε Q(y)]dy + P [Y ∈ S ∧ f (Y ) > ε]
ZS
≤ eε Q(y)I[f (y) ≤ ε]dy + P [Y ∈ S ∧ f (Y ) > ε]
S

=eε P [Y 0 ∈ S ∧ f (Y 0 ) ≤ ε] + P [Y ∈ S ∧ f (Y ) > ε]
=eε P [Y 0 ∈ S] − eε P [Y 0 ∈ S ∧ f (Y 0 ) > ε] + P [Y ∈ S ∧ f (Y ) > ε]


≤eε P [Y 0 ∈ S] + P [f (Y ) > ε] − eε P [f (Y 0 ) > ε] .
Thus we want to bound
δ =P [f (Y ) > ε] − eε P [f (Y 0 ) > ε]
=E [I[f (Y ) > ε]] − E0 [eε I[f (Y 0 ) > ε]]
Y
Y
Z
eε I[f (y) > ε]Q(y)dy
=E [I[f (Y ) > ε]] −
Y
ZY
Q(y)
eε I[f (y) > ε]
=E [I[f (Y ) > ε]] −
P (y)dy
Y
P (y)
Y


=E [I[f (Y ) > ε]] − E eε I[f (Y ) > ε]e−f (Y )
Y
Y


ε−Z
=E I[Z > ε] 1 − e
Z



=E max 0, 1 − eε−Z
Z
Z ∞

=
1 − eε−z P [Z = z] dz.
ε

In particular,
δ ≤ E [I[Z > ε]] = P [Z > ε] .
Z

Alternatively, by integration by parts,
Z
δ=

∞

eε−z P [Z > z] dz.

ε

Now it remains to bound P [Z > z].
42

As in Lemma 3.5, by Markov’s inequality, for all α > 1 and λ > ξ + ρ,


0
E e(α−1)Z
e(α−1)Dα (M (x)kM (x ))
P [Z > λ] ≤
≤
≤ e(α−1)(ξ+ρα−λ) .
e(α−1)λ
e(α−1)λ
Choosing α = (λ − ξ + ρ)/2ρ > 1 gives
P [Z > λ] ≤ e−(λ−ξ−ρ)
2 /4ρ

Thus δ ≤ P [Z > ε] ≤ e−(ε−ξ−ρ)
Z

. Furthermore,

eε−z P [Z > z] dz

Zε ∞
≤
Z

.

∞

δ=

ε

2 /4ρ

2 /4ρ

eε−z e−(z−ξ−ρ)

∞

dz

2

e−(z−ξ+ρ) /4ρ−ξ+ε dz
ε
√
Z
eε−ξ · 2π · 2ρ ∞ −(z−ξ+ρ)2 /4ρ
= √
e
dz
2π · 2ρ
ε
p
=eε−ξ · 2π · 2ρ · P [N (ξ − ρ, 2ρ) > ε]


√
ε+ρ−ξ
ε−ξ
=e · 2 π · ρ · P N (0, 1) > √
.
2ρ
√
2
Define h(x) = P [N (0, 1) > x] · 2π · ex /2 . Then
=

δ≤e

ε−ξ

√
·2 π·ρ· √

h





ε+ρ−ξ
√
2ρ
2


2π · e

ε+ρ−ξ
√
2ρ

/2



p
p
ε−ξ−ρ
−(ε−ξ−ρ)2 /4ρ
= 2ρ · e
·h
2ρ + √
.
2ρ

Now we can substitute upper bounds on h to obtain the desired results.
p
2
First we use P [N (0, 1) > x] ≤ 12 e−x /2 , which holds for all x ≥ 0. That is, h(x) ≤ π/2,
whence
r
p
π
−(ε−ξ−ρ)2 /4ρ
δ ≤ 2ρ · e
·
.
2
This rearranges to
q
√
ε ≤ ξ + ρ + 4ρ · log( π · ρ/δ).
√
2
Alternatively, we can use P [N (0, 1) > x] ≤ e−x /2 / 2πx, which holds for all x > 0. That
is, h(x) ≤ 1/x and
p
2
δ ≤ 2ρ · e−(ε−ξ−ρ) /4ρ · h



ε−ξ+ρ
√
2ρ



2

2ρ
e−(ε−ξ−ρ) /4ρ
2
=
· e−(ε−ξ−ρ) /4ρ =
·.
ε+ρ−ξ
1 + (ε − ξ − ρ)/2ρ
43

Finally, we can use P [N (0, 1) > x] ≤ e−x

2 /2

· 2/(

p
√
x2 + 8/π + x) 2π, which holds for

all x ≥ 0 p
[Due10, Equation (4)][Coo09, Equation (7)][AS64, Equation 7.1.13]. That is,
h(x) ≤ 2/( x2 + 8/π + x) and
p
2
δ ≤ 2ρ · e−(ε−ξ−ρ) /4ρ · h



ε−ξ+ρ
√
2ρ



2

2 · e−(ε−ξ−ρ) /4ρ
r
=
2
ε−ξ−ρ
1 + 2ρ +
1 + ε−ξ−ρ
+
2ρ

.
4
πρ

Lemma B.3 (Restating Lemma 3.7). Let M : X n → Y satisfy (ε, δ)-DP for all δ > 0 and
p
(11)
ε = ξˆ + ρ̂ log(1/δ)


1
4
ˆ ρ̂ ∈ [0, 1]. Then M is ξˆ − 1 ρ̂ + 5√
-zCDP.
for some constants ξ,
ρ̂
ρ̂,
4
4
Proof. Let x, x0 ∈ X n be neighbouring. Define f (y) = log(P [M (x) = y] /P [M (x0 ) = y]). Let
Y ∼ M (x) and Z = f (Y ). That is, Z = PrivLoss (M (x)kM (x0 )) is the privacy loss random
variable. Let Y 0 ∼ M (x0 ) and Z 0 = f (Y 0 ). That is, −Z 0 is the privacy loss random variable
if we swap x and x0 .
Let ε, δ > 0 satisfy (11). By postprocessing, for all t ∈ R,
P [Z > t] =P [f (M (x)) > t]
≤eε P [f (M (x0 )) > t] + δ
Z
ε
=e
P [M (x0 ) = y] · I(P [M (x) = y] > et P [M (x0 ) = y])dy + δ
ZY
<eε P [M (x) = y] · e−t · I(P [M (x) = y] > et P [M (x0 ) = y])dy + δ
Y

=eε−t P [Z > t] + δ,
whence P [Z > t] ≤

δ
.
1−eε−t

2
Then we can set ε = ξˆ + λ and δ = e−λ /ρ̂ to obtain

2

e−λ /ρ̂
.
0<λ<t 1 − eλ−t

h
i
ˆ
∀t > 0 P Z > ξ + t ≤ inf
In particular, for all t ≥ 0,
2

h

P Z > ξˆ +

p
4

i
ρ̂ + t ≤

e−t /ρ̂
2 −t2 /ρ̂
√
≤ √
e
.
4
4
−
ρ̂
ρ̂
1−e

44

We use the inequality 1 + xeξ ≤ ex+ξ for all x, ξ ≥ 0. We have
Z ∞


 (α−1)Z 
P e(α−1)Z > t dt
E e
=

Z0 ∞ 
log t
P Z>
=
dt
α−1
0
Z ∞
dt
P [Z > z] dz
=
dz
Z−∞
∞
(α − 1)e(α−1)z · P [Z > z] dz
=
−∞

√
ξ̂+ 4 ρ̂

∞

√
2 −t2 /ρ̂
4
e
dt
(α − 1)e(α−1)(t+ξ̂+ ρ̂) · √
4
ρ̂
−∞
0
Z ∞
√
√
2
(α−1)(ξ̂+ 4 ρ̂)
(α−1)(ξ̂+ 4 ρ̂) 2
√
=e
+ (α − 1)e
e(α−1)t · e−t /ρ̂ dt
4
ρ̂ 0
Z ∞
√
√
(α−1)(ξ̂+ 4 ρ̂) 2
(α−1)(ξ̂+ 4 ρ̂)
−(t− 12 (α−1)ρ̂)2 /ρ̂+ 14 (α−1)2 ρ̂
√
+ (α − 1)e
dt
≤e
e
4
ρ̂ −∞
√
√
2 1 (α−1)2 ρ̂ p
4
4
=e(α−1)(ξ̂+ ρ̂) + (α − 1)e(α−1)(ξ̂+ ρ̂) √
e4
π ρ̂
4
ρ̂

√ 
√ p
1
4
(α−1)2 ρ̂
(α−1)(ξ̂+ 4 ρ̂)
4
1 + (α − 1)2 π ρ̂e
=e

Z

≤

(α − 1)e

√
4

(α−1)z

Z

· 1dz +

√ √
4

1

≤e(α−1)(ξ̂+ ρ̂) e(α−1)2 π ρ̂+ 4 (α−1)
√
√ √
1
4
4
=e(α−1)(ξ̂+ ρ̂+2 π ρ̂+ 4 (α−1)ρ̂)
√

=e(α−1)(ξ̂+(1+2

√
π) 4 ρ̂− ρ̂4 + ρ̂4 α)

2 ρ̂

.



0
Since E e(α−1)Z = e(α−1)Dα (M (x)kM (x )) , this completes the proof.
We make use of the following technical lemma taken from [DSS+ 15].
Lemma B.4. Let X be a random variable. Then
h
i 1   1 

X−E[X]
E e
≤ E e2X + E e−2X .
2
2
Proof. Let X 0 be an independent copy of X and let Y ∈ {0, 1} be uniformly random and
independent from X and X 0 . By Jensen’s inequality,
h
i
h E [X−X 0 ] i
h
i
h 2E[Y X−(1−Y )X 0 ] i
0
X−E[X]
E e
=E eX 0
≤ E 0 eX−X = E 0 e Y
X
X,X
X,X
i 1   1 
h
i
h

 1

1
2Y X−2(1−Y )X 0
2X−0
0−2X 0
= E0 e
+ E0 e
= E e2X + E e−2X .
≤ E0 e
X,X ,Y
2 X,X
2 X,X
2
2

45

n
Lemma B.5
√ (Restating Lemma 4.3). If M : X → Y satisfies (ξ, ρ)-zCDP, then M satisfies
(ξ + ρ, O( ξ + 2ρ))-CDP.

Proof. Let x and x0 be neighbouring databases and Z ∼ PrivLoss (M (x)kM (x0 )) the privacy
loss random variable We have E [Z] = D1 (M (x)kM (x0 )) ∈ [0, ξ + ρ] by non-negativity and
zCDP. By zCDP, for all α ∈ (1, ∞), we have


0
E e(α−1)Z = e(α−1)Dα (M (x)kM (x )) ≤ e(α−1)(ξ+ρα)
and


E e−αZ =

E

Y ∼M (x)

=



P [M (x) = Y ]



P [M (x0 ) = Y ]

"

P [M (x0 ) = Y ]

E

!−α 

!α #

P [M (x) = Y ]

Y ∼M (x)

0

=e(α−1)Dα (M (x )kM (x))
≤e(α−1)(ξ+ρα) .
By Lemma B.4, for λ ≥ 1/2,
h
i 1 
 1 
 1
1
2
λ(Z−E[Z])
E e
≤ E e2λZ + E e−2λZ ≤ e2λ(ξ+ρ(2λ+1)) + e(2λ−1)(ξ+2ρλ) ≤ e4(ξ+2ρ)λ
2
2
2
2
and, for λ ≤ −1/2,
h
i 1 
 1 
 1
1
2
λ(Z−E[Z])
E e
≤ E e2λZ + E e−2λZ ≤ e(−2λ−1)(ξ−2ρλ) + e−2λ(ξ+ρ(1−2λ)) ≤ e4(ξ+2ρ)λ .
2
2
2
2
Now suppose |λ| < 1/2. Then
h
i 1 
 1 

λ(Z−E[Z])
E e
≤ E e2λZ + E e−2λZ
2
2
∞
X
(2λ)2k  2k 
=1 +
E Z
(2k)!
k=1
2

≤1 + (2λ)

∞
X



1
E Z 2k
(2k)!

 k=1

1  Z  1  −Z 
2
=1 + 4λ
E e + E e
−1
2
2

≤1 + 4λ2 eξ+2ρ − 1
≤eλ

2 O(ξ+2ρ)

.

46

B.1

Proof of Lemma 2.2

Proof of Non-Negativity. Let h(t) = tα . Then h00 (t) = α(α − 1)tα−2 > 0 for all t > 0
and α > 1. Thus h is strictly convex. Hence e(α−1)Dα (P kQ)) = E [h(P (x)/Q(x))] ≥
x∼Q

h( E [P (x)/Q(x)]) = h(1) = 1, as required.
x∼Q

Proof of Composition.
(α−1)Dα (P kQ)

e

Z

P (x, y)α Q(x, y)1−α d(x, y)
ZΩ×Θ
Z
0
α 0
1−α
= P (x) Q (x)
Px0 (y)α Q0x (y)1−α dydx
Θ
ZΩ
0
0
= P 0 (x)α Q0 (x)1−α e(α−1)Dα (Px kQx ) dx
ZΩ
0
0
≤ P 0 (x)α Q0 (x)1−α dx · max e(α−1)Dα (Px kQx )
=

Ω
(α−1)Dα (P 0 kQ0 )

=e

x

(α−1) maxx Dα (Px0 kQ0x )

·e

.

The other side of the inequality is symmetric.
Proof of Quasi-Convexity. Unfortunately Rényi divergence is not convex for α > 1. (Although KL-divergence is.) However, the following property implies that Rényi divergence is
quasi-convex.
Lemma B.6. Let P0 , P1 , Q0 , Q1 be distributions on Ω. For t ∈ [0, 1], define Pt = tP1 + (1 −
t)P0 and Qt = tQ1 + (1 − t)Q0 to be the convex combinations specified by t. Then
e(α−1)Dα (Pt kQt ) ≤ te(α−1)Dα (P1 kQ1 ) + (1 − t)e(α−1)Dα (P0 kQ0 ) .
Moreover, the limit as α → 1+ gives
D1 (Pt kQt ) ≤ tD1 (P1 kQ1 ) + (1 − t)D1 (P0 kQ0 ) .
Proof of Lemma B.6. Let f (t) = e(α−1)Dα (Pt kQt ) . Since the equality is clearly true for t = 0

47

and t = 1, it suffices to show that f 00 (t) ≥ 0 for all t ∈ [0, 1]. We have
Z
f (t) = Pt (x)α Qt (x)1−α dx,
ZΩ
d
f 0 (t) =
Pt (x)α Qt (x)1−α dx
dt




ZΩ
d
d
α−1
1−α
α
−α
= αPt (x)
Pt (x) Qt (x)
+ (1 − α)Pt (x) Qt (x)
Qt (x) dx
dt
dt
Ω
Z
= αPt (x)α−1 (P1 (x) − P0 (x)) Qt (x)1−α + (1 − α)Pt (x)α Qt (x)−α (Q1 (x) − Q0 (x)) dx,
ZΩ
f 00 (t) = α(α − 1)Pt (x)α−2 (P1 (x) − P0 (x))2 Qt (x)1−α
Ω

+ α(1 − α)Pt (x)α−1 (P1 (x) − P0 (x)) Qt (x)−α (Q1 (x) − Q0 (x))
+ (1 − α)αPt (x)α−1 (P1 (x) − P0 (x)) Qt (x)−α (Q1 (x) − Q0 (x))
+ (1 − α)(−α)Pt (x)α Qt (x)−α−1 (Q1 (x) − Q0 (x))2 dx
Z p
2
p
α−2
1−α
α
−α−1
=α(α − 1)
Pt (x) Qt (x)
(P1 (x) − P0 (x)) − Pt (x) Qt (x)
(Q1 (x) − Q0 (x)) dx
Ω

≥0.

Proof of Postprocessing. Let h(x) = xα . Note that h is convex. Let f −1 (y) = {x ∈ Ω :
f (x) = y}. Let Qy be the conditional distribution on x ∼ Q conditioned on f (x) = y. By
Jensen’s inequality,
α 

P (x)
(α−1)Dα (P kQ)
e
= E
x∼Q
Q(x)


 
P (x)
= E
E h
y∼f (Q) x∼Qy
Q(x)
 


P (x)
≥ E
h
E
x∼Qy Q(x)
y∼f (Q)
 Z

Q(x) P (x)
= E
h
dx
−1 (y)) Q(x)
y∼f (Q)
f −1 (y) Q(f
 

P (f −1 (y))
= E
h
y∼f (Q)
Q(f −1 (y))
=e(α−1)Dα (f (P )kf (Q)) .

48

α0 −1

Proof of Monotonicity. Let 1 < α ≤ α0 < ∞. Let h(x) = x α−1 . Then

 0
α −1
α0 − 1 α0 − 1
00
h (x) =
− 1 x α−1 −2 ≥ 0,
α−1 α−1
so h is convex on (0, ∞). Thus
(α0 −1)Dα (P kQ)

e

=h e


(α−1)Dα (P kQ)

"
=h

E

x∼P

P (x)
Q(x)

"

α−1 #!
≤ E

x∼P


h

P (x)
Q(x)

α−1 !#

which gives the result.

C

Privacy versus Sampling

In this appendix we prove the technical Lemma 7.5. Essentially we show that if a private
mechanism can accurately answer a set of queries with a given sample complexity, then those
queries can be approximated on an unknown distribution with the same sample complexity.
This is related to lower bounds on private sample complexity using Vapnik-Chervonenkis
dimension e.g. [DR14, Theorem 4.8] and [BNSV15, Theorem 5.5].
First we state Pinsker’s inequality [vEH14, Theorem 31].
Lemma C.1 (Pinsker’s Inequality). Let X and Y be random variables on [−1, 1]. Then
p
E [X] − E [Y ] ≤ 2D1 (XkY )
We can also generalise Pinsker’s inequality using Rényi divergence:
Lemma C.2. Let P and Q be distributions on Ω and f : Ω → R. Then
E [f (x)] − E [f (x)] ≤

x∼P

x∼Q

q

E [f (x)2 ] ·

x∼Q

p
eD2 (P kQ) − 1.

In particular, if M : X n → Y satisfies (ξ, ρ)-zCDP. Then, for any f : Y → R and all
neighbouring x, x0 ∈ X n ,
p
q
E [f (M (x0 ))] − E [f (M (x))] ≤ E [f (M (x))2 ] · eξ+2ρ − 1.
Proof. By Cauchy-Schwartz,





P (x)
E [f (x)] − E [f (x)] = E f (x)
−1
x∼P
x∼Q
x∼Q
Q(x)
v
"
u
2 #
u
q
P
(x)
≤ E [f (x)2 ] · t E
−1
.
x∼Q
x∼Q
Q(x)
49

0

= e(α −1)Dα0 (P kQ) ,

Now
"
E

x∼Q

"
#
2 #
2
P (x)
P (x)
P (x)
−1
= E
−2
+1
x∼Q
Q(x)
Q(x)
Q(x)
"
2 #
P (x)
= E
−2+1
x∼Q
Q(x)
=eD2 (P kQ) − 1.

Proposition C.3. Let q : X → Rk satisfy maxx∈X kq(x)k ≤ 1, where k · k is some norm.
Let M : X n → Rk satisfy (ξ, ρ)-zCDP and
E [kM (x) − q(x)k] ≤ α

M

for all x ∈ X n . Then, for any distribution D on X ,
En

x∼D ,M

[kM (x) − q(D)k] ≤ α +

p
2(ξ + ρ)

and
E n [kq(x) − q(D)k] ≤ 2α +

x∼D

p
2(ξ + ρ),

where q(D) = E [q(z)].
z∼D

Proof. First define the dual norm: For x ∈ Rk ,
kxk∗ :=

max

y∈Rk :kyk=1

hx, yi.

By definition, hx, yi = hy, xi ≤ kxk∗ ·kyk for all x, y ∈ Rk . Moreover, kzk = maxy∈Rk :kyk∗ =1 hz, yi
for all z ∈ Rk .
Fix a distribution D. Define W : X n → Rk × Rk as follows. On input x ∈ X n , compute
a = M (x) and
s = argmax ha − q(D), vi,
v∈Rk :kvk∗ =1

and output (a, s).
By postprocessing, W satisfies (ξ, ρ)-zCDP and
E [ha − q(x), si | (a, s) = W (x)] ≤ E [ka − q(x)k · ksk∗ | (a, s) = W (x)] = E [kM (x) − q(x)k] ≤ α

W

W

M

(12)
for all x ∈ X n .

50

The following is similar to [BNS+ 16a, Lemma 3.1]. Let x ∼ Dn and y ∼ D. Now
1X
E [hq(x), si | (a, s) = W (x)] =
E [hq(xi ), si | (a, s) = W (x)]
x,W
x,W
n

(13)

i∈[n]

=

1X
E [f (xi , W (x))]
x,W
n
i∈[n]

(letting f : X × Rk × Rk → [−1, 1] be f (z, a, s) = hq(z), si/ksk∗ )
≤

1X
E [f (xi , W (x1 , · · · , xi−1 , y, xi+1 , · · · , xn ))]
x,y,W
n
i∈[n]
p
+ 2D1 (f (xi , W (x))kf (xi , W (x1 , · · · , xi−1 , y, xi+1 , · · · , xn )))

(by Pinsker’s inequality)
≤

1X
E [f (y, W (x1 , · · · , xi−1 , xi , xi+1 , · · · , xn ))]
x,y,W
n
i∈[n]
p
+ 2D1 (W (x)kW (x1 , · · · , xi−1 , y, xi+1 , · · · , xn ))

(by postprocessing and convexity and the fact that xi and y are interchangable)
≤

1X
E [hq(y), si | (j, s, a) = W (x)]
x,y,W
n
i∈[n]
p
+ 2(ξ + ρ)

(by zCDP)
= E [hq(D), si | (a, s) = W (x)] +
x,W

p
2(ξ + ρ).

Combining (12) and (13) gives
E [kM (x) − q(D)k] = E [ha − q(D), si | (a, s) = W (x)] ≤ α +

x,M

x,W

p
2(ξ + ρ).

Finally, combining (14) and (12) gives
E [kq(x) − q(D)k] ≤ E [kM (x) − q(x)k] + E [kM (x) − q(D)k] ≤ 2α +
x

x,M

x,M

51

p
2(ξ + ρ).

(14)

0

Proof of Lemma 7.5. Fix x ∈ X n . Let D be the uniform distribution on elements of x so
that q(D) = q(x). By Proposition C.3,
p
E n [kq(x̂) − q(D)k] ≤ 2α + 2(ξ + ρ).
x̂∼D

In particular, there must exist x̂ ∼ Dn such that kq(x̂) − q(D)k ≤ 2α +
required.

52

p
2(ξ + ρ), as

