Local Obfuscation Mechanisms for Hiding
Probability Distributions ?
Yusuke Kawamoto1[0000−0002−2151−9560] andTakao Murakami2[0000−0002−5110−1261]
1

AIST, Tsukuba, Japan
AIST, Tokyo, Japan

2

Abstract. We introduce a formal model for the information leakage ofprobability distributions and define a notion called distribution privacy
as the local differential privacy for probability distributions. Roughly,
the distribution privacy of a local obfuscation mechanism means thatthe attacker cannot significantly gain any information on the distribution of the mechanism’s input by observing its output. Then we showthat existing local mechanisms can hide input distributions in terms of
distribution privacy, while deteriorating the utility by adding too muchnoise. For example, we prove that the Laplace mechanism needs to add alarge amount of noise proportionally to the infinite Wasserstein distance
between the two distributions we want to make indistinguishable. To improve the tradeoff between distribution privacy and utility, we introduce
a local obfuscation mechanism, called a tupling mechanism, that adds
random dummy data to the output. Then we apply this mechanism tothe protection of user attributes in location based services. By experiments, we demonstrate that the tupling mechanism outperforms popular
local mechanisms in terms of attribute obfuscation and service quality.
Keywords: local differential privacy · obfuscation mechanism · location
privacy · attribute privacy · Wasserstein metric · compositionality

1

Introduction

Differential privacy [1] is a quantitative notion of privacy that has been applied
to a wide range of areas, including databases, geo-locations, and social network.
The protection of differential privacy can be achieved by adding controlled noise
to given data that we wish to hide or obfuscate. In particular, a number of recent
studies have proposed local obfuscation mechanisms [2–4], namely, randomized
algorithms that perturb each single “point” data (e.g., a geo-location point) byadding certain probabilistic noise before sending it out to a data collector. However, the obfuscation of a probability distribution of points (e.g., a distributionof locations of users at home/outside home) still remains to be investigated interms of differential privacy.
?

This work was partially supported by JSPS KAKENHI Grant JP17K12667,
JP19H04113, and Inria LOGIS project.

2

Y. Kawamoto et al.

For example, a location-based service (LBS) provider collects each user’s geolocation data to provide a service (e.g., navigation or point-of-interest search),and has been widely studied in terms of the privacy of user locations. As shownin [3, 5], users can hide their accurate locations by sending to the LBS provider
only approximate location information calculated by an obfuscation mechanism.
Nevertheless, a user’s location information can be used for an attacker toinfer the user’s attributes (e.g., age, gender, social status, and residence area)or activities (e.g., working, sleeping, and shopping) [6–9]. For example, when an
attacker knows the distribution of residence locations, he may detect whether
given users are at home or outside home after observing their obfuscated locations. For another example, an attacker may learn whether users are rich or poorby observing their obfuscated behaviors. These attributes can be used by robbers
hence should be protected from them. Privacy issues of such attribute inference
are also known in other applications, including recommender systems [10, 11]
and online social networks [12, 13]. However, to our knowledge, no literature hasaddressed the protection of attributes in terms of local differential privacy.
To illustrate the privacy of attributes in an LBS, let us consider a running
example where users try to prevent an attacker from inferring whether they areat home or not. Let λhome and λout be the probability distributions of locations of the users at home and outside home, respectively. Then the privacy ofthis attribute means that the attacker cannot learn from an obfuscated location
whether the actual location follows the distribution λhome or λout .
This can be formalized using differential privacy. For each t ∈ {home, out},
we denote by p(y | λt ) the probability of observing an obfuscated location y whenan actual location is distributed over λt . Then the privacy of t is defined by:p(y | λhome )≤ eε ,
p(y | λout )which represents that the attacker cannot distinguish whether the users follow
the distribution λhome or λout with degree of ε.
To generalize this, we define a notion, called distribution privacy (DistP),
as the differential privacy for probability distributions. Roughly, we say that amechanism A provides DistP w.r.t. λhome and λout if no attacker can detect
whether the actual location (input to A) is sampled from λhome or λout after heobserved an obfuscated location y (output by A)3 . Here we note that each user
applies the mechanism A locally by herself, hence can customize the amount ofnoise added to y according to the attributes she wants to hide.
Although existing local differential privacy mechanisms are designed to protect point data, they also hide the distribution that the point data follow. However, we demonstrate that they need to add a large amount of noise to obfuscate
distributions, and thus deteriorate the utility of the mechanisms.
To achieve both high utility and strong privacy of attributes, we introduce
a mechanism, called the tupling mechanism, that not only perturbs an actual
3

In our setting, the attacker observes only a sampled output of A, and not the exact
histogram of A’s output distribution. See Section 3.5 for more details.

Local Obfuscation Mechanisms for Hiding Probability Distributions

3

input, but also adds random dummy data to the output. Then we prove that
this mechanism provides DistP. Since the random dummy data obfuscate theshape of the distribution, users can instead reduce the amount of noise added tothe actual input, hence they get better utility (e.g., quality of a POI service).
This implies that DistP is a relaxation of differential privacy that guarantees
the privacy of attributes while achieving higher utility by weakening the differentially private protection of point data. For example, suppose that users do
not mind revealing their actual locations outside home, but want to hide (e.g.,
from robbers) the fact that they are outside home. When the users employ the
tupling mechanism, they output both their (slightly perturbed) actual locations
and random dummy locations. Since their outputs include their (roughly) actual locations, they obtain high utility (e.g., learning shops near their locations),
while their actual location points are protected only weakly by differential privacy. However, their attributes at home/outside home are hidden among thedummy locations, hence protected by DistP. By experiments, we demonstratethat the tupling mechanism is useful to protect the privacy of attributes, and outperforms popular existing mechanisms (the randomized response [14], the planar
Laplace [3] and Gaussian mechanisms) in terms of DistP and service quality.
Our contributions. The main contributions of this work are given as follows:– We propose a formal model for the privacy of probability distributions interms of differential privacy. Specifically, we define the notion of distribution
privacy (DistP) to represent that the attacker cannot significantly gain information on the distribution of a mechanism’s input by observing its output.
– We provide theoretical foundation of DistP, including its useful properties(e.g., compositionality) and its interpretation (e.g., in terms of Bayes factor).
– We quantify the effect of distribution obfuscation by existing local mechanisms. In particular, we show that (extended) differential privacy mechanisms are able to make any two distributions less distinguishable, while
deteriorating the utility by adding too much noise to protect all point data.
– For instance, we prove that extended differential privacy mechanisms (e.g.,the Laplace mechanism) need to add a large amount of noise proportionallyto the ∞-Wasserstein distance W∞,d (λ0 , λ1 ) between the two distributions
λ0 and λ1 that we want to make indistinguishable.
– We show that DistP is a useful relaxation of differential privacy when users
want to hide their attributes, but not necessarily to protect all point data.
– To improve the tradeoff between DistP and utility, we introduce the tuplingmechanism, which locally adds random dummies to the output. Then weshow that this mechanism provides DistP and hight utility for users.
– We apply local mechanisms to the obfuscation of attributes in location based
services (LBSs). Then we show that the tupling mechanism outperforms
popular existing mechanisms in terms of DistP and service quality.
All proofs of technical results can be found in Appendix.

4

2

Y. Kawamoto et al.

Preliminaries

In this section we recall some notions of privacy and metrics used in this paper.
Let N>0 be the set of positive integers, and R>0 (resp. R≥0 ) be the set of
positive (resp. non-negative) real numbers. Let [0, 1] be the set of non-negative
real numbers not grater than 1. Let ε, ε0 , ε1 ∈ R≥0 and δ, δ0 , δ1 ∈ [0, 1].
2.1

Notations for Probability Distributions

We denote by DX the set of all probability distributions over λ
0
0.5
0.3
a set X , and by |X | the number of elements in a finite set X .
0.2
Given a finite set X and a distribution λ ∈ DX , the1
2
3
probability of drawing a value x from λ is denoted by λ[x]. γ 0.2 0.1 0.2 0.3
0000.2 AFor
 ? AU ?
P a finite0 subset X ⊆ X we define λ[X ] by: λ[X ] =
?
λ[x
].
For
a
distribution
λovera
finite
set
X
,
its
0
0
x ∈X
0.5
support supp(λ) is defined by supp(λ) = {x ∈ X : λ[x] > 0}. λ1 0.3
0.2
Given a λ ∈ DX and a f : X → R, the expected value of f
1
2
3
def P
over λ is: Ex∼λ [f (x)] = x∈X λ[x]f (x).
For a randomized algorithm A : X → DY and a set Fig. 1: Coupling γ.
R ⊆ Y we denote by A(x)[R] the probability that given
input x, A outputs one of the elements of R. Given a randomized algorithm
A : X → DY and a distribution λ over X , we define A# (λ) as the distributionof the output of A. Formally, for a finite set X , the lifting of A w.r.t. X is thedef Pfunction A# : DX → DY such that A# (λ)[R] = x∈X λ[x]A(x)[R].
2.2

Differential Privacy (DP)Differential privacy [1] captures the idea that given two “adjacent” inputs x and
x0 (from a set X of data with an adjacency relation Φ), a randomized algorithm
A cannot distinguish x from x0 (with degree of ε and up to exceptions δ).
Definition 1 (Differential privacy). Let e be the base of natural logarithm.
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.
2.3

Differential Privacy Mechanisms and Sensitivity

Differential privacy can be achieved by a privacy mechanism, namely a randomized algorithm that adds probabilistic noise to a given input that we want toprotect. The amount of noise added by some popular mechanisms (e.g., the exponential mechanism) depends on a utility function u : X × Y → R that maps
a pair of input and output to a utility score. More precisely, the noise is added
according to the “sensitivity” of u, which we define as follows.

Local Obfuscation Mechanisms for Hiding Probability Distributions

5

Definition 2 (Utility distance). The utility distance w.r.t a utility functiondefu : (X ×Y) → R is the function d given by: d (x, x0 ) = maxy∈Y u(x, y)−u(x0 , y) .
Note that d is a pseudometric. Hereafter we assume that for all x, y, u(x, y) = 0
is logically equivalent to x = y. Then the utility distance d is a metric.
Definition 3 (Sensitivity w.r.t. an adjacency relation). The sensitivity ofa utility function u w.r.t. an adjacency relation Φ ⊆ X × X is defined as:
def∆Φ,d =

2.4

max d (x, x0 ) = max
max u(x, y) − u(x0 , y) .
0

(x,x0 )∈Φ

(x,x )∈Φ y∈Y

Extended Differential Privacy (XDP)

We review the notion of extended differential privacy [15], which relaxes DP byincorporating a metric d. Intuitively, this notion guarantees that when two inputs
x and x0 are closer in terms of d, the output distributions are less distinguishable.
Definition 4 (Extended differential privacy). For a metric d : X × X → R,
we say that a randomized algorithm A : X → DY provides (ε, δ, d)-extended
differential privacy (XDP) if for all x, x0 ∈ X and for any R ⊆ Y,
0

Pr[A(x) ∈ R] ≤ eεd(x,x ) Pr[A(x0 ) ∈ R] + δ.
2.5

Wasserstein Metric

We recall the notion of probability coupling as follows.
Definition 5 (Coupling). Given λ0 ∈ DX0 and λ1 ∈ DX1 , a coupling of λ0
and λ1 is a γ ∈ D(X0 × X1 ) such
Pthat λ0 and λ1 are γ’s marginal distributions,
i.e., for each x0 ∈ X0 , λ0 [x0 ] = x0 ∈X1 γ[x0 , x01 ] and for each x1 ∈ X1 , λ1 [x1 ] =1P0x0 ∈X0 γ[x0 , x1 ]. We denote by cp(λ0 , λ1 ) the set of all couplings of λ0 and λ1 .
0

Example 1 (Coupling as transformation of distributions). Let us consider two
distributions λ0 and λ1 shown in Fig. 1. A coupling γ of λ0 and λ1 shows a wayof transforming λ0 to λ1 . For example, γ[2, 1] = 0.1 moves from λ0 [2] to λ1 [1].
We then recall the ∞-Wasserstein metric [16] between two distributions.
Definition 6 (∞-Wasserstein metric). Let d be a metric over X . The ∞Wasserstein metric W∞,d w.r.t. d is defined by: for any λ0 , λ1 ∈ DX ,W∞,d (λ0 , λ1 ) =

min

max

d (x0 , x1 ).

γ∈cp(λ0 ,λ1 ) (x0 ,x1 )∈supp(γ)

The ∞-Wasserstein metric W∞,d (λ0 , λ1 ) represents the minimum largest
move between points in a transportation from λ0 to λ1 . Specifically, in a transportation γ, max(x0 ,x1 )∈supp(γ) d (x0 , x1 ) represents the largest move from a point
in λ0 to another in λ1 . For instance, in the coupling γ in Example 1, the largest

6

Y. Kawamoto et al.

move is 1 (from λ0 [2] to λ1 [1], and from λ0 [2] to λ1 [3]). Such a largest move isminimized by a coupling that achieves the ∞-Wasserstein metric. We denoteby Γ∞,d the set of all couplings that achieve the ∞-Wasserstein metric.
Finally, we recall the notion of the lifting of relations.
Definition 7 (Lifting of relations). Given a relation Φ ⊆ X × X , the liftingof Φ is the maximum relation Φ# ⊆ DX × DX such that for any (λ0 , λ1 ) ∈ Φ# ,there exists a coupling γ ∈ cp(λ0 , λ1 ) satisfying supp(γ) ⊆ Φ.
Note that by Definition 5, the coupling γ is a probability distribution over Φ
whose marginal distributions are λ0 and λ1 . If Φ = X × X , then Φ# = DX × DX .

3

Privacy Notions for Probability Distributions

In this section we introduce a formal model for the privacy of user attributes,
which is motivated in Section 1.
3.1

Modeling the Privacy of User Attributes in Terms of DP

As a running example, we consider an LBS (location based service) in which
each user queries an LBS provider for a list of shops nearby. To hide a user’s
exact location x from the provider, the user applies a randomized algorithm
A : X → DY, called a local obfuscation mechanism, to her location x, andobtains an approximate information y with the probability A(x)[y].
To illustrate the privacy of attributes, let us consider an example in whichusers try to prevent an attacker from inferring whether they are male or female
by obfuscating their own exact locations using a mechanism A. For each t ∈{male, female}, let λt ∈ DX be the prior distribution of the location of the users
who have the attribute t. Intuitively, λmale (resp. λfemale ) represents an attacker’s
belief on the location of the male (resp. female) users before the attacker observes
an output of the mechanism A. Then the privacy of t can be modeled as aproperty that the attacker has no idea on whether the actual location x follows
the distribution λmale or λfemale after observing an output y of A.
This can be formalized in terms of ε-local DP. For each t ∈ {male, female},
we denote by p(y | λt ) the probability of observing an obfuscatedP location y whenan actual location x is distributed over λt , i.e., p(y | λt ) = x∈X λt [x]A(x)[y].
Then we can define the privacy of t by:p(y | λmale )εp(y | λfemale ) ≤ e .

3.2

Distribution Privacy and Extended Distribution Privacy

We generalize the privacy of attributes (in Section 3.1) and define the notionof distribution privacy (DistP) as the differential privacy where the input is a
probability distribution of data rather than a value of data. This notion models
a level of obfuscation that hides which distribution a data value is drawn from.
Intuitively, we say a randomized algorithm A provides DistP if, by observing an
output of A, we cannot detect from which distribution an input to A is generated.

Local Obfuscation Mechanisms for Hiding Probability Distributions

7

Definition 8 (Distribution privacy). Let ε ∈ R≥0 and δ ∈ [0, 1]. We saythat 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 ) ∈ Ψ and all R ⊆ Y, we have:A# (λ)[R] ≤ eε · A# (λ0 )[R] + δ.
We say A provides (ε, δ)-DistP w.r.t. Λ ⊆ DX if it provides (ε, δ)-DistP w.r.t. Λ2 .
For example, the privacy of a user attribute t ∈ {male, female} described in
Section 3.1 can be formalized as (ε, 0)-DistP w.r.t. {λmale , λfemale }.
Mathematically, DistP is not a new notion but the DP for distributions. To
contrast with DistP, we refer to the DP for data values as point privacy.
Next we introduce an extended form of distribution privacy to a metric.
Intuitively, extended distribution privacy guarantees that when two input distributions are closer, then the output distributions must be less distinguishable.
Definition 9 (Extended distribution privacy). Let d : (DX × DX ) → R bea utility distance, and Ψ ⊆ DX × DX . We say that a mechanism A : X → DY
provides (ε, d, δ)-extended distribution privacy (XDistP) w.r.t. Ψ if the lifting A#
provides (ε, d, δ)-XDP w.r.t. Ψ , i.e., for all (λ, λ0 ) ∈ Ψ and all R ⊆ Y, we have:0

A# (λ)[R] ≤ eεd(λ,λ ) · A# (λ0 )[R] + δ.
3.3

Interpretation by Bayes Factor

The interpretation of DP has been explored in previous work [17, 15] using thenotion of Bayes factor. Similarly, the meaning of DistP can also be explained interms of Bayes factor, which compares the attacker’s prior and posterior beliefs.
Assume that an attacker has some belief on the input distribution before
observing the output values of an obfuscater A. We denote by p(λ) the priorprobability that a distribution λ is chosen as the input distribution. By observing
an output y of A, the attacker updates his belief on the input distribution. We
denote by p(λ|y) the posterior probability of λ being chosen, given an output y.
For two distributions λ0 , λ1 , the Bayes factor K(λ0 , λ1 , y) is defined as theratio of the two posteriors divided by that of the two priors: K(λ0 , λ1 , y) =p(λ0 |y)  p(λ0 )p(λ1 |y) p(λ1 ) . If the Bayes factor is far from 1 the attacker significantly updates
his belief on the distribution by observing a perturbed output y of A.
Assume that A provides (ε, 0)-DistP. By Bayes’ theorem, we obtain:#p(λ0 |y) p(λ1 )A (λ0 )[y]0)εK(λ0 , λ1 , y) = p(λ· p(λ0 ) = p(y|λp(y|λ1 ) = A# (λ1 )[y] ≤ e .
1 |y)Intuitively, if the attacker believes that λ0 is k times more likely than λ1 before
the observation, then he believes that λ0 is k · eε times more likely than λ1 after
the observation. This means that for a small value of ε, DistP guarantees thatthe attacker does not gain information on the distribution by observing y.
In the case of XDistP, the Bayes factor K(λ0 , λ1 , y) is bounded above byeεd(λ0 ,λ1 ) . Hence the attacker gains more information for a larger distance d(λ0 , λ1 ).

8

Y. Kawamoto et al.

Table 1: Summary of basic properties of DistP.
Sequential composition

Ab is (εb , δb )-DistP⇒ A1 A0 is (ε0 + ε1 , (δ0 + δ1 ) · |Φ|)-DistP
Sequential composition •Ab is (εb , δb )-DistP⇒ A1 • A0 is (ε0 + ε1 , δ0 + δ1 )-DistP
Post-processing
A0 is (ε, δ)-DistP ⇒ A1 ◦ A0 is (ε, δ)-DistP
Pre-processing (by c-stable T ) A is (ε, δ)-DistP ⇒ A ◦ T is (c ε, δ)-DistP

3.4

Privacy Guarantee for Attackers with Close Beliefs

In the previous sections, we assume that we know the distance between two
actual input distributions, and can determine the amount of noise required for
distribution obfuscation. However, an attacker may have different beliefs on the
distributions that are closer to the actual ones, e.g., more accurate distributions
obtained by more observations and specific situations (e.g., daytime/nighttime).
To see this, for each λ ∈ DX , let λ̃ be an attacker’s belief on λ. We say thatan attacker has (c, d )-close beliefs if each distribution λ satisfies d (λ, λ̃) ≤ c.
Then extended distribution privacy in the presence of an attacker is given by:
Proposition 1 (XDistP with close beliefs) Let A : X → DY provide (ε, d , 0)XDistP w.r.t. some Ψ ⊆ X × X . If an attacker has (c, d )-close beliefs, then forall (λ0 , λ1 ) ∈ Ψ and all R ⊆ Y, we have A# (λ˜0 )[R] ≤ eε(d(λ0 ,λ1 )+2c) · A# (λ˜1 )[R].
When the attacker’s beliefs are closer to ours, then c is smaller, hence astronger distribution privacy is guaranteed. See Appendix B.2 for DistP. Notethat assuming some attacker’s beliefs are inevitable also in many previous studies, e.g., when we want to protect the privacy of correlated data [18–20].
3.5

Difference from the Histogram Privacy

Finally, we present a brief remark on the difference between DistP and the differential privacy of histogram publication (e.g., [21]). Roughly, a histogram publication mechanism is a central mechanism that aims at hiding a single recordx ∈ X and outputs an obfuscated histogram, e.g., a distribution µ ∈ DY, whereasa DistP mechanism is a local mechanism that aims at hiding an input distribution
λ ∈ DX and outputs a single perturbed value y ∈ Y.
Note that neither of these implies the other. The ε-DP of a histogram publication mechanism means that for any two adjacent inputs x, x0 ∈ X and anyp(µ|x)
εhistogram µ ∈ DY, p(µ|x0 ) ≤ e . However, this does not derive ε-DistP, i.e., forp(y|λ)
εany adjacent input distributions λ, λ0 ∈ DX and any output y ∈ Y, p(y|λ0) ≤ e .

4

Basic Properties of Distribution Privacy

In Table 1, we show basic properties of DistP.(See Appendices B.4 and B.5 forthe details.)

Local Obfuscation Mechanisms for Hiding Probability Distributions

9

The composition A1 A0 means that an identical input x is given to two DistP
mechanisms A0 and A1 , whereas the composition A1 •A0 means that independent
inputs xb are provided to mechanisms Ab [22]. The compositionality can beused to quantify the attribute privacy against an attacker who obtains multiple
released data each obfuscated for the purpose of protecting a different attribute.
For example, let Ψ = {(λmale , λfemale ), (λhome , λout )}, and A0 (resp. A1 ) bea mechanism providing ε0 -DistP (resp. ε1 -DistP) w.r.t. Ψ . When A0 (resp. A1 )obfuscates a location x0 for the sake of protecting male/female (resp. home/out),
then both male/female and home/out are protected with (ε0 + ε1 )-DistP.
As for pre-processing, the stability notion is different from that for DP:
Definition 10 (Stability). Let c ∈ N>0 , Ψ ⊆ DX × DX , and W be a metricover DX . A transformation T : DX → DX is (c, Ψ )-stable if for any (λ0 , λ1 ) ∈ Ψ ,T (λ0 ) can be reached 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 ).
We present relationships among privacy notions in Appendices B.3 and B.7
An important property is that when the relation Ψ ⊆ DX × DX includes pairs of
point distributions (i.e., distributions having single points with probability 1),
DistP (resp. XDistP) implies DP (resp. XDP). In contrast, if Ψ does not include
pairs of point distributions, DistP (resp. XDistP) may not imply DP (resp. XDP),
as in Section 6.

5

Distribution Obfuscation by Point Obfuscation

In this section we present how the point obfuscation mechanisms (including DP
and XDP mechanisms) contribute to the obfuscation of probability distributions.
(See Appendix B.1 for the proofs.)
5.1

Distribution Obfuscation by DP Mechanisms

We first show every DP mechanism provides DistP. (See Definition 7 for Φ# .)Theorem 1 ((ε, δ)-DP ⇒ (ε, δ · |Φ|)-DistP) Let Φ ⊆ X × X . If A : X → DY
provides (ε, δ)-DP w.r.t. Φ, then it provides (ε, δ · |Φ|)-DistP w.r.t. Φ# .
This means that the mechanism A makes any pair (λ0 , λ1 ) ∈ Φ# indistinguishable up to the threshold ε and with exceptions δ · |Φ|. Intuitively, when λ0
and λ1 are adjacent w.r.t. the relation Φ# , we can construct λ1 from λ0 only bymoving mass from λ0 [x0 ] to λ1 [x1 ] where (x0 , x1 ) ∈ Φ (i.e., x0 is adjacent to x1 ).
Example 2 (Randomized response). By Theorem 1, the (ε, 0)-DP randomized
response [14] and RAPPOR [4] provide (ε, 0)-DistP. When we use these mechanisms, the estimation of the input distribution is harder for a smaller ε. However,these DP mechanisms tend to have small utility, because they add much noise
to hide not only the input distributions, but everything about inputs.

10

5.2

Y. Kawamoto et al.

Distribution Obfuscation by XDP Mechanisms

Compared to DP mechanisms, XDP mechanisms are known to provide better
utility. Alvim et al. [23] show the planar Laplace mechanism [3] adds less noise
than the randomized response, since XDP hides only closer locations. However,
we show XDP mechanisms still need to add much noise proportionally to the ∞Wasserstein distance between the distributions we want make indistinguishable.
The ∞-Wasserstein distance W∞,d as Utility Distance We first observe
how much ε0 is sufficient for an ε0 -XDP mechanism (e.g., the Laplace mechanism)to make two distribution λ0 and λ1 indistinguishable in terms of ε-DistP.
Suppose that λ0 and λ1 are point distributions such that λ0 [x0 ] = λ1 [x1 ] = 1
for some x0 , x1 ∈ X . Then an ε0 -XDP mechanism A satisfies:
D∞ (A# (λ0 ) k A# (λ1 )) = D∞ (A(x0 ) k A(x1 )) ≤ ε0 d (x0 , x1 ).
In order for A to provide ε-DistP, ε0 should be defined as d(x0ε,x1 ) . That is, thenoise added by A should be proportional to the distance between x0 and x1 .
To extend this to arbitrary distributions, we need to define a utility metricbetween distributions. A natural possible definition would be the largest distance
between values of λ0 and λ1 , i.e., the diameter over the supports defined by:diam(λ0 , λ1 ) =max

x0 ∈supp(λ0 ),x1 ∈supp(λ1 )d (x0 , x1 ).

However, when there is an outlier in λ0 or λ1 that is far from other values in the
supports, then the diameter diam(λ0 , λ1 ) is large. Hence the mechanisms thatadd noise proportionally to the diameter would lose utility too much.
To have better utility, we employ the ∞-Wasserstein metric W∞,d . The idea
is that given two distributions λ0 and λ1 over X , we consider the cost of atransportation of weights from λ0 to λ1 . The transportation is formalized as acoupling γ of λ0 and λ1 (see Definition 5), and the cost of the largest move is∆supp(γ),d =max
d (x0 , x1 ), i.e., the sensitivity w.r.t. the adjacency rela(x0 ,x1 )∈supp(γ)

tion supp(γ) ⊆ X × X (Definition 3). The minimum cost of the largest move is
given by the ∞-Wasserstein metric: W∞,d (λ0 , λ1 ) =min ∆supp(γ),d .
γ∈cp(λ0 ,λ1 )XDP implies XDistP We show every XDP mechanism provides XDistP with themetric W∞,d . To formalize this, we define a lifted relation Φ#
W∞ as the maximum#
relation over DX s.t. for any (λ0 , λ1 ) ∈ ΦW∞ , there is a coupling γ ∈ cp(λ0 , λ1 )#satisfying supp(γ) ⊆ Φ and γ ∈ Γ∞,d (λ0 , λ1 ). Then Φ#
W∞ ⊆ Φ holds.
Theorem 2 ((ε, d , δ)-XDP⇒(ε, W∞,d , δ·|Φ|)-XDistP) If A : X → DY provides(ε, d , δ)-XDP w.r.t. Φ ⊆ X × X , it provides (ε, W∞,d , δ·|Φ|)-XDistP w.r.t. Φ#
W∞ .

Local Obfuscation Mechanisms for Hiding Probability Distributions

11

tp
Algorithm 1 Tupling mechanism Qk,ν,A

Input: x: input, k: #dummies, ν: distribution of dummies, A: randomized algorithm
Output: y = (r1 , . . . , ri , s, ri+1 , . . . , rk ): the output value of the tupling mechanism$s ← A(x) ; // Draw an obfuscated value s of an input x$

r1 , r2 , . . . , rk ← ν ; // Draw k dummies from a given distribution ν$

i ← {1, 2, . . . , k + 1} ; // Draw i to decide the order of the outputs
return (r1 , . . . , ri , s, ri+1 , . . . , rk ) ;By Theorem 2, when δ > 0, the noise required for obfuscation is proportional to |Φ|, which is at most the domain size squared |X |2 . This implies thatfor a larger domain X , the Gaussian mechanism is not suited for distribution
obfuscation. We will demonstrate this by experiments in Section 7.4.
In contrast, the Laplace/exponential mechanisms provide (ε, W∞,d , 0)-DistP.
Since W∞,d (λ0 , λ1 ) ≤ diam(λ0 , λ1 ), the noise added proportionally to W∞,d canbe smaller than diam. This implies that obfuscating a distribution requires lessnoise than obfuscating a set of data. However, the required noise can still bevery large when we want to make two distant distributions indistinguishable.

6

Distribution Obfuscation by Random Dummies

In this section we introduce a local mechanism called a tupling mechanism to
improve the tradeoff between DistP and utility, as motivated in Section 1.
6.1

Tupling Mechanism

We first define the tupling mechanism as a local mechanism that obfuscates agiven input x by using a point perturbation mechanism A (not necessarily interms of DP or XDP), and that also adds k random dummies r1 , r2 , . . . , rk to
the output to obfuscate the input distribution (Algorithm 1). The probabilitytptpthat given an input x, the mechanism Qk,ν,A
outputs ȳ is given by Qk,ν,A(x)[ȳ].
6.2

Privacy of the Tupling Mechanism

Next we show that the tupling mechanism provides DistP w.r.t. the followingclass of distributions. Given β, η ∈ [0, 1] and A : X → DY, we define Λβ,η,A by: $Λβ,η,A = λ ∈ DX | Pr y ← Y : A# (λ)[y] ≤ β ≥ 1 − η .
For instance, a distribution λ satisfying maxx λ[x] ≤ β belongs to Λβ,0,A . (See
Proposition 12 in Appendix B.8.)
Theorem 3 (DistP of the tupling mechanism) Let k ∈ N>0 , ν be the unik
form distribution over Y, A : X → DY, and β, η ∈ [0, 1]. Given an 0 < α < |Y|,12

Y. Kawamoto et al.
2− 2αlet εα = ln k+(α+β)·|Y|and δα = 2e kβ2 + η. Then the (k, ν, A)-tupling mechak−α·|Y|nism provides (εα , δα )-DistP w.r.t. Λ2β,η,A .
This claim states that just adding random dummies achieves DistP without
any assumption on A (e.g., A does not have to provide DP). For a smaller range
size |Y| and a larger number k of dummies, we obtain a stronger DistP.
tp
Note that the distributions protected by Qk,ν,Abelong to the set Λβ,η,A .
– When β = 1, Λβ,η,A is the set of all distributions (i.e., Λ1,η,A = DX ) while
εα and δα tend to be large.
– For a smaller β, the set Λβ,η,A is smaller while εα and δα are smaller; that is,
the mechanism provides a stronger DistP for a smaller set of distributions.
– If A provides εA -DP, Λβ,η,A goes to DX for εA → 0. More generally, Λβ,η,Ais larger when the maximum output probability maxy A# (λ)[y] is smaller.
In practice, even when εA is relatively large, a small number of dummies enables
us to provide a strong DistP, as shown by experiments in Section 7.
We note that Theorem 3 may not imply DP of the tupling mechanism, depending on A. For example, suppose that A is the identity function. For small εαand δα , we have β  1, hence no point distribution λ (where λ[x] = 1 for some x)
belongs to Λβ,η,A , namely, the tupling mechanism does not provide (εα , δα )-DP.

6.3

Service Quality Loss and Cost of the Tupling Mechanism

When a mechanism outputs a value y closer to the original input x, she obtains alarger utility, or equivalently, a smaller service quality loss d (x, y). For example,
in an LBS (location based service), if a user located at x submits an obfuscatedlocation y, the LBS provider returns the shops near y, hence the service qualitydefloss can be expressed as the Euclidean distance d (x, y) = kx − yk.
Since each output of the tupling mechanism consists of k + 1 elements, thequality loss of submitting a tuple ȳ = (y1 , y2 , . . . , yk+1 ) amounts to d (x, ȳ):=minid (x, yi ). Then the expected quality loss of the mechanism is defined as follows.
Definition 11 (Expected quality loss of the tupling mechanism). For atp
λ ∈ DX and a metric d : X × Y → R, the expected quality loss of Qk,ν,A
is:
 P
P
tp
tp
L Qk,ν,A= x∈X ȳ∈Y k+1 λ[x] Qk,ν,A(x)[ȳ] mini d (x, yi ).
For a larger number k of random dummies, mini d (x, yi ) is smaller on avtp
erage, hence L Qk,ν,A
is also smaller. Furthermore, thanks to the distribution
obfuscation by random dummies, we can instead reduce the perturbation noise
added to the actual input x to obtain the same level of DistP. Therefore, theservice quality is much higher than existing mechanisms, as shown in Section 7.

Local Obfuscation Mechanisms for Hiding Probability Distributions
δ = 0.001
δ = 0.010
δ = 0.100

0.1

0.2

0.012

0.08

0.15

0.15

δ = 0.001
δ = 0.010
δ = 0.100

0.12ε-DistP

ε-DistP

0.2

ε-DistPδ = 0.001
δ = 0.010
δ = 0.100

0.25

Expected loss

0.3

0.3

0.25

0.01

0.008

0.06

0.006

0.1

0.1

0.05

0.05

0.02

0.002

0

0

0

0

4

8

12

Number of dummies

0.04

1

4

16

64

256

1024

4096

εA of restricted Laplace noise

0.01

13

0.004

0.02

0.03

0.04

Radius r of restricted Laplace noiseradius = 0.040
radius = 0.030
radius = 0.020
radius = 0.010
1

4

16

64

256

1024

4096

εA of restricted Laplace noise(a) #dummies and (b) εA of (εA , 0.020)- (c) A radius r of (d) εA of (εA , r)- RL
ε-DistP (when us- RL mechanism and (100, r)-RL
mech- mechanism and theing (100, 0.020)-RL ε-DistP (with 10 anism and ε-DistP expected loss (with 5
mechanism).
dummies).
(with 10 dummies). dummies).
tpFig. 2: Empirical DistP and quality loss of Qk,ν,A
for the attribute male/female.

6.4

Improving the Worst-Case Quality Losstp
As a point obfuscation mechanism A used in the tupling mechanism Qk,ν,A,
we define the restricted Laplace (RL) mechanism below. Intuitively, (εA , r)-RL
mechanism adds εA -XDP Laplace noise only within a radius r of the original location x. This ensures that the worst-case quality loss of the tupling mechanisms
is bounded above by the radius r, whereas the standard Laplace mechanism
reports a location y that is arbitrarily distant from x with a small probability.

Definition 12 (RL mechanism). Let Yx,r = {y 0 ∈ Y | d (x, y 0 ) ≤ r}. We
define (εA , r)-restricted Laplace (RL) mechanism as the A : X → DY defined by:−εd(x,y)A(x)[y] = P e e−εd(x,y0 ) if y ∈ Yx,r , and A(x)[y] = 0 otherwise.
y 0 ∈Yx,rSince the support of A is limited to Yx,r , A provides better service quality
tp
but does not provide DP. Nevertheless, as shown in Theorem 3, Qk,ν,AprovidesDistP, due to dummies in Y \ Yx,r . This implies that DistP is a relaxation of
DP that guarantees the privacy of attributes while achieving higher utility by
weakening the DP protection of point data. In other words, DistP mechanisms
are useful when users want both to keep high utility and to protect the attributeprivacy more strongly than what a DP mechanism can guarantee (e.g., whenusers do not mind revealing their actual locations outside home, but want to hidefrom robbers the fact that they are outside home, as motivated in Section 1).

7

Application to Attribute Privacy in LBSs

In this section we apply local mechanisms to the protection of the attribute privacy in location based services (LBSs) where each user submits her own location
x to an LBS provider to obtain information relevant to x (e.g., shops near x).
7.1

Experimental Setup

We perform experiments on location privacy in Manhattan by using the Foursquaredataset (Global-scale Check-in Dataset) [24]. We first divide Manhattan into

14

Y. Kawamoto et al.

11 × 10 regions with 1.0km intervals. To provide more useful information tousers in crowded regions, we further re-divide these regions to 276 regions byrecursively partitioning each crowded region into four until each resulting region
has roughly similar population density.4 Let Y be the set of those 276 regions,and X be the set of the 228 regions inside the central 10km × 9km area in Y.
tp
As an obfuscation mechanism Q, we use the tupling mechanism Qk,ν,A
that
uses an (εA , r)-RL mechanism A and the uniform distribution ν over Y to generate dummy locations. Note that ν is close to the population density distribution
over Y, because each region in Y is constructed to have roughly similar population density. In the definitions of the RL mechanism and the quality loss, we
use the Euclidean distance k · k between the central points of the regions.
In the experiments, we measure the privacy of user attributes, formalized
as DistP. For example, let us consider the attribute male/female. For each t ∈{male, female}, let λt ∈ DX be the prior distribution of the location of the users
having the attribute t. Then, λmale (resp. λfemale ) represents an attacker’s belief
on the location of the male (resp. female) users. We define these as the empirical
distributions that the attacker can calculate from the above Foursquare dataset.

7.2

Evaluation of the Tupling Mechanism

Distribution privacy We demonstrate by experiments that the male users
cannot be recognized as which of male or female in terms of DistP. In Fig. 2,
tp
we show the experimental results on the DistP of the tupling mechanism Qk,ν,A.
For a larger number k of dummy locations, we have a stronger DistP (Fig. 2a).
For a larger εA , (εA , 0.020)-RL mechanism A adds less noise, hence the tuplingmechanism provides a weaker DistP (Fig. 2b)5 . For a larger radius r, the RL
mechanism A spreads the original distribution λmale and thus provides a strong
DistP (Fig. 2c). We also show the relationship between k and DistP in the eastern/western Tokyo and London, which have different levels of privacy (Fig. 3).
These results imply that if we add more dummies, we can decrease the noiselevel/radius of A to have better utility, while keeping the same level ε of DistP.
Conversely, if A adds more noise, we can decrease the number k of dummies.

Expected quality loss In Fig. 2d, we show the experimental results on the
expected quality loss of the tupling mechanism. For a larger εA , A adds less noise,hence the loss is smaller. We confirm that for more dummy data, the expected
quality loss is smaller. Unlike the planar Laplace mechanism (PL), A ensuresthat the worst quality loss is bounded above by the radius r. Furthermore, for asmaller radius r, the expected loss is also smaller as shown in Fig. 2d.
4This partition may be useful to achieve smaller values (ε, δ) of DistP, because β tends
to be smaller when the population density is closer to the uniform distribution.
5
In Fig. 2b, for εA → 0, ε does not converge to 0, since the radius r = 0.020 of RL
does not cover the whole Y. However, if r ≥ maxx,y kx − yk, ε converges to 0.

Local Obfuscation Mechanisms for Hiding Probability Distributions
0.9

0.5
0.4
0.3
0.2

PG
RR
PL
TM

0.035
0.03

Expected loss

0.6

δ = 0.001
δ = 0.010
δ = 0.100
0.8

Attack success rate

0.7

(ε, 0.001)-DistP

0.04

1

Manhattan
Tokyo (east)
Tokyo (west)
London

0.8

0.6

0.4

15

0.025
0.02
0.015
0.01

0.2

0.005

0.1
0

0

0
4

8

12

0.5

1

Number of dummies

1.5

2

ε-DistP

0.06

0.08

0.1

0.12

0.14

0.16

ε-DistP

Fig. 3: k and DistP for Fig. 4: DistP and ASR Fig. 5: (ε, 0.001)-DistP and exmale/female in differ- of the tupling (k = 10, pected loss for male/female andent cities.
r = 0.020).
TM using k = 10, r = 0.020.

7.3

Appropriate Parameters

We define the attack success rate (ASR) as the ratio that the attacker succeeds
to infer a user has an attribute when she does actually. We use an inference
algorithm based on the Bayes decision rule [25] to minimize the identification
error probability when the estimated posterior probability is accurate [25].
In Fig. 4, we show the relationships between DistP and ASR in Manhattan
for the attribute home, meaning the users located at their home. In theory,
ASR = 0.5 represents the attacker learns nothing about the attribute, whereas
the empirical ASR in our experiments fluctuates around 0.5. This seems to becaused by the fact that the dataset and the number of locations are finite. From
Fig. 4, we conclude that ε = 1 is an appropriate parameter for (ε, 0.001)-DistPto achieve ASR = 0.5 in our setting, and we confirm this for other attributes.
However, we note that this is an empirical criterion possibly depending on our
setting, and the choice of ε for DistP can be as controversial as that for DP andshould also be investigated using approaches for DP (e.g., [26]) in future work.
In Appendices A.1, A.2, and A.3, we show that different levels of DistP
are achieved for different attributes in different cities. In particular, we present
appropriate parameters for the tupling mechanism for various attributes in acouple of cities.
7.4

Comparison of Obfuscation Mechanisms

We demonstrate that the tupling mechanism (TM) outperforms the popularmechanisms: the randomized response (RR), the planar Laplace (PL), and theplanar Gaussian (PG). In Fig. 5 we compare these concerning the relationshipbetween ε-DistP and expected quality loss. Since PG always has some δ, it provides a weaker DistP than PL for the same quality loss. We also confirm that
PL has smaller loss than RR, since it adds noise proportionally to the distance.
Comparison using other attributes can be found in Appendix A.1.
Finally, we briefly discuss the computational cost of the tupling mechanism
tp
Qk,ν,A, compared to PL. In the implementation, for a larger domain X , PLdeals with a larger size |X | × |Y| of the mechanism’s matrix, since it outputs

16

Y. Kawamoto et al.

each region with a non-zero probability. In contrast, since the RL mechanism A
tp
used in Qk,ν,Amaps each location x to a region within a radius r of x, the sizeof A’s matrix is |X | × |Yx,r |, requiring much smaller memory space than PL.
Furthermore, the users of TM can simply ignore the responses to dummy
queries, whereas the users of PL need to select relevant POIs (point of interests)
from a large radius of x, which could cost computationally for many POIs.
Therefore, TM is more suited to be used in mobile environments than PL.

8

Related Work

Differential privacy. Since the seminal work of Dwork [1] on DP, a numberof its variants have been studied to provide different privacy guarantees; e.g., f divergence privacy [27], d-privacy [15], Pufferfish privacy [19], local DP [2], andutility-optimized local DP [28]. All of these are intended to protect the input
data rather than the input distributions. Note that distributional privacy [29] isdifferent from DistP and does not aim at protecting the privacy of distributions.
To our knowledge, this is the first work that investigates the differential privacy of probability distributions lying behind the input. However, a few studies
have proposed related notions. Jelasity et al. [30] propose distributional differential privacy w.r.t. parameters θ and θ0 of two distributions, which aims at protecting the privacy of the distribution parameters but is defined in a Bayesianstyle (unlike DP and DistP) to satisfy that for any output sequence y, p(θ|y) ≤eε p(θ0 |y). After a preliminary version of this paper appeared in arXiv [31], a
notion generalizing DistP, called profile based privacy, is proposed in [32].
Some studies are technically related to our work. Song et al. [20] propose theWasserstein mechanism to provide Pufferfish privacy, which protects correlated
inputs. Fernandes et al. [33] introduce Earth mover’s privacy, which is technicallydifferent from DistP in that their mechanism obfuscates a vector (a bag-of-words)
instead of a distribution, and perturbs each element of the vector. Sei et al. [34]propose a variant of the randomized response to protect individual data andprovide high utility of database. However, we emphasize again that our work
differs from these studies in that we aim at protecting input distributions.
Location privacy. Location privacy has been widely studied in the literature,and its survey can be found in [35]. A number of location obfuscation methods
have been proposed so far, and they can be broadly divided into the following
four types: perturbation (adding noise) [36, 3, 5], location generalization (merging regions) [37, 38], and location hiding (deleting) [37, 39], and adding dummy
locations [40–42]. Location obfuscation based on DP (or its variant) have also
been widely studied, and they can be categorized into the ones in the centralized model [43, 44] and the ones in the local model [3, 5]. However, these methods
aim at protecting locations, and neither at protecting users’ attributes (e.g., age,gender) nor activities (e.g., working, shopping) in a DP manner. Despite the factthat users’ attributes and activities can be inferred from their locations [6–8],
to our knowledge, no studies have proposed obfuscation mechanisms to provide
rigorous DP guarantee for such attributes and activities.

Local Obfuscation Mechanisms for Hiding Probability Distributions

9

17

Conclusion

We have proposed a formal model for the privacy of probability distributions andintroduced the notion of distribution privacy (DistP). Then we have shown thatexisting local mechanisms deteriorate the utility by adding too much noise toprovide DistP. To improve the tradeoff between DistP and utility, we have introduced the tupling mechanism and applied it to the protection of user attributes
in LBSs. Then we have demonstrated that the tupling mechanism outperforms
popular local mechanisms in terms of attribute obfuscation and service quality.
As future work, we will improve the theoretical bound on ε for the tuplingmechanism. We also plan to design optimal mechanisms that minimize the quality loss and computational costs, while providing DistP, in various applications.
Acknowledgment We thank the reviewers, Catuscia Palamidessi, Gilles Barthe,and Frank D. Valencia for their helpful comments on preliminary drafts.

References
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 and statisticalminimax rates,” in Proc. FOCS, 2013, pp. 429–438.
3. M. E. Andrés, N. E. Bordenabe, K. Chatzikokolakis, and C. Palamidessi, “Geoindistinguishability: differential privacy for location-based systems,” in Proc. CCS.
ACM, 2013, pp. 901–914.
4. Úlfar Erlingsson, V. Pihur, and A. Korolova, “RAPPOR: Randomized aggregatableprivacy-preserving ordinal response,” in Proc. CCS, 2014, pp. 1054–1067.
5. N. E. Bordenabe, K. Chatzikokolakis, and C. Palamidessi, “Optimal geoindistinguishable mechanisms for location privacy,” in Proc. CCS, 2014, pp. 251–
262.
6. L. Liao, D. Fox, and henry Kautz, “Extracting places and activities from GPS
traces using hierarchical conditional random fields,” Int. J. Robotics Res., vol. 1,
no. 26, pp. 119–134, 2007.
7. V. W. Zheng, Y. Zheng, and Q. Yang, “Joint learning user’s activities and profiles
from GPS data,” in Proc. LBSN, 2009, pp. 17–20.
8. Y. Matsuo, N. Okazaki, K. Izumi, Y. Nakamura, T. Nishimura, and K. Hasida,“Inferring long-term user properties based on users’ location history,” in Proc.
IJCAI, 2007, pp. 2159–2165.
9. 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.
10. J. Otterbacher, “Inferring gender of movie reviewers: Exploiting writing style, content and metadata,” in Proc. CIKM, 2010, pp. 369–378.
11. U. Weinsberg, S. Bhagat, S. Ioannidis, and N. Taft, “BlurMe: Inferring and obfuscating user gender based on ratings,” in Proc. RecSys, 2012, pp. 195–202.
12. N. Z. Gong and B. Liu, “Attribute inference attacks in online social networks,”
ACM Trans. Privacy and Security, vol. 21, no. 1, pp. 3:1–3:30, 2018.
13. A. Mislove, B. Viswanath, P. K. Gummadi, and P. Druschel, “You are who you
know: inferring user profiles in online social networks,” in Proc. WSDM, 2010, pp.
251–260.

18

Y. Kawamoto et al.

14. P. Kairouz, K. Bonawitz, and D. Ramage, “Discrete distribution estimation underlocal privacy,” in Proc. ICML, 2016, pp. 2436–2444.
15. K. Chatzikokolakis, M. E. Andrés, N. E. Bordenabe, and C. Palamidessi, “Broadening the scope of Differential Privacy using metrics,” in Proc. PETS, 2013, pp.
82–102.
16. L. Vaserstein, “Markovian processes on countable space product describing large
systems of automata.” Probl. Peredachi Inf., vol. 5, no. 3, pp. 64–72, 1969.
17. C. Dwork, F. Mcsherry, K. Nissim, and A. Smith, “Calibrating noise to sensitivity
in private data analysis,” in Proc. TCC, 2006, pp. 265–284.
18. D. Kifer and A. Machanavajjhala, “No free lunch in data privacy,” in Proc. SIGMOD, 2011, pp. 193–204.
19. ——, “A rigorous and customizable framework for privacy,” in Proc. PODS, 2012,
pp. 77–88.
20. S. Song, Y. Wang, and K. Chaudhuri, “Pufferfish privacy mechanisms for correlateddata,” in Proc. SIGMOD, 2017, pp. 1291–1306.
21. 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.
22. Y. Kawamoto, K. Chatzikokolakis, and C. Palamidessi, “On the compositionalityof quantitative information flow,” Log. Methods Comput. Sci., vol. 13, no. 3, 2017.
23. 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.
24. D. Yang, D. Zhang, and B. Qu, “Participatory cultural mapping based on collective
behavior data in location based social networks,” ACM Transactions on Intelligent
Systems and Technology, vol. 7, no. 3, pp. 30:1–30:23, 2015.
25. R. O. Duda, P. E. Hart, and D. G. Stork, Pattern Classification.
WileyInterscience, 2000.
26. J. Hsu, M. Gaboardi, A. Haeberlen, S. Khanna, A. Narayan, B. C. Pierce, and
A. Roth, “Differential privacy: An economic method for choosing epsilon,” in Proc.
CSF, 2014, pp. 398–410.
27. G. Barthe and F. Olmedo, “Beyond differential privacy: Composition theorems andrelational logic for f-divergences between probabilistic programs,” in Proc. ICALP,
ser. LNCS, vol. 7966, 2013, pp. 49–60.
28. T. Murakami and Y. Kawamoto, “Utility-optimized local differential privacy mechanisms for distribution estimation,” in Proc. USENIX Security, 2019, to appear.
29. A. Blum, K. Ligett, and A. Roth, “A learning theory approach to noninteractive
database privacy,” J. ACM, vol. 60, no. 2, pp. 12:1–12:25, 2013.
30. M. Jelasity and K. P. Birman, “Distributional differential privacy for large-scale
smart metering,” in Proc. IH&MMSec, 2014, pp. 141–146.
31. Y. Kawamoto and T. Murakami, “Local obfuscation mechanisms for hiding
probability distributions,” CoRR, vol. abs/1812.00939, 2018. [Online]. Available:
http://arxiv.org/abs/1812.00939
32. J. Geumlek and K. Chaudhuri, “Profile-based privacy for locally private computations,” CoRR, vol. abs/1903.09084, 2019.
33. N. Fernandes, M. Dras, and A. McIver, “Generalised differential privacy for text
document processing,” in Proc. POST, 2019, pp. 123–148.
34. Y. Sei and A. Ohsuga, “Differential private data collection and analysis based on
randomized multiple dummies for untrusted mobile crowdsensing,” IEEE Trans.
Inf. Forensics Secur., vol. 12, no. 4, pp. 926–939, 2017.

Local Obfuscation Mechanisms for Hiding Probability Distributions

19

35. K. Chatzikokolakis, E. ElSalamouny, C. Palamidessi, and P. Anna, “Methods forlocation privacy: A comparative overview,” Foundations and Trends R in Privacy
and Security, vol. 1, no. 4, pp. 199–257, 2017.
36. R. Shokri, G. Theodorakopoulos, C. Troncoso, J.-P. Hubaux, and J.-Y. L. Boudec,“Protecting location privacy: optimal strategy against localization attacks,” inProc. CCS. ACM, 2012, pp. 617–627.
37. R. Shokri, G. Theodorakopoulos, J.-Y. L. Boudec, and J.-P. Hubaux, “Quantifying
location privacy,” in Proc. S&P. IEEE, 2011, pp. 247–262.
38. M. Xue, P. Kalnis, and H. Pung, “Location diversity: Enhanced privacy protection
in location based services,” in Proc. LoCA. Springer, 2009, pp. 70–87.
39. B. Hoh, M. Gruteser, H. Xiong, and A. Alrabady, “Preserving privacy in gps traces
via uncertainty-aware path cloaking,” in Proc. CCS. ACM, 2007, pp. 161–171.
40. V. Bindschaedler and R. Shokri, “Synthesizing plausible privacy-preserving location traces,” in Proc. S&P, 2016, pp. 546–563.
41. R. Chow and P. Golle, “Faking contextual data for fun, profit, and privacy,” inProc. PES. ACM, 2009, pp. 105–108.
42. H. Kido, Y. Yanagisawa, and T. Satoh, “Protection of location privacy using dummies for location-based services,” in Proc. ICDE Workshops, 2005, p. 1248.
43. A. Machanavajjhala, D. Kifer, J. M. Abowd, J. Gehrke, and L. Vilhuber, “Privacy:
Theory meets practice on the map,” in Proc. ICDE. IEEE, 2008, pp. 277–286.
44. S.-S. Ho and S. Ruan, “Differential privacy for location pattern mining,” in Proc.
SPRINGL. ACM, 2011, pp. 17–24.
45. Z. Cheng, J. Caverlee, K. Lee, and D. Z. Sui, “Exploring millions of footprints inlocation sharing services,” in Proc. ICWSM, 2011.
46. Please Rob Me - Raising Awareness about Over-sharing, http://pleaserobme.com/.
47. Y. Kawamoto and T. Murakami, “Local distribution obfuscation via probability
coupling,” in Proc. Allerton, 2019, to appear.
48. C. Dwork, G. N. Rothblum, and S. P. Vadhan, “Boosting and differential privacy,”in Proc. FOCS, 2010, pp. 51–60.

20

Y. Kawamoto et al.

A

Experimental Results

A.1

Experimental Comparison among Attributes in Manhattan

In this section we present the experimental results on more attributes of users
in the location data in Manhattan. We investigate the following four attributes:– social/less-social (Fig. 9) represent whether a user’s social status (definedin [45] as the number of followers divided by the number of followings) isgreater than 5 or not. In [9], the social status is regarded as a private attributethat can be leaked by the user’s behaviour and should be protected. We set
5 to be a threshold, because mobility patterns of people are substantiallydifferent when their social status is greater than 5 [45].
– workplace/non-workplace (Fig. 10) represent whether a user is at office ornot. This attribute can be sensitive when it implies users are unemployed.
– home/out (Fig. 11) represent whether a user is at home or not. This attributeshould be protected, for instance, from robbers [46].
– north/south (Fig. 12) represent whether a user’s home is located in the northern or southern Manhattan. This attribute needs to be protected, for instance, from stalkers. However, the residential area is highly correlated withvisited places, hence can be inferred by the current location relatively easily.
Note that these figures also show the results of KL-DistP, which is not definedin this paper but is introduced in [47].
Compared to the attribute of male/female (Fig. 2), the attributes home/out(Fig. 11) and north/south (Fig. 12) require more noise for distribution obfuscation. This is because the distances between the two distributions of users ofthese attributes are larger than that of λmale and λfemale . The histograms formale/female and for north/south are shown in Fig. 7 and Fig. 8 respectively.
We also show the comparison of different obfuscation mechanisms for various
attributes in Fig. 6.
A.2

Experimental Comparison among Time Periods in Manhattan

In this section we present the experimental results on different periods of time:
00h-05h, 06h-11h, 12h-17h, and 18h-23h in Manhattan in Figs. 13 to 16. It canbe seen that ε depends on a period of time. For example, hiding the attributemale/female and social/less-social requires more noise in 06h-11h. This might
be related to the fact that more social people tend to attend social events in themorning. On the other hand, the attribute home/out requires similar amount ofnoise in any period of time. This implies that residential areas are distant fromother areas in each city, and this fact does not change over time.
A.3

Experimental Comparison among Various Cities

In this section we compare the experimental results on five cities: Manhattan,
eastern Tokyo, western Tokyo, London, and Paris. In Table 3 we show examples

Local Obfuscation Mechanisms for Hiding Probability Distributions
0.04

PG
RR
PL
TM

0.035
0.03

Expected loss

0.03

Expected loss

0.04

PG
RR
PL
TM

0.035

0.025
0.02
0.015

21

0.025
0.02
0.015

0.01

0.01

0.005

0.005

0

0
0.06

0.08

0.1

0.12

0.14

0.16

0.22

0.24

0.26

0.28

ε-DistP

0.3

0.32

0.34

0.36

0.38

ε-DistP(a) Relationship between (ε, 0.001)-DistP (b) Relationship between (ε, 0.001)-DistPand expected loss for male/female.
and expected loss for social/less-social.
0.04

PG
RR
PL
TM

0.035
0.03

Expected loss

0.03

Expected loss

0.04

PG
RR
PL
TM

0.035

0.025
0.02
0.015

0.025
0.02
0.015

0.01

0.01

0.005

0.005

0

0
0.4

0.5

0.6

0.7

0.8

0.9

1

1

ε-DistP(c) Relationship between (ε, 0.001)-DistPand loss for workplace/non-workplace.

1.2

1.4

1.6

1.8

2

ε-DistP(d) Relationship between (ε, 0.001)-DistPand expected loss for home/out.

Fig. 6: Comparison of the randomized response (RR), the planar Laplace mechanism (PL), the planar Gaussian mechanism (PG), and the tupling mechanism
tp(TM) Qk,ν,Awith k = 10 dummies and a radius r = 0.020. The experiments are
performed for the location data in Manhattan.

of parameters that achieve the same levels of DistP in different cities. Moredetailed comparison among those cities is shown in Fig. 17 (male/female), Fig. 18(social/less-social), Fig. 19 (workplace/non-workplace), and Fig. 20 (home/out).
When we use the same parameters in the tupling mechanism, the levels ε of
DistP differ among those cities. In western Tokyo, for instance, the attributes
social/less-social and workplace/non-workplace are more difficult to hide. Thisimplies that areas for social events and workplace might be more separated fromthe other areas in western Tokyo. Since each attribute in each city may requiredifferent levels of noise for distribution obfuscation, the reference parameters(e.g., those shown in Table 3) would be useful to select appropriate parameters
for the tupling mechanism to protect the privacy of attributes in different cities.

A.4

Theoretical/Empirical Values of ε-DistPIn Table 2, we show the theoretical values of ε calculated by Theorem 3 forδ = 0.001, 0.01, 0.1. Compared to the experimental results, those theoreticalvalues can only give loose upper bounds on ε. This is because the concentration
inequality used to derive Theorem 3 give loose bounds.

22

Y. Kawamoto et al.

tp
Table 2: Theoretical/empirical ε-DistP of Qk,ν,A(k = 10, εA = 10, r = 0.020).

δ = 0.001 δ = 0.01 δ = 0.1
Theoretical bounds 2.170
1.625
1.140
Empirical values
0.04450 0.03534 0.02295

Table 3: The number k of dummies required for achieving DistP in different cities(MH = Manhattan, TKE = Tokyo (east), TKW = Tokyo (west), LD = London,
PR = Paris) when εA = 100 and r = 0.020. Note that the data of Paris formale/female are excluded because of the insufficient sample size.
MH TKE TKW LD PR
2
2
2
3

>20
3
2
5

5
10 —
>20
2
3
>20
1
2
>20 >20 4

40.8

40.8

40.79

40.79

40.78

40.78

40.78

40.77

40.77

40.77

40.77

40.76

40.76

40.76

40.76

40.75
40.74

40.75
40.74

Latitude

40.8
40.79

40.78

Latitude

40.8
40.79

LatitudeLatitude(0.25, 0.001)-DistP for male / female(0.50, 0.001)-DistP for social / less social(1.00, 0.001)-DistP for work / non-work(1.50, 0.001)-DistP for home / outside

40.75
40.74

40.75
40.74

40.73

40.73

40.73

40.73

40.72

40.72

40.72

40.72

40.71

40.71

40.71

40.7

40.7

40.7

-74.04-74.02-74-73.98-73.96

Longitude-73.94-73.92-74.04-74.02-74-73.98-73.96-73.94-73.92Longitude(e) The histogram of (f) The histogram oflocations of the male locations of the feusers in Manhattan. male users in Manhattan.

-74.0440.71
40.7-74.02-74-73.98-73.96

Longitude-73.94-73.92-74.04-74.02-74-73.98-73.96-73.94-73.92Longitude(a) The histogram (b) The histogramof locations of the of locations of theusers living in north- users living in southern Manhattan.
ern Manhattan.

Fig. 7: Histograms of user locations Fig. 8: Histograms of user locations
used in experiments. Darker colors rep- used in experiments. Darker colors represent larger population.
resent larger population.

Local Obfuscation Mechanisms for Hiding Probability Distributions
0.6

0.6

0.3

ε-DistP

0.3

0.4
0.3

0
4

8

0.01

0.25
0.2

0.2

0.1

0.1

0.05

0

0

12

0.012

0.15

0.2

0.1

δ = 0.001
δ = 0.010
δ = 0.100
KL-DistP

0.35

0.5

ε-DistP

ε-DistP

0.4

0.4

δ = 0.001
δ = 0.010
δ = 0.100
KL-DistP

0.7

Expected loss

δ = 0.001
δ = 0.010
δ = 0.100
KL-DistP

0.5

1

4

16

64

256

1024

4096

0.008
0.006
0.004

radius = 0.040
radius = 0.030
radius = 0.020
radius = 0.010

0.002
0
0.01

εA of restricted Laplace noise

Number of dummies

0.02

0.03

23

0.04

1

4

16

64

256

1024

4096

εA of restricted Laplace noise

Radius r of restricted Laplace noise(a)Relationship (b) Relationship be- (c) Relationship be- (d) Relationship bebetween ε-DistP and tween ε-DistP and tween ε-DistP and a tween the expected#dummies(when εA of (εA , 0.020)-RL radius r of (100, r)- loss and εA of (εA ,using (100, 0.020)- mechanism (with 10 RL mechanism (with r)-RL
mechanism
RL mechanism).
dummies).
10 dummies).
(with 5 dummies).

Fig. 9: Empirical DistP and loss for attribute social/less-social in Manhattan.
δ = 0.001
δ = 0.010
δ = 0.100
KL-DistP

1.4
1.2

δ = 0.001
δ = 0.010
δ = 0.100
KL-DistP

0.6
0.5

0.012
0.01

Expected loss

δ = 0.001
δ = 0.010
δ = 0.100
KL-DistP

1

0.8

0.6

0.4

ε-DistP

ε-DistP

ε-DistP

1
0.8
0.6

0.2

4

8

0.3
0.2

0.4

0

0.4

0.008
0.006
0.004

0.2

0.1

0.002

0

0

0

12

1

4

16

64

256

1024

4096

0.01

εA of restricted Laplace noise

Number of dummies

0.02

0.03

0.04

radius = 0.040
radius = 0.030
radius = 0.020
radius = 0.010
1

4

16

64

256

1024

4096

εA of restricted Laplace noise

Radius r of restricted Laplace noise(a)Relationship (b) Relationship be- (c) Relationship be- (d) Relationship bebetween ε-DistP and tween ε-DistP and tween ε-DistP and a tween the expected#dummies(when εA of (εA , 0.020)-RL radius r of (100, r)- loss and εA of (εA ,using (100, 0.020)- mechanism (with 10 RL mechanism (with r)-RL
mechanism
RL mechanism).
dummies).
10 dummies).
(with 5 dummies).

Fig. 10: Empirical DistP and loss for workplace/non-workplace in Manhattan.
1.8

1.4

δ = 0.001
δ = 0.010
δ = 0.100
KL-DistP

2.5

2

0.016

δ = 0.001
δ = 0.010
δ = 0.100
KL-DistP

1.2
1

0.014
0.012

Expected loss

δ = 0.001
δ = 0.010
δ = 0.100
KL-DistP

1.6

1
0.8

ε-DistP

ε-DistP

ε-DistP

1.2
1.5

0.8
0.6

1

0.6

0.4

0.01
0.008
0.006
0.004

0.4
0.5

0.2

0.2
0

0
4

8

12

1

4

16

64

256

1024

4096

0
0.01

εA of restricted Laplace noise

Number of dummies

radius = 0.040
radius = 0.030
radius = 0.020
radius = 0.010

0.002

0
0.02

0.03

0.04

1

4

16

64

256

1024

4096

εA of restricted Laplace noise

Radius r of restricted Laplace noise(a)Relationship (b) Relationship be- (c) Relationship be- (d) Relationship bebetween ε-DistP and tween ε-DistP and tween ε-DistP and a tween the expected#dummies(when εA of (εA , 0.020)-RL radius r of (100, r)- loss and εA of (εA ,using (100, 0.020)- mechanism (with 10 RL mechanism (with r)-RL
mechanism
RL mechanism).
dummies).
10 dummies).
(with 5 dummies).

Fig. 11: Empirical DistP and loss for the attribute home/out in Manhattan.
1.2

δ = 0.001
δ = 0.010
δ = 0.100
KL-DistP

1.6
1.4

0.9

δ = 0.001
δ = 0.010
δ = 0.100
KL-DistP1

0.014

δ = 0.001
δ = 0.010
δ = 0.100
KL-DistP

0.8
0.7

0.012

0.8
0.6

0.6

ε-DistP

1

ε-DistP

ε-DistP

0.8

Expected loss

1.2

0.6

0.4

0.5
0.4
0.3

0.01
0.008
0.006
0.004

0.4

0.2
0.2

0.2
0

0
4

8

Number of dummies

12

0
1

4

16

64

256

1024

εA of restricted Laplace noise

4096

radius = 0.040
radius = 0.030
radius = 0.020
radius = 0.010

0.002

0.1

0
0.01

0.02

0.03

Radius r of restricted Laplace noise

0.04

1

4

16

64

256

1024

4096

εA of restricted Laplace noise(a)Relationship (b) Relationship be- (c) Relationship be- (d) Relationship bebetween ε-DistP and tween ε-DistP and tween ε-DistP and a tween the expected#dummies(when εA of (εA , 0.020)-RL radius r of (100, r)- loss and εA of (εA ,using (100, 0.020)- mechanism (with 10 RL mechanism (with r)-RL
mechanism
RL mechanism).
10 dummies).
dummies).
(with 5 dummies).

Fig. 12: Empirical DistP and loss for the attribute north/south in Manhattan.

Y. Kawamoto et al.

0.5
0.4
0.3

0.35

00h-05h06h-11h12h-17h18h-23h0.8(ε, 0.001)-DistP

0.6(ε, 0.001)-DistP

100h-05h06h-11h12h-17h18h-23h0.700h-05h06h-11h12h-17h18h-23h

0.3

0.6

0.4

0.01

0.008

0.25

Expected loss

0.8

(ε, 0.001)-DistP

24

0.2
0.15

0.2

0
8

12

0
1

4

16

64

256

1024

4096

0
0.01

εA of restricted Laplace noise

Number of dummies

00h-05h06h-11h12h-17h18h-23h

0.002

0.05

0.1

4

0.004

0.1

0.2

0

0.006

0.02

0.03

0.04

1

4

16

64

256

1024

4096

εA of restricted Laplace noise

Radius r of restricted Laplace noise(a)Relationship (b) Relationship be- (c) Relationship be- (d) Relationship bebetween ε-DistP and tween ε-DistP and tween ε-DistP and a tween the expected#dummies(when εA of (εA , 0.020)-RL radius r of (100, r)- loss and εA of (εA ,using (100, 0.020)- mechanism (with 10 RL mechanism (with r)-RL
mechanism
RL
mechanism). dummies).
10 dummies).
(with 5 dummies).

Fig. 13: Empirical DistP and loss for male/female in different hours.

0.6
0.5
0.4
0.3

0.9

00h-05h06h-11h12h-17h18h-23h2.5(ε, 0.001)-DistP(ε, 0.001)-DistP

0.7

00h-05h06h-11h12h-17h18h-23h

0.8
0.7

2

1.5

1

0.2

0.01

0.008

Expected loss

00h-05h06h-11h12h-17h18h-23h0.8(ε, 0.001)-DistP

0.9

0.6
0.5
0.4
0.3
0.2

0.004

00h-05h06h-11h12h-17h18h-23h

0.002

0.5
0.1

0.006

0.1

0

0
4

8

12

0
1

4

16

64

256

1024

4096

0
0.01

εA of restricted Laplace noise

Number of dummies

0.02

0.03

0.04

1

4

16

64

256

1024

4096

εA of restricted Laplace noise

Radius r of restricted Laplace noise(a)Relationship (b) Relationship be- (c) Relationship be- (d) Relationship bebetween ε-DistP and tween ε-DistP and tween ε-DistP and a tween the expected#dummies(when εA of (εA , 0.020)-RL radius r of (100, r)- loss and εA of (εA ,using (100, 0.020)- mechanism (with 10 RL mechanism (with r)-RL
mechanism
RL mechanism).
dummies).
10 dummies).
(with 5 dummies).

Fig. 14: Empirical DistP and loss for social/less-social in different hours.

1
0.8
0.6

00h-05h06h-11h12h-17h18h-23h2.5

200h-05h06h-11h12h-17h18h-23h1(ε, 0.001)-DistP

1.2(ε, 0.001)-DistP(ε, 0.001)-DistP

1.4

1.5

1

0.01

0.8

0.008

Expected loss

00h-05h06h-11h12h-17h18h-23h

1.6

0.6

0.4

0.006

0.004

0.4
0.5

0.2

0.002

0

0

0

00h-05h06h-11h12h-17h18h-23h

0.2
0
4

8

12

1

4

16

64

256

1024

4096

0.01

εA of restricted Laplace noise

Number of dummies

0.02

0.03

0.04

1

4

16

64

256

1024

4096

εA of restricted Laplace noise

Radius r of restricted Laplace noise(a)Relationship (b) Relationship be- (c) Relationship be- (d) Relationship bebetween ε-DistP and tween ε-DistP and tween ε-DistP and a tween the expected#dummies(when εA of (εA , 0.020)-RL radius r of (100, r)- loss and εA of (εA ,using (100, 0.020)- mechanism (with 10 RL mechanism (with r)-RL
mechanism
RL mechanism).
dummies).
10 dummies).
(with 5 dummies).

Fig. 15: Empirical DistP and loss for workplace/non-workplace in different hours.

2

1.5

1

0.012
0.01

Expected loss

100h-05h06h-11h12h-17h18h-23h1.5(ε, 0.001)-DistP

1.5

200h-05h06h-11h12h-17h18h-23h2.5(ε, 0.001)-DistP(ε, 0.001)-DistP

300h-05h06h-11h12h-17h18h-23h

2

1

0.008
0.006
0.004

0.5

0.5
0.5

0
4

8

Number of dummies

1200h-05h06h-11h12h-17h18h-23h

0.002

0

0
1

4

16

64

256

1024

εA of restricted Laplace noise

4096

0
0.01

0.02

0.03

Radius r of restricted Laplace noise

0.04

1

4

16

64

256

1024

4096

εA of restricted Laplace noise(a)Relationship (b) Relationship be- (c) Relationship be- (d) Relationship bebetween ε-DistP and tween ε-DistP and tween ε-DistP and a tween the expected#dummies(when εA of (εA , 0.020)-RL radius r of (100, r)- loss and εA of (εA ,using (100, 0.020)- mechanism (with 10 RL mechanism (with r)-RL
mechanism
RL mechanism).
dummies).
10 dummies).
(with 5 dummies).

Fig. 16: Empirical DistP and loss for home/out in different hours.

Local Obfuscation Mechanisms for Hiding Probability Distributions

0.8(ε, 0.001)-DistP(ε, 0.001)-DistP

0.7
0.6
0.5
0.4
0.3
0.2

0.45

Manhattan
Tokyo (east)
Tokyo (west)
London1

Manhattan
Tokyo (east)
Tokyo (west)
London

0.4
0.35

0.6

0.4

0.01

0.008

Expected loss

Manhattan
Tokyo (east)
Tokyo (west)
London0.8(ε, 0.001)-DistP

0.9

0.3
0.25
0.2
0.15
0.1

0.2

0.1

0.006

0.004

Manhattan
Tokyo (east)
Tokyo (west)
London
Paris

0.002

0.05

0

0
4

8

12

0
1

4

16

64

256

1024

4096

0
0.01

εA of restricted Laplace noise

Number of dummies

25

0.02

0.03

0.04

1

4

16

64

256

1024

4096

εA of restricted Laplace noise

Radius r of restricted Laplace noise(a)Relationship (b) Relationship be- (c) Relationship be- (d) Relationship bebetween ε-DistP and tween ε-DistP and tween ε-DistP and a tween the expected#dummies(when εA of (εA , 0.020)-RL radius r of (100, r)- loss and εA of (εA ,using (100, 0.020)- mechanism (with 10 RL mechanism (with r)-RL
mechanism
RL mechanism).
dummies).
10 dummies).
(with 5 dummies).

Fig. 17: Empirical DistP and loss for male/female in different cities.

1
0.8
0.6

Manhattan
Tokyo (east)
Tokyo (west)
London
Paris

1.6
1.4
1.2
1
0.8
0.6

0.4

0.4

0.2

0.2

0
8

12

1

0.01

0.008

0.8
0.6
0.4

0
1

4

16

64

256

1024

4096

0.004

Manhattan
Tokyo (east)
Tokyo (west)
London
Paris

0
0.01

εA of restricted Laplace noise

Number of dummies

0.006

0.002

0.2

0
4

Manhattan
Tokyo (east)
Tokyo (west)
LondonParis

1.2

Expected loss

1.2

(ε, 0.001)-DistP(ε, 0.001)-DistP

1.4(ε, 0.001)-DistP

Manhattan
Tokyo (east)
Tokyo (west)
London
Paris

1.6

0.02

0.03

0.04

1

4

16

64

256

1024

4096

εA of restricted Laplace noise

Radius r of restricted Laplace noise(a)Relationship (b) Relationship be- (c) Relationship be- (d) Relationship bebetween ε-DistP and tween ε-DistP and tween ε-DistP and a tween the expected#dummies(when εA of (εA , 0.020)-RL radius r of (100, r)- loss and εA of (εA ,using (100, 0.020)- mechanism (with 10 RL mechanism (with r)-RL
mechanism
RL mechanism).
dummies).
10 dummies).
(with 5 dummies).

Fig. 18: Empirical DistP and loss for social/less-social in different cities.

1.5

1

0.5

1.5

0.012

0.01

Expected loss

1

2

Manhattan
Tokyo (east)
Tokyo (west)
LondonParis2(ε, 0.001)-DistP(ε, 0.001)-DistP

1.5

Manhattan
Tokyo (east)
Tokyo (west)
LondonParis

2.5(ε, 0.001)-DistP

Manhattan
Tokyo (east)
Tokyo (west)
London
Paris

2

1

0.008

0.006

0.004

Manhattan
Tokyo (east)
Tokyo (west)
London
Paris

0.5
0.5

0

0.002

0
4

8

12

0
1

4

16

64

256

1024

4096

0
0.01

εA of restricted Laplace noise

Number of dummies

0.02

0.03

0.04

1

4

16

64

256

1024

4096

εA of restricted Laplace noise

Radius r of restricted Laplace noise(a)Relationship (b) Relationship be- (c) Relationship be- (d) Relationship bebetween ε-DistP and tween ε-DistP and tween ε-DistP and a tween the expected#dummies(when εA of (εA , 0.020)-RL radius r of (100, r)- loss and εA of (εA ,using (100, 0.020)- mechanism (with 10 RL mechanism (with r)-RL
mechanism
RL mechanism).
dummies).
10 dummies).
(with 5 dummies).

Fig. 19: Empirical DistP and loss for workplace/non-workplace in different cities.

2
1.5

3
2.5
2
1.5

1

1

0.5

0.5

0.014

Manhattan
Tokyo (east)
Tokyo (west)
London
Paris

2.5

2

0.012

Expected loss

2.5

Manhattan
Tokyo (east)
Tokyo (west)
LondonParis

3.5(ε, 0.001)-DistP(ε, 0.001)-DistP

3(ε, 0.001)-DistP

Manhattan
Tokyo (east)
Tokyo (west)
London
Paris

3.5

1.5

1

0
4

8

Number of dummies

12

4

16

64

256

1024

εA of restricted Laplace noise

4096

Manhattan
Tokyo (east)
Tokyo (west)
London
Paris

0.002

0
1

0.006
0.004

0.5

0

0.01
0.008

0
0.01

0.02

0.03

Radius r of restricted Laplace noise

0.04

1

4

16

64

256

1024

4096

εA of restricted Laplace noise(a)Relationship (b) Relationship be- (c) Relationship be- (d) Relationship bebetween ε-DistP and tween ε-DistP and tween ε-DistP and a tween the expected#dummies(when εA of (εA , 0.020)-RL radius r of (100, r)- loss and εA of (εA ,using (100, 0.020)- mechanism (with 10 RL mechanism (with r)-RL
mechanism
RL mechanism).
dummies).
10 dummies).
(with 5 dummies).

Fig. 20: Empirical DistP and loss for home/out in different cities.

26

Y. Kawamoto et al.

B

Proofs of Technical Results

B.1

Distribution Obfuscation by Point Obfuscation

In this section we show the results on how point obfuscation mechanisms provide
distribution privacy.
Theorem 1 ((ε, δ)-DP ⇒ (ε, δ · |Φ|)-DistP) Let Φ ⊆ X × X . If A : X → DY
provides (ε, δ)-DP w.r.t. Φ, then it provides (ε, δ · |Φ|)-DistP w.r.t. Φ# .
Proof. Assume A provides (ε, δ)-DP w.r.t. Φ. Let δ 0 = δ · |Φ|, and (λ0 , λ1 ) ∈ Φ# .
By Definition 7, there is a coupling γ ∈ cp(λ0 , λ1 ) satisfying supp(γ) ⊆ Φ. By
Definition 5, we have:Pfor each x0 ∈ X , λ0 [x0 ] = x1 ∈X γ[x0 , x1 ](1)Pfor each x1 ∈ X , λ1 [x1 ] = x0 ∈X γ[x0 , x1 ].
(2)
Let R ⊆ Y such that A# (λ0 )[R] > δ 0 . We first show that A# (λ1 )[R] > 0
as follows. To derive a contradiction, we assume A# (λ1 )[R] = 0. Then for any
x1 ∈ supp(λ1 ), A(x1 )[R] = 0. Let Sx1 = {x0 ∈ X | (x0 , x1 ) ∈ Φ}. For any
x0 ∈ Sx1 , we have:A(x0 )[R] ≤ eε A(x1 )[R] + δ(by the (ε, δ)-DP of A w.r.t. Φ)≤δ(by A(x1 )[R] = 0)

Thus we obtain:X

A# (λ0 )[R] =λ0 [x0 ]A(x0 )[R]x0 ∈supp(λ0 )≤ |supp(λ0 )| · δ≤ |Φ| · δ=δ(by |supp(λ0 )| ≤ |supp(γ)| ≤ |Φ|)0This contradicts the definition of R. Hence A# (λ1 )[R] > 0.
Then we calculate the ratio of the probability that A# outputs an elementof R given input λ0 to that given input λ1 :A# (λ0 )[R] − δ 0
A# (λ1 )[R]P0x0 ∈X λ0 [x0 ] · A(x0 )[R] − δP=
x1 ∈X λ1 [x1 ] · A(x1 )[R]Pδ0(x0 ,x1 )∈supp(γ) γ[x0 , x1 ]A(x0 )[R] − |supp(γ)|
P=(by (1), (2))(x0 ,x1 )∈supp(γ) γ[x0 , x1 ]A(x1 )[R]≤δ0
γ[x0 , x1 ] · A(x0 )[R] − |supp(γ)|γ[x0 , x1 ] · A(x1 )[R]
(x0 ,x1 )∈supp(γ)

maxLocal Obfuscation Mechanisms for Hiding Probability Distributions≤

A(x0 )[R] − δ(x0 ,x1 )∈supp(γ) A(x1 )[R](by − γ[x0 ,xδ·|Φ|≤−δ )1 ]·|supp(γ)|

max≤ eε .

27(by (x0 , x1 ) ∈ supp(γ) ⊆ Φ and (ε, δ)-DP w.r.t. Φ)

Therefore A provides (ε, δ · |Φ|)-DistP w.r.t. Φ# .

tu

Theorem 2 ((ε, d , δ)-XDP⇒(ε, W∞,d , δ·|Φ|)-XDistP) If A : X → DY provides(ε, d , δ)-XDP w.r.t. Φ ⊆ X × X , it provides (ε, W∞,d , δ·|Φ|)-XDistP w.r.t. Φ#
W∞ .
Proof. Assume that A provides (ε, d , δ)-XDP w.r.t. Φ. Let (λ0 , λ1 ) ∈ Φ#
W∞ . Bydefinition, there exists a coupling γ ∈ cp(λ0 , λ1 ) that satisfies supp(γ) ⊆ Φand γ ∈ Γ∞,d (λ0 , λ1 ). Then γ minimizes the sensitivity ∆supp(γ) ; i.e., γ ∈argmin ∆supp(γ 0 ) .
γ 0 ∈cp(λ0 ,λ1 )0Let δ = δ · |Φ|. Let R ⊆ Y such that A# (λ0 )[R] > δ 0 . Analogously to theproof for Theorem 1, we obtain A# (λ1 )[R] > 0. Then it follows from supp(γ) ⊆ Φand (ε, d , δ)-XDP w.r.t. Φ that:A# (λ0 )[R] − δ 0
A# (λ1 )[R]≤max

A(x0 )[R] − δA(x1 )[R](x0 ,x1 )∈supp(γ)≤

maxeεd(x0 ,x1 )(x0 ,x1 )∈supp(γ)=eεW∞,d (λ0 ,λ1 ) .

(by γ ∈ Γ∞,d (λ0 , λ1 ))Therefore A provides (ε, W∞,d , δ 0 )-XDistP w.r.t. Φ#
W∞ .
B.2

t
u

Distribution Privacy with Attacker’s Close Beliefs

Next we show the propositions on distribution privacy with an attacker’s beliefs.
Proposition 1 (XDistP with close beliefs) Let A : X → DY provide (ε, d , 0)XDistP w.r.t. some Ψ ⊆ X × X . If an attacker has (c, d )-close beliefs, then forall (λ0 , λ1 ) ∈ Ψ and all R ⊆ Y, we have A# (λ˜0 )[R] ≤ eε(d(λ0 ,λ1 )+2c) · A# (λ˜1 )[R].
Proof. We obtain the proposition by:
A# (λ˜0 )[R] ≤ eεc · A# (λ0 )[R]≤ eε(d(λ0 ,λ1 )+c) · A# (λ1 )[R]≤ eε(d(λ0 ,λ1 )+2c) · A# (λ˜1 )[R](by d (λ0 , λ˜0 ) ≤ c)(by d (λ1 , λ˜1 ) ≤ c).
tu

Similarly, we say that the attacker has close beliefs w.r.t an adjacency relation
Ψ if for each (λ0 , λ1 ) ∈ Ψ , we have (λ˜0 , λ0 ) ∈ Ψ and (λ1 , λ˜1 ) ∈ Ψ . Then we obtain:

28

Y. Kawamoto et al.

Proposition 2 (DistP with close beliefs) Let A : X → DY provide (ε, δ)DistP w.r.t. an adjacency relation Ψ ⊆ DX × DX . Let δ 0 = (1 + eε + e2ε )δ. If
an attacker has close beliefs w.r.t. Ψ , then we obtain (3ε, δ 0 )-DistP against theattacker, i.e., for all (λ0 , λ1 ) ∈ Ψ and all R ⊆ Y, we have:A# (λ˜0 )[R] ≤ e3ε · A# (λ˜1 )[R] + δ 0 .
Proof. We obtain the proposition by:
A# (λ˜0 )[R] ≤ eε · A# (λ0 )[R] + δ

B.3(by (λ˜0 , λ0 ) ∈ Ψ )≤ eε (eε · A# (λ1 )[R] + δ) + δ≤ eε (e2ε · A# (λ˜1 )[R] + (1 + eε )δ) + δ(by (λ0 , λ1 ) ∈ Ψ )(by (λ1 , λ˜1 ) ∈ Ψ )≤ e3ε · A# (λ˜1 )[R] + (1 + eε + e2ε )δ.

tu

Point Obfuscation by Distribution Obfuscation

Next we show that DP is an instance of DistP if an adjacency relation includes
pairs of point distributions.
Definition 13 (Point distribution). For each x ∈ X , the point distribution
ηx of x is the distribution over X such that: ηx [x0 ] = 1 if x0 = x, and ηx [x0 ] = 0
otherwise.
Lemma 1. Let Φ ⊆ X × X . For any (x0 , x1 ) ∈ Φ, we have (ηx0 , ηx1 ) ∈ Φ#
W∞ .
Proof. Let (x0 , x1 ) ∈ Φ. We define γ ∈ D(X × X ) by: γ[x, x0 ] = 1 if x = x0 and
x0 = x1 , and γ[x, x0 ] = 0 otherwise. Then γ is the only coupling between ηx0
and ηx1 , hence γ ∈ Γ∞,d (ηx0 , ηx1 ). Also supp(γ) = {(x0 , x1 )} ⊆ Φ. Therefore bydefinition, we obtain (ηx0 , ηx1 ) ∈ Φ#tu
W∞ .
Theorem 4 (DistP ⇒ DP and XDistP ⇒ XDP) Let ε ∈ R≥0 , Φ ⊆ X × X ,and A : X → DY be a randomized algorithm.
1. If A provides (ε, δ)-DistP w.r.t. Φ# , it provides (ε, δ)-DP w.r.t. Φ.
2. If A provides (ε, W∞,d , δ)-XDistP w.r.t. Φ#
W∞ , it provides (ε, d , δ)-XDP w.r.t. Φ.
Proof. We prove the first claim as follows. Assume that A provides (ε, δ)-DistP
w.r.t. Φ# . Let (x0 , x1 ) ∈ Φ, and ηx0 and ηx1 be the point distributions, defined in##
Definition 13. By Lemma 1 and Φ#
W∞ ⊆ Φ , we have (ηx0 , ηx1 ) ∈ Φ . It follows
from (ε, δ)-DistP that for any R ⊆ Y, we obtain:
A(x0 )[R] = A# (ηx0 )[R] ≤ eε · A# (ηx1 )[R] + δ = eε · A(x1 )[R] + δ.
Hence A provides (ε, δ)-DP w.r.t. Φ.

Local Obfuscation Mechanisms for Hiding Probability Distributions
A1

29

A1 • A0

A0
x0 (∼ λ)-A0x (∼ λ)y0-?
(a) Composition

-

A0
y0

y1

A1

x1 (∼ λ)-with shared input.

-

?

y1

A1

-

(b) Composition • with independent inputs.

Fig. 21: Two kinds of sequential compositionsand •.

Next we show the second claim. Assume that A provides (ε, W∞,d , δ)-XDistP
w.r.t. Φ#
W∞ . Let (x0 , x1 ) ∈ Φ, and ηx0 and ηx1 be the point distributions. By
Lemma 1, we have (ηx0 , ηx1 ) ∈ Φ#
W∞ . Then for any R ⊆ Y, we obtain:
A(x0 )[R] = A# (ηx0 )[R]≤ eεW∞,d (ηx0 ,ηx1 ) · A# (ηx1 )[R] + δ=eεd(x0 ,x1 )(by XDistP of A)· A(x1 )[R] + δ

where the last equality follows from the definition of W∞,d . Hence A provides(ε, d , δ)-XDP w.r.t. Φ.
t
u

B.4

Sequential Compositionsand •In this section we show two kinds of compositionality.
Sequential Composition
with Shared Input We first present the definition of the sequential composition with shared input (Fig. 21a).
Definition 14 (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 → DY1such that: for any x ∈ X , (A1 A0 )(x) = A1 (A0 (x), x)).
Then we show that it is harder to obfuscate distributions when an identical
input is applied to the mechanism multiple times.
Proposition 3 (Sequential compositionof (ε, δ)-DistP) Let Φ ⊆ X ×X .
If A0 : X → DY0 provides (ε0 , δ0 )-DistP w.r.t. Φ# and for each y0 ∈ Y0 , A1 (y0 ) :X → DY1 provides (ε1 , δ1 )-DistP w.r.t. Φ# then the sequential composition A1
A0 provides (ε0 + ε1 , (δ0 + δ1 ) · |Φ|)-DistP w.r.t. Φ# .
Proof. By Theorem 4, A0 provides (ε0 , δ0 )-DP w.r.t. Φ, and for each y0 ∈ Y0 ,A1 (y0 ) provides (ε1 , δ1 )-DP w.r.t. Φ. By the sequential composition theorem for
DP mechanisms, A1 A0 provides (ε0 + ε1 , δ0 + δ1 )-DP w.r.t. Φ. By Theorem 1,
A1 A0 provides (ε0 + ε1 , (δ0 + δ1 ) · |Φ|)-DistP w.r.t. Φ# .

30

Y. Kawamoto et al.

The compositionality for XDistP can be shown analogously to Proposition 3.
Proposition 4 (Sequential compositionof (ε, δ)-XDistP) Let Φ ⊆ X ×
X . If A0 : X → DY0 provides (ε0 , W∞,d , δ0 )-XDistP w.r.t. Φ#
W∞ and for eachy0 ∈ Y0 , A1 (y0 ) : X → DY1 provides (ε1 , W∞,d , δ1 )-XDistP w.r.t. Φ#
W∞ then thesequential composition A1 A0 provides (ε0 + ε1 , W∞,d , (δ0 + δ1 ) · |Φ|)-XDistP
w.r.t. Φ#W∞ .
Proof. By Theorem 4, A0 provides (ε0 , d , δ0 )-XDP w.r.t. Φ, and for each y0 ∈ Y0 ,A1 (y0 ) provides (ε1 , d , δ1 )-XDP w.r.t. Φ. By the sequential composition theorem
for XDP mechanisms, A1 A0 provides (ε0 + ε1 , d , δ0 + δ1 )-XDP w.r.t. Φ. By
Theorem 2, A1 A0 provides (ε0 + ε1 , W∞,d , (δ0 + δ1 ) · |Φ|)-XDistP w.r.t. Φ#
W∞ .
Sequential Composition • with Independent Sampling We first note#that the lifting of the sequential composition (A1 A0 ) does not coincide with##the sequential composition of the liftings A1
A1 . Then the latter is arandomized algorithm A1 # A0 # : DX → DY1 such that for any λ ∈ DX ,(A1 # A0 # )(λ) = A1 # (A0 # (λ), λ). Then each of A0 and A1 receives an input
independently sampled from λ. This is different from A1 A0 , in which A0 andA1 share an identical input drawn from λ, as shown in Figure 21a.
To see this difference in detail, we deal with another definition of sequential
composition.
Definition 15 (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 → DY1such that: for any x0 , x1 ∈ X , (A1 • A0 )(x0 , x1 ) = A1 (A0 (x0 ), x1 )).
#Then the lifting of the sequential composition (A1 • A0 ) coincides with thesequential composition of the liftings A1# • A1# in the sense that for any λ0 , λ1 ∈DX ,#(A1 • A0 ) (λ0 ×λ1 ) = A1# (A0# (λ0 ), λ1 ) = (A1# • A1# )(λ0 , λ1 ),(3)where λ0 ×λ1 is the probability distribution over X ×X such that for all x0 , x1 ∈X , (λ0 × λ1 )[x0 , x1 ] = λ0 [x0 ]λ1 [x1 ].
To show the compositionality for distribution privacy, we introduce an operator  between binary relations Ψ0 and Ψ1 by:Ψ0  Ψ1 = {(λ0 × λ1 , λ00 × λ01 ) | (λ0 , λ00 ) ∈ Ψ0 , (λ1 , λ01 ) ∈ Ψ1 }.
Proposition 5 (Sequential composition • of (ε, δ)-DistP) Let Ψ ⊆ DX ×
DX . If A0 : X → DY0 provides (ε0 , δ0 )-DistP w.r.t. Ψ and for each y0 ∈ Y0 ,A1 (y0 ) : X → DY1 provides (ε1 , δ1 )-DistP w.r.t. Ψ then the sequential composition A1 • A0 provides (ε0 + ε1 , δ0 + δ1 )-DistP w.r.t. Ψ  Ψ .

Local Obfuscation Mechanisms for Hiding Probability Distributions
A1 #
λ

-

31

A0 #

A0 #
µ0

?

λ

Fig. 22: Sequential composition A1 #from λ.

A1 #

µ1

-

A0 # involves two independent samplings

Proof. By the definition of DistP, we have that A0 # provides (ε0 , δ0 )-DP w.r.t.
#
Ψ and for each y0 ∈ Y0 , A1 (y0 ) provides (ε1 , δ1 )-DP w.r.t. Ψ . By the sequential#
composition theorem for DP mechanisms and Equation (3), (A1 • A0 ) provides(ε0 +ε1 , δ0 +δ1 )-DP w.r.t. Ψ Ψ . Therefore A1 •A0 provides (ε0 +ε1 , δ0 +δ1 )-DistP
w.r.t. Ψ  Ψ .
For brevity, we omit the case of XDistP.
Finally, we remark that the comparison of the compositions with shared input
and with independent input is also discussed from the viewpoint of quantitative
information flow in [22].
B.5

Post-processing and Pre-processing

Next we show that distribution privacy is immune to the post-processing. For
A0 : X → DY and A1 : Y → DZ, we define A1 ◦A0 by: (A1 ◦A0 )(x) = A1 (A0 (x)).
Proposition 6 (Post-processing) Let Ψ ⊆ DX × DX , and W : DX × DX →R≥0 be a metric. Let A0 : X → DY, and A1 : Y → DZ.
1. If A0 provides (ε, δ)-DistP w.r.t. Ψ then so does the composite function A1 ◦A0 .
2. If A0 provides (ε, W , δ)-XDistP w.r.t. Ψ then so does the composite function
A1 ◦ A0 .
Proof. Let (λ0 , λ1 ) ∈ Ψ . Since every randomized algorithm is a convex combination of deterministic algorithms, there are a distribution µ Pover an index set I
and deterministic algorithms A1,i : Ui → R such that A1 = i∈I µ[i]A1,i . Then
we obtain:#(A1 ◦ A0 ) (λ0 )[R]P
= x0 ∈X λ0 [x0 ] · (A1 ◦ A0 )(x0 )[R]P
P= i∈I µ[i] x0 ∈X λ0 [x0 ] · (A1,i ◦ A0 )(x0 )[R]P
P= i∈I µ[i] x0 ∈X λ0 [x0 ] · A0 (x0 )[Ui ]P= i∈I µ[i] · A0 # (λ0 )[Ui ].

(4)

32

Y. Kawamoto et al.

Then we show the first claim as follows. Assume that A0 provides (ε, δ)-DistP
w.r.t. Ψ .
#(A1 ◦ A0 ) (λ0 )[R]P
= i∈I µ[i] · A0 # (λ0 )[Ui ](by (4))P#ε≤ i∈I µ[i] · e · A0 (λ1 )[Ui ] + δ(by (ε, δ)-DistP of A0 # )PP= i∈I µ[i] · eε · x1 λ1 [x1 ]A0 (x1 )[Ui ] + δPP= i∈I µ[i] · eε · x1 λ1 [x1 ](A1,i ◦ A0 )(x1 )[R] + δP#= eε ·i∈I µ[i] · (A1,i ◦ A0 ) (λ1 )[R] + δ#= eε · (A1 ◦ A0 ) (λ1 ))[R] + δ.
Therefore A1 ◦ A0 provides (ε, δ)-DistP w.r.t. Ψ .
Analogously, we show the second claim. Assume that A0 provides (ε, W , δ)XDistP w.r.t. Ψ .
#(A1 ◦ A0 ) (λ0 )[R]X=µ[i] · A0 # (λ0 )[Ui ](by (4))

i∈I

≤

X

µ[i] · eε·W (λ0 ,λ1 ) · A0 # (λ1 )[Ui ] + δi∈I= eε·W (λ0 ,λ1 ) ·X

(by (ε, W , δ)-XDistP of A0 # )#µ[i]·(A1,i ◦ A0 ) (λ1 )[R] + δi∈Iε·W (λ0 ,λ1 )=e#·(A1 ◦ A0 ) (λ1 ))[R] + δ.

Therefore A1 ◦ A0 provides (ε, W , δ)-XDistP w.r.t. Ψ .

tu

We then show a property on pre-processing.
Proposition 7 (Pre-processing) Let c ∈ R≥0 , Ψ ⊆ DX × DX , and W :DX × DX → R≥0 be a metric.
1. If T : DX → DX is a (c, Ψ )-stable transformation and A : X → DY provides(ε, δ)-DistP w.r.t Ψ , then A ◦ T provides (c ε, δ)-DistP w.r.t Ψ .
2. If T : DX → DX is a (c, W )-stable transformation and A : X → DY
provides (ε, W , δ)-XDistP, then A ◦ T provides (c ε, W , δ)-XDistP.
Proof. We show the first claim as follows. Assume that A provides (ε, δ)-DistP
w.r.t. Ψ . Let (λ, λ0 ) ∈ Ψ , and R ⊆ Y. Then we have:#(A ◦ T ) (λ)[R] = A# (T # (λ))[R]≤ ecε A# (T # (λ0 ))[R]#= ecε (A ◦ T ) (λ0 )[R].

Local Obfuscation Mechanisms for Hiding Probability Distributions

33

Therefore A ◦ T provides (c ε, δ)-DistP.
Next we show the second claim. Assume that A provides (ε, W , δ)-XDistP.
Let λ, λ0 ∈ DX , and R ⊆ Y. Then we obtain:#(A ◦ T ) (λ)[R] = A# (T # (λ))[R]≤ eεW (T#(λ),T # (λ0 ))0A# (T # (λ0 ))[R]#≤ ecεW (λ,λ ) (A ◦ T ) (λ0 )[R].
Therefore A ◦ T provides (c ε, W , δ)-XDistP.
B.6

t
u

Probabilistic Distribution Privacy (PDistP)

We next introduce an approximate notion of distribution privacy analogously
to the notion of probabilistic differential privacy (PDP) [48]. Intuitively, a randomized algorithm provides (ε, δ)-probabilistic distribution privacy if it provides
ε-distribution privacy with probability at least (1 − δ).
Definition 16 (Probabilistic distribution privacy). Let Ψ ⊆ DX ×DX . We
say that a randomized algorithm A : X → DY provides (ε, δ)-probabilistic distribution privacy (PDistP) w.r.t. Ψ if the lifting A# provides (ε, δ)-probabilistic
differential privacy w.r.t. Ψ , i.e., for all (λ, λ0 ) ∈ Ψ , there exists an R0 ⊆ Y suchthat A# (λ)[R0 ] ≤ δ, A# (λ0 )[R0 ] ≤ δ, and that for all R ⊆ Y, we have:A# (λ)[R \ R0 ] ≤ eε · A# (λ0 )[R \ R0 ]A# (λ0 )[R \ R0 ] ≤ eε · A# (λ)[R \ R0 ],where the probability space is taken over the choices of randomness in A.
B.7

Relationships between PDistP and DistPIn this section we show the relationships between PDistP and DistP. By definition, (ε, 0)-DistP is equivalent to (ε, 0)-PDistP. In general, however, (ε, δ)-DistP
does not imply (ε, δ)-PDistP, while (ε, δ)-PDistP implies (ε, δ)-DistP.
Proposition 8 ((ε, 0)-PDistP ⇔ (ε, 0)-DistP) A randomized algorithm A provides (ε, 0)-PDistP w.r.t. an adjacency relation Ψ iff it provides (ε, 0)-DistP
w.r.t. Ψ .
Proof. Immediate from the definitions.

tuProposition 9 ((ε, δ)-PDistP ⇒ (ε, δ)-DistP) If a randomized algorithm A provides (ε, δ)-PDistP w.r.t. an adjacency relation Ψ , then it provides (ε, δ)-DistP
w.r.t. Ψ .

34

Y. Kawamoto et al.

Proof. Let Ψ ⊆ DX × DX , (λ, λ0 ) ∈ Ψ , R ⊆ Y, and A : X → DY be any
randomized algorithm that provides (ε, δ)-PDistP w.r.t. Ψ . Then there exists an
R0 ⊆ Y such that A# (λ)[R0 ] ≤ δ, and A# (λ)[R \ R0 ] ≤ eε · A# (λ0 )[R \ R0 ]. Hence
we obtain:
A# (λ)[R] = A# (λ)[R \ R0 ] + A# (λ)[R0 ]≤ eε · A# (λ0 )[R \ R0 ] + δ≤ eε · A# (λ0 )[R] + δ.
tu

Therefore A provides (ε, δ)-DistP w.r.t. Ψ .

B.8

Properties of the Tupling Mechanism

In this section we show properties of the tupling mechanism.
We first present a minor result with δ = 0.

Proposition 10 ((εA , 0)-DistP of the tupling mechanism) If A provides (εA , 0)tp
DP w.r.t. Φ, then the (k, ν, A)-tupling mechanism Qk,ν,Aprovides (εA , 0)-DistP#
w.r.t. Φ .

Proof. Let Φ ⊆ X × X . Since A provides (εA , 0)-DP w.r.t. Φ, Theorem 1 implies
that A provides (εA , 0)-DistP w.r.t. Φ# .
tp
Let (λ0 , λ1 ) ∈ Φ# and R ⊆ Y k+1 such that Qk,ν,A(λ0 )[R] > 0. Since thetp
dummies are uniformly distributed over Y, we have Qk,ν,A(λ1 )[R] > 0. Let ȳ =tp
(y1 , y2 , . . . , yk+1 ) ∈ R be an output of Qk,ν,A . Since i is uniformly drawn fromtp
{1, 2, . . . , k + 1} in the mechanism Qk,ν,A, the output of A appears as the i-th
1
. For each b = 0, 1, when an input
element yi of the tuple ȳ with probability k+1
x is drawn from λb , the probability that A outputs yi is:

A# (λb )[yi ] =Px∈X λb [x]A(x)[yi ].

On the other hand, for each j 6= i, the probability that yj is drawn from thedummy distribution ν is given by ν[yj ]. Therefore, the probability that the mechtp
anism Qk,ν,A
outputs the tuple ȳ is:tp
1
Qk,ν,A(λb )[ȳ] = k+1

Pk+1
i=1

A# (λb )[yi ]Q

j6=i ν[yj ].

Local Obfuscation Mechanisms for Hiding Probability Distributions

35

Hence we obtain:
tp
Qk,ν,A(λ0 )[R]tp
Qk,ν,A(λ1 )[R]Ptpȳ∈R Qk,ν,A (λ0 )[ȳ]=Ptpȳ∈R Qk,ν,A (λ1 )[ȳ]P
Pk+1 #
Q
1ȳ∈R k+1i=1 A (λ0 )[yi ]j6=i ν[yj ]
=P
P
Q
k+1
1
#
ȳ∈R k+1i=1 A (λ1 )[yi ]j6=i ν[yj ]P
Pk+1 #ȳ∈R
i=1 A (λ0 )[yi ]=P
Pk+1 #ȳ∈R
i=1 A (λ1 )[yi ](since ν is uniform)

A# (λ0 )[yi ]ȳ∈R i∈{1,2,...,k+1} A# (λ1 )[yi ]≤ max≤ e εAmax(by (εA , 0)-DistP of A w.r.t. Φ# )tp
Therefore Qk,ν,Aprovides (εA , 0)-DistP w.r.t. Φ# .

Next we show that the tupling mechanism provides PDistP without any restriction on A, i.e., A does not have to provide DP in order for the tuplingmechanism to provides PDistP.
Proposition 11 ((εα , δα )-PDistP of the tupling mechanism) Let k ∈ N>0 ,ν be the uniform distribution over Y, A : X → DY, and β, η ∈ [0, 1]. For an
2α2α ∈ R>0 , let εα = ln k+(α+β)·|Y|and δα = 2 exp − kβ+ η. Then for any2k−α·|Y|tpk
0 < α < |Y|, the tupling mechanism Qk,ν,Aprovides (εα , δα )-PDistP w.r.t Λ2β,η,A .
tp
Proof. Let λ0 , λ1 ∈ Λβ,η,A , and R ⊆ Y k+1 such that Qk,ν,A(λ0 )[R] > 0. Sincetp
the dummies are uniformly distributed over Y, we have Qk,ν,A(λ1 )[R] > 0. As
in the proof for Proposition 10, for any ȳ = (y1 , y2 , . . . , yk+1 ) ∈ R:
Pk+1 #tp
Qk,ν,A(λ0 )[ȳ]A (λ0 )[yi ].
(5)= Pi=1tp
k+1 #Qk,ν,A (λ1 )[ȳ]i=1 A (λ1 )[yi ]Recall that in the definition of the tupling mechanism, yi is the output of A while
for each j 6= i, yj is generated
from the uniform distribution ν over Y. HencePk. Therefore it follows fromthe expected value of j6=i A# (λ0 )[yj ] is given by |Y|
the Hoeffding’s inequality that for any α > 0, we have:
P


#
k
2α2
Pr
j6=i A (λ0 )[yj ] ≥ |Y| + α ≤ exp − kβ 2
P


#
k
2α2
Pr
j6=i A (λ1 )[yj ] ≤ |Y| − α ≤ exp − kβ 2
where each yj is independently drawn from ν, hence each of A# (λ0 )[yj ] and
2α2A# (λ1 )[yj ] is independent. By δα = 2 exp − kβ
2 , we obtain:
hX
i
X
k
k
Pr
A# (λ0 )[yj ]≥ |Y|+ α andA# (λ1 )[yj ]≤ |Y|− α ≤δα .
(6)
j6=i

j6=i

36

Y. Kawamoto et al.

tp
When ȳ is drawn from Qk,ν,A(λ0 ), let yi be the output of A# (λ0 ). Then we
obtain: tp
Qk,ν,A (λ0 )[ȳ]
ε
Pr
≥
e
tp
Qk,ν,A(λ1 )[ȳ] Pk+1 #
j=1 A (λ0 )[yj ]ε= Pr Pk+1≥e(by (5))#
j=1 A (λ1 )[yj ] Pk+1 #k|Y| + α + β
j=1 A (λ0 )[yj ]= Pr Pk+1(by def. of ε)≥k#|Y| − αj=1 A (λ1 )[yj ] Pk+1 #k#|Y| + α + A (λ0 )[yi ]j=1 A (λ0 )[yj ]≥ k≤ Pr Pk+1+η##|Y| − α + A (λ1 )[yi ]j=1 A (λ1 )[yj ]by Pr A# (λ0 )[yi ] ≤ β ≥ 1 − η and A# (λ1 )[yi ] ≥ 0Pk#|Y| + αj6=i A (λ0 )[yj ]= Pr P≥+ηk#j6=i A (λ1 )[yj ]|Y| − α≤ δα .

(by (6))tp
Then there is an R0 ⊆ Y k+1 such that Qk,ν,A(λ0 )[R0 ] ≤ δα , and that for any
Q tp(λ0 )[ȳ]ȳ ∈ R, ȳ ∈ R0 iff Qk,ν,A≥ eε . Then:tp(λ )[ȳ]
k,ν,A

1

tp
Qk,ν,A(λ1 )[R0 ] =Xtp
Qk,ν,A(λ1 )[ȳ]

ȳ∈R0

≤

X

tp
e−ε · Qk,ν,A(λ0 )[ȳ]ȳ∈R0tp= e−ε · Qk,ν,A(λ0 )[R0 ]≤ δα .
tp
Therefore Qk,ν,Aprovides (εα , δα )-PDistP w.r.t. Λ2β,η,A .

Then, we obtain the DistP of the tupling mechanism from Propositions 11
and 9 as follows.
Theorem 3 (DistP of the tupling mechanism) Let k ∈ N>0 , ν be the unik
form distribution over Y, A : X → DY, and β, η ∈ [0, 1]. Given an 0 < α < |Y|
,
2

− 2α

let εα = ln k+(α+β)·|Y|and δα = 2e kβ2 + η. Then the (k, ν, A)-tupling mechak−α·|Y|nism provides (εα , δα )-DistP w.r.t. Λ2β,η,A .
tp
Proof. By Proposition 11, Qk,ν,Aprovides (εα , δα )-PDistP w.r.t. Λ2β,η,A . Hencetp
by Proposition 9, Qk,ν,A provides (εα , δα )-DistP w.r.t. Λ2β,η,A .

Local Obfuscation Mechanisms for Hiding Probability Distributions

37

Finally, we note that if A spreads the input distribution (e.g., A provides εDP for a smaller ε), then β becomes smaller (by Proposition 12), hence smaller
values of εα and δα as shown in experimental results in Section 7.
Proposition 12 Let λ ∈ DX , A : X → DY, and y ∈ Y. Then we haveminx∈X λ[x] ≤ A# (λ)[y] ≤ maxx∈X λ[x].
P
Proof. By A# (λ)[y] = x0 ∈X λ[x0 ]A(x0 )[y], we obtain:
 P
A# (λ)[y] ≤ max λ[x] · x0 ∈X A(x0 )[y] = max λ[x]
x∈X
x∈X
 P
A# (λ)[y] ≥ min λ[x] · x0 ∈X A(x0 )[y] = min λ[x].
x∈Xx∈X