ABSTRACT
Concerns on location privacy frequently arise with the rapid development of GPS enabled devices and location-based applications. While spatial transformation techniques such as location perturbation or generalization have been studied extensively, most techniques rely on syntactic privacy models without rigorous privacy guarantee. Many of them only consider static scenarios or perturb the location at single timestamps without considering temporal correlations of a moving user's locations, and hence are vulnerable to various inference attacks. While differential privacy has been accepted as a standard for privacy protection, applying differential privacy in location based applications presents new challenges, as the protection needs to be enforced on the fly for a single user and needs to incorporate temporal correlations between a user's locations.
In this paper, we propose a systematic solution to preserve location privacy with rigorous privacy guarantee. First, we propose a new definition, "δ-location set" based differential privacy, to account for the temporal correlations in location data. Second, we show that the well known l1-norm sensitivity fails to capture the geometric sensitivity in multidimensional space and propose a new notion, sensitivity hull, based on which the error of differential privacy is bounded. Third, to obtain the optimal utility we present a planar isotropic mechanism (PIM) for location perturbation, which is the first mechanism achieving the lower bound of differential privacy. Experiments on real-world datasets also demonstrate that PIM significantly outperforms baseline approaches in data utility.
- M. E. Andrés, N. E. Bordenabe, K. Chatzikokolakis, and C. Palamidessi. Geo-indistinguishability: Differential privacy for location-based systems. CCS '13, pages 901--914. ACM, 2013. Google ScholarDigital Library
- G. Apostolos. Notes on isotropic convex bodies. 2003.Google Scholar
- A. R. Beresford and F. Stajano. Location privacy in pervasive computing. Pervasive Computing, IEEE, 2(1):46--55, 2003. Google ScholarDigital Library
- A. Bhaskara, D. Dadush, R. Krishnaswamy, and K. Talwar. Unconditional differentially private mechanisms for linear queries. STOC '12, New York, NY, USA, 2012. Google ScholarDigital Library
- K. Chatzikokolakis, M. Andrés, N. Bordenabe, and C. Palamidessi. Broadening the scope of differential privacy using metrics. Lecture Notes in Computer Science, pages 82--102. Springer Berlin Heidelberg, 2013.Google Scholar
- R. Chen, B. C. Fung, B. C. Desai, and N. M. Sossou. Differentially private transit data publication: a case study on the montreal transportation system. KDD '12, pages 213--221, New York, NY, USA, 2012. ACM. Google ScholarDigital Library
- E. Cho, S. A. Myers, and J. Leskovec. Friendship and mobility: User movement in location-based social networks. KDD '11, pages 1082--1090, New York, NY, USA, 2011. Google ScholarDigital Library
- A. Dey, J. Hightower, E. de Lara, and N. Davies. Location-based services. Pervasive Computing, IEEE, 9(1):11--12, 2010. Google ScholarDigital Library
- C. Dwork. Differential privacy. In Automata, languages and programming, pages 1--12. Springer, 2006. Google ScholarDigital Library
- C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. Proceedings of the 3rd Theory of Cryptography Conference, 2006. Google ScholarDigital Library
- C. Dwork, M. Naor, T. Pitassi, and G. N. Rothblum. Differential privacy under continual observation. STOC '10, pages 715--724, New York, NY, USA, 2010. ACM. Google ScholarDigital Library
- L. Fan, L. Xiong, and V. S. Sunderam. Differentially private multi-dimensional time series release for traffic monitoring. In DBSec, pages 33--48, 2013. Google ScholarDigital Library
- C. Fang and E.-C. Chang. Differential privacy with(δ)-neighbourhood for spatial and dynamic datasets. ASIA CCS '14, pages 159--170, New York, NY, USA, 2014. ACM. Google ScholarDigital Library
- B. Gedik and L. Liu. Protecting location privacy with personalized k-anonymity: Architecture and algorithms. Mobile Computing, IEEE Transactions on, 7(1):1--18, 2008. Google ScholarDigital Library
- G. Ghinita. Privacy for Location-Based Services. Synthesis Lectures on Information Security, Privacy, and Tru. Morgan & Claypool, 2013. Google ScholarDigital Library
- M. C. Gonzalez, C. A. Hidalgo, and A.-L. Barabási. Understanding individual human mobility patterns. Nature, 453(7196):779--782, June 2008.Google ScholarCross Ref
- M. Götz, S. Nath, and J. Gehrke. Maskit: Privately releasing user context streams for personalized mobile applications. SIGMOD '12, New York, NY, USA, 2012. Google ScholarDigital Library
- M. Hardt and K. Talwar. On the geometry of differential privacy. In STOC, pages 705--714. ACM, 2010. Google ScholarDigital Library
- X. He, A. Machanavajjhala, and B. Ding. Blowfish privacy: Tuning privacy-utility trade-offs using policies. SIGMOD '14, pages 1447--1458, New York, NY, USA, 2014. ACM. Google ScholarDigital Library
- I. A. Junglas and R. T. Watson. Location-based services. Communications of the ACM, 51(3):65--69, 2008. Google ScholarDigital Library
- D. Kifer and A. Machanavajjhala. No free lunch in data privacy. In SIGMOD, pages 193--204. ACM, 2011. Google ScholarDigital Library
- J. Krumm. Inference attacks on location tracks. PERVASIVE'07, pages 127--143, Berlin, Heidelberg, 2007. Springer-Verlag. Google ScholarDigital Library
- J. Krumm. A survey of computational location privacy. Personal and Ubiquitous Computing, 13(6):391--399, 2009. Google ScholarDigital Library
- H. Li, L. Xiong, and X. Jiang. Differentially private synthesization of multi-dimensional data using copula functions. EDBT'14, pages 475--486, 2014.Google Scholar
- L. Liao, D. J. Patterson, D. Fox, and H. Kautz. Learning and inferring transportation routines. Artif. Intell., 171(5--6):311--331, Apr. 2007. Google ScholarDigital Library
- L. Lovász and S. Vempala. Hit-and-run from a corner. STOC '04, pages 310--314, New York, NY, USA, 2004. ACM. Google ScholarDigital Library
- L. Lovász and S. Vempala. Simulated annealing in convex bodies and an o*(n4) volume algorithm. J. Comput. Syst. Sci., 72(2):392--417, Mar. 2006. Google ScholarDigital Library
- McSherry. Privacy integrated queries: an extensible platform for privacy-preserving data analysis. In SIGMOD '09, pages 19--30, New York, NY, USA, 2009. ACM. Google ScholarDigital Library
- V. Milman and A. Pajor. Isotropic position and inertia ellipsoids and zonoids of the unit ball of a normed n-dimensional space. Lecture Notes in Mathematics, pages 64--104. Springer Berlin Heidelberg, 1989.Google Scholar
- A. Nikolov, K. Talwar, and L. Zhang. The geometry of differential privacy: The sparse and approximate cases. ACM STOC '13, pages 351--360, NY, USA, 2013. Google ScholarDigital Library
- J. O'Rourke. Computational Geometry in C. Cambridge University Press, New York, NY, USA, 2nd edition, 1998. Google ScholarDigital Library
- S. Papadopoulos, S. Bakiras, and D. Papadias. Nearest neighbor search with strong location privacy. Proceedings of the VLDB Endowment, 3(1--2):619--629, 2010. Google ScholarDigital Library
- W. H. Qardaji, W. Yang, and N. Li. Differentially private grids for geospatial data. In ICDE, pages 757--768, 2013. Google ScholarDigital Library
- S. Qiao, C. Tang, H. Jin, T. Long, S. Dai, Y. Ku, and M. Chau. Putmode: prediction of uncertain trajectories in moving objects databases. Applied Intelligence, 33(3):370--386, Dec. 2010. Google ScholarDigital Library
- V. Rastogi, M. Hay, G. Miklau, and D. Suciu. Relationship privacy: output perturbation for queries with joins. PODS '09, pages 107--116, New York, NY, USA, 2009. ACM. Google ScholarDigital Library
- M. Rudelson. Random vectors in the isotropic position. J. Funct. Anal, pages 60--72, 1999.Google ScholarCross Ref
- R. Shokri, G. Theodorakopoulos, J.-Y. Le Boudec, and J.-P. Hubaux. Quantifying location privacy. IEEE SP '11, pages 247--262, Washington, DC, USA, 2011. Google ScholarDigital Library
- C. Song, Z. Qu, N. Blumm, and A.-L. Barabási. Limits of predictability in human mobility. Science, 327(5968):1018--1021, 2010.Google ScholarCross Ref
- S. Vempala. Geometric random walks: a survey. Combinatorial and Computational Geometry, pages 573--612, 2005.Google Scholar
- Y. Zheng, X. Xie, and W.-Y. Ma. Geolife: A collaborative social networking service among user, location and trajectory. IEEE Data Eng. Bull., 33(2):32--39, 2010.Google Scholar
Index Terms
- Protecting Locations with Differential Privacy under Temporal Correlations
Recommendations
Preserving location privacy without exact locations in mobile services
Privacy preservation has recently received considerable attention in location-based services (LBSs). A large number of location cloaking algorithms have been proposed for protecting the location privacy of mobile users. However, most existing cloaking ...
A Survey Of differential privacy-based techniques and their applicability to location-Based services
AbstractThe widespread use of mobile devices such as smartphones, tablets, and smartwatches has led users to constantly generate various location data during their daily activities. Consequently, a growing interest has been seen in location-...
Protecting location privacy using location semantics
KDD '11: Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data miningAs the use of mobile devices increases, a location-based service (LBS) becomes increasingly popular because it provides more convenient context-aware services. However, LBS introduces problematic issues for location privacy due to the nature of the ...
Comments