Local Distribution Obfuscation via Probability Coupling*
Yusuke Kawamoto1

Abstract— We introduce a general model for the local obfuscation of probability distributions by probabilistic perturbation,e.g., by adding differentially private noise, and investigate its
theoretical properties. Specifically, we relax a notion of distribution privacy (DistP) by generalizing it to divergence, andpropose local obfuscation mechanisms that provide divergence
distribution privacy. To provide f -divergence distribution privacy, we prove that probabilistic perturbation noise should be
added proportionally to the Earth mover’s distance between theprobability distributions that we want to make indistinguishable. Furthermore, we introduce a local obfuscation mechanism,
which we call a coupling mechanism, that provides divergence
distribution privacy while optimizing the utility of obfuscateddata by using exact/approximate auxiliary information on the
input distributions we want to protect.

I. I NTRODUCTION
Differential privacy (DP) [1] is one of the most popularprivacy notions that have been studied in various areas,
including databases, machine learning, geo-locations, andsocial networks. The protection of DP can be achieved byadding probabilistic noise to the data we want to obfuscate.
In particular, many studies have proposed local obfuscation
mechanisms [2], [3], [4] that perturb each single “point”
datum (e.g., a geo-location point) by adding controlled
probabilistic noise before sending it out to a data collector.
Recent researches [5], [6], [7] show that local obfuscation
mechanisms can be used to hide the probability distributions
that lie behind such point data and implicitly represent sensitive attributes (e.g., age, gender, social status). In particular,[6] proposes the notion of distribution privacy (DistP) as
the local DP of probability distributions. Roughly, DistP of a
local obfuscation mechanism A represents that the adversary
cannot significantly gain information on the distribution of
A’s input by observing A’s output. However, since DistP
assumes the worst case risk in the sense of DP, it imposes
strong requirement and might unnecessarily lose the utilityof obfuscated data.
In this paper, we relax the notion of DistP by generalizing it to an arbitrary divergence. The basic idea issimilar to point privacy notions that relax DP and improveutility by relying on some divergence (e.g., total variation
privacy [8], Kullback-Leibler divergence privacy [8], [9],and Rényi differential privacy [10]). We define the notionof divergence distribution privacy by replacing the DP-stylewith an arbitrary divergence D. This relaxation allows us toformalize “on-average” DistP, and to explore privacy notions*This work was partially supported by JSPS KAKENHI Grant
JP17K12667, JP19H04113, and Inria LOGIS project.
1 Yusuke Kawamoto is with AIST, Tsukuba, Japan.
2 Takao Murakami is with AIST, Tokyo, Japan.

Takao Murakami2

against an adversary performing the statistical hypothesis test
corresponding to the divergence [8].
Furthermore, we propose and investigate local obfuscation
mechanisms that provide divergence DistP. Specifically, we
consider the following two scenarios:(i) when we have no idea on the input distributions;(ii) when we know exact or approximate information on
the input distributions (e.g., when we can use public
datasets [11], [12] to learn approximate distributions oflocations of male/female users if we want to obfuscate
the attribute male/female).
For the scenario (i), we clarify how much perturbationnoise should be added to provide f -divergence DistP when
we use an existing mechanism for obfuscating point data. For
the scenario (ii), we introduce a local obfuscation mechanismthat provides divergence DistP while optimizing the utilityof obfuscated data by using the auxiliary information. Hereit should be noted that probability coupling techniques are
crucial in constructing divergence DistP mechanisms in boththe scenarios.
Our contributions. The main contributions are as follows:• We introduce notions of divergence DistP and investigate theoretical properties of distribution obfuscation,
especially the relationships between local distribution
obfuscation and probability coupling.
• We investigate the relationships among various notionsof DistP based on f -divergences, such as KullbackLeibler divergence, which models “on-average” risk.
• In the scenario (i), we present how much divergence
DistP can be achieved by local obfuscation. In particular, by using probability coupling techniques, we provethat perturbation noise should be added proportionallyto the Earth mover’s distance between the input distributions that we want to make indistinguishable.
• In the scenario (ii), we propose a local obfuscation
mechanism, called a (utility-optimal) coupling mechanism, that provides divergence DistP while minimizing
utility loss. The construction of the mechanism relies
on solving an optimal transportation problem using
probability coupling.
• We theoretically evaluate the divergence DistP andutility loss of coupling mechanisms that can use exact/approximate knowledge on the input distributions.
Paper organization. The rest of this paper is organized
as follows. Section II presents background knowledge. Section III introduces notions of divergence DistP. Section IV
investigates important properties of divergence DistP, andrelationships among privacy notions. Section V shows that

in the scenario (i), an f -privacy mechanism can provide f divergence DistP. Section VI generalizes DistP to use exact/approximate information on the input distribution in the
scenario (ii), and proposes a local mechanism for providing
DistP while optimizing utility. Section VII discusses related
work and Section VIII concludes.

Input data

Perturbed output datax (∼ λ)-y (∼ A#(λ))
Obfuscater A-

Fig. 1: A local obfuscation mechanism A perturbs input data
x and returns output data y. Then the underlying probability
distribution λ can also be seen to be obfuscated.

II. P RELIMINARIESIn this section we recall some notions of privacy, divergence, and metrics used in this paper.
A. Notations
Let R≥0 be the set of non-negative real numbers, anddef[0, 1] = {r ∈ R≥0 | r ≤ 1}. Let ε, ε0 , ε1 ∈ R≥0 ,δ, δ0 , δ1 ∈ [0, 1], and e be the base of natural logarithm.
We denote by |X | the number of elements in a finite set X ,and by DX the set of all probability distributions over aset X . Given a probability distribution λ over a finite set
X , the probability of drawing a value x from λ is denotedby λ[x]. P
For a finite subset X 0 ⊆ X , we define λ[X 0 ] by0
λ[X ] = x0 ∈X 0 λ[x0 ]. For a distribution λ over a finite set
X , its support is supp(λ) = {x ∈ X : λ[x] > 0}.
For a randomized algorithm A : X → DY and a set R ⊆Y, we denote by A(x)[R] the probability that given an input
x, A outputs one of the elements of R. For a randomized
algorithm A : X → DY and a distribution λ over X , wedefine A# (λ) as the probability distribution of the output
of A. Formally, the lifting of A : X → DY is the function
def
#
#
A
P : DX → DY such that for any R ⊆ Y, A (λ)[R] =x∈X λ[x]A(x)[R].
B. Differential Privacy
Differential privacy [1] is a notion of privacy guaranteeingthat we cannot learn which of two “adjacent” inputs x and x0
is used to generate an output of a randomized algorithm. This
notion is parameterized by a degree ε of indistinguishability,
a ratio δ of exception, and some adjacency relation Φ overa set X of data. The formal definition is given as follows.
Definition 1 (Differential privacy): A randomized algorithm A : X → DY provides (ε, δ)-differential privacy (DP)w.r.t. an adjacency relation Φ ⊆ X ×X if for any (x, x0 ) ∈ Φ
and any R ⊆ Y,
Pr[A(x) ∈ R] ≤ eε Pr[A(x0 ) ∈ R] + δ
where the probability is taken over the random choices in A.
Then the protection of DP is stronger for smaller ε and δ.
DP can be achieved by a local obfuscation mechanism or
privacy mechanism (illustrated in Fig. 1), namely a randomized algorithm that adds controlled noise probabilistically togiven inputs that we want to protect.
C. Extended Differential Privacy (XDP)
The notion of DP can be relaxed by incorporating a metricd over the set X of input data. In [13] Chatzikokolakis et al.
propose the notion of “d-privacy”, an extension of (ε, 0)-DP
to a metric d on input data. Intuitively, this notion guarantees
that when two inputs x and x0 are closer in terms of d, theoutput distributions are less distinguishable1 . Here we show
the definition of this extended DP equipped with δ.
Definition 2 (Extended differential privacy): Let d : X ×
X → R be a metric. We say that a randomized algorithm
A : X → DY provides (ε, δ, d)-extended differential privacy(XDP) if for all x, x0 ∈ X and R ⊆ Y,
0

Pr[A(x) ∈ R] ≤ eεd(x,x ) Pr[A(x0 ) ∈ R] + δ
where the probability is taken over the random choices in A.
To achieve XDP, obfuscation mechanisms should add
noise proportionally to the distance d(x, x0 ) between the two
inputs x and x0 that we want to make indistinguishable, hence
more noise is require for a larger d(x, x0 ).
D. Distribution Privacy and Extended Distribution Privacy
Distribution privacy (DistP) [6] is a privacy notion thatmeasures how much information on the input distribution isleaked by an output of a randomized algorithm. For example,
let λmale (resp. λfemale ) be a (prior) probability distributionof the locations of the male (resp. female) users. When
we observe an output of an obfuscation mechanism A andcannot learn whether the input to A is drawn from λmaleor λfemale , then we say that A provides (ε, δ)-DistP w.r.t.
(λmale , λfemale ). Formally, DistP is defined as follows.
Definition 3 (Distribution privacy): Let ε ∈ R≥0 and δ ∈[0, 1]. We say that a randomized algorithm A : X → DY provides (ε, δ)-distribution privacy (DistP) w.r.t. an adjacency
relation Ψ ⊆ DX × DX if its lifting A# : DX → DY
provides (ε, δ)-DP w.r.t. Ψ , i.e., for all pairs (λ, λ0 ) ∈ Ψ andR ⊆ Y, we have A# (λ)[R] ≤ eε · A# (λ0 )[R] + δ.
Next we recall an extension [6] of DistP with a metricd as follows. Intuitively, this extended notion guarantees
that when two input distributions are closer, then the output
distributions must be less distinguishable.
Definition 4 (Extended distribution privacy): Let d : (DX× DX ) → R be a metric, and Ψ ⊆ DX × DX . We
say that a mechanism A : X → DY provides (ε, d, δ)extended distribution privacy (XDistP) w.r.t. Ψ if the liftingA# provides (ε, d, δ)-XDP w.r.t. Ψ , i.e., for all (λ, λ0 ) ∈ Ψ
0
and R ⊆ Y, we have A# (λ)[R] ≤ eεd(λ,λ ) · A# (λ0 )[R] + δ.
Analogously to XDP, noise should be added proportionally to the distance d(λ, λ0 ).
1 Compared to DP, XDP provides weaker privacy and higher utility, as it
obfuscates closer points. E.g., [14] shows the planar Laplace mechanism [3](with XDP) adds less noise than the randomized response (with DP).

Definition 7 (Coupling): Given λ ∈ DX0 and µ ∈ DX1 , a
coupling of λ and µ is a joint distribution γ ∈ D(X0 × X1 )such that λ and µ are
P γ’s marginal distributions, i.e., for eachx0 ∈ X0 , λ[x0 ] = x0 ∈X1 γ[x0 , x01 ] and for each x1 ∈ X1 ,1Pµ[x1 ] = x0 ∈X0 γ[x00 , x1 ]. We denote by cp(λ, µ) the set of0
all couplings of λ and µ.

TABLE I: Instances of f -divergence
Divergence
KL-divergence
Reverse KL-divergence
Total variation
χ2 -divergence
Hellinger distance

λ

γ
0.5
0.2
1

γ

f (t)
t log t−t log t
1
2 |t − 1|2(t −√ 1) 21
2 ( t − 1)

2

6
0.1

0.3
3

λ

6
0.2

µ
0.5

0.3

0.2

1

2
location

3(a) An original distribution λ anda target distribution µ.

1
2
3

1
0.2
0.1

G. p-Wasserstein Metric

µ
2
0.2

3
0.2
0.3

(b) A coupling γ of its two
marginals λ and µ can be interpreted as a transportation thattransforms λ to µ. E.g., to construct µ from λ, 0.1 moves
from 2 to 1, and 0.2 moves from
2 to 3.

Fig. 2: A coupling γ that transforms λ to µ.

E. Divergence
A divergence over a non-empty set Y is a function D(· k ·) :DY × DY → R≥0 such that for all µ, µ0 ∈ DY, (i) D(µ kµ0 ) ≥ 0 and (ii) D(µ k µ0 ) = 0 iff µ = µ0 . Note that adivergence may not be symmetric or subadditive. We denote
by Div(Y) the set of all divergences over Y.
Next we recall the notion of (approximate) max divergence, which can be used to define DP.
Definition 5 (Max divergence): Let δ ∈ [0, 1] and µ, µ0 ∈DY. Then δ-approximate max divergence between µ, µ0 is:δD∞(µ k µ0 ) =maxR⊆supp(µ),µ[R]≥δγ∈cp(λ,µ)+F = {f : R → R | f is convex and f (1) = 0}.
Let Y be a finite set, and µ, µ0 ∈ DY such that for everyy ∈ Y, µ0 [y] = 0 implies µ[y] = 0. Then for an f ∈ F, thef -divergence of µ from µ0 is defined as:X
Df (µ k µ0 ) =µ0 [y] f µµ[y]0 [y] .
y∈supp(µ0 )F. Probability Coupling
We recall the notion of probability coupling as follows.
Example 1 (Coupling as transformation of distributions):
Let us consider two distributions λ and µ shown in Fig. 2.
A coupling γ of λ and µ shows a way of transforming λ toµ. For example, γ[2, 1] = 0.1 moves from λ[2] to µ[1].
Formally, a coupling is defined as follows.

(x0 ,x1 )∈supp(γ)

W1,d is also called the Earth mover’s distance.
The intuitive meaning of W1,d (λ, µ) is the minimum costof transportation from λ to µ in transportation theory. As
illustrated in Fig. 2, we regard the distribution λ (resp. µ)
as the set of points where each point x has weight λ[x](resp. µ[x]), and we move some weight in λ from a point
x0 to another x1 to construct µ. We represent by γ[x0 , x1 ]the amount of weight moved from x0 to x1 .2 We denote byd (x0 , x1 ) the cost (i.e., distance) of move from x0 to x1 .
Then the minimum cost of the whole transportation is:X
W1,d (λ, µ) = mind (x0 , x1 ) γ[x0 , x1 ].
γ∈cp(λ,µ)(x0 ,x1 )∈supp(γ)

E.g., in Fig. 2, when the cost function d is the Euclid distanceover X (e.g., d(2, 1) = |2 − 1| = 1), the transportation γ
achieves the minimum cost 0.1 · 1 + 0.2 · 1 = 0.3.
Let Γp,d the set of all couplings achieving Wp,d ; i.e.,X1Γp,d (λ, µ) = argmin
d (x0 , x1 )p γ[x0 , x1 ] p .

ln µ[R]−δµ0 [R] .

We recall the notion of the f -divergences [15]. As shownin Table I, many divergence notions (e.g. Kullback-Leiblerdivergence [16]) are instances of f -divergence.
Definition 6 (f -divergence): Let F be the collection offunctions defined by:+

Then we recall the p-Wasserstein metric [17] between two
distributions, which is defined using a coupling as follows.
Definition 8 (p-Wasserstein metric): Let d be a metricover X , and p ∈ R≥1 ∪{∞}. The p-Wasserstein metric Wp,dw.r.t. d is defined by: for any two distributions λ, µ ∈ DX ,X
1
Wp,d (λ, µ) = mind (x0 , x1 )p γ[x0 , x1 ] p .

γ∈cp(λ,µ)(x0 ,x1 )∈supp(γ)

Then γ ∈ Γ1,d (λ, µ) can be efficiently computed by theNorth-West corner rule [18] when d is submodular 3 .
III. D IVERGENCE D ISTRIBUTION P RIVACY
In this section we introduce new definitions of distribution
privacy generalized to an arbitrary divergence D. The main
motivation is to discuss distribution privacy based on f divergences, especially Kullback-Leibler divergence, whichmodels “on-average” risk.
A. Divergence DP and Divergence XDP
To generalize distribution privacy notions, we first present
a generalized formulation of point privacy parameterizedwith a divergence D. Intuitively, we say that a randomized
algorithm A provides (ε, D)-DP if a divergence D cannot
distinguish the input to A by observing an output of A.
2 The amount of weight moved from a point x in λ is given by0P
λ[x0 ] = x0 ∈X γ[x0 , x01 ], while the amount moved into x1 in µ is given
1Pby µ[x1 ] = x0 ∈X γ[x00 , x1 ]. Hence γ is a coupling of λ and µ.
0

3 d is submodular if d(x , x ) + d(x0 , x0 ) ≤ d(x0 , x ) + d(x , x0 ).
0
1
1
0
0
1
0
1

Definition 9 (Divergence DP w.r.t. adjacency relation):
For an adjacency relation Φ ⊆ X × X and a divergence
D ∈ Div(Y), we say that a randomized algorithm A : X →DY provides (ε, D)-DP w.r.t. Φ if for all (x, x0 ) ∈ Φ, wehave D(A(x) k A(x0 )) ≤ ε and D(A(x0 ) k A(x)) ≤ ε .
Note that some instances of divergence DP are known in
the literature. In [8], (ε, Df )-DP is called ε-f -divergence
privacy, (ε, DKL )-DP (KLP) is called ε-KL-privacy, and(ε, DTV )-DP is called ε-total variation privacy. Furtherδ
more, (ε, D∞)-DP is equivalent to (ε, δ)-DP, since it is
known that (ε, δ)-DP can be defined using the approximateδmax divergence D∞
as follows:
Proposition 1: A randomized algorithm A : X → DY
provides (ε, δ)-DP w.r.t. Φ ⊆ X × X iff for any (x, x0 ) ∈ Φ,δδD∞(A(x) k A(x0 )) ≤ ε and D∞(A(x0 ) k A(x)) ≤ ε.
Next we generalize the notion of extended differential
privacy (XDP) to an arbitrary divergence D as follows.
Definition 10 (Divergence XDP): Let d : X × X → R
be a metric, Φ ⊆ X × X , and D ∈ Div(Y). We say that arandomized algorithm A : X → DY provides (ε, d, D)-XDP
w.r.t. Φ if for all (x, x0 ) ∈ Φ, D(A(x) k A(x0 )) ≤ εd(x, x0 ).
These notions will be used to define (extended) divergence
distribution privacy in the next section.
B. Divergence DistP and Divergence XDistPIn this section we generalize the notion of (extended)
distribution privacy to an arbitrary divergence D. The main
aim of generalization is to present theoretical properties of
distribution privacy in a more general form, and also to
discuss distribution privacy based on the f -divergences.
Intuitively, we say that a randomized algorithm A provides (ε, D)-distribution privacy w.r.t. a set Ψ of pairs of
distributions if for each pair (λ0 , λ1 ) ∈ Ψ , a divergence D
cannot distinguish which distribution (of λ0 and λ1 ) is used
to generate A’s input value.
Definition 11 (Divergence DistP): Let D ∈ Div(Y), andΨ ⊆ DX × DX . We say that a randomized algorithm
A : X → DY provides (ε, D)-distribution privacy (DistP)
w.r.t. Ψ if the lifting A# provides (ε, D)-DP w.r.t. Ψ , i.e., forall (λ, λ0 ) ∈ Ψ ,D(A# (λ) k A# (λ0 )) ≤ ε.
As with the generalization of DP to f -divergence [8], DDistP expresses privacy against an adversary performing the
hypothesis test corresponding to the divergence D. When D
involves averaging (e.g., D = DKL ), D-DistP formalizes“on-average” privacy, which relaxes the original DistP.
Next we introduce XDistP parameterized with a divergence D. Intuitively, XDistP with a divergence D guarantees
that when two input distributions λ and λ0 are closer (interms of a metric d), then the output distributions A# (λ)
and A# (λ0 ) must be less distinguishable (in terms of D).
Definition 12 (Divergence XDistP): Let d be a metricover DX , D ∈ Div(Y), and Ψ ⊆ DX × DX . We say thata randomized algorithm A : X → DY provides (ε, d, D)extended distribution privacy (XDistP) w.r.t. Ψ if the liftingA# provides (ε, d, D)-XDP w.r.t. Ψ , i.e., for all (λ, λ0 ) ∈ Ψ ,
#

#

0

0

D(A (λ) k A (λ )) ≤ εd(λ, λ ).

A1

λ

-

A0

-

y0
?
A1

x
-

(a)

A1 • A0

A0

with shared input.

λ
y1
-

λ

x0
-

A0

-

y0
?
A1

x1

y1
-

(b) • with independent inputs.

Fig. 3: Two kinds of sequential compositionsand •.

IV. P ROPERTIES OF D IVERGENCE D ISTRIBUTIONP RIVACY
In this section we show useful properties of divergence
distribution privacy, such as compositionality and relationships among distribution privacy notions.
A. Basic Properties of Divergence Distribution Privacy
In Tables II and III we summarize the results on two kindsof sequential compositions (Fig. 3a) and • (Fig. 3b), postprocessing, and pre-processing for divergence DistP and fordivergence XDistP, respectively. We present the details andproofs for these results in Appendices D, E, and F.
The two kinds of composition have been studies inprevious work (e.g., [19], [6]). For two mechanisms A0
and A1 , the composition A1 A0 means that an identical
input value x is given to two DistP mechanisms A0 and
A1 , whereasA1 • A0 means that independent inputs xb
are provided to mechanisms Ab . Note that this kind ofcomposition is adaptive in the sense that the output of A1 canbe dependent on that of A0 . Hence the compositonality does
not hold in general for f -divergence, whereas we show thecompositionality for KL-divergence in Tables II and III. For
non-adaptive sequential composition, the compositionalityof divergence DistP/XDistP is straightforward from [20],which show the compositionality of popular f -divergences,including total variation and Hellinger distance.
As for pre-processing, we use the following definition ofstability [6], which is analogous to the stability for DP.
Definition 13 (Stability): Let c ∈ N, Ψ ⊆ DX × DX , andW be a metric over DX . A transformation T : DX → DX
is (c, Ψ )-stable if for any (λ0 , λ1 ) ∈ Ψ , T (λ0 ) can bereached from T (λ1 ) at most c-steps over Ψ . Analogously,
T : DX → DX is (c, W )-stable if for any λ0 , λ1 ∈ DX ,W (T (λ0 ), T (λ1 )) ≤ cW (λ0 , λ1 ).
B. Relationships among Distribution Privacy Notions
In Fig. 4 we show the summary of the relationships amongnotions of divergence XDP and divergence XDistP. See
Appendices B and G for details and proofs.
V. L OCAL M ECHANISMS FOR D IVERGENCED ISTRIBUTION P RIVACY
In this section we present how much degree of divergence DistP/XDistP can be achieved by local obfuscation.
Specifically, we show how f -divergence privacy contribute

TABLE II: Summary of basic properties of divergence DistP.
Sequential composition(DKL )

Sequential composition • (DKL )Post-processing
Pre-processing (by c-stable T )Ab is (εb , DKL )-DistP⇒ A1 A0 is (ε0 + ε1 , DKL )-DistP
Ab is (εb , DKL )-DistP⇒ A1 • A0 is (ε0 + ε1 , DKL )-DistP
A0 is (ε, Df )-DistP ⇒ A1 ◦ A0 is (ε, Df )-DistP
A is (ε, D)-DistP ⇒ A ◦ T is (c ε, D)-DistPTABLE III: Summary of basic properties of divergence XDistP.
Sequential composition(DKL )

Sequential composition • (DKL )Post-processing
Pre-processing (by c-stable T )Ab is (εb , W1,d , DKL )-XDistP⇒ A1 A0 is (ε0 + ε1 , W1,d , DKL )-XDistP
Ab is (εb , W1,d , DKL )-XDistP⇒ A1 • A0 is (ε0 + ε1 , W1,d , DKL )-XDistP
A0 is (ε, W , Df )-XDistP ⇒ A1 ◦A0 is (ε, W , Df )-XDistP
A is (ε, W , D)-XDistP ⇒ A ◦ T is (c ε, W , D)-XDistP

Theorem 2 of [6]δ(ε, d, D∞)-XDP

Proposition 10

δ·|Φ|(ε, W∞,d , D∞)-XDistP

if δ = 0-

Theorem 2(ε, W∞,d , DKL )-XDistP

if δ = 0- (ε, d, DKL )-XDP

if δ = 0

Theorem 4

6

Proposition 9
δ·|Φ|(ε, W1,d , D∞)-XDistP

Theorem 4

6
Proposition 10
if δ = 0-

Proposition 9(ε, W1,d , DKL )-XDistP

Fig. 4: Relationships among divergence XDistP notions.

to the obfuscation of probability distributions. To prove thoseresults, we use the notion of probability coupling.

A. Divergence DistP by Local Obfuscation
We first show that f -divergence privacy mechanisms provide Df -DistP. To present this formally, we recall the notionof the lifting of relations as follows.
Definition 14 (Lifting of relations): Given a relation Φ ⊆X × X , the lifting of Φ is the maximum relation Φ# ⊆DX × DX such that for any (λ0 , λ1 ) ∈ Φ# , there exists a
coupling γ ∈ cp(λ0 , λ1 ) satisfying supp(γ) ⊆ Φ.
Intuitively, when λ0 and λ1 are adjacent w.r.t. the lifted
relation Φ# , then we can construct λ1 from λ0 according to
the coupling γ, that is, only by moving mass from λ0 [x0 ]to λ1 [x1 ] where (x0 , x1 ) ∈ Φ (i.e., x0 is adjacent to x1 ).
Note that by Definition 7, the coupling γ is a probability
distribution over Φ whose marginal distributions are λ0
and λ1 . If Φ = X × X , then Φ# = DX × DX .
Now we show that every f -divergence privacy mechanism
provides Df -DistP as follows. (See Appendix A for the
proof.)
Theorem 1 ((ε, Df )-DP ⇒ (ε, Df )-DistP): Let Φ ⊆ X ×
X . If a randomized algorithm A : X → DY provides(ε, Df )-DP w.r.t. Φ, then it provides (ε, Df )-DistP w.r.t. Φ# .
Intuitively, the f -divergence privacy mechanism A makes
any pair (λ0 , λ1 ) of input distributions in Φ# indistinguishable in terms of Df up to the threshold ε.

B. Divergence XDistP by Local Obfuscation
Next we investigate how much noise should be added for
local obfuscation mechanisms to provide divergence XDistP.
We first consider two point distributions λ0 at x0 and λ1
at x1 , i.e., λ0 [x0 ] = λ1 [x1 ] = 1. Then an (ε, d , Df )-XDP
mechanism A satisfies:
Df (A#(λ0 ) k A#(λ1 )) = Df (A(x0 ) k A(x1 )) ≤ εd (x0 , x1 ).
Hence the noise added by A should be proportional to the
distance d (x0 , x1 ) between x0 and x1 .
To generalize this observation on point distributions to arbitrary distributions, we need to employ some metric between
distributions. As the metric, we could use the diameter overthe supports, which is defined by:diam(λ0 , λ1 ) =max

x0 ∈supp(λ0 ),x1 ∈supp(λ1 )d (x0 , x1 ),or the ∞-Wasserstein metric W∞,d , which is used for
XDistP [6]. However, when there is an outlier in λ0 or
λ1 , then diam(λ0 , λ1 ) and W∞,d (λ0 , λ1 ) tend to be large.
Since the mechanism needs to add noise proportionally to the
distance diam(λ0 , λ1 ) or W∞,d (λ0 , λ1 ) to achieve XDistP,
it needs to add large amount of noise and thus loses utility
significantly.
To have better utility, we employ the Earth mover’s
distance (1-Wasserstein metric) W1,d as a metric for Df XDistP mechanisms. Given two distributions λ0 and λ1
over X , we consider a transportation γ from λ0 to λ1 thatminimizes the expected cost of the transportation. Then theminimum of the expected cost is given by the Earth mover’s
distance W1,d (λ0 , λ1 ).
Now we show that, to achieve Df -XDistP, we only have to
add noise proportionally to the Earth mover’s distance W1,dbetween the input distributions. To formalize this, we define
a lifted relation Φ#
Wp as the maximum relation over DX s.t.
for any (λ0 , λ1 ) ∈ Φ#
Wp , there is a coupling γ ∈ cp(λ0 , λ1 )satisfying supp(γ) ⊆ Φ and γ ∈ Γp,d (λ0 , λ1 ).
Theorem 2 ((ε, d , Df )-XDP ⇒ (ε, W1,d , Df )-XDistP):
Let d : X × X → R be a metric. If a randomized algorithm
A : X → DY provides (ε, d , Df )-XDP w.r.t. Φ then it
provides (ε, W1,d , Df )-XDistP w.r.t. Φ#
W1 .
See Appendix A for the proof. Since the Earth mover’s
distance is not grater than the diameter or ∞-Wasserstein distance, Df -XDistP may require less noise than D∞ -XDistP.
VI. L OCAL D ISTRIBUTION O BFUSCATION WITH
AUXILIARY I NPUTSIn this section we introduce a local obfuscation mechanism
which we call a coupling mechanism in order to provide
distribution privacy while optimizing utility. Specifically, a
coupling mechanism uses (full or approximate) knowledge
on the input probability distributions to perturb each single
input value so that the output distribution gets indistinguishable from some target probability distribution. To define themechanism, we calculate the probability coupling of each
input distribution and the target distribution.
A. Privacy Definitions with Auxiliary Inputs
We first extend the definition of divergence DistP so thata local obfuscation mechanism A can receive some auxiliary
input (e.g. context information) ranging over a set S, whichmight be used for A to apply different randomized algorithms
in different situations or to different input distributions.
Definition 15 (Divergence DistP with auxiliary inputs):
Let ε ∈ R≥0 , D ∈ Div(Y), and Ψ ⊆ (S × DX ) × (S × DX ).
We say that a randomized algorithm A : S × X → DY
provides (ε, D)-distribution privacy w.r.t. Ψ if for all pairs((s, λ), (s0 , λ0 )) ∈ Ψ ,D(A# (s, λ) k A# (s0 , λ0 )) ≤ ε.
In this definition, the auxiliary input over S typically
represents contextual information about where the obfuscation mechanism A is used or what distribution an input issampled from. Such information may be useful to customize
A to improve utility while providing distribution privacy inspecific situations. For example, assume that each auxiliary
input s represents the fact that an input x is sampled froma distribution λs . If a local mechanism A uses this auxiliary
information to always produce a distribution µ of outputs4 ,it can prevent the leakage of information on the input
distribution λs . We elaborate on this in the next sections.
4 If A can use no auxiliary information but wants to produce µ, then the
output value needs to be independent of the input, hence very poor utility.

B. Coupling Mechanisms
In this section we introduce a new local obfuscation
mechanism, which we call a coupling mechanism. The aim of
the new mechanism is to improve the utility while protecting
distribution privacy when we know the input distribution
fully or approximately. Intuitively, a coupling mechanism
uses (full or partial) information on the input distribution
λ ∈ DX and produces an output value following some
identical distribution µ ∈ DY, which we call a target distribution. More specifically, given some auxiliary informations about λ, a coupling mechanism A : S × X → DY
probabilistically maps each input value x to some output
value y so that y is distributed over the target distribution µ.
The simplest construction of a coupling mechanism would
be to randomly sample a value y from µ independently of
the input x. However, this mechanism provides very poor
utility, since the output y loses all information on x.
Instead, we construct a mechanism by calculating a coupling γ ∈ D(X ×Y) that transforms λ to µ with the minimum
loss. We explain this using a simple example below.
Example 2 (Coupling mechanism): A coupling γ of two
distributions λ and µ (Fig. 2b) shows a way of transforming
λ to µ by probabilistically adding noise to each single input
value drawn from λ. More specifically, γ[2, 1] = 0.1 meansthat 0.1 (out of λ[2] = 0.5) moves from 2 to 1, and γ[2, 3] =0.2 means that 0.2 moves from 2 to 3. Based on this couplingγ, we construct the coupling mechanism C that maps the
input 2 to the output 1 with probability 20%(= 0.1/0.5),
and to the output 3 with probability 40%(= 0.2/0.5). By
applying this mechanism C to the input distribution λ, theresulting output distribution C # (λ) is identical to µ.
Formally, we assume that for each auxiliary input s ∈ S,
bs ∈we learn that the input distribution is approximately λDX while the actual distribution is λs ∈ DX . Then we define
the coupling mechanism C as follows.
Definition 16 (Coupling mechanism): Let µ ∈ DY. Forbs ∈ DX be an approximate input
each s ∈ S, let λbs , µ) be a coupling of λbs anddistribution, and γs ∈ cp(λµ. Then a coupling mechanism w.r.t. µ is defined as arandomized algorithm C : S × X → DY such that givens ∈ S and x ∈ X , outputs y ∈ Y with the probability:
C (s, x)[y] = γbs [x,y] .
λs [x]

bs is
When C can access the exact information on λs (i.e., λidentical to the actual distribution λs from which inputs are
sampled), then C provides (0, D)-DistP for any divergenceD, i.e., no information on the input distribution is leaked by
the output of C . However, we often obtain only approximate
information on the input distribution. In this case, C still
provides strong privacy as shown in the next section.
C. Distribution Privacy of Coupling Mechanisms
In this section we evaluate the DistP and utility ofcoupling mechanisms. (See Appendix C for the proof.)
Theorem 3 (DistP of the coupling mechanism): Let Ψ ⊆(S × DX ) × (S × DX ) such that each element of Ψ is of theform (s, λs ) for some s ∈ S. Let C be a coupling mechanism
w.r.t. a target distribution µ. Assume that for each s ∈ S, thebs is close to the actual distribution
approximate knowledge λbbs ) ≤ ε.
λs in the sense that D∞ (λs k λs ) ≤ ε and D∞ (λs k λThen C provides:
1) (2ε, D∞ )-DistP w.r.t. Ψ ;2) (2ε eε , DKL )-DistP w.r.t. Ψ ;3) (eε f (e2ε ), Df )-DistP w.r.t. Ψ .
This theorem implies that when the mechanism C learns
bs = λs , then by ε = 0 it provides
the exact distribution, i.e., λ(0, D∞ )-DistP, hence there is no leaked information on the
input distributions. For ε ≈ 0, we have ε eε ≈ ε(1 + ε) ≈ ε,hence C provides approximately (2ε, DKL )-DistP .
D. Utility-Optimal Coupling Mechanisms
In this section we introduce a utility-optimal couplingmechanism. Here we assume that there is some metric d over
X ∪ Y. Then the notion of utility loss of a local obfuscation
mechanism is defined as follows.
Definition 17 (Expected utility loss): Given an input distribution λ ∈ DX and a metric d over X ∪ Y, the expectedutility loss of a randomized algorithm A : X → DY is:X
λ[x]A(x)[y]d (x, y).
x∈X ,y∈Y

The utility loss of a coupling mechanism depends onthe choice of the coupling used in the mechanism. Givenbs , thean Euclid distance d and an input distribution λexpected utility loss of a coupling mechanism w.r.t. a target distribution µ using a coupling γs is represented byP(x0 ,x1 )∈supp(γs ) d (x0 , x1 )γs [x0 , x1 ].
Now we define the coupling mechanism that minimizes
the expected utility loss as follows.
Definition 18 (Utility-optimal coupling mechanism):
Let µ ∈ DY. A utility-optimal coupling mechanism w.r.t.
µ is a coupling mechanism w.r.t. µ that uses a couplingγs ∈ Γ1,d (λs , µ) for each s ∈ S.
Proposition 2 (Loss of the coupling mechanism): Foreach s ∈ S, the expected utility loss of a utility-optimal
coupling mechanism w.r.t. a target distribution µ ∈ DY is
bs , µ).
given by the Earth mover’s distance W1,d (λThe proof is straightforward from the definition of the
Earth mover’s distance. Note that as mentioned in Section IIG, the coupling γs ∈ Γ1,d (λs , µ) can be efficiently calculatedby the North-West corner rule when d is submodular.
Analogously, we could define a coupling mechanism thatminimizes the maximum loss by using a coupling γs ∈Γ∞,d (λs , µ) for each s ∈ S. Then the worst-case utility loss
bs , µ).
is given by the ∞-Wasserstein metric W∞,d (λVII. R ELATED WORK
Since the seminal work of Dwork [1] on differential
privacy (DP), a lot of its variants have been studied toprovide different types of privacy guarantees [21]; e.g.,d-privacy [13], f -divergence privacy [20], [8], mutualinformation DP [9], concentrated DP [22], Rényi DP [10],Pufferfish privacy [23], Bayesian DP [24], local DP [2],personalized DP [25], and utility-optimized local DP [26].
All of these are intended to protect single input values insteadof input distributions.
A few researches have explored the privacy of distributions. Jelasity et al. [5] propose distributional DP to protect
the privacy of distribution parameters θ in a Bayesian style(unlike DP and DistP). Kawamoto et al. [6] propose the
DistP notion in a DP style. Geumlek et al. [7] propose
profile-based privacy, a variant of DistP that allows themechanisms to depend on the perfect knowledge of input
distributions. However, these studies deal only with theworst-case risk, and neither relax them to the averagecase risk (with divergence) nor allow them to use arbitrary
auxiliary information (in spite that available information on
input distributions is often approximate only).
There have been many studies (e.g., [27]) on the DPof histogram publishing, which is different from DistP as
follows. Histogram publishing is a central mechanism thathides a single record x ∈ X and outputs an obfuscatedhistogram, e.g., µ ∈ DY, whereas a DistP mechanism isa local mechanism that aims at hiding an input distribution
λ ∈ DX and outputs a single perturbed value y ∈ Y. As
explained in [6], neither of these implies the other.
VIII. C ONCLUSION
We introduced the notions of divergence DistP and presented their useful theoretical properties in a general form.
By using probability coupling techniques, we presented how
much divergence DistP can be achieved by local obfuscation.
In particular, we proved that the perturbation noise should be
added proportionally to the Earth mover’s distance between
the input distributions. We also proposed a local mechanism
called a (utility-optimal) coupling mechanism and theoretically evaluated their DistP and utility loss in the presence of(exact or approximate) knowledge on the input distributions.
As for future work, we are planning to develop various
kinds of coupling mechanisms for specific applications, suchas location privacy.
R EFERENCES[1] C. Dwork, “Differential privacy,” in Proc. ICALP, 2006, pp. 1–12.
[2] J. C. Duchi, M. I. Jordan, and M. J. Wainwright, “Local privacy andstatistical minimax rates,” in Proc. FOCS, 2013, pp. 429–438.
[3] M. E. Andrés, N. E. Bordenabe, K. Chatzikokolakis, andC. Palamidessi, “Geo-indistinguishability: differential privacy forlocation-based systems,” in Proc. CCS. ACM, 2013, pp. 901–914.
[4] Úlfar Erlingsson, V. Pihur, and A. Korolova, “RAPPOR: Randomized
aggregatable privacy-preserving ordinal response,” in Proc. CCS, 2014,
pp. 1054–1067.
[5] M. Jelasity and K. P. Birman, “Distributional differential privacy forlarge-scale smart metering,” in Proc. IH&MMSec, 2014, pp. 141–146.
[6] Y. Kawamoto and T. Murakami, “Local obfuscation mechanisms forhiding probability distributions,” in Proc. ESORICS, 2019, pp. 128–
148.
[7] J. Geumlek and K. Chaudhuri, “Profile-based privacy for locallyprivate computations,” CoRR, vol. abs/1903.09084, 2019.
[8] R. F. Barber and J. C. Duchi, “Privacy and statistical risk: Formalisms
and minimax bounds,” CoRR, vol. abs/1412.4451, 2014.
[9] P. Cuff and L. Yu, “Differential privacy as a mutual information
constraint,” in Proc. CCS, 2016, pp. 43–54.
[10] I. Mironov, “Rényi differential privacy,” in Proc. CSF, 2017, pp. 263–
275.

[11] D. Yang, D. Zhang, and B. Qu, “Participatory cultural mapping basedon collective behavior data in location based social networks,” ACM
TIST, vol. 7, no. 3, pp. 30:1–30:23, 2015.
[12] D. Yang, B. Qu, and P. Cudré-Mauroux, “Privacy-preserving social
media data publishing for personalized ranking-based recommendation,” IEEE Trans. Knowl. Data Eng., vol. 31, no. 3, pp. 507–520,
2019.
[13] K. Chatzikokolakis, M. E. Andrés, N. E. Bordenabe, andC. Palamidessi, “Broadening the scope of Differential Privacy using
metrics,” in Proc. PETS, 2013, pp. 82–102.
[14] M. S. Alvim, K. Chatzikokolakis, C. Palamidessi, and A. Pazii,“Invited paper: Local differential privacy on metric spaces: Optimizing
the trade-off with utility,” in Proc. CSF, 2018, pp. 262–267.
[15] I. Csiszar, “Information measures of difference of probability distributions and indirect observations,” Studia Sci. Math. Hungar., vol. 2,
pp. 299–318, 1967.
[16] S. Kullback and R. A. Leibler, “On information and sufficiency,” Ann.
Math. Statist., vol. 22, no. 1, pp. 79–86, 03 1951.
[17] L. Vaserstein, “Markovian processes on countable space productdescribing large systems of automata.” Probl. Peredachi Inf., vol. 5,
no. 3, pp. 64–72, 1969.
[18] A. J. Hoffman, “On simple linear programming problems,” in Convexity: Proceedings of the Seventh Symposium in Pure Mathematicsof the American Mathematical Society, 1963, vol. 7, p. 317.
[19] Y. Kawamoto, K. Chatzikokolakis, and C. Palamidessi, “On the compositionality of quantitative information flow,” Log. Methods Comput.
Sci., vol. 13, no. 3, 2017.
[20] G. Barthe and F. Olmedo, “Beyond differential privacy: Composition
theorems and relational logic for f-divergences between probabilistic
programs,” in Proc. ICALP, ser. LNCS, vol. 7966, 2013, pp. 49–60.
[21] D. Desfontaines and B. Pejó, “Sok: Differential privacies,”
CoRR,
vol.
abs/1906.01337,
2019.
[Online].
Available:
http://arxiv.org/abs/1906.01337[22] C. Dwork and G. N. Rothblum, “Concentrated differential privacy,”
CoRR, vol. abs/1603.01887, 2016.
[23] D. Kifer and A. Machanavajjhala, “A rigorous and customizable
framework for privacy,” in Proc. PODS, 2012, pp. 77–88.
[24] B. Yang, I. Sato, and H. Nakagawa, “Bayesian differential privacy on
correlated data,” in Proc. SIGMOD, 2015, pp. 747–762.
[25] Z. Jorgensen, T. Yu, and G. Cormode, “Conservative or liberal?
Personalized differential privacy,” in Proc. ICDE’15, 2015, pp. 1023–
1034.
[26] T. Murakami and Y. Kawamoto, “Utility-optimized local differential
privacy mechanisms for distribution estimation,” in Proc. USENIX
Security, 2019, pp. 1877–1894.
[27] J. Xu, Z. Zhang, X. Xiao, Y. Yang, G. Yu, and M. Winslett, “Differentially private histogram publication,” VLDB J., vol. 22, no. 6, pp.
797–822, 2013.

A PPENDIX

= min

P

≤ min

P

= min

P

= min

P

P

yc f

γ∈Γ

yc

γ∈Γ

x0 ,x1P

x0 ,x1γ[x0 ,x1 ] A(x1 )[y] γ[x0 ,x1 ] A(x0 )[y] · γ[x0 ,x1 ] A(x1 )[y]cγ[x0 ,x1 ] A(x1 )[y]0 ,x1 ] A(x0 )[y]· f γ[xcγ[x0 ,x1 ] A(x1 )[y](by Jensen’s inequality and the convexity of f )X
A(x0 )[y] A(x1 )[y] ·f A(xx0 ,x1 γ[x0 , x1 ]1 )[y]

γ∈Γ

y

γ∈Γ

x0 ,x1 γ[x0 , x1 ] Df (A(x0 ) k A(x1 )).

(1)Assume that A provides (ε, Df )-DP w.r.t. Φ. By Definition 14, there is a coupling γ ∈ Γ with supp(γ) ⊆ Φ. Then:
Df (A# (λ0 ) k A# (λ1 ))P= min x0 ,x1 γ[x0 , x1 ] Df (A(x0 ) k A(x1 ))γ∈ΓP≤ min x0 ,x1 γ[x0 , x1 ] ε(by (1))γ∈Γ(by (x0 , x1 ) ∈ supp(γ) ⊆ Φ and (ε, Df )-DP)= ε.
Hence A provides (ε, Df )-DistP w.r.t. Φ# .
Theorem 2 ((ε, d , Df )-XDP ⇒ (ε, W1,d , Df )-XDistP):
Let d : X × X → R be a metric. If a randomized algorithm
A : X → DY provides (ε, d , Df )-XDP w.r.t. Φ then it
provides (ε, W1,d , Df )-XDistP w.r.t. Φ#
W1 .
Proof: Assume that A provides (ε, d , Df )-XDP w.r.t. Φ.
Let (λ0 , λ1 ) ∈ Φ#
W1 . By definition, there exists a couplingγ ∈ Γ that satisfies supp(γ) ⊆ Φ and γ ∈ Γ1,d (λ0 , λ1 ). Thenit follows from (1) in the proof for Theorem 1 that:
Df (A# (λ0 ) k A# (λ1 ))P= min x0 ,x1 γ[x0 , x1 ] Df (A(x0 ) k A(x1 ))γ∈ΓP≤ min x0 ,x1 γ[x0 , x1 ] ε d (x0 , x1 )(by (1))γ∈Γ(by (x0 , x1 ) ∈ supp(γ) ⊆ Φ and (ε, d , Df )-XDP)= ε W1,d (λ0 , λ1 ).

(by γ ∈ Γ1,d (λ0 , λ1 ))Hence A provides (ε, W1,d , Df )-XDistP w.r.t. Φ#
W1 .

A. Local Mechanisms for Df -DistP/XDistP

B. Point Obfuscation by Distribution Obfuscation

We first show the proofs for the Df -DistP/XDistP
achieved by local obfuscation mechanisms.

Next we show that divergence DP is an instance ofdivergence DistP if an adjacency relation includes pairs of
point distributions (i.e., distributions having single points
with probability 1).

Theorem 1 ((ε, Df )-DP ⇒ (ε, Df )-DistP): Let Φ ⊆ X ×
X . If a randomized algorithm A : X → DY provides(ε, Df )-DP w.r.t. Φ, then it provides (ε, Df )-DistP w.r.t. Φ# .
def
Proof: Let (λ0 , λ1 ) ∈ Φ# and Γ = cp(λ0 , λ1 ).
Df (A# (λ0 ) k A# (λ1 ))#P(λ0 )[y] = y A# (λ1 )[y] f A
A# (λ1 )[y]
 P λ [x ] A(x )[y] 
P P
0 0
0
= y x1 λ1 [x1 ] A(x1 )[y] f Px0 λ1 [x1 ] A(x1 )[y]
x1

P
P
γ[x0 ,x1 ] A(x0 )[y]= min y,x0 ,x1 γ[x0 , x1 ] A(x1 )[y] f P x0 ,x1γ[x0 ,x1 ] A(x1 )[y]γ∈Γx0 ,x1(where (x0 , x1 ) ranges over supp(γ))
 PP= min y c f 1c x0 ,x1 γ[x0 , x1 ] A(x0 )[y]γ∈Γ(where c =Px0 ,x1γ[x0 ,x1 ] A(x1 )[y])Lemma 1: Let p ∈ R≥1 ∪ {∞} and Φ ⊆ X × X . For any(x0 , x1 ) ∈ Φ, we have (ηx0 , ηx1 ) ∈ Φ#Wp .
Theorem 4 (DistP ⇒ DP and XDistP ⇒ XDP): Letε ∈ R≥0 , p ∈ R≥1 ∪ {∞}, D ∈ Div(Y), Φ ⊆ X × X , andA : X → DY be a randomized algorithm.
1) If A provides (ε, D)-DistP w.r.t. Φ# , then it provides(ε, D)-DP w.r.t. Φ.
2) If A provides (ε, Wp,d , D)-XDistP w.r.t. Φ#
Wp , then it
provides (ε, d , D)-XDP w.r.t. Φ.
Proof: We show the first claim as follows. Assume that
A provides (ε, D)-DistP w.r.t. Φ# . Let (x0 , x1 ) ∈ Φ, andηx0 and ηx1 be the point distributions. By Lemma 1 and##Φ#Wp ⊆ Φ , we have (ηx0 , ηx1 ) ∈ Φ . By (ε, D)-DistP, weobtain D(A(x0 ) k A(x1 )) = D(A# (ηx0 ) k A# (ηx1 )) ≤ ε.
Hence A provides (ε, D)-DP w.r.t. Φ.
Next we show the second claim. Assume that A provides(ε, Wp,d , D)-XDistP w.r.t. Φ#
Wp . Let (x0 , x1 ) ∈ Φ, and ηx0
and ηx1 be the point distributions. By Lemma 1, we have(ηx0 , ηx1 ) ∈ Φ#
Wp . Then we obtain:#

Finally, the f -divergence is given by:
Df (C # (s0 , λs0 ) k C # (s1 , λs1 )) #
C (s ,λ )[y]= sup C # (s1 , λs1 )[y] · f C # (s10 ,λss0 )[y]
1
y

ε
2ε
≤ e sup µ[y]f ey≤ eε f (e2ε ).

#D(A(x0 ) k A(x1 )) = D(A (ηx0 ) k A (ηx1 ))≤ εWp,d (ηx0 , ηx1 )(by XDistP of A)= εd (x0 , x1 ),where the last equality follows from the definition of Wp,d .
Hence A provides (ε, d , D)-XDP w.r.t. Φ.
C. Privacy and Utility of Coupling Mechanisms
Next, we show the privacy of the coupling mechanisms.
Theorem 3 (DistP of the coupling mechanism): Let Ψ ⊆(S × DX ) × (S × DX ) such that each element of Ψ is of theform (s, λs ) for some s ∈ S. Let C be a coupling mechanism
w.r.t. a target distribution µ. Assume that for each s ∈ S, thebs is close to the actual distribution
approximate knowledge λbs k λs ) ≤ ε and D∞ (λs k λbs ) ≤ ε.
λs in the sense that D∞ (λThen C provides:
1) (2ε, D∞ )-DistP w.r.t. Ψ ;2) (2ε eε , DKL )-DistP w.r.t. Ψ ;3) (eε f (e2ε ), Df )-DistP w.r.t. Ψ .
Proof: Let ((s0 , λs0 ), (s1 , λs1 )) ∈ Ψ , and R ⊆ Y. When
C is applied to λs0 the output distribution is given by:Xγ [x,R]C #(s0 , λs0 )[R] =λs0 [x] · bs0
λs0 [x]

x∈X

≤ eε

X

bs ) ≤ ε)γs0 [x, R] (by D∞ (λs0 k λ
0x∈X

Therefore C provides (eε f (e2ε ), Df )-DistP w.r.t. Ψ .
D. Sequential Composition

Then we present the compositionality of DKL -DistP. Notethat since this composition is adaptive, the compositionality
does not hold in general for f -divergence.
Proposition 3 (Sequential composition of DKL -DistP):
Let Φ ⊆ X ×X . If A0 : X → DY0 provides (ε0 , DKL )-DistP
w.r.t. Φ# and for each y0 ∈ Y0 , A1 (y0 ) : X → DY1 provides(ε1 , DKL )-DistP w.r.t. Φ# , the sequential composition
A1 A0 provides (ε0 + ε1 , DKL )-DistP w.r.t. Φ# .
Proof: By Theorem 4 in Appendix B, A0 provides(ε0 , DKL )-DP w.r.t. Φ, and for each y0 ∈ Y0 , A1 (y0 )provides (ε1 , DKL )-DP w.r.t. Φ. Let (x, x0 ) ∈ Φ. Then:
DKL ((A1 A0 )(x) k (A1 A0 )(x0 ))X(A1 A0 )(x)[y1 ]=(A1 A0 )(x)[y1 ] ln (A0
1 A0 )(x )[y1 ]
y1

=

ε

= e µ[R].

≥e−ελs1 [x]0 ]·A1 (y0 ,x)[y1 ]A0 (x)[y0 ] · A1 (y0 , x)[y1 ] ln AA00(x(x)[y0 )[y ]·A (y ,x0 )[y ]
0
1
0
1

=

X

(x)[y0 ]A0 (x)[y0 ] ln AA00(x0 )[y ]
0

y0

+

X

(y0 ,x)[y1 ]A0 (x)[y0 ]A1 (y0 , x)[y1 ] ln AA11(y00 ,x )[y1 ]y0 ,y1X

bs k λs ) ≤ ε)γs1 [x, R] (by D∞ (λ
1
1

x∈X

= e−ε µ[R].

≤ DKL (A0 (x) k A0 (x0 ))X(y0 ,x)[y1 ]+ max A1 (y0 , x)[y1 ] ln AA11(y00 ,x )[y1 ]y0#

C (s0 ,λ0 )[R]2ε
. Therefore C provides (2ε, D∞ )Hence C# (s ,λ )[R] ≤ e
1
1
DistP w.r.t. Ψ .
Next the KL-divergence is given by:#X
y0 ,y1

When C is applied to λs1 the output distribution is:Xγ [x,R]C #(s1 , λs1 )[R] =λs1 [x] · bs1
x∈X

with Shared Input

We first recall the definition of the sequential composition
with shared input (Fig. 3a) in previous work.
Definition 19 (Sequential composition ): Giventwo
randomized algorithms A0 : X → DY0 and A1 : Y0
× X → DY1 , we define the sequential composition of A0
and A1 as the randomized algorithm A1 A0 : X → DY1such that for any x ∈ X , (A1 A0 )(x) = A1 (A0 (x), x)).

#

DKL (C (s0 , λs0 ) k C (s1 , λs1 )) #C (s ,λ )[y]= sup C # (s0 , λs0 )[y] · ln C # (s01 ,λss0 )[y]
1
y

ε
2ε
≤ e sup µ[y] ln ey≤ 2ε eε .
Therefore C provides (2ε eε , Df )-DistP w.r.t. Ψ .

y1= DKL (A0 (x) k A0 (x0 )) + max DKL (A1 (y0 , x) k A1 (y0 , x0 ))y0≤ ε0 + ε1 .
Hence A1 A0 provides (ε0 + ε1 , DKL )-DP w.r.t. Φ. By
Theorem 1, A1 A0 provides (ε0 +ε1 , DKL )-DistP w.r.t. Φ# .
Proposition 4 (Sequential composition of DKL -XDistP):
Let d be a metric over X , and Φ ⊆ X ×X . If A0 : X → DY0
provides (ε0 , W1,d , DKL )-XDistP w.r.t. Φ#
W1 and for eachy0 ∈ Y0 , A1 (y0 ) : X → DY1 provides (ε1 , W1,d , DKL )XDistP w.r.t. Φ#
A0
W1 then the sequential composition A1
provides (ε0 + ε1 , W1,d , DKL )-XDistP w.r.t. Φ#.
W1

Proof: Analogous to the proof for Proposition 3.
E. Sequential Composition • with Independent Sampling
In this section we present the compositionality with independent sampling, which is defined as follows.
Definition 20 (Sequential composition •): Given two randomized algorithms A0 : X → DY0 and A1 : Y0 × X →DY1 , we define the sequential composition of A0 and A1 as
the randomized algorithm A1 •A0 : X ×X → DY1 such that:for any x0 , x1 ∈ X , (A1 • A0 )(x0 , x1 ) = A1 (A0 (x0 ), x1 )).
We define an operator  between binary relations Ψ0 and Ψ1 :
Ψ0 Ψ1 = {(λ0 ×λ1 , λ00 ×λ01 ) | (λ0 , λ00 ) ∈ Ψ0 , (λ1 , λ01 ) ∈ Ψ1 }.
Now we show the compositionality for DKL -DistP.
Proposition 5 (Sequential composition • of DKL -DistP):
Let Ψ ⊆ DX × DX . If A0 : X → DY0 provides (ε0 , DKL )DistP w.r.t. Ψ and for each y0 ∈ Y0 , A1 (y0 ) : X → DY1
provides (ε1 , DKL )-DistP w.r.t. Ψ , then the composition
A1 • A0 provides (ε0 + ε1 , DKL )-DistP w.r.t. Ψ  Ψ .
Proof: Let (λ0 , λ00 ), (λ1 , λ01 ) ∈ Ψ .
##

DKL ((A1 • A0 ) (λ0 × λ1 ) k (A1 • A0 ) (λ00 × λ01 ))X#(A1 •A0 )# (λ0 ×λ1 )[y1 ]=(A1 • A0 ) (λ0 × λ1 )[y1 ] ln (A•A )# (λ0 ×λ0 )[y ]
1

0

0

y1

=

X

#

#

0

X

0

0

1

0

1

1

0

X

(by (c, W )-stable).

Therefore A ◦ T provides (c ε, W , D)-XDistP.
10

y0 ,y1

1

1≤DKL (A0 # (λ0 ) k A0 # (λ00 ))X#
1 (y0 )(λ1 )[y1 ]A1 # (y0 )(λ1 )[y1 ] ln A
+ max
A1 # (y0 )(λ0 )[y1 ]y0≤ εW (T # (λ), T # (λ0 ))##1 (y0 ) (λ1 )[y1 ]A0 (λ0 )[y0 ]A1 (y0 ) (λ1 )[y1 ] ln A
A (y )# (λ0 )[y ]##= D(A# (T # (λ)) k A# (T # (λ0 )))≤ c εW (λ, λ0 )#0 (λ0 )[y0 ]A0 # (λ0 )[y0 ] ln A
A0 # (λ0 )[y0 ]

y0

+

#

A0 (λ0 )[y0 ]A1 (y0 ) (λ1 )[y1 ]A0#(λ0)[y0 ]A1 (y0 ) (λ1)[y1 ] ln A#(λ0 )[y ]A (y )#(λ0 )[y ]y0 ,y1=#

D((A ◦ T ) (λ) k (A ◦ T ) (λ0 ))1

11) If A0 provides (ε, Df )-DistP w.r.t. Ψ then so does thecomposite function A1 ◦ A0 .
2) If A0 provides (ε, W , Df )-XDistP w.r.t. Ψ then sodoes the composite function A1 ◦ A0 .
Proof: The claim is immediate from the data processing
inequality for the f -divergence.
We then show properties of pre-processing as follows.
Proposition 8 (Pre-processing): Let c ∈ R≥0 , Ψ ⊆ DX ×
DX , W : DX × DX → R≥0 be a metric, and D ∈ Div(Y).
1) If T : DX → DX is a (c, Ψ )-stable transformation
and A : X → DY provides (ε, D)-DistP w.r.t. Ψ , thenA ◦ T provides (c ε, D)-DistP w.r.t. Ψ .
2) If T : DX → DX is a (c, W )-stable transformation
and A : X → DY provides (ε, W , D)-XDistP, thenA ◦ T provides (c ε, W , D)-XDistP.
Proof: We show the first claim as follows. Assume
that A provides (ε, D)-DistP w.r.t. Ψ . Let (λ, λ0 ) ∈ Ψ .
##Then D((A ◦ T ) (λ) k (A ◦ T ) (λ0 )) = D(A# (T # (λ)) k## 0
A (T (λ ))) ≤ cε by (c, Ψ )-stability. Therefore A ◦ T
provides (c ε, D)-DistP w.r.t. Ψ .
Next we show the second claim. Assume that A provides(ε, W , D)-XDistP. Let λ, λ0 ∈ DX . Then we obtain:1y1= DKL (A0 # (λ0 ) k A0 # (λ00 ))+ max DKL (A1 # (y0 )(λ1 ) k A1 # (y0 )(λ01 ))y0≤ ε0 + ε1 .
Hence A1 • A0 provides (ε0 + ε1 , DKL )-DistP w.r.t. Ψ  Ψ .
Proposition 6 (Sequential composition • of DKL -XDistP):
Let d be a metric over X , and Ψ ⊆ DX × DX . If
A0 : X → DY0 provides (ε0 , W1,d , DKL )-XDistP w.r.t.
Ψ and for each y0 ∈ Y0 , A1 (y0 ) : X → DY1 provides(ε1 , W1,d , DKL )-XDistP w.r.t. Ψ , then the composition
A1 • A0 provides (ε0 + ε1 , W1,d , DKL )-XDistP w.r.t. Ψ  Ψ .
Proof: Analogous to the proof for Proposition 5.
F. Post-processing and Pre-processing
Next we show that divergence distribution privacy isimmune to the post-processing. For A0 : X → DY and A1 :Y → DZ, we define A1 ◦A0 by: (A1 ◦A0 )(x) = A1 (A0 (x)).
Proposition 7 (Post-processing): Let Ψ ⊆ DX × DX , andW : DX × DX → R≥0 be a metric. Let A0 : X → DY andA1 : Y → DZ.

G. Relationships among XDistP Notions
Finally, we show relationships among distribution privacy
notions with different metric d and divergence D.
Proposition 9 (W1,d -XDistP ⇒ W∞,d -XDistP): Let
D ∈ Div(Y). If A : X → DY provides (ε, W1,d , D)XDistP, then it provides (ε, W∞,d , D)-XDistP.
Proof: Assume that A provides (ε, W1,d , D)-XDistP.
Let λ0 , λ1 ∈ DX . By the property of the p-Wasserstein
metric, W1,d (λ0 , λ1 ) ≤ W∞,d (λ0 , λ1 ). Then D(µ0 k µ1 ) ≤W1,d (λ0 , λ1 ) ≤ W∞,d (λ0 , λ1 ). Hence the claim follows.
Proposition 10 (D ≤ D 0 & D 0 -XDistP ⇒ D-XDistP):
Let d : (DX × DX ) → R be a metric. Let D, D0 ∈ Div(Y)be two divergences such that for all µ0 , µ1 ∈ DY,
D(µ0 k µ1 ) ≤ D 0 (µ0 k µ1 ). If A : X → DY provides(ε, d, D 0 )-XDistP, then it provides (ε, d, D)-XDistP.
Then (ε, d, D∞ )-XDistP implies (ε, d, DKL )-XDistP.
Proof: Assume A provides (ε, d, D 0 )-XDistP. Let
λ0 , λ1 ∈ DX . Then D 0 (A# (λ0 )kA# (λ1 )) ≤ εd(λ0 , λ1 ). By
definition, D(A# (λ0 )kA# (λ1 )) ≤ D 0 (A# (λ0 )kA# (λ1 )) ≤εd(λ0 , λ1 ). Thus A provides (ε, d, D)-XDistP.