1

Matching Anonymized and Obfuscated
Time Series to Users’ Profiles
Nazanin Takbiri Student Member, IEEE, Amir Houmansadr Member, IEEE,

arXiv:1710.00197v1 [cs.IT] 30 Sep 2017

Dennis Goeckel Fellow, IEEE, Hossein Pishro-Nik Member, IEEE,

Abstract
Many popular applications use traces of user data to offer various services to their users; example applications include driver-assistance systems and smart home services. However, revealing user
information to such applications puts users’ privacy at stake, as adversaries can infer sensitive private
information about the users such as their behaviors, interests, and locations. Recent research shows that
adversaries can compromise users’ privacy when they use such applications even when the traces of
users’ information are protected by mechanisms like anonymization and obfuscation.
In this work, we derive the theoretical bounds on the privacy of users of these applications when
standard protection mechanisms are deployed. We build on our recent study in the area of location
privacy, in which we introduced formal notions of location privacy for anonymization-based location
privacy-protection mechanisms. More specifically, we derive the fundamental limits of user privacy when
both anonymization and obfuscation-based protection mechanisms are applied to users’ time series of
data. We investigate the impact of such mechanisms on the tradeoff between privacy protection and
user utility. In particular, we study achievability results for the case where the time-series of users are
governed by an i.i.d. process. The converse results are proved both for the i.i.d. case as well as the
more general Markov Chain model. We demonstrate that as the number of users in the network grows,
the obfuscation-anonymization plane can be divided into two regions: in the first region, all users have
perfect privacy; and, in the second region, no user has privacy.
N. Takbiri is with the Department of Electrical and Computer Engineering, University of Massachusetts, Amherst, MA, 01003
USA e-mail: (ntakbiri@umass.edu).
A. Houmansadr is with the College of Information and Computer Sciences, University of Massachusetts, Amherst, MA, 01003
USA e-mail:(amir@cs.umass.edu)
H. Pishro-Nik and D. Goeckel are with the Department of Electrical and Computer Engineering, University of Massachusetts,
Amherst, MA, 01003 USA e-mail:(pishro@engin.umass.edu)
This work was supported by National Science Foundation under grants CCF–0844725, CCF–1421957 and CNS1739462.
This work was presented in part in IEEE International Symposium on Information Theory (ISIT 2017) [1].

2

Index Terms
User-Data Driven Services (UDD), Privacy-Protection Mechanisms, Information Theoretic Privacy,
Anonymization, Obfuscation.

I. I NTRODUCTION
Various emerging systems and applications work by analyzing the data submitted by their users
in order to serve them; we call such systems user-data driven (UDD) services. Examples of UDD
services include smart cities, connected vehicles, smart homes, and connected healthcare devices,
which have the promise of a significant societal impact. Unfortunately, the sheer volume of user
data collected by these systems can compromise users’ privacy [2]. Even the use of standard
privacy-protection mechanisms (specifically, anonymization of user identities and obfuscation
of submitted data) does not guarantee users’ privacy: the adversaries are able to use powerful
statistical inference techniques to learn sensitive private information of the users [2]–[8].
To illustrate the threat of privacy leakage, consider three popular UDD services: (1) Health
care: Wearable monitors that constantly track user health variables can be invaluable in assessing
individual health trends and responding to emergencies. However, such monitors produce long
time-series of user data uniquely matched to the health characteristics of each user; (2) Smart
homes: Emerging smart-home technologies such as fine-grained power measurement systems
can help users and utility providers to address one of the key challenges of the twenty-first
century: energy conservation. But the measurements of power by such devices can be mapped
to users and reveal their lifestyle habits; and, (3) Connected vehicles: The location data provided
by connected vehicles promises to greatly improve everyday lives by reducing congestion and
traffic accidents. However, the matching of such location traces to prior behavior not only allows
for user tracking, but also reveals a user’s habits. In summary, despite their potential impact on
society and their emerging popularity, these services have one thing in common: their utility
critically depends on their collection of user data, which puts users’ privacy at significant risk.
There are two main approaches to augment privacy in UDD services: identity perturbation
(anonymization) [9]–[14], and location perturbation (obfuscation) [15]–[17]. In anonymization
techniques, privacy is obtained by concealing the mapping between users and data, and the
mapping is changed periodically to thwart statistical inference attacks that try to deanonymize
the anonymized data traces by matching user data to known user profiles. In contrast, obfuscation

3

mechanisms aim at protecting privacy by perturbing user data, e.g., by adding noise to user
locations.
The anonymization and obfuscation mechanisms improve user privacy at the cost of user
utility. The anonymization mechanism works by frequently changing the pseudonym mappings
of users; this improves privacy by reducing the length of time series that can be exploited by
statistical analysis. However, this frequent change may also decrease the usability by concealing
the temporal relation between a user’s locations, which may be critical in the utility of some
systems, e.g., a dining recommendation system that makes suggestions based on the dining history
of its users. On the other hand, obfuscation mechanisms work by adding noise to users’ collected
data, e.g., location information. The added noise may degrade the utility of UDD applications.
Thus, choosing the right level of privacy-protection mechanism is an important question, and
understanding what levels of anonymization and obfuscation can provide theoretical guarantees
of privacy is of interest.
We will consider the ability of an adversary to perform statistical analyses on time series
and match those to descriptions of user behavior. In related work, Unnikrishnan [8] provides a
comprehensive analysis of the asymptotic (in the length of the time series) optimal matching
of time series to source distributions. However, there are several key differences between that
analysis and the work here. First, Unnikrishnan [8] looks at the optimal matching tests, but does
not consider any privacy metrics as considered in this paper, and a significant component of our
study is demonstrating that mutual information converges to zero so we can conclude there is
no privacy leakage (hence, “perfect privacy”). Second, the setting of [8] is different from us,
as it does not consider: (a) obfuscation, which is one of the two major protection mechanisms;
and (b) sources that are not independent and identically distributed (i.i.d.). Third, the setting of
Unnikrishnan [8] assumes a fixed distribution on sources (i.e., classical inference), whereas we
assume the existence of general (but possibly unknown) prior distributions for the sources (i.e.,
a Bayesian setting). Finally, we study the fundamental limits in terms of both the number of
users and the number of observations, while Unnikrishnan [8] focuses on the case where the
number of users are fixed, finite values.
We derive the fundamental limits of user privacy in UDD services in the presence of both
anonymization and obfuscation protection mechanisms. We build on our previous work on
formalizing privacy in location-based services [18]–[21], but we extensively expand that work
here not just in application area but also user models and settings. In particular, our previous

4

work introduced the notion of perfect privacy for location-based services, and we derived the rate
at which an anonymization mechanism should change the pseudonyms in order to achieve the
defined perfect privacy. In this work, we expand the notion of perfect privacy to UDD services in
general, and derive the conditions for it to hold when both anonymization and obfuscation-based
protection mechanisms are employed.
We study both achievability and converse results. After discussing related work in detail in
Section II and introducing the general framework in Section III, we consider an i.i.d. model
extensively in Section IV and the first half of Section V. The i.i.d. model would apply directly to
data that is sampled at a low rate. In addition, understanding the i.i.d. case can also be considered
the first step toward understanding the more complicated case where there is dependency, as
was done for anonymization-only LPPMs in [20] and will be done in Section V.C. In addition,
dependency can only favor the adversary, so our extensive results for the i.i.d. case provide lower
bounds on the achievable privacy in the case of dependency, which would be desirable if the
dependency is poorly understood.
A. Summary of the Results
Given n, the total number of the users in a network, their degree of privacy depends on two
parameters: (1) The number of observations m = m(n) by the adversary per user for a fixed
anonymization mapping (i.e., the number of observations before the pseudonyms are changed);
and (2) the value of the noise added by the obfuscation technique (as defined in Section III,
we quantify the obfuscation noise with a parameter an , where larger an means a higher level of
obfuscation). Intuitively, smaller m(n) and larger an result in stronger privacy, at the expense of
lower utility for the users.
Our goal is to identify values of an and m(n) that satisfy perfect privacy in the asymptote
of a large number of users (n → ∞). We show that when the users’ data sets are governed by
an i.i.d. process, the m(n) − an plane can be divided into two areas. In the first area, all users
have perfect privacy (as defined in Section III), and, in the second area, users have no privacy.
Figure 1 shows the limits of privacy in the entire m(n)− an plane. As the figure shows, in regions
1, 2, and 3, users have perfect privacy, while in region 4 users have no privacy.
For the case where the users’ data sets are governed by irreducible and aperiodic Markov
chains with r states and
|E | edges, we show that users will have no privacy if m = cn |E |−r +α

2

and an = c0n

−

1
|E |−r +β

, for some constants c > 0, c0 > 0, α > 0, and β >

α
4.

We also provide

5

Fig. 1: Limits of privacy in the entire m(n) − an plane: in regions 1, 2, and 3, users have perfect
privacy, and in region 4 users have no privacy.

some insights for the opposite direction (under which conditions users have perfect privacy) for
the case of Markov chains.
II. R ELATED W ORK
Previously, mutual information has been used as a privacy metric in a number of settings, [22]–
[29]. However, the framework and problem formulation for our setting (Internet of Things
(IoT) privacy) is quite different from those encountered in previous work. More specifically,
the IoT privacy problem we consider here is based on a large set of time-series data that belong
to different users with different statistical patterns that has gone through a privacy-preserving
mechanism, and the adversary is aiming at de-anonymizing and de-obfuscating the data.

6

Next, consider related works in smart-home/public environment Internet of Things (IoT)
systems. The authors in [30] investigate privacy for IoT smart energy metering where the concern
results from the fact that any privacy breach can reveal in-house activity. A ‘Dynamic Privacy
Analyzer’ scheme is proposed as an attempt towards achieving a unique privacy metric that is
derived from fundamental principles like robust statistics and information theory. To deal with
concerns in different smart-home IoT devices such as lights, smoke-alarms, power switches,
baby monitors, and weighing scales, which again makes it possible for the entities to snoop and
intrude into the family’s activities, the authors in [31] suggest that device-level protections be
augmented with network-level security solutions. This can be achieved through software defined
networking technology when used to dynamically block/quarantine suspicious devices. In [32],
the authors consider the privacy issues in public environments such as an IoT-enabled retail store.
An IoT-enable retail store has the potential to provide rich, targeted information and services to
users within the environment. However, to fully realize such potential, users must be willing to
share certain data regarding their habits and preferences with the public IoT facility. To encourage
users to share such information, the paper proposes a protocol to ensure the customers that their
data will not be leaked to third parties.
As far as other applications of IoT is concerned, authors in [33] investigate privacy considerations for IoT applications on Smart Grids. In particular, the authors address three types
of challenge domains: customer domain, information and communication domain, and the grid
domain. In [34], the author tried to provide privacy for smart-metering systems with rechargeable
batteries by obscuring the user’s power demand. In [35], the authors consider the privacy issue
of wearable devices. These devices make it possible for health care services start a new phase
in serving patients needs and monitor their health remotely. Finally, authors in [36], overview
the privacy challenges in industrial IoT systems.
Among these applications, location privacy constitutes one of the most important aspects of
IoT privacy. Location privacy preserving mechanisms (LPPMs) can be categorized into two main
classes: identity perturbation LPPMs (anonymization) [9]–[14] and location perturbation LPPMs
(obfuscation) [15]–[17].
There are various approaches suggested for identity perturbation LPPMs. Particularly, kanonymity approaches help to keep each user’s identity indistinguishable within a group of
k − 1 other users [9], [16], [17], [37]–[44]. Another proposal changes users’ pseudonyms within
areas called mix-zones [10], [45], [45]–[47]. There are also various approaches used by location

7

perturbation LPPMs. For instance, cloaking replaces each user’s location information with a
larger region [16], [17], [39], [41], [48]–[63], while an alternative direction is to use dummy
locations in the set of possible locations of users [64]–[69]. Some prior works combine techniques
to achieve stronger location privacy. For instance, Freudiger et al. combine techniques from
cryptography with mix-zones to improve location privacy [11].
Differential privacy, which aims at protecting queries on aggregated data, has also been applied
to the problem of location privacy. Particularly, several identity perturbation [17], [70]–[73]
and location perturbation [17], [74]–[77] LPPMs are based on differential privacy techniques.
Dewri [78] combines k-anonymity and differential privacy to achieve higher location privacy.
Alternatively, Andres et al. hide the exact location of a user in a region by adding Laplacian
distributed noise to achieve a desired level of geo-indistinguishability [77]. In [79]. it is proved
that differential privacy arises out of maximizing entropy principle which is equal to minimizing
informaion leakage and is measured using the mutual information notion. [80] tries to reduce
the expected estimating loss by using differential privacy and constraing the privacy level.
Several studies aim at quantifying location privacy protection. Shokri et al. [13], [81] define
the expected estimation error of the adversary as a metric to evaluate LPPM mechanisms. Ma
et al. [12] use uncertainty about users’ location information to quantify user location privacy
in vehicular networks. To defeat localization attacks and achieve privacy at the same time,
Shokri et al. [15] proposed a method which finds optimal LPPM for an LS B given service
quality constraints. Shokri et al. [15] design LPPM mechanisms that will defeat localization
attacks. In [82] and [83], privacy leakage of location sharing and interdependent location privacy
risks are quantified, respectively. A similar idea is proposed in [84] where the quantification
model is based on the Bayes conditional risk. Yu et al. [85] combine two complementary
notaions, geo-indstingushability and expected inference error, to achieve location privacy. The
geo-indstingushability is derived from differential privacy but cannot adequately protect users’
location against inference attacks of adversary by using prior information, and the expected
inference error as privacy metric doesn’t consider posterior information obtained from pseudolocation. As a result, combining both notations gives users the opportunity to have locatin privacy.
In addition, users are allowed to personalized error boound for different locations.
In [86], the authors propose a novel model for preserving location privacy in IoT in which
they propose the so-called Enhanced Semantic Obfuscation Technique (ESOT). In [87], in the
context of IoT based wireless sensor networks, the authors propose a flexible routing strategy,

8

called Multi-routing Random Walk, which protects the sensor’s location. Another approach has
been proposed in [88].
The discussed studies demonstrate the growing importance of privacy. What is missing from the
current literature is a solid theoretical framework for privacy that is general enough to encompass
various privacy preserving methods in the literature. Such a framework will allow us to achieve
provable privacy guarantees, obtain fundamental trade-offs between privacy and performance,
and provide analytical tools to optimally achieve provable privacy. The closest works to this
paper are [1], [18]–[21]. As mentioned, these works only consider anonymization and only
achiveability. In this paper, by considering obfuscation and anonymization, we characterize the
limits of privacy in the entire m(n) − an plane by considering both achievability and converse
results.
III. F RAMEWORK
In this paper, we adopt a similar framework to that employed in [18]–[20]. The general set up
is provided here, and the refinement to the precise models for this paper will be presented in the
following sections. We assume a system with n users with Xu (k) denoting a sample of the data
of user u at time k, which would we like to protect from an interested adversary A. We consider
a strong adversary A that has complete statistical knowledge of the users’ data patterns based
on the previous observations or other resources. In order to secure data privacy of users, both
obfuscation and anonymization techniques are used as shown in Figure 2. In Figure 2, Zu (k)
shows the (reported) sample of the data of user u at time k after applying obfuscation, and Yu (k)
shows the (reported) sample of the data of user u at time k after applying anonymization. The
adversary observes only Yu (k), k = 1, 2, · · · , m(n), where m(n) is the number of observations of
each user before the identities are permuted. The adversary then tries to estimate Xu (k) by using
those observations.

Fig. 2: Applying obfuscation and anonymization techniques to users’ data samples.
Let Xu(n) be the m(n) × 1 vector containing the sample of the data of user u, and X(n) be the

9

m(n) × n matrix with uth column equal to Xu(n) ;

Xu(n)

 X (1) 
 u 


 X (2) 
 u 
=  . ,
 .. 




 Xu (m)



i
h
(n)
(n)
.
,
·
·
·
,
X
,
X
X(n) = X(n)
n
2
1

Data Samples Model: We assume there are r ≥ 2 possible values (0, 1, · · · , r − 1) for each
sample of the users’ data. In the first part of the paper (perfect privacy analysis), we assume an
i.i.d. model as motivated in Section I. At any time, Xu (k) is equal to a value in {0, 1, · · · , r − 1}
according to a user-specific probability distribution. The collection of user distributions, which
satisfy some mild regularity conditions discussed below, is known to the adversary A, and
he/she employs such to distinguish different users based on statistical matching of those user
distributions to traces of user activity of length m(n).
Obfuscation Model: The first step in obtaining privacy is to apply the obfuscation operation
in order to perturb the users’ data samples. In this paper, we assume that each user has only
limited knowledge of the characteristics of the overall population and thus we employ a simple
distributed method in which the samples of the data of each user are reported with error with
a certain probability, where that probability itself is generated randomly for each user. More
precisely, let Zu(n) be the vector which contains the obfuscated versions of user u’s data sample,
and Z(n) is the collection of Zu(n) for all users,

Zu(n)

 Z (n) (1) 
 u

 (n) 
 Z (2) 
 u

=  . ,
 .. 


 (n) 
 Zu (m)



(n)

Z

=

h

(n)
Z(n)
1 , Z2 , · · ·

, Z(n)
n

i

.

To create a noisy version of data samples, for each user u we independently generate a random
variable Ru(n) that is uniformly distributed between 0 and an 1 . The value of Ru(n) shows the
probability that the user’s data sample are changed to a different data sample by obfuscation,
1 The

(n)

uniform distribution assumption for Ru is not necessary and the results can be extended to a general set of distributions

(n)
when we employ a2n = E[Ru ]. However, the assumption of a uniform random variable simplifies the presentation of the results

significantly.

10

and an is termed the “noise level” of the system. For example, for the case of r = 2 where there
are two states for users’ data pattern (state 0 and state 1), we can write



 Xu (k),

with probability 1 − Ru(n)
(n)
Zu (k) =

(n)

 1 − Xu (k), with probability of Ru

Note that the effect of the obfuscation is to alter the probability distribution function of each user
across the r possibilities in a way that is unknown to the adversary, since it is independent of
all past activity of the user, and hence the obfuscation inhibits user identification. For each user,
Ru(n) is generated once and is kept constant for the collection of samples of length m(n), thus
providing a very low-weight obfuscation algorithm. We will discuss the extension to the case
where Ru(n) are regenerated independently over time in Section VI. There, we will also provide
a discussion about obfuscation using continuous noise distributions (e.g., Gaussian noise).
Anonymization Model: Anonymization is modeled by a random permutation Π (n) on the set
of n users. The user u is assigned the pseudonym Π (n) (u). For simplicity, we will employ Π(u)
instead of Π (n) (u) where the meaning is not ambiguous. Y(n) is the anonymized version of Zu(n) ;
thus


(n)
(n)
Y(n) = Perm Z(n)
,
Z
,
·
·
·
,
Z
;
Π
n
1
2
i
h
(n)
(n)
= Z(n)
,
Z
,
·
·
·
,
Z
Π −1 (1) Π −1 (2)
Π −1 (n)
h
i
(n)
(n)
= Y(n)
1 , Y2 , · · · , Y n ,
where Perm( . , Π) is permutation operation with permutation function Π. As a result, Yu(n) =
Z(n)
and Y(n)
= Zu(n) .
Π(u)
Π −1 (u)
Adversary Model: We protect against the strongest reasonable adversary. Through past observations or some other sources, the adversary is assumed to have complete statistical knowledge
of the users’ patterns; in other words, he/she knows the probability distribution for each user on
the set of data samples {0, 1, . . . , r −1}. The adversary also knows the value of an as it is a design
parameter. However, the adversary does not know the realization of the random permutation Π
or the realizations of random variables Ru(n) , as these are independent of the past behavior of the
users.
In [20], perfect privacy is defined as follows:

11

Definition 1. User u has perfect privacy at time k, if and only if


∀k ∈ N, lim I Xu (k); Y(n) = 0,
n→∞

where I(X; Y ) denotes the mutual information between random variables (vectors) X and Y .
In this paper, we also consider the situation in which there is no privacy:
Definition 2. User u has no privacy at time k, if and only if there exists an algorithm for the
adversary to estimate Xu (k) perfectly as n goes to infinity. In other words, as n → ∞,



∀k ∈ N, Pe (1) , P Xu (k) , Xu (k) → 0.
where Xu (k) is the actual sample of the data of user u at time k, X
u (k) is the adversary’s
estimated sample of the data of user u at time k, and Pe (u) is the error probability.


d

Notation: Throughout the paper, Xn →
− X denotes convergence in distribution. We use P X = x Y = y


for the conditional probability of X = x given Y = y. When we write P X = x Y , we are
referring to a random variable that is defined as a function of Y .
IV. P ERFECT P RIVACY A NALYSIS : I.I.D. C ASE
A. Two-State Model
We first consider the two-state (r = 2) case which captures the salient aspects of the problem.
For the two-state case, the sample of the data of user u at any time is a Bernoulli random variable
with parameter pu , which is the probability of user u being at location 1. Thus,
Xu (k) ∼ Bernoulli (pu ) .
Per Section III, the parameters pu , u = 1, 2, · · · , n are drawn independently from a continuous
density function, fP (pu ), on the (0, 1) interval. The density fP (pu ) might be unknown, so all it
is assumed here is that such density exists. From the results of the paper, it will be evident that
knowing or not knowing fP (pu ) does not change the results asymptotically. Further, we assume
there are δ1, δ2 > 0 such that2 :

2 The




 δ1 < fP (pu ) < δ2,


pu ∈ (0, 1).



 fP (pu ) = 0,


pu < (0, 1).

condition δ1 < fP (pu ) < δ2 is not actually necessary for the results and can be relaxed; however, we keep it here to

avoid unnecessary technicalities.



12

The adversary knows the values of pu , u = 1, 2, · · · , n and uses this knowledge to identify
users. We will use capital letters (i.e., Pu ) when we are referring to the random variable, and
use lower case (i.e., pu ) to refer to the realization of Pu .
In addition, since the user data (Xu (k)) are i.i.d. and have a Bernoulli distribution, the obfuscated data (Zu (k)) are also i.i.d. with a Bernoulli distribution. Specifically,


(n)
(n)
Zu (k) ∼ Bernoulli Qu ,
where
Qu(n) = Pu (1 − Ru(n) ) + (1 − Pu )Ru(n)
= Pu + (1 − 2Pu ) Ru(n),
and recall that Ru(n) is the probability that user u’s data sample is altered at any time. For
convenience, define a vector where element Qu(n) is the probability that an obfuscated data sample
of user u is equal to one:
h
i
(n)
(n)
Q(n) = Q(n)
,
Q
,
·
·
·
,
Q
n ,
1
2
and a vector containing the permutation of those probabilities after anonymization


(n)
(n)
(n)
(n)
V = Perm Q1 , Q2 , · · · , Q n ; Π
i
h
(n)
(n)
(n)
= Q Π−1 (1), Q Π−1 (1), · · · , Q Π−1 (1)
h
i
(n) (n)
(n)
= V1 , V2 , · · · , Vn
(n)
where Vu(n) = Q(n)
and VΠ(u)
= Qu(n) . As a result, for u = 1, 2, ..., n, the distribution of the data
Π −1 (u)

symbols for the user with pseudonym u is given by:




Yu(n) (k) ∼ Bernoulli Vu(n) ∼ Bernoulli Q(n)
.
Π −1 (u)
The following theorem states that if an is significantly larger than

1
n

in this two-state model,

then all users have perfect location privacy independent of the value of m(n).
Theorem 1. For the above two-state model, if Z(n) is the obfuscated version of X(n) , and Y(n)
is the anonymized version of Z(n) as defined above, and
•

m = m(n) is arbitrary;

•

Ru(n) ∼ Uni f orm[0, an ], where an , c0n−(1−β) for c0 > 0 and β > 0;

13

then user 1 has perfect privacy. That is,
∀k ∈ N,



(n)

lim I X1 (k); Y



n→∞

= 0.

Intuition behind the Proof of Theorem 1:
Since m(n) is arbitrary, the adversary is able to estimate very accurately (in the limit, perfectly)
the distribution from which each data sequence Yu(n) , u = 1, 2, · · · , n is drawn; that is, the
adversary is able to accurately estimate the probability Vu(n) , u = 1, 2, · · · , n. Clearly, if there
were no obfuscation for each user u, the adversary would then simply look for the i such that
ei (k) = Yu(n) (k), resulting in no privacy for any user.
pi is very close to Vu(n) and set X
Hence, in order to make sure that the adversary obtains no information about X1 (k), the data
of user 1, we need to establish that there are a large number of users, each whose probability pu
is such that, when obfuscated, it could have resulted in an obfuscated probability consistent with
p1 . Consider asking whether another probability p2 is sufficiently close enough to be confused
with p1 after obfuscation; in particular, we will look for p2 such that, even if the adversary
(n)
(n)
is given the obfuscated probabilities VΠ(1)
and VΠ(2)
, he/she cannot associate these probabilities
(n)
with p1 and p2 . This requires that the distributions Q(n)
1 and Q 2 of the obfuscated data of user

1 and user 2 have significant overlaps; we explore this next.
Recall that Qi(n) = Pi + (1 − 2Pi )Ri(n) , and Ri(n) ∼ Uni f orm[0, an ]. Thus, we know Qi(n) |Pi = pi
has a uniform distribution with length (1 − 2pi )an . Specifically,
Qi(n) Pi = pi ∼ Uni f orm (pi, pi + (1 − 2pi )an ) .
Figure 3 shows the distribution of Qi(n) given Pi = pi .

Fig. 3: Distribution of Qi(n) given Pi = pi .
(n)
Consider two cases: In the first case, the support of the distributions Q(n)
1 P1 = p1 and Q 2 P2 =

p2 are small relative to the difference between p1 and p2 (Figure 4); in this case, given the
(n)
(n)
probabilities VΠ(1)
and VΠ(2)
of the anonymized data sequences, the adversary can associate those

with p1 and p2 without error. In the second case, the support of the distributions Q(n)
1 P1 = p1

14

and Q(n)
2 P2 = p2 is large relative to the difference between p1 and p2 (Figure 5), so it is difficult
(n)
(n)
for the adversary to associate the probabilities VΠ(1)
and VΠ(2)
of the anonymized data sequences
(n)
(n)
with p1 and p2 . In particular, if VΠ(1)
and VΠ(2)
fall into the overlap of the support of Q(n)
1

and Q(n)
2 , we will show the adversary can only guess randomly how to de-anonymize the data.
Thus, if the ratio of the support of the distributions to p1 − p2 goes to infinity, the adversary’s
posterior probability for each user converges to 12 , thus implying no information leakage on the
user identities. More generally, if we can somehow guarantee that there will be a large set of
users with pu ’s very close to p1 compared to the support of Q(n)
1 P1 = p1 , we will be able to
obtain perfect privacy as demonstrated rigorously below.

Fig. 4: Case 1: The support of the distributions is small relative to the difference between p1
and p2 .

Fig. 5: Case 2: The support of the distributions is large relative to the difference between p1
and p2 .
Given this intuition, the formal proof proceeds as follows. Given p1 , we define a set J (n) of
users whose parameter pu of their data distributions is sufficiently close to p1 (Figure 5; case
(n)
2), so that it is likely that Q(n)
1 and Q u cannot be readily associated with p1 and pu .

The purpose of Lemmas 1, 2, and 3 is to show that, from the adversary’s perspective, the users
in the set J (n) are indistinguishable. More specifically, the goal is to show that the obfuscated data
corresponding to each of these users could have been generated by any other users in J (n) in an
equally likely manner. To show this, Lemma 1 employs the fact that, if the observed values of N

15

uniformly distributed random variable is within the intersection of their ranges, it is impossible
to infer any information about the matching between the observed values and the distributions.
That is, all possible N! matchings are equally likely. Lemmas 2 and 3 leverage Lemma 1 to
show that even if the adversary is given a set that includes all of the pseudonyms of the users
∆ 
in set J (n) (i.e., Π(J (n) ) = Π −1 (u) ∈ J (n) ) he/she still will not be able to infer any information
about the matching of each specific user in set J (n) and his pseudonym. Then Lemma 5 uses the
above fact to show that the mutual information between the data set of user 1 at time k and the
observed data sets of the adversary converges to zero for large enough n.
Proof of Theorem 1:
Proof. Note, per Lemma 6 of Appendix A, it is sufficient to establish the results on a sequence
of sets with high probability. That is, we can condition on high-probability events.
Now, define the critical set J (n) with size N (n) = J (n) as follows:
n
o


(n)


 i ∈ {1, 2, . . . , n} : p1 ≤ Pi ≤ p1 + n ; p1 + n ≤ Qi ≤ p1 + (1 − 2p1 )an , for 0 ≤ p1 < 12
J (n) = n
o

(n)

 i ∈ {1, 2, . . . , n} : p1 − n ≤ Pi ≤ p1 ; p1 + (1 − 2p1 )an ≤ Qi ≤ p1 − n , for 21 ≤ p1 ≤ 1

where n ,

1
n

1−

β
2

, an = c0n−(1−β) and β is defined in the statement of Theorem 1.

Note for large enough n, if 0 ≤ p1 <

1 3
2 ,

we have 0 ≤ pi < 12 . As a result,

Qi(n) Pi = pi ∼ Uni f orm (pi, pi + (1 − 2pi )an ) .
We can prove that with high probability, 1 ∈ J (n) for large enough n, as follows. First
Q(n)
1 P1 = p1 ∼ Uni f orm (p1, p1 + (1 − 2p1 )an ) .
Now, accordring to Figure 7,


P 1 ∈ J (n) = 1 −
=1−

n
(1 − 2p1 ) an
1
β

(1 − 2p1 ) c0n 2

→ 1.

Now in the second step, we define the probability W j(n) for any j ∈ Π(J (n) ) = {Π(u) : u ∈ J (n) }
as
W j(n)
3 The





= P Π(1) = j V , Π(J ) .

proof for the case 21 ≤ p1 ≤ 1 is analogous and is omitted.

(n)

(n)

16

Fig. 6: Range of Pi and Qi(n) for elements of set J (n) and probability density function of Qi(n) Pi =
pi .

Fig. 7: Range of Pi and Qi(n) for elements of set J (n) and probability density function of Q(n)
1 P1 =
p1 .

W j(n) is the conditional probability that Π(1) = j after perfectly observing the values of the
permuted version of obfuscated probabilities (V(n) ) and set including all of the pseudonyms of
the users in set J (n) . Since V(n) and Π(J (n) ) are random, W j(n) is treated as a random variable.
However, we will prove shortly that in fact W j(n) =

1
,
N (n)

for all j ∈ Π(J (n) ).

Note: Since, we are looking from the adversary’s point of view, the assumption is that all
the values of Pu , u ∈ {1, 2, · · · , n} are known, so all of the probabilities are conditioned on the
values of P1 = p1, P2 = p2, · · · , Pn = pn . Thus, to be accurate, we should write


(n)
(n)
(n)
W j = P Π(1) = j V , Π(J ), P1, P2, · · · , Pn .
Nevertheless,for simplicity of notation, we often omit the conditioning on P1, P2, · · · , Pn .
First, we need a lemma from elementary probability.
Lemma 1. Let N be a positive integer, and let a1, a2, · · · , aN and b1, b2, · · · , bN be real numbers
such that ai ≤ bi for all i. Assume that X1, X2, · · · , XN are independent random variables such
that
Xi ∼ Uni f orm[ai, bi ].

17

Let also γ1, γ2, · · · , γN be distinct real numbers such that
γj ∈

N
Ù

[ai, bi ] for all j ∈ {1, 2, .., N }

i=1

Suppose that we know the event E has occurred, meaning that the observed values of Xi ’s is
equal to the set of γ j ’s (but with unknown ordering), i.e.,
E

≡

{X1, X2, · · · , XN } = {γ1, γ2, · · · , γN }.

Then

1
P X1 = γ j |E = .
N


Proof. Lemma 1 is proved in Appendix B.
Using the above lemma, we can state our desired result for W j(n) .
Lemma 2. For all j ∈ Π(J (n) ), W j(n) =

1
.
N (n)

Proof. We argue that the setting of this lemma is essentially equivalent to the assumptions in
Lemma 1. First, remember that
W j(n)





= P Π(1) = j V , Π(J ) .
(n)

(n)

Note that Qu(n) = Pu + (1 − 2Pu )Ru(n) , and since Ru(n) are uniformly distributed, Qu(n) conditioned
on Pu are also uniformly distributed in the appropriate intervals. Moreover, since Vu(n) = Q(n)
,
Π −1 (u)
we conclude Vu(n) are also uniformly distributed. So looking at the definition of W j(n) , we can say
the following: given the values of the uniformly distributed random variables Qu(n) , we would
(n)
like to know which one of the values in V(n) is the actual value of Q(n)
1 = VΠ(1) , i.e., is Π(1) = j?

This is equivalent to the setting of Lemma 1 as described further below.
Note that since 1 ∈ J (n) , Π(1) ∈ Π(J (n) ). Therefore, when searching for the value of Π(1), it is
sufficient to look inside the set Π(J (n) ). Therefore, instead of looking among all the values of Vu(n) ,
it is sufficient to look at Vu(n) for u ∈ Π(J (n) ). Let’s show these values by VΠ(n) = {v1, v2, · · · , vN (n) },
so
W j(n)



= P Π(1) = j

(n)
V(n)
Π , Π(J )



.

Thus we have the following scenario: Qi(n), i ∈ J (n) are independent random variables, and
Qi(n) Pi = pi ∼ Uni f orm[pi, pi + (1 − 2pi )an ].

18

Also v1, v2, · · · , vN (n) are the observed values of Qi(n) with unknown ordering (unknown mapping
Π). We also know from the definition of set J (n) that
Pi ≤ p1 + n ≤ Qi(n),
Qi(n) ≤ p1 (1 − 2an ) + an ≤ Pi (1 − 2an ) + an,
so we can conclude
vj ∈

(n)
N
Ù

[pi, pi + (1 − 2pi )an ] for all j ∈ {1, 2, .., N (n) }

i=1

We know the event E has occurred, meaning that the observed values of Qi(n) ’s is equal to the
set of v j ’s (but with unknown ordering), i.e.,
≡

E

{Qi(n), i ∈ J (n) } = {v1, v2, · · · , vN (n) }.

Then according to Lemma 1,


1
P Q1(n) = v j |E, P1, P2, · · · , Pn = (n) .
N
Note that there is a subtle difference between this lemma and Lemma 1 as here N (n) is a random
variable while N is a fixed number in Lemma 1. Nevertheless, since the assertion holds for every
fixed N, it also holds for the case where N is treated as a random variable. Now, note that




(n)
P Q1 = v j |E, P1, P2, · · · , Pn = P Π(1) = j E, P1, P2, · · · , Pn


(n)
(n)
= P Π(1) = j VΠ , Π(J ), P1, P2, · · · , Pn
= W j(n) .
Thus, we can conclude
W j(n) =

1
.
N (n)


g
In third step, we define W j(n) for any j ∈ Π(J (n) ) as


g
(n)
(n)
(n)
W j = P Π(1) = j Y , Π(J ) .
g
W j(n) is the conditional probability that Π(1) = j after observing the values of anonymized
version of obfuscated samples of users’ data (Y(n) ) and aggregate set including all the pseudonyms

19

∆ 
g
of the users in set J (n) (i.e., Π(J (n) ) = Π −1 (u) ∈ J (n) ) Since Y(n) and Π(J (n) ) are random, W j(n)
g
is treated as a random variable. Now, in following lemma, we will prove W j(n) = N1(n) , for all

j ∈ Π(J (n) ) by using Lemma 3.
Note in the following lemma, we want to show even if the adversary is given a set including
all of the pseudonyms of the users in set J (n) , he/she cannot match each specific user in set J (n)
and his pseudonym.
g
Lemma 3. For all j ∈ Π(J (n) ), W j(n) =

1
.
N (n)

Proof. First, note that
 





Õ
g
(n)
(n)
(n)
(n)
(n)
(n)
(n)
,V = v P V = v Y ,Π J
Wj =
P Π(1) = j Y , Π J
for all v

Also, we note that given V(n) , Π(J (n) ) and Y(n) are independent. Intuitively, this is because
when observing Y (n) , any information regarding Π(J (n) ) is leaked through estimating V(n) . This
can be rigorously proved similar to the proof of Lemma 1 in [20]. We can state this fact as




(n)
(n)
(n)
(n)
(n)
P Yu (k) Vu = vu, Π(J ) = P Yu (k) Vu = vu = vu .
The right and left hand side are given by Bernoulli(vu ) distributions.
As a result,

 


Õ
g
(n)
(n)
(n)
(n)
(n)
(n)
Wj =
P Π(1) = j Π(J ), V = v P V = v Y , Π J
for all v

Note

W j(n)



= P Π(1) = j

Π(J (n) ), V(n)


, so




Õ
g
(n)
(n)
(n)
(n)
(n)
Wj =
Wj P V = v Y , Π J
for all v




1 Õ
(n)
(n)
(n)
= (n)
P V = vY ,Π J
N for all v
=

1
.
N (n)


To show that no information is leaked, we need to show that the size of set J (n) goes to
infinity. This is established in Lemma 4.

20

Lemma 4. If N (n) , |J (n) |, then N (n) → ∞ with high probability as n → ∞. More specifically,
there exists λ > 0 such that

P N

(n)


λ β
2
> n → 1.
2


Proof. Lemma 4 is proved in Appendix C.
d
In the final step, we define W j(n) for any j ∈ Π(J (n) ) as


d
(n)
(n)
(n)
W j = P X1 (k) = 1 Y , Π(J ) .

d
W j(n) is the conditional probability that X1 (k) = 1 after observing the values of anonymized
version of obfuscated samples of users’ data (Y(n) ) and aggregate set including all the pseudonyms
g
of the users in set J (n) (Π(J (n) )). W j(n) is treated as a random variable because Y(n) and Π(J (n) )
g
are random. Now, in following lemma, we will prove W j(n) converges in distribution to p1 .
Note that this is the probability from the adversary’s point of view. That is, given that the
adversary has observed Y (n) as well as the extra information Π(J (n) ), what can he/she infer about
X1 (k)?
d d
Lemma 5. For all j ∈ Π(J (n) ), W j(n) →
− p1 .
Proof. We know
d
W j(n) =

Õ







(n)

(n)

j∈Π(J (n) )



g
(n)
(n)
(n)
and according to definition of W j = Π(1) = j Y , Π(J ) , we have


Õ

d
W j(n) =



g
P X1 (k) = 1 Π(1) = j, Y , Π(J ) W j(n)
(n)

(n)

j∈Π(J (n) )

1
= (n)
N

Õ





P X1 (k) = 1 Π(1) = j, Y , Π(J ) .
(n)

(n)

j∈Π(J (n) )

We now claim that




P X1 (k) = 1 Π(1) = j, Y , Π(J ) = p1 + o(1).
(n)

(n)

The reasoning goes as follows. Given Π(1) = j and knowing Y (n) , we know that

(n)
YΠ(1)
(k)



P X1 (k) = 1 Π(1) = j, Y , Π(J ) P Π(1) = j Y , Π(J ) ,
(n)

=

Z1(n) (k)

=




 X1(n) (k),


with probability of 1 − R1(n) .


(n)

 1 − X1 (k),


with probability of R1(n) .

(n)

21

Thus, given Yj(n) (k) = 1, then according to Bayes’ rule,

 
 P(X (k) = 1)
1
(n)
(n)
P X1 (k) = 1 Π(1) = j, Y , Π(J ) = 1 − R1(n)
(n)
P(YΠ(1) (k) = 1)


p1
= 1 − R1(n)
(n)
p1 (1 − R1 ) + (1 − p1 )R1(n)
= 1 − o(1),
and similarly, given Yj(n) (k) = 0,


P(X1 (k) = 1)
(n)
(n)
P X1 (k) = 1 Π(1) = j, Y , Π(J ) = R1(n)
(n)
P(YΠ(1)
(k) = 0)
= R1(n)

p1
p1 (1 − R1(n) ) + (1 − p1 )R1(n)

= o(1).
Note that by the independence assumption, the above probabilities do not depend on the other
values of Yu(n) (k) (as we are conditioning on Π(1) = j ). Thus, we can write


Õ
1
d
(n)
(n)
(n)
P X1 (k) = 1 Π(1) = j, Y , Π(J )
W j = (n)
N
(n)
j∈Π(J

=

First, note that since

n

1
N (n)

)

Õ

(1 − o(1)) +

(n)
j∈Π(J (n) ),Yj (k)=1

j ∈ Π(J (n) ), Yj(n) (k) = 0

o

1
N (n)

Õ

o(1).

(n)
j∈Π(J (n) ),Yj (k)=0

≤ N (n) , the second term above converges to zero.

Thus,
n
d
W j(n) →

(n)
j ∈ Π(J (n) ), YΠ(1)
(k) = 1

N (n)

o
.

Since for all j ∈ Π(J (n) ), Yj(n) (k) ∼ Bernoulli (p1 + o(1)), by a simple application of Chebyshev’s
d
inequality, we can conclude W j(n) → p1 . Appendix D provides the detail.

As a result,
X1 (k)|Y(n), Π(J (n) ) → Bernoulli(p1 ),
thus,


H X1 (k) Y , Π(J
(n)

(n)


→ H (X1 (k))

22

We know conditioning reduces entropy, so




(n)
(n)
(n)
H X1 (k) Y , Π(J
≤ H X1 (k) Y ,
and as a result,


(n)

lim H (X1 (k)) − H X1 (k) Y

n→∞



lim I X1 (k); Y

(n)



n→∞


≤0

≤ 0.



By knowing that I X1 (k); Y(n) cannot take any negative value, we can conclude that


(n)
I X1 (k); Y
→ 0.

B. Extension to r-States
Now, assume users’ data samples can have r possibilities (0, 1, · · · , r − 1), and pu (i) shows
the probability of user u having data sample i. We define the vector pu and the matrix P as
 p (1) 
 u



 p (2) 
 u

pu = 
,
.


..




 pu (r − 1)



P = [p1, p2, · · · , pn ] .

We assume pu (i)’s are drawn independently from some continuous density function, fP (pu ),
which has support on a subset of the (0, 1)r−1 hypercube (Note that the pu (i)’s sum to one, so
one of them can be considered as the dependent value and the dimension is r − 1). In particular,
define the range of distribution as
RP = {(x1, · · · , xr−1 ) ∈ (0, 1)r−1 : xi > 0, x1 + x2 + · · · + xr−1 < 1}.
Figure 8 shows the range RP for the case where r = 3.
Then, we assume there are δ1, δ2 > 0 such that:



 δ1 < fP (pu ) < δ2,


pu ∈ RP .



pu < RP .
 fP (pu ) = 0,

The obfuscation is similar to the two-state case. Specifically, for j ∈ {0, 1, · · · , r − 1} we can
write

23

Fig. 8: RP for case r = 3.

P(Zu(n) (k) = j |Xu (k) = i) =




 1 − Ru(n),


for j = i.

(n)

Ru

,
 r−1


for j , i.

Theorem 2. For the above r-state model, if Z(n) is the obfuscated version of X(n) , and Y(n) is
the anonymized version of Z(n) as defined previously, and
•

m = m(n) is arbitrary;

•

Ru(n) ∼ Uni f orm[0, an ], where an , c0n−( r−1 −β) for c0 > 0 and β > 0;

1

then user 1 has perfect privacy. That is,
∀k ∈ N,



lim I X1 (k); Y(n) = 0.

n→∞

The proof of Theorem 2 is similar to the proof of Theorem 1. The major difference is
that instead of the random variables Pu, Qu(n), Vu(n) , we need to consider the random vectors
Pu, Qu(n), Vu(n) . Similarly, for user u, we define the vector Qu(n) as

Qu(n)

 Q(n) (1) 


u


 Q(n) (2) 
u


=
.
.


..


 (n)

Qu (r − 1)



24

Note that in this case
Qu(n) (l)



= Pu (l) 1 −

Ru(n) (l)



= Pu + 1 − r Pu





Ru(n)
+ 1 − Pu (l)
r −1




Ru(n)
,
r −1

We also need to define the critical set J (n) . To do so, we define for l = 0, 1, · · · , r − 1 the set
Jl(n) as follows. If 0 ≤ p1 (l) < 1r , then
Jl(n) =
n
an o
i ∈ {1, 2, . . . , n} : p1 (l) ≤ Pi (l) ≤ p1 (l) + n ; p1 (l) + n ≤ Qi(n) (l) ≤ p1 (l) + (1 − r p1 (l))
,
r −1
1
1
−β)
0 −( r−1
where n ,
. If
β and β is defined in the statement of Theorem 2, i.e., an = c n
1

1
r

n r−1 − 2

≤ p1 (l) ≤ 1, then
Jl(n) =
n
o
an
(n)
i ∈ {1, 2, . . . , n} : p1 (l) − n ≤ Pi (l) ≤ p1 (l); p1 (l) + (1 − r p1 (l))
≤ Qi (l) ≤ p1 (l) − n .
r −1

We will then define the critical set J (n) as follows:
r−1
Ù
J (n) =
Jl(n) .
l=0

Using these, we can repeat the same arguments in the proof of Theorem 1 to complete the proof.
V. C ONVERSE R ESULTS : N O P RIVACY R EGION
In this section, we prove that if the number of observations by the adversary is larger than
its critical value and the noise level is less than its critical value, then the adversary can find an
algorithm to successfully estimate users’ data samples with arbitrarily small error probability.
Combined with the results of the previous section, this implies that asymptotically (as n →
∞), privacy can be achieved if and only if at least one of the two techniques (obfuscation or
anonymization) are used above their thresholds. This statement needs a clarification as follows:
Looking at the results of [20], we notice that anonymization alone can provide perfect privacy
if m(n) is below its threshold. On the other hand, the threshold for obfuscation requires some
anonymization: In particular, the identities of the users must be permuted once to prevent the
adversary from readily identifying the users.

25

Fig. 9: p1 , sets B(n) and C (n) for case r = 2.

A. Two-State Model
Let us start with the simplest case: i.i.d. two-state model. The data sample of users at any
time is a Bernoulli random variable with parameter pu .
As before, we assume that pu ’s are drawn independently from some continuous density
function, fP (pu ), on the (0, 1) interval. Specifically, there are δ1, δ2 > 0 such that:



 δ1 < fP (pu ) < δ2, pu ∈ (0, 1).



 fP (pu ) = 0,


pu < (0, 1).

Theorem 3. For the above two-state mode, if Z(n) is the obfuscated version of X(n) , and Y(n) is
the anonymized version of Z(n) as defined, and
•

m = cn2+α for c > 0 and α > 0;

•

Ru(n) ∼ Uni f orm[0, an ], where an , c0n−(1+β) for c0 > 0 and β > α4 ;

user 1 has no privacy as n goes to infinity. In other words, there exists an algorithm for the
adversary to produce the estimation of X
1 (k) such that for large enough n,
∀k ∈ N,





Pe (1) , P X1 (k) , X1 (k) → 0.

Since this is a converse result, we give an explicit detector at the adversary and show that it
can be used by the adversary to recover the true data pattern of user 1.
Proof. The adversary first inverts the anonymization mapping Π to obtain Z1 (k), and then
estimates the value of X1 (k) from that. To invert the anonymization, the adversary calculates the
empirical probability that each string is in state 1 and then assigns the string with the empirical
probability closest to p1 to user 1.
Formally, for u = 1, 2, · · · , n, the adversary computes Yu(n) , the empirical probability of user u
being in state 1, as follows
Yu(n) =

Yu(n) (1) + Yu(n) (2) + · · · + Yu(n) (m)
.
m

26

Thus,
(n)
YΠ(u)
=

Zu(n) (1) + Zu(n) (2) + · · · + Zu(n) (m)
.
m

As shown in Figure 9, define
B(n) , {x ∈ (0, 1); p1 − ∆n < x < p1 + ∆n } ,
where ∆n =
an =

1
α and α is defined in
n1+ 4
c0n−(1+β) , and large enough n,

the statement of Theorem 3. We claim that for m = cn2+α ,



(n)
1) P YΠ(1) ∈ B(n) → 1.

!
n
Ð
(n)
2) P
YΠ( j) ∈ B(n) → 0.
j=2

Thus, the adversary can identify Π(1) by examining Yu(n) ’s and assigning the one in B(n) to user
1.
First, we show that as n goes to infinity,


(n)
(n)
→ 1.
P YΠ(1) ∈ B
We can write
m
Í
(n)


© Z1 (i)
ª
­ i=1
(n)
(n)
(n) ®
P YΠ(1) ∈ B
= P­
∈B ®
­
®
m
«
¬
m
Í
Z1(n) (i)
©
ª
­
®
i=1
= P ­ p1 − ∆ n <
< p1 + ∆n ®
­
®
m
«
¬
!
m
Õ
(n)
= P mp1 − m∆n − mQ(n)
Z1(n) (i) − mQ(n)
.
1 <
1 < mp1 + m∆n − mQ 1
i=1

Note that for any u ∈ {1, 2, · · · , n}, we have
|pu − Qu(n) | = |1 − 2pu |Ru(n)
≤ Ru(n) ≤ an .

27

So we can conclude
!


m
Õ
(n)
(n)
(n)
(n)
(n)
Z1 (i) − mQ1 < mp1 + m∆n − mQ1
P YΠ(1) ∈ B(n) = P mp1 − m∆n − mQ1 <
i=1

≥ P −m∆n + man <

m
Õ

!
Z1(n) (i) − mQ(n)
1 < −man + m∆n

i=1
m
Õ

=P

!
Z1(n) (i)

−

mQ(n)
1

< m(∆n − an ) .

i=1

Since an → 0, for p1 ∈ (0, 1) and large enough n, we can say p1 + an < 2p1 . According to
Chernoff bound,

P

m
Õ

!
Z1(n) (i)

−

mQ(n)
1

< m(∆n − an ) ≥ 1 − 2e

n)
− m(∆n −a
(n)
3Q

2

1

i=1


≥ 1 − 2e

− 3(p 1+an ) cn2+α 1+1 α
1
n 4
00

≥ 1 − 2e

α

c
− 6p
n2
1

→ 1.

As a result, as n becomes large,


(n)
(n)
P YΠ(1) ∈ B
→ 1.
Now, we need to show that as n goes to infinity,

n 
©Ø (m)
(n) ª
P­
YΠ( j) ∈ B ® → 0.
« j=2
¬
First, we define
C (n) = {x ∈ (0, 1); p1 − 2∆n < x < p1 + 2∆n } ,
and claim as n goes to infinity,
n 

©Ø
(n) ª
P­
P j ∈ C ® → 0.
j=2
«
¬

Note


4∆n δ1 < P P j ∈ C (n) < 4∆n δ2,

c0
− 1+β
n

2

28

and according to the union bound, for large enough n,
n
n 



Õ
©Ø
(n) ª
P P j ∈ C (n)
P­
Pj ∈ C ® ≤
« j=2
¬ j=2

≤ 4n∆n δ2
= 4n

1
α

n1+ 4

δ2

α

= 4n− 4 δ2 → 0.
As a result, we can conclude that all p j ’s are outside of C (n) for j ∈ {2, 3, · · · , n} with high
probability.


Now, we claim that given all p j ’s are outside of C (n) , P YΠ( j) ∈ B(n) is small. Remember
that for any u ∈ {1, 2, · · · , n}, we have
|pu − Qu(n) | ≤ an .
Now, noting the definitions of the sets B(n) and C (n) , we can write




(n)
(n)
(n)
≤ P YΠ( j) − Q j > (∆n − an )
P YΠ( j) ∈ B
=P

m
Õ

!
(n)
Z (n)
> m(∆n − an ) .
j (i) − mQ j

i=1

According to the Chernoff bound,
P

m
Õ

!
(n)
Z (n)
> m(∆n − an ) ≤ 2e
j (i) − mQ j

n)
− m(∆n −a
(n)
3Q

2

1

i=1

≤ 2e

1
cn2+α
1 +an )

− 3(p

00

≤ 2e
00

1
1+ α
n 4

−

c0
n1+β

α

c
n2
− 6p
1



.

α

c
n2
− 6p

We also know that as n goes to infinity, 2e
goes to zero. As a result,


(n)
(n)
P YΠ( j) ∈ B
→ 0.
1

Now, by using union bound, we have



n 
n
Õ
©Ø (m)
(m)
(n) ª
(n)
P­
YΠ( j) ∈ B ® ≤
P YΠ( j) ∈ B
j=2
j=2
«
¬


α
c 00 2
− 6p
n
≤ n 2e 1
,

2

29

and thus, as n goes to infinity,

n 
©Ø (m)
(n) ª
P­
YΠ( j) ∈ B ® → 0.
« j=2
¬
So the adversary can successfully recover Z1(n) (k). Since Z1(n) (k) = X1 (k) with probability
1 − Ru(n) = 1 − o(1), the adversary can recover X1 (k) with vanishing error probability.



B. Extension to r-States
Now, assume users’ data samples can have r possibilities (0, 1, · · · , r − 1), and pu (i) shows
the probability of user u having data sample i. We define the vector pu as
 p (1) 
 u



 p (2) 
u


pu = 
 , for each u ∈ {1, 2, · · · , n}.
..


.




 pu (r − 1)


We also assume pu ’s are drawn independently from some continuous density function, fP (pu ),
which has support on a subset of the (0, 1)r−1 hypercube. In particular, define the range of
distribution as

RP = (x1, · · · , xr−1 ) ∈ (0, 1)r−1 : xi > 0, x1 + x2 + · · · + xr−1 < 1 .
Then, we assume there are δ1, δ2 > 0 such that:



 δ1 < fP (pu ) < δ2,



 fP (pu ) = 0,


pu ∈ RP .
pu < RP .

Theorem 4. For the above r-states mode, if Z(n) is the obfuscated version of X(n) , and Y(n) is
the anonymized version of Z(n) as defined, and
•

m = cn r−1 +α for c > 0 and 0 < α < 1;

•

Ru(n) ∼ Uni f orm[0, an ], where an , c0n−( r−1 +β) for c0 > 0 and β > α4 ;

2

1

then user 1 has no privacy as n goes to infinity. In other words, there exists an algorithm for the
adversary to produce the estimation of X
1 (k) such that for large enough n,
∀k ∈ N,





Pe (1) , P X1 (k) , X1 (k) → 0.

30

Fig. 10: p1 , sets B0(n) and C 0(n) in RP for case r = 3.

The proof of Theorem 4 is similar to the proof of Theorem 3, so we just provide the general
idea. We similarly define the empirical probabilities Y(m)
j . The difference is that now for each
j ∈ {1, 2, · · · , n}, Y(m)
is a vector of size r − 1. In other words,
j
h
i
(m)
(m)
(m)
Y(m)
=
Y
(1),
Y
(2),
·
·
·
,
Y
(r
−
1)
,
j
j
j
j
where Yj(m) (i) is the empirical probability that the user with pseudonym j has data sample i.
Define sets B0(n) and C 0(n) as

B0(n) , (x1, ..., xr−1 ) ∈ RP : p1 (i) − ∆0n < xi < p1 (i) + ∆0n, i = 1, ..., r − 1 ,

C 0(n) , (x1, ..., xr−1 ) ∈ RP : p1 (i) − 2∆0n < xi < p1 (i) + 2∆0n, i = 1, ..., r − 1 ,
where ∆0n =

1

1
α
n r−1 + 4

. Figure 10 shows p1 and the sets B0(n) and C 0(n) for the case r = 3.

We claim
for m =cn r−1 +α and as n become large:

1) P Y(m)
∈ B0(n) → 1
Π(1)

!
n
Ð
2) P
Y(m)
∈ B0(n) → 0
Π( j)
2

j=2

This can be shown similar to the above proof that we provided for the two-state case. Thus, the
adversary can de-anonymize the data and then recover X1 (k) with vanishing error probability as
in the two-state model.

31

C. Markov Chain Model
So far, we have assumed users’ data sample can have r possibilities (0, 1, · · · , r − 1) and
users’ patterns are i.i.d. Here, we model users’ pattern by using Markov chains, to capture the
dependency of the users’ pattern over time. Again, we assume there are r possibilities (the
number of states in the Markov chains). Let E be the set of edges. More specifically, (i, j) ∈ E
if there exists an edge from i to j with probability p(i, j) > 0. What distinguishes different users
is their transition probabilities pu (i, j) (the probability that user u jumps from state i to state
j). The adversary knows the transition probabilities of all users. The model for obfuscation and
anonymization is exactly the same as before.
We show that the adversary will be able to estimate the data samples of the users with low error
probability if m(n) and an are in the appropriate range. The key idea is that the adversary can
focus on a subset of transition probabilities that are sufficient for recovering the entire transition
probability matrix. By estimating those from the observed data and matching with the known
transition probabilities of the users, the adversary will be able to first de-anonymize the data,
and then estimate the locations of users. In particular, note that for each state i, we must have
r
Õ

pu (i, j) = 1,

for each u ∈ {1, 2, · · · , n}

j=1

so the Markov chain of user u is completely determined by a subset of size d = |E | − r of
transition probabilities. Let’s write this subset in a new vector as follows:
 p (1) 
u




 p (2) 
u


pu = 
,
..


.




 pu (|E | − r)



for each u ∈ {1, 2, · · · , n}.

We also consider pu ’s are drawn independently from some continuous density function, fP (pu ),
which has support on a subset of the (0, 1)|E |−r hypercube. Let Rp ⊂ Rd be the range of acceptable
values for Pu . As before, we assume there are δ1, δ2 > 0, such that:



 δ1 < fP (p) < δ2, p ∈ Rp .



p < Rp .
 fP (p) = 0,

Using the above observations, we can show the following theorem.

32

Theorem 5. For an irreducible, aperiodic Markov chain with r states and |E | edges as defined
above, if Z(n) is the obfuscated version of X(n) , and Y(n) is the anonymized version of Z(n) , and
m = cn |E |−r +α for c > 0 and α > 0;
2

•

(n)
• Ru

∼ Uni f orm[0, an ], where an ,

−
c0 n



1
|E |−r +β



for c0 > 0 and β > α4 ;

then the adversary can successfully identify the pattern of user 1 as n goes to infinity. In other
words, for large enough n,
∀k ∈ N,





Pe (1) , P X1 (k) , X1 (k) → 0.

The proof has a lot of similarity to the i.i.d. case, so we provide a sketch, mainly focusing on
the differences. We argue as follows. If the total number of observations per user is m = m(n),
then define Mi (u) to be the total number of visits by user u to state i, for i = 0,1, · · · , r − 1.
Since the Markov Chain is irreducible and aperiodic, and m(n) → ∞, all

Mi (u)
m(n)

converge to their

stationary values. Now conditioned on Mi (u) = mi (u), the transitions from state i to state j for
user u follow a multinomial distribution with probabilities pu (i, j).
Given the above, the setting is now very similar to the i.i.d. case. Each user is uniquely
characterized by a vector pu of size |E | − r. We define the sets B
B
C
where ∆00n =

00 (n)

00 (n)

1

00 (n)

and C

00 (n)

as

, {(x1, ..., xd ) ∈ RP : p1 (i) − ∆00n < xi < p1 (i) + ∆00n , i = 1, ..., d},

, {(x1, ..., xd ) ∈ RP : p1 (i) − 2∆00n < xi < p1 (i) + 2∆00n , i = 1, ..., d},

1 +α
n |E |−r 4

, and d = |E | − r. Then, we can show that for the stated values of m(n) and

an , as n becomes large:

00 (n)
(m)
1) P YΠ(1) ∈ B
→ 1.

!
n
Ð
00 (n)
(m)
YΠ( j) ∈ B
2) P
→ 0.
j=2

which means that the adversary can estimate the pattern of user 1 with vanishing error probability.
The proof is very similar to the proof of the i.i.d. case; however, there are two differences that
need to be addressed:
First, the probability of observing an erroneous observation is not exactly given by Ru(n) . In
fact, a transition is distorted if at least one of its nodes is distorted. So if the actual transition is
from state i to state j, then the probability of an erroneous observation is
(n) (n)
Ri(n) + R(n)
j − 2Ri R j .

33

Nevertheless,
 
 here the order only matters and the above expression is still in the order of an =
− |E1|−r +β
.
O n
The second difference is more subtle. As opposed to the i.i.d. case, the error probabilities are
not completely independent. In particular, if Xu (k) is reported in error, then both the transition
to that state and from that state are reported in error. This means that there is a dependency
between errors of adjacent transitions. We can address this issue in the following way:
The adversary makes his decision only based on a subset of the observations. More specifically,
the adversary looks at only odd-numbered transitions: First, third, fifth, etc., and ignores the evennumbered transitions. This way, the number of observations is effectively reduced from m to
m
2

which again does not impact the order of the result (remember that the Markov chain is

aperiodic). However, the adversary has now access to observations with independent errors.
VI. P ERFECT P RIVACY A NALYSIS : M ARKOV C HAIN M ODELS
So far, we have provided both achievability and converse results for the i.i.d. case. However,
we have only provided the converse results for the Markov chain case. Here, we investigate
achievability for Markov chain models. It turns out that for this case, the assumed obfuscation
technique is not sufficient to achieve a reasonable level of privacy. Loosely speaking, we can
state that if the adversary can make enough observations, then he can break the anonymity. The
culprit is the fact that the observed sequence by the adversary is no longer a Markov chain;
namely it can be modeled by a hidden Markov chain. This allows the adversary to successfully
estimate the obfuscation random variable Ru(n) as well as the pu (i, j) values for each sequence,
hence successfully de-anonymize the sequences.
More specifically, as we will see below, there is a fundamental difference between the i.i.d.
case and the Markov chain case. In the i.i.d. case, if the noise level is beyond a relatively small
threshold, the adversary will be clueless in de-anonymizing the data, let alone in recovering the
actual values of the data sets for users, no matter how large m is. On the other hand, in the
Markov chain case, if m = m(n) is large enough, then the adversary can easily de-anonymize
the data. To better illustrate this, let’s consider a very simple example.
Example 1. Consider the simple scenario where there are only two states and users’ data
samples change between the two states according to the Markov chain shown in Figure 11. What
distinguishes the users is their different values of p. Now suppose we use the same obfuscation

34

method as before. That is, to create a noisy version of data samples, for each user u we generate
the random variable Ru(n) that is the probability that the data sample of the user is changed to a
different data sample by obfuscation. Specifically,



 Xu (k),

with probability 1 − Ru(n) .
(n)
Zu (k) =

(n)

 1 − Xu (k), with probability of Ru .


0

)1m

1

i

1−p

p

Fig. 11: A state transition diagram.

To analyze this problem, we can construct the underlying Markov chain as follows. Each state
in this Markov chain is identified by two values: the real state of the user, and the observed
value by the adversary. In particular, we can write
(Real value, Observed value) ∈ {( 0, 0), (0, 1), (1, 0), (1, 1)}.
Figure 12 shows the state transition diagram of this new Markov chain.

F 00 f
p(1−R)

pR

p(1−R)

01

X

1−R

R

 x
F 10 o

8

1−R

R
(1−p)R

(1−p)R

pR

& 
7 11 X
(1−p)(1−R)

(1−p)(1−R)

Fig. 12: The state transition diagram of the new Markov chain.

35

We know
p
(1 − R).
1+p
p
R.
π01 = π0 R =
1+p
1
π10 = π1 R =
R.
1+p
1
= π1 (1 − R) =
(1 − R).
1+p

π00 = π0 (1 − R) =

π11

The observed process by the adversary is not a Markov chain; nevertheless we can define
limiting probabilities. In particular, let θ 0 be the limiting probability of observing a zero. That
is, we have
M0 d
→
− θ 0,
m

as n → ∞,

where m is the total number of observations by the adversary, and M0 is the number of 0’s
observed. Then,
θ 0 = π00 + π10 =

(1 − R)p + R
.
1+p

Also, let θ 1 be the limiting probability of observing a one, so
θ 1 = π01 + π11 =

pR + (1 − R)
= 1 − θ0 .
1+p

Now by estimating θ 0 , the adversary obtains
θ̂ 0 =

(1 − R)p + R
.
1+p

(1)

Note that if the number of observations by the adversary can be arbitrarily large, the adversary
can obtain an arbitrarily accurate estimate of θ 0 . The adversary can obtain another equation easily.
For example, let θ 01 be the limiting portion of transitions from state 0 to 1 in the observed chain
by the adversary. We can write
θ 01 = P {(00 → 01), (00 → 11), (10 → 01), (10 → 11)}
= π00 (1 − R) + π10 PR + π10 (1 − p)(1 − R).
As a result,
θ̂ 01 =

p(1 − R)2 + R (PR(1 − R)(1 − p))
.
1+p

(2)

Again, if the number of observations can be arbitrarily large, the adversary can obtain an arbitrarily accurate estimate of θ 01 . By solving the Equations 3 and 4, the adversary can successfully
recover R and p; thus, he/she can successfully de-anonymize users’ locations.

36

VII. D ISCUSSION
A. Markov Chain Model
As opposed to the i.i.d. case, we see from Section III that if we do not limit m = m(n), the
assumed obfuscation method will not be sufficient to achieve perfect privacy. There are a few
natural questions here. First, for a given noise level, what would be the maximum m(n) that
could guarantee perfect privacy in this model? The more interesting question is, how can we
possibly modify the obfuscation technique to make it more suitable for the Markov chain model?
A natural solution seems to be re-generating the obfuscation random variables Ru(n) periodically.
This will keep the adversary from easily estimating them by observing a long sequence of data
at a small increase in complexity. In fact, this will make the obfuscation much more robust to
modeling uncertainties and errors. It is worth noting, however, that this change would not affect
the other results in the paper. That is, even if the obfuscation random variables are re-generated
frequently, it is relatively easy to check that all the previous theorems in the paper remain valid.
However, the increase in robustness to modeling errors will definitely be a big advantage. Thus,
the question is how often should the random variables Ru(n) be re-generated to strike a good
balance between complexity and privacy? These are all interesting questions for future research.
B. Obfuscating the Sample of Users’ Data Using Continuous Noise
Here, we argue that for the setting of this paper, continuous noise such as Gaussian noise is
not a good option to obfuscate the sample of users’ data with the finite alphabet when we want
to achieve perfect privacy. For better understanding, let’s consider a simple example.
Example 2. Consider the simple scenario where the users’ data sets are governed by i.i.d. model
and the number of possible values for each sample of the users’ data (r) is equal to 2 (two-state
model). Note the data sequence for user u is a Bernoulli random variable with parameter pu .
Here we assume that the actual sample of the data of user u at time k (Xu (k)) is obfuscated
using a noise with Gaussian distribution (Su(n) (k)), and Zu(n) (k) is the obfuscated version of Xu (k).
That is, we can write
Zu(n) (k) = Xu (k) + Su(n) (k);



Su(n) (k) ∼ N 0, Ru(n)

where Ru(n) is chosen from some distributions. For simplicity, we can consider Ru(n) ∼ N 0, an2
where an is the noise level.



37

We also apply anonymization technique in order to anonymize Zu(n) (k), and as before Yu(n) (k)
is the reported sample of the data of user u at time k after applying anonymization technique.
According to Section III, anonymization is modeled by a random permutation Π (n) (u) on the set
of n users.
Now the question is as follows: Is it possible to achieve perfect privacy independent of the
number of adversary’s observation (m(n)) while using this continuous noise (Su(n) (k)) to obfuscate
the sample of users’ data?
Note that, the density function of the reported sample of the data of user u after applying
obfuscation is
fZ (n) (z) = pu fS(n) (k) (z − 1) + (1 − pu ) fS(n) (k) (z)
u

u

u

1

= pu √
e
2πRu(n)

2
− (z−1)
(n)
2Ru

1

e
+ (1 − pu ) √
2πRu(n)

−

z2
(n)
2Ru

.

In this case, when the number of adversary’s observation of the sample of users’ data is large,
the adversary can estimate the values of Pu and Ru(n) for each user with an arbitrarily small error
probability. As a result, the adversary can de-anonymize the data and then recover Xu (k). The
conclusion here is that continuous noise distribution gives too much information to adversary
when used for obfuscation of finite alphabet data. A method to remedy this issue is to regenerate
the random variables Ru(n) frequently (similar to our previous discussion for Markov chains).
Understanding the optimal frequency and perfect analysis in this case is an interesting future
research direction.
C. Relation to Differential Privacy
Differential privacy is mainly used when there is a statistical database of users’ sensitive
information and the goal is to protect an individual’s data while publishing aggregate information
about the database [17], [70]–[73]. The goal of differential privacy is publishing aggregate queries
with low sensitivity. It means the effect of changes in a single individual on the outcome of the
aggregated information is negligible.
In [89] three different approaches for differential privacy are presented. The one that best
matches to our setting is stated as
P(X1 (k) = x1 |Y(n) )
P(X1 (k) = x2 |Y(n) )

≤ er

P(X1 (k) = x1 )
,
P(X1 (k) = x2 )

38

where Y(n) is the set of reported data sets. It means Y(n) has limited effect on the probabilities
assigned by the attacker. In differential privacy, user 1 has strongest differential privacy when
r = 0.
In Lemma 5, we proved that if user 1 has perfect privacy, this implies that asymptotically (for
large enough n)


P X1 (k) = x1 Y



→ P (X1 (k) = x1 ) .

(3)



P X1 (k) = x2 Y(n) → P (X1 (k) = x2 ) .

(4)

(n)

As a result, by using (3) and (4) we can conclude that if we satisfy perfect privacy condition
in this paper, we can also satisfy differential privacy with r = 0, i.e., the strongest case of
differential privacy.
VIII. C ONCLUSIONS
In this paper, we considered both obfuscation and anonymization techniques to achieve privacy.
We characterized the limits of privacy in the entire m(n)− an plane for the i.i.d. case. The privacy
level of the users depend on both m(n) (number of observations per user by the adversary for a
fixed anonymization mapping) and an (noise level). That is, larger m(n) and smaller an indicate
weaker privacy. In this paper, we obtained the exact values of the thresholds for m(n) and an .
 1 
 2 
We showed that if m(n) is fewer than O n r−1 , or an is bigger than Ω n− r−1 , users have perfect
privacy. On the other hand, if none of the above conditions are satisfied, users have no privacy.
For the case, where the users’ patterns are modeled by Markov chains, we obtained a no-privacy
region in the m(n) − an plane.
Future research in this area needs to characterize the exact privacy/no-privacy regions for the
Markov models. It is also important to consider different ways to obfuscate users’ data sets, and
study the utility-privacy trade-offs for different kinds of obfuscation techniques.
A PPENDIX A
L EMMA 6 AND ITS P ROOF
Here, we state that we can condition on high-probability events.
Lemma 6. Let p ∈ (0, 1), and X ∼ Bernoulli(p) be defined on a probability space (Ω, F , P).
Consider B1, B2, · · · be a sequence of events defined on the same probability space such that

39

P(Bn ) → 1 as n goes to infinity. Also, let Y(1), Y(2), · · · be a sequence of random vectors
(matrices) in the same probability space, then:
I(X; Y(n) ) → 0 iff I(X; Y(n) |Bn ) → 0.
Proof. First, we prove that as n becomes large,
H(X |Bn ) − H(X) → 0.

(5)

Note that as n goes to infinity,








 
P (X = 1) = P X = 1 Bn P (Bn ) + P X = 1 Bn P Bn


= P X = 1 Bn ,




d

thus, X Bn →
− X, and as n goes to infinity,
H (X |Bn ) − H(X) → 0.
Similarly as n becomes large,




(n)
(n)
P X = 1 Y = y → P X = 1 Y = y, Bn ,
and




H X |Y(n) = y, Bn − H X |Y(n) = y → 0.

(6)

Remembering that


I X; Y

(n)



= H(X) − H(X |Y(n) ),

(7)

and using (5), (6), and (7), we can conclude that as n goes to infinity,




I X; Y(n) |Bn − I X, Y(n) → 0.
As a result, for large enough n,




(n)
(n)
I X; Y
→ 0 ⇐⇒ I X; Y |Bn → 0.


40

A PPENDIX B
P ROOF OF L EMMA 1
Here, we provide a formal proof for Lemma 1 which we restate as follows.
Let N be a positive integer, and let a1, a2, · · · , aN and b1, b2, · · · , bN be real numbers such
that ai ≤ bi for all i. Assume that X1, X2, · · · , XN are N independent random variables such that
Xi ∼ Uni f orm[ai, bi ].
Let also γ1, γ2, · · · , γN be real numbers such that
N
Ù
γj ∈
[ai, bi ] for all j ∈ {1, 2, .., N }
i=1

Suppose that we know the event E has occurred, meaning that the observed values of Xi ’s is
equal to the set of γ j ’s (but with unknown ordering), i.e.,
E

≡

{X1, X2, · · · , XN } = {γ1, γ2, · · · , γN }.

Then

1
P X1 = γ j |E = .
N
Proof. Define the sets P and Pj as follows.
P = The set of all permutations Π on {1, 2, .., N }.
Pj = The set of all permutations Π on {1, 2, .., N } such that Π(1) = j.
So, we have |P| = N! and |P| = (N − 1)!. Then
Í
π∈Pj fX1,X2,··· ,X N (γπ(1), γπ(2), · · · , γπ(N) )
P(X1 = α j |E) = Í
π∈P fX1,X2,··· ,X N (γπ(1), γπ(2), · · · , γπ(N) )
(N − 1)!

N
Î
i=1

=
N!

N
Î
i=1

1
bi −ai

1
bi −ai

1
= .
N


41

A PPENDIX C
P ROOF OF L EMMA 4
Here, we provide a formal proof for Lemma 4 which we restate as follows. The following
lemma confirms that the number of elements in J (n) goes to infinity as n becomes large.
If N (n) , |J (n) |, then N (n) → ∞ with high probability as n → ∞. More specifically, there
exists λ > 0 such that


λ β
P N > n 2 → 1.
2
1
Proof. We prove the lemma for 0 ≤ p1 < 2 . A similar proof can be used for p1 ≥ 12 .


(n)

Define the events A, B as
A ≡ p1 ≤ Pi ≤ p1 + n
B ≡ p1 + n ≤ Qi(n) ≤ p1 + (1 − 2p1 )an .
Then, for i ∈ {1, 2, . . . , n} and 0 ≤ p1 < 12 :


P i ∈ J (n) = P (A ∩ B)

= P (A) P B A .
So, given p1 ∈ (0, 1) and the assumption 0 < δ1 < fp < δ2 , for n large enough, we have
∫ p1 +n
P(A) =
fP (p)dp,
p1

so we can conclude that
n δ1 < P(A) < n δ2 .
We can find a δ such that δ1 < δ < δ2 and
P(A) = n δ.
We know
Qi(n) Pi = pi ∼ Uni f orm (pi, pi + (1 − 2pi )an ) ,
so according to Figures 6, for p1 ≤ pi ≤ p1 + n ,
p1 + (1 − 2p1 )an − p1 − n
P (B|Pi = pi ) =
pi + (1 − 2pi )an − pi
(1 − 2p1 )an − n
=
(1 − 2pi )an
(1 − 2p1 )an − n
≥
(1 − 2p1 )an
n
=1−
,
(1 − 2p1 )an

(8)

42

which implies
P (B| A) ≥ 1 −

n
.
(1 − 2p1 )an

Using (8) and (9), we can conclude



(n)
P i∈J
≥ n δ 1 −

(9)


n
.
(1 − 2p1 )an

Then, we can say that N (n) has a binomial distribution with expected value of N (n) greater than


n
nn δ 1 − (1−2p
, and by substituting n and an , we get
1 )an


h
i
β
β
1
(n)
≥ λn 2 .
E N
≥ δ n2 − 0
c (1 − 2p1 )
Now by using the above followed by Chebyshev’s


E
λ β
(n)
P N ≤ n 2 ≤ P N (n) ≤
2

inequality, as n goes to infinity,
 (n)  !
N
2

!
i
h
E N (n)
(n)
(n)
≥
≤ P N −E N
2


4V ar N (n)
≤

 2 .
E N (n)

Since N (n) is binomial, we also have
i

h

V ar N (n) ≤ E N (n) ,
so we can conclude for large enough n,


λ β
4
(n)

P N ≤ n2 ≤ 
2
E N (n)
4
≤
→ 0.
β
λn 2
Therefore,


λ β
(n)
P N > n2 → 1
2
As a result, N (n) → ∞ with high probability for large enough n.



43

A PPENDIX D
C OMPLETION OF THE P ROOF OF L EMMA 5
Let p1 ∈ (0, 1), and let N (n) be a random variable as above, i.e., N (n) → ∞ as n → ∞. Consider
the sequence of independent random variables Yi(n) ∼ Bernoulli(pi(n) ) for i = 1, 2, · · · , N (n) such
that

1) For all n and all i ∈ 1, 2, · · · N (n) , pi(n) − p1 ≤ ζn .
2) lim ζn = 0.
n→∞

Define
Y
then Y

(n)

N (n)
1 Õ (n)
, (n)
Y ,
N i=1 i

(n) d

→
− p1 .

Proof. Note
E[Y

(n)

N (n)
1 Õ (n)
] = (n)
p
N i=1 i
N (n)
1 Õ
≤ (n)
(p1 + ζn )
N i=1

=

1
· N (n) (p1 + ζn )
(n)
N

= p1 + ζn .
h (n) i
Similarly we can prove E Y
≥ p1 − ζn . Since as n becomes large, ζn → 0 and p1 ∈ (0, 1),
we can conclude
h (n) i
lim E Y
= p1 .

n→∞

Also,
 (n) 
V ar Y
=

≤
=
=

N (n)
Õ

1
N (n)

2

1
(N (n) )2
1
(N (n) )2

pi (1 − pi )

i=1
N (n)
Õ

(p1 + ζn ) (1 − p1 + ζn )

i=1

· N (n) (p1 + ζn ) (1 − p1 + ζn )

1
(p1 + ζn ) (1 − p1 + ζn ) .
N (n)

(10)

44

Thus,
 (n) 
lim V ar Y
=0

(11)

n→∞

By using (10), (11), and Chebyshev’s inequality, we can conclude
Y

(n) d

→
− p1 .


R EFERENCES
[1] N. Takbiri, A. Houmansadr, D. L. Goeckel, and H. Pishro-Nik, “Limits of location privacy under anonymization and
obfuscation,” in International Symposium on Information Theory (ISIT).

IEEE, 2017.

[2] F. S. Report, “Internet of things: Privacy and security in a connected world,” 2015.
[3] A. Mohsenia and N. K. Jha, “The quest for privacy in the internet of things,” IEEE Cloud Computing, 2016.
[4] A. Mohsen-Nia and N. K. Jha, “A comprehensive study of security of internet-of-things,” IEEE Transactions on Emerging
Topics in Computing, 2016.
[5] A. Ukil, S. Bandyopadhyay, and A. Pal, “IoT-privacy: To be private or not to be private,” in Computer Communications
Workshops (INFOCOM WKSHPS), IEEE Conference on.

IEEE, 2014, pp. 123–124.

[6] S. Hosseinzadeh, S. Rauti, S. Hyrynsalmi, A. LeppÃČÂd’nen, Ville Ukil, S. Bandyopadhyay, and A. Pal, “Security in the
internet of things through obfuscation and diversification,” in Computing, Communication and Security (ICCCS), IEEE
Conference on.

IEEE, 2015, pp. 123–124.

[7] N. Apthorpe, D. Reisman, and N. Feamster, “A Smart Home is No Castle: Privacy Vulnerabilities of Encrypted IoT Traffic,”
in Workshop on Data and Algorithmic Transparency, 2016.
[8] J. Unnikrishnan, “Asymptotically optimal matching of multiple sequences to source distributions and training sequences,”
IEEE Transactions on Information Theory, vol. 61, no. 1, pp. 452–468, 2015.
[9] G. P. Corser, H. Fu, and A. Banihani, “Evaluating location privacy in vehicular communications and applications,” IEEE
Transactions on Intelligent Transportation Systems, vol. 17, no. 9, pp. 2658–2667, 2016.
[10] B. Hoh and M. Gruteser, “Protecting location privacy through path confusion,” in Security and Privacy for Emerging Areas
in Communications Networks, 2005. SecureComm 2005. First International Conference on.

IEEE, 2005, pp. 194–205.

[11] J. Freudiger, M. Raya, M. Félegyházi, P. Papadimitratos, and J.-P. Hubaux, “Mix-zones for location privacy in vehicular
networks,” in CM Workshop on Wireless Networking for Intelligent Transportation Systems (WiN-ITS), 2007.
[12] Z. Ma, F. Kargl, and M. Weber, “A location privacy metric for v2x communication systems,” in Sarnoff Symposium, 2009.
SARNOFF’09. IEEE.

IEEE, 2009, pp. 1–6.

[13] R. Shokri, G. Theodorakopoulos, J.-Y. Le Boudec, and J.-P. Hubaux, “Quantifying location privacy,” in Security and
Privacy (SP), 2011 IEEE Symposium on.

IEEE, 2011, pp. 247–262.

[14] F. Naini, J. Unnikrishnan, P. Thiran, and M. Vetterli, “Where you are is who you are: User identification by matching
statistics,” IEEE Transactions on Information Forensics and Security, vol. 11, no. 2, pp. 358–372, 2016.
[15] R. Shokri, G. Theodorakopoulos, C. Troncoso, J.-P. Hubaux, and J.-Y. Le Boudec, “Protecting location privacy: optimal
strategy against localization attacks,” in Proceedings of the 2012 ACM conference on Computer and communications
security.

ACM, 2012, pp. 617–627.

45

[16] M. Gruteser and D. Grunwald, “Anonymous usage of location-based services through spatial and temporal cloaking,” in
Proceedings of the 1st international conference on Mobile systems, applications and services.

ACM, 2003, pp. 31–42.

[17] N. E. Bordenabe, K. Chatzikokolakis, and C. Palamidessi, “Optimal geo-indistinguishable mechanisms for location privacy,”
in Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security. ACM, 2014, pp. 251–
262.
[18] Z. Montazeri, A. Houmansadr, and H. Pishro-Nik, “Defining perfect location privacy using anonymization,” in 2016 Annual
Conference on Information Science and Systems (CISS).

IEEE, 2016, pp. 204–209.

[19] Z. Montazeri, A. Houmansadr, and H.Pishro-Nik, “Achieving perfect location privacy in markov models using anonymization,” in 2016 International Symposium on Information Theory and its Applications (ISITA2016), Monterey, USA, oct
2016.
[20] Z. Montazeri, A. Houmansadr, and H. Pishro-Nik, “Achieving Perfect Location Privacy in Wireless Devices Using
Anonymization,” IEEE Transaction on Information Forensics and Security, to appear, 2017.
[21] N. Takbiri, A. Houmansadr, D. Goeckel, and H. Pishro-Nik, “Fundamental limits of location privacy using anonymization,”
in Annual Conference on Information Science and Systems (CISS).

IEEE, 2017.

[22] S. Salamatian, A. Zhang, F. du Pin Calmon, S. Bhamidipati, N. Fawaz, B. Kveton, P. Oliveira, and N. Taft, “How to hide
the elephant-or the donkey-in the room: Practical privacy against statistical inference for large data.” in GlobalSIP, 2013,
pp. 269–272.
[23] I. Csiszár, “Almost independence and secrecy capacity,” Problemy Peredachi Informatsii, vol. 32, no. 1, pp. 48–57, 1996.
[24] F. P. Calmon, A. Makhdoumi, and M. Médard, “Fundamental limits of perfect privacy,” in Information Theory (ISIT), 2015
IEEE International Symposium on.

IEEE, 2015, pp. 1796–1800.

[25] L. Sankar, S. R. Rajagopalan, and H. V. Poor, “Utility-privacy tradeoffs in databases: An information-theoretic approach,”
Information Forensics and Security, IEEE Transactions on, vol. 8, no. 6, pp. 838–852, 2013.
[26] J. Liao, L. Sankar, F. du Pin Calmon, and V. Y. F. Tan, “Hypothesis testing under maximal leakage privacy constraints,”
CoRR, vol. abs/1701.07099, 2017. [Online]. Available: http://arxiv.org/abs/1701.07099
[27] K. Kalantari, L. Sankar, and O. Kosut, “On information-theoretic privacy with general distortion cost functions,” in 2017
IEEE International Symposium on Information Theory (ISIT).

Aachen, Germany: IEEE, 2017.

[28] H. Yamamoto, “A source coding problem for sources with additional outputs to keep secret from the receiver or wiretappers
(corresp.),” IEEE Transactions on Information Theory, vol. 29, no. 6, pp. 918–923, 1983.
[29] J. Liao, L. Sankar, V. Y. F. Tan, and F. du Pin Calmon, “Hypothesis testing in the high privacy limit,” CoRR, vol.
abs/1607.00533, 2016. [Online]. Available: http://arxiv.org/abs/1607.00533
[30] A. Ukil, S. Bandyopadhyay, and A. Pal, “Privacy for IoT: Involuntary privacy enablement for smart energy systems,” in
Communications (ICC), 2015 IEEE International Conference on.

IEEE, 2015, pp. 536–541.

[31] V. Sivaraman, H. H. Gharakheili, A. Vishwanath, R. Boreli, and O. Mehani, “Network-level security and privacy control
for smart-home IoT devices,” in Wireless and Mobile Computing, Networking and Communications (WiMob), 2015 IEEE
11th International Conference on.

IEEE, 2015, pp. 163–167.

[32] A. F. Harris, H. Sundaram, and R. Kravets, “Security and privacy in public IoT spaces,” in Computer Communication and
Networks (ICCCN), 2016 25th International Conference on.

IEEE, 2016, pp. 1–8.

[33] F. Dalipi and S. Y. Yayilgan, “Security and privacy considerations for IoT application on smart grids: Survey and research
challenges,” in Future Internet of Things and Cloud Workshops (FiCloudW), IEEE International Conference on.

IEEE,

2016, pp. 63–68.
[34] S. Li, A. Khisti, and A. Mahajan, “Privacy-optimal strategies for smart metering systems with a rechargeable battery,”
CoRR, vol. abs/1510.07170, 2015. [Online]. Available: http://arxiv.org/abs/1510.07170

46

[35] E. Al Alkeem, C. Y. Yeun, and M. J. Zemerly, “Security and privacy framework for ubiquitous healthcare IoT devices,” in
Internet Technology and Secured Transactions (ICITST), 2015 10th International Conference for. IEEE, 2015, pp. 70–75.
[36] A.-R. Sadeghi, C. Wachsmann, and M. Waidner, “Security and privacy challenges in industrial internet of things,” in Design
Automation Conference (DAC), 2015 52nd ACM/EDAC/IEEE.

IEEE, 2015, pp. 1–6.

[37] Y. Zhang, W. Tong, and S. Zhong, “On designing satisfaction-ratio-aware truthful incentive mechanisms for k-anonymity
location privacy,” IEEE Transactions on Information Forensics and Security, vol. 11, no. 11, pp. 2528–2541, 2016.
[38] R. Dewri and R. Thurimella, “Exploiting service similarity for privacy in location-based search queries,” IEEE Transactions
on Parallel and Distributed Systems, vol. 25, no. 2, pp. 374–383, 2014.
[39] B. Gedik and L. Liu, “Location privacy in mobile systems: A personalized anonymization model,” in Distributed Computing
Systems, 2005. ICDCS 2005. Proceedings. 25th IEEE International Conference on.

IEEE, 2005, pp. 620–629.

[40] G. Zhong and U. Hengartner, “A distributed k-anonymity protocol for location privacy,” in Pervasive Computing and
Communications, 2009. PerCom 2009. IEEE International Conference on.

IEEE, 2009, pp. 1–10.

[41] M. F. Mokbel, C.-Y. Chow, and W. G. Aref, “The new casper: query processing for location services without compromising
privacy,” in Proceedings of the 32nd international conference on Very large data bases.

VLDB Endowment, 2006, pp.

763–774.
[42] L. Sweeney, “k-anonymity: A model for protecting privacy,” International Journal of Uncertainty, Fuzziness and
Knowledge-Based Systems, vol. 10, no. 05, pp. 557–570, 2002.
[43] P. Kalnis, G. Ghinita, K. Mouratidis, and D. Papadias, “Preventing location-based identity inference in anonymous spatial
queries,” Knowledge and Data Engineering, IEEE Transactions on, vol. 19, no. 12, pp. 1719–1733, 2007.
[44] X. Liu, K. Liu, L. Guo, X. Li, and Y. Fang, “A game-theoretic approach for achieving k-anonymity in location based
services,” in INFOCOM, 2013 Proceedings IEEE.

IEEE, 2013, pp. 2985–2993.

[45] A. R. Beresford and F. Stajano, “Location privacy in pervasive computing,” IEEE Pervasive computing, no. 1, pp. 46–55,
2003.
[46] J. Freudiger, R. Shokri, and J.-P. Hubaux, “On the optimal placement of mix zones,” in Privacy enhancing technologies.
Springer, 2009, pp. 216–234.
[47] B. Palanisamy and L. Liu, “Mobimix: Protecting location privacy with mix-zones over road networks,” in Data Engineering
(ICDE), 2011 IEEE 27th International Conference on.

IEEE, 2011, pp. 494–505.

[48] R. Shokri, G. Theodorakopoulos, P. Papadimitratos, E. Kazemi, and J.-P. Hubaux, “Hiding in the mobile crowd:
Locationprivacy through collaboration,” IEEE transactions on dependable and secure computing, vol. 11, no. 3, pp. 266–
279, 2014.
[49] M. A. Zurbaran, K. Avila, P. Wightman, and M. Fernandez, “Near-rand: Noise-based location obfuscation based on random
neighboring points,” IEEE Latin America Transactions, vol. 13, no. 11, pp. 3661–3667, 2015.
[50] B. Hoh, M. Gruteser, H. Xiong, and A. Alrabady, “Preserving privacy in gps traces via uncertainty-aware path cloaking,”
in Proceedings of the 14th ACM conference on Computer and communications security.

ACM, 2007, pp. 161–171.

[51] B. Gedik and L. Liu, “Protecting location privacy with personalized k-anonymity: Architecture and algorithms,” Mobile
Computing, IEEE Transactions on, vol. 7, no. 1, pp. 1–18, 2008.
[52] M. Duckham and L. Kulik, “A formal model of obfuscation and negotiation for location privacy,” in Pervasive computing.
Springer, 2005, pp. 152–170.
[53] M. Duckham, L. Kulik, and A. Birtley, “A spatiotemporal model of strategies and counter strategies for location privacy
protection,” in Geographic Information Science.

Springer, 2006, pp. 47–64.

[54] M. Xue, P. Kalnis, and H. K. Pung, “Location diversity: Enhanced privacy protection in location based services,” in
Location and Context Awareness.

Springer, 2009, pp. 70–87.

47

[55] M. Wernke, P. Skvortsov, F. Dürr, and K. Rothermel, “A classification of location privacy attacks and approaches,” Personal
and Ubiquitous Computing, vol. 18, no. 1, pp. 163–175, 2014.
[56] Y. Cai and G. Xu, “Cloaking with footprints to provide location privacy protection in location-based services,” Jan. 1
2015, uS Patent App. 14/472,462. [Online]. Available: https://www.google.com/patents/US20150007341
[57] C.-Y. Chow, M. F. Mokbel, and X. Liu, “Spatial cloaking for anonymous location-based services in mobile peer-to-peer
environments,” GeoInformatica, vol. 15, no. 2, pp. 351–380, 2011.
[58] R. Cheng, Y. Zhang, E. Bertino, and S. Prabhakar, “Preserving user location privacy in mobile data management
infrastructures,” in Privacy Enhancing Technologies.

Springer, 2006, pp. 393–412.

[59] P. Kalnis, G. Ghinita, K. Mouratidis, and D. Papadias, “Preserving anonymity in location based services,” 2006.
[60] A. Khoshgozaran, C. Shahabi, and H. Shirani-Mehr, “Location privacy: going beyond k-anonymity, cloaking and
anonymizers,” Knowledge and Information Systems, vol. 26, no. 3, pp. 435–465, 2011.
[61] B. Bamba, L. Liu, P. Pesti, and T. Wang, “Supporting anonymous location queries in mobile environments with privacygrid,”
in Proceedings of the 17th international conference on World Wide Web.

ACM, 2008, pp. 237–246.

[62] J.-H. Um, H.-D. Kim, and J.-W. Chang, “An advanced cloaking algorithm using hilbert curves for anonymous location
based service,” in Social Computing (SocialCom), 2010 IEEE Second International Conference on.

IEEE, 2010, pp.

1093–1098.
[63] H. Zhangwei and X. Mingjun, “A distributed spatial cloaking protocol for location privacy,” in Networks Security Wireless
Communications and Trusted Computing (NSWCTC), 2010 Second International Conference on, vol. 2. IEEE, 2010, pp.
468–471.
[64] H. Kido, Y. Yanagisawa, and T. Satoh, “Protection of location privacy using dummies for location-based services,” in Data
Engineering Workshops, 2005. 21st International Conference on.

IEEE, 2005, pp. 1248–1248.

[65] J. Krumm, “A survey of computational location privacy,” Personal and Ubiquitous Computing, vol. 13, no. 6, pp. 391–399,
2009.
[66] P. Shankar, V. Ganapathy, and L. Iftode, “Privately querying location-based services with sybilquery,” in Proceedings of
the 11th international conference on Ubiquitous computing.

ACM, 2009, pp. 31–40.

[67] R. Chow and P. Golle, “Faking contextual data for fun, profit, and privacy,” in Proceedings of the 8th ACM workshop on
Privacy in the electronic society.

ACM, 2009, pp. 105–108.

[68] H. Kido, Y. Yanagisawa, and T. Satoh, “An anonymous communication technique using dummies for location-based
services,” in Pervasive Services, 2005. ICPS’05. Proceedings. International Conference on.

IEEE, 2005, pp. 88–97.

[69] H. Lu, C. S. Jensen, and M. L. Yiu, “Pad: privacy-area aware, dummy-based location privacy in mobile services,” in
Proceedings of the Seventh ACM International Workshop on Data Engineering for Wireless and Mobile Access.

ACM,

2008, pp. 16–23.
[70] J. Lee and C. Clifton, “Differential identifiability,” in Proceedings of the 18th ACM SIGKDD international conference on
Knowledge discovery and data mining.

ACM, 2012, pp. 1041–1049.

[71] K. Chatzikokolakis, C. Palamidessi, and M. Stronati, “Geo-indistinguishability: A principled approach to location privacy,”
in Distributed Computing and Internet Technology.

Springer, 2015, pp. 49–72.

[72] H. H. Nguyen, J. Kim, and Y. Kim, “Differential privacy in practice,” Journal of Computing Science and Engineering,
vol. 7, no. 3, pp. 177–186, 2013.
[73] A. Machanavajjhala, D. Kifer, J. Abowd, J. Gehrke, and L. Vilhuber, “Privacy: Theory meets practice on the map,” in
Data Engineering, 2008. ICDE 2008. IEEE 24th International Conference on.

IEEE, 2008, pp. 277–286.

[74] K. Chatzikokolakis, M. E. Andrés, N. E. Bordenabe, and C. Palamidessi, “Broadening the scope of differential privacy
using metrics.” in Privacy Enhancing Technologies.

Springer, 2013, pp. 82–102.

48

[75] R. Shokri, “Optimal user-centric data obfuscation,” arXiv preprint arXiv:1402.3426, 2014.
[76] K. Chatzikokolakis, C. Palamidessi, and M. Stronati, “Location privacy via geo-indistinguishability,” ACM SIGLOG News,
vol. 2, no. 3, pp. 46–69, 2015.
[77] M. E. Andrés, N. E. Bordenabe, K. Chatzikokolakis, and C. Palamidessi, “Geo-indistinguishability: Differential privacy for
location-based systems,” in Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security.
ACM, 2013, pp. 901–914.
[78] R. Dewri, “Local differential perturbations: Location privacy under approximate knowledge attackers,” Mobile Computing,
IEEE Transactions on, vol. 12, no. 12, pp. 2360–2372, 2013.
[79] M. J. Darakhshan, “Information-theoretic foundations of differential privacy,” in International Symposium on Foundations
and Practice of Security.

Springer, 2012.

[80] M. Ye and A. Barg, “Optimal schemes for discrete distribution estimation under locally differential privacy,” CoRR, vol.
abs/1702.00610, 2017. [Online]. Available: http://arxiv.org/abs/1702.00610
[81] R. Shokri, G. Theodorakopoulos, G. Danezis, J.-P. Hubaux, and J.-Y. Le Boudec, “Quantifying location privacy: the case
of sporadic location exposure,” in Privacy Enhancing Technologies.

Springer, 2011, pp. 57–76.

[82] H. Li, H. Zhu, S. Du, X. Liang, and X. Shen, “Privacy leakage of location sharing in mobile social networks: Attacks and
defense,” IEEE Transactions on Dependable and Secure Computing, vol. PP, no. 99, 2016.
[83] A.-M. Olteanu, K. Huguenin, R. Shokri, M. Humbert, and J.-P. Hubaux, “Quantifying interdependent privacy risks with
location data,” IEEE Transactions on Mobile Computing, vol. PP, no. 99, pp. 1–1, 2016.
[84] X. Zhang, X. Gui, F. Tian, S. Yu, and J. An, “Privacy quantification model based on the bayes conditional risk in locationbased services,” Tsinghua Science and Technology, vol. 19, no. 5, pp. 452–462, 2014.
[85] L. Yu, L. Liu, and C. Pu, “Dynamic differential location privacy with personalized error bounds,” in The Network and
Distributed System Security Symposium, 2017.
[86] I. Ullah and M. A. Shah, “A novel model for preserving location privacy in internet of things,” in Automation and Computing
(ICAC), 2016 22nd International Conference on.

IEEE, 2016, pp. 542–547.

[87] L. Zhou, Q. Wen, and H. Zhang, “Preserving sensor location privacy in internet of things,” in Computational and Information
Sciences (ICCIS), 2012 Fourth International Conference on.

IEEE, 2012, pp. 856–859.

[88] J. Sathishkumar and D. R. Patel, “Enhanced location privacy algorithm for wireless sensor network in internet of things,”
in Internet of Things and Applications (IOTA), International Conference on.

IEEE, 2016, pp. 208–212.

[89] M. E. Andres, N. E. Bordenabe, K. Chatzikokolakis, and C. Palamidessi, “Geo-indistinguishability: differential privacy for
location-based systems,” in Proceedings of the 2013 ACM SIGSAC conference on Computer and communications security,
New York, NY, 2013, pp. 901–914.

