Abstract
With the tremendous increase in the number of smart phones, App stores have been overwhelmed with applications requiring geo-location access in order to provide their users better services through personalization. Revealing a user’s location to these third party Apps, no matter at what frequency, is a severe privacy breach which can have unpleasant social consequences. In order to prevent inference attacks derived from geo-location data, a number of location obfuscation techniques have been proposed in the literature. However, none of them provides any objective measure of privacy guarantee. Some work has been done to define differential privacy for geo-location data in the form of geo-indistinguishability with l privacy guarantee. These techniques do not utilize any prior background information about the Points of Interest (PoIs) of a user and apply Laplacian noise to perturb all the location coordinates. Intuitively, the utility of such a mechanism can be improved if the noise distribution is derived after considering some prior information about PoIs. In this paper, we apply the standard definition of differential privacy on geo-location data. We use first principles to model various privacy and utility constraints, prior background information available about the PoIs (distribution of PoI locations in a 1D plane) and the granularity of the input required by different types of apps, in order to produce a more accurate and a utility maximizing differentially private algorithm for geo-location data at the OS level. We investigate this for a particular category of Apps and for some specific scenarios. This will also help us to verify whether Laplacian noise is still the optimal perturbation when we have such prior information.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
References
Bindschaedler, V., Shokri, R.: Synthesizing plausible privacy preserving location traces. IEEE, August 2016
Andrés, M., Bordenable, N.E., Chatzikokolakis, K., Palamidessi, C.: Geo-indistinguishability: differential privacy for location-based systems. Springer, Switzerland (2015)
Andreś, M., Bordenable, N.E., Chatzikokolakis, K., Palamidessi, C.: Optimal geo-indistinguishable mechanisms for location privacy. In: Proceedings of the 2014 ACM SIGSAC, Conference on Computer and Communications Security
Polakis, I., Argyros, G., Petsios, T., Sivakorn, S., Keromytis, A.D.: Where’s Wally? Precise user discovery attacks in location proximity services. In: Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security (2015)
Srivastava, V., Naik, V., Gupta, A.: Privacy breach of social relation from location based mobile applications. In: IEEE CS Home, pp. 324–328 (2014)
Liao, L., Fox, D., Kautz, H.: Extracting places and activities from GPS traces using hierarchical conditional random fields. Int. J. Robot. Res. Arch. 26(1), 119–134 (2007)
Brenner, H., Nissim, K.: Impossibility of differentially private universally optimal mechanisms. In: 2010 51st Annual IEEE Symposium Foundations of Computer Science (FOCS)
Nunez, M., Frignal, J.: Geo–location inference attacks: from modelling to privacy risk assessment. In: EDCC 2014 Proceedings of the 2014 Tenth European Dependable Computing Conference
Gruteser, M., Grunwald, D.: Anonymous usage of location–based service through spatial and temporal cloaking. In: Proceeding MobiSys 2003 Proceedings of the 1st International Conference on Mobile Systems, Applications and Services
Kulik, L., Duckham, M.: A Formal Model of Obfuscation and Negotiation for Location Privacy. PERVASIVE Springer-Verlag, Heidelberg (2005)
Ardagna, C.A., Cremonini, M., Damiani, E., Samarati, P.: Location privacy protection through obfuscation–based techniques. In: IFIP Annual Conference on Data and Applications Security and Privacy DBSec 2007: Data and Applications Security
Chatzikokolakis, K., Elsalamouny, E., Palamidessi, C.: Practical Mechanisms for Location Privacy. Inria and LIX, cole Polytechnique
ElSalamouny, E., Gambs, S.: Differential privacy models for location based services. Trans. Data Priv. 9, 15–48 (2016). INRIA, France
Acknowledgement
We would like to thank Dr. Aleksandra Korolova for being the guiding light throughout the course of this paper.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Appendices
Appendix A
The domain \(\mathbb {D}\) and range \(\mathbb {R}\) is the x-axis discretized with step \(\delta \). Let p be the maximum value that should occur at the original location \(i=(0,0)\). The probability values for output points z at points \(\in (\delta , \infty )\) are smaller than p but greater than points \(\in (-\delta , -\infty )\).
i\z | \(-\infty \) | \(\ldots \) | \(-\delta \) | 0 | \(\delta \) | \(\ldots \) | +\(\infty \) |
---|---|---|---|---|---|---|---|
-\(\infty \) | |||||||
\(\vdots \) | |||||||
-\(\delta \) | p | ||||||
0 | \(\downarrow \) | p | \(\uparrow \) | ||||
\(\delta \) | p | ||||||
\(\vdots \) | |||||||
\(\infty \) |
Now using the privacy constraint–
\(\sum _{z=-\infty }^{\infty } P(i, z,\psi ){=}1\)
\(\sum _{z=-\infty }^{-\delta } P(i,z,\psi ) + p + \sum _{z=\delta }^{\infty }P(i,z,\psi ) =1\) ... (1)
or \(A + B + C=1\)
\(A= \sum _{z=-\infty }^{-\delta } P(i,z,\psi ); B= p; C= \sum _{z=\delta }^{\infty }P(i,z,\psi )\)
For C, we can use differential privacy constraint-
\(\frac{P(i, K(i){=}z,\psi )}{P(j, K(j){=}z, \psi )} \le e^{\rho }; |i-j|\le \delta \)
\(i=(0,0), P(0,0, \psi )=p\) and \( j=(\delta ,0)\) so we can write \(P(\delta ,z, \psi )\)–
For \(P(2\delta ,z, \psi )\), we have–
\(P(2\delta ,z, \psi )\le p.e^{-2\rho }\) and in general,
\(P(x\delta ,z, \psi )\le p.e^{-x\rho }\), therefore we can rewrite C in Eq. (1) as
\(\sum \nolimits _{x=\delta }^{\infty }p.e^{x\rho }\) ... (2)
For part A of Eq. (1), we have \(P(0,-\delta ,\psi )<P(0,\delta , \psi )<p\). With utility constraint of \(min.|z-i|\), along with the constraint of having higher probability of outputting points in the direction of prior, we can say that after some point \(\alpha \delta \) it would be better to output points near the original location i either in the direction opposite to the prior, i.e.,
\(P(0,-\delta , \psi )\ge P(0,\alpha \delta ,\psi )= p.e^{-\alpha \rho }\).
While maintaining the differential privacy constraint for the points \(-\delta , -2\delta , ...\), we can write–
\(P(0,-\delta ,\psi )\ge e^{-\rho }.P(0,-2\delta , \psi )\), or
\(p.e^{-\alpha \rho }. e^{\rho } \ge P(0,-2\delta ,\psi )\) and in general–
\(e^{(x-\alpha )\rho }.p\ge P(0, -(x-1)\delta ,\psi )\), therefore we can write A in Eq. (1) as
\(\sum \nolimits _{x={-\infty }^{-\delta }}e^{(x-\alpha )\rho }.p\) ... (3)
Combining (1), (2) and (3)-
\(\sum \nolimits _{x={-\infty }^{-\delta }}e^{(x-\alpha )\rho }.p + p + \sum \nolimits _{x=\delta }^{\infty }p.e^{x\rho } \le 1\)
Solving this with \(\delta =1\) we get,
\(p\le \frac{(1-e^{-\rho })}{1+e^{-(\alpha +1)\rho }}\)
Appendix B
For query 2, using the constraints we can write–
\(\sum _{z=-{\infty }}^{\infty } P(i, z,\psi ){=}1\)
\(\sum _{z=-{\infty }}^{-\delta } P(i,z,\psi ) + p + \sum _{z={\delta }}^L P(i,z,\psi ) + \sum _{z=L}^{2L}P(i,z,\psi ) + p+ \sum _{z=2L}^{\infty }P(i,z,\psi ) =1\) ... (1)
or \(A + B + C + D + E +F=1\)
Since we are interested in the magnitude of the probability, for the sake of simplicity, we can safely apply same approximation before i and after 2L, and using the symmetry around L, we can write–
\(p \le \frac{1}{\frac{e^{-\alpha \rho }+e^{-2\alpha .L.\rho }}{1-e^{-\alpha \rho }}+2+\frac{2.e^{-\rho }[1-(e^{-\rho .L})]}{1-e^{-\rho }}}\)
or approximately– \(p\le \frac{(1-e^{-\rho })}{2(1+e^{-(\alpha +1)\rho })}\), when \(\delta =1\)
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Palia, A., Tandon, R. (2019). Optimizing Noise Level for Perturbing Geo-location Data. In: Arai, K., Kapoor, S., Bhatia, R. (eds) Advances in Information and Communication Networks. FICC 2018. Advances in Intelligent Systems and Computing, vol 887. Springer, Cham. https://doi.org/10.1007/978-3-030-03405-4_5
Download citation
DOI: https://doi.org/10.1007/978-3-030-03405-4_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-03404-7
Online ISBN: 978-3-030-03405-4
eBook Packages: EngineeringEngineering (R0)