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].