1. bookVolume 2016 (2016): Issue 4 (October 2016)
Journal Details
First Published
16 Apr 2015
Publication timeframe
4 times per year
access type Open Access

Location Privacy with Randomness Consistency

Published Online: 14 Jul 2016
Page range: 62 - 82
Received: 29 Feb 2016
Accepted: 02 Jun 2016
Journal Details
First Published
16 Apr 2015
Publication timeframe
4 times per year

Location-Based Social Network (LBSN) applications that support geo-location-based posting and queries to provide location-relevant information to mobile users are increasingly popular, but pose a location-privacy risk to posts. We investigated existing LBSNs and location privacy mechanisms, and found a powerful potential attack that can accurately locate users with relatively few queries, even when location data is well secured and location noise is applied. Our technique defeats previously proposed solutions including fake-location detection and query rate limits.


[1] Boundaries - Census Blocks (Chicago, IL). http://www.cityofchicago.org/city/en/depts/doit/dataset/boundaries_-_censusblocks.html.Search in Google Scholar

[2] Facebook. Online socail mobile application. https://itunes.apple.com/us/app/facebook/id284882215?mt=8.Search in Google Scholar

[3] Fact Finder. http://factfinder.census.gov/faces/nav/jsf/pages/index.xhtml.Search in Google Scholar

[4] Hinge. Online dating mobile application. http://hinge.co.Search in Google Scholar

[5] Match. Online dating mobile application. http://www.match.com.Search in Google Scholar

[6] Skout. http://www.skout.com.Search in Google Scholar

[7] Tinder. Online dating mobile application. https://www.gotinder.com.Search in Google Scholar

[8] Whisper. Anonymous mobile social network. https: //whisper.sh.Search in Google Scholar

[9] Yelp. http://www.yelp.com.Search in Google Scholar

[10] Yik Yak. Anonymous mobile social network. http://www.yikyakapp.com.Search in Google Scholar

[11] Police: Thieves robbed homes based on Facebook, social media sites. http://www.wmur.com/Police-Thieves-Robbed-Homes-Based-On-Facebook-Social-Media-Sites/11861116, 2010.Search in Google Scholar

[12] New social App has juicy posts, all anonymous. http:// www.nytimes.com/2014/03/19/technology/new-social-apphas-juicy-posts-but-no-names.html?_r=0, 2014.Search in Google Scholar

[13] G. Ananthanarayanan, V. N. Padmanabhan, L. Ravindranath, and C. A. Thekkath. Combine: leveraging the power of wireless peers through collaborative downloading. In Proceedings of the 5th international conference on Mobile systems, applications and services, pages 286-298. ACM, 2007.Search in Google Scholar

[14] 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, pages 901-914. ACM, 2013.Search in Google Scholar

[15] C. A. Ardagna, M. Cremonini, E. Damiani, S. D. C. Di Vimercati, and P. Samarati. Location privacy protection through obfuscation-based techniques. In Data and Applications Security XXI, pages 47-60. Springer, 2007.Search in Google Scholar

[16] M. Bellare and P. Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. In Proceedings of the 1st ACM conference on Computer and communications security, pages 62-73. ACM, 1993.Search in Google Scholar

[17] G. Danezis and P. Mittal. Sybilinfer: Detecting sybil nodes using social networks. In NDSS. San Diego, CA, 2009.Search in Google Scholar

[18] R. A. Finkel and J. L. Bentley. Quad trees a data structure for retrieval on composite keys. Acta informatica, 4(1):1-9, 1974.Search in Google Scholar

[19] 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, pages 620-629. IEEE, 2005.Search in Google Scholar

[20] A. Gendar and A. Lisberg. How cell phone helped cops nail key murder suspect. Secret ’pings’ that gave bouncer away. http://www.nydailynews.com/archives/news/cell-phonehelped-cops-nail-key-murder-suspect-secret-pings-gavebouncer-article-1.599672, 2006.Search in Google Scholar

[21] G. Ghinita, P. Kalnis, A. Khoshgozaran, C. Shahabi, and K.- L. Tan. Private queries in location based services: anonymizers are not necessary. In Proceedings of the 2008 ACM SIGMOD international conference on Management of data, pages 121-132. ACM, 2008.Search in Google Scholar

[22] P. Golle and K. Partridge. On the anonymity of home/work location pairs. In Pervasive computing, pages 390-397. Springer, 2009.Search in Google Scholar

[23] F. Grace. Stalker victims should check for GPS. http://www.cbsnews.com/news/stalker-victims-should-checkfor-gps/, 2003.Search in Google Scholar

[24] 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, pages 31-42. ACM, 2003.Search in Google Scholar

[25] P. Harremoës and F. Topsøe. Maximum entropy fundamentals. Entropy, 3(3):191-226, 2001.Search in Google Scholar

[26] M. Hendrickson. The state of location-based social networking on the iPhone. http://techcrunch.com/2008/09/28/thestate-of-location-based-social-networking-on-the-iphone, 2008.Search in Google Scholar

[27] T. Jiang, H. J. Wang, and Y.-C. Hu. Preserving location privacy in wireless lans. In Proceedings of the 5th international conference on Mobile systems, applications and services, pages 246-257. ACM, 2007.Search in Google Scholar

[28] 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, 19(12):1719-1733, 2007.Search in Google Scholar

[29] J. Krumm. Inference attacks on location tracks. In Pervasive Computing, pages 127-143. Springer, 2007.Search in Google Scholar

[30] M. Li, H. Zhu, Z. Gao, S. Chen, L. Yu, S. Hu, and K. Ren. All your location are belong to us: Breaking mobile social networks for automated user location tracking. In Proceedings of the 15th ACM international symposium on Mobile ad hoc networking and computing, pages 43-52. ACM, 2014.Search in Google Scholar

[31] N. Li and G. Chen. Analysis of a location-based social network. In Computational Science and Engineering, 2009. CSE’09. International Conference on, volume 4, pages 263-270. Ieee, 2009.Search in Google Scholar

[32] M. F. Mokbel, C.-Y. Chow, and W. G. Aref. The new casper: A privacy-aware location-based database server. In Data Engineering, 2007. ICDE 2007. IEEE 23rd International Conference on, pages 1499-1500. IEEE, 2007.Search in Google Scholar

[33] M. Motani, V. Srinivasan, and P. S. Nuggehalli. Peoplenet: engineering a wireless virtual social network. In Proceedings of the 11th annual international conference on Mobile computing and networking, pages 243-257. ACM, 2005.Search in Google Scholar

[34] A. Narayanan, N. Thiagarajan, M. Lakhani, M. Hamburg, and D. Boneh. Location privacy via private proximity testing. In NDSS. Citeseer, 2011.Search in Google Scholar

[35] 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.Search in Google Scholar

[36] I. Polakis, G. Argyros, T. Petsios, S. Sivakorn, and A. D. Keromytis. Where’s wally?: Precise user discovery attacks in location proximity services. In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, pages 817-828. ACM, 2015.Search in Google Scholar

[37] K. P. Puttaswamy, S. Wang, T. Steinbauer, D. Agrawal, A. El Abbadi, C. Kruegel, and B. Y. Zhao. Preserving location privacy in geosocial applications. Mobile Computing, IEEE Transactions on, 13(1):159-173, 2014.Search in Google Scholar

[38] K. P. Puttaswamy and B. Y. Zhao. Preserving privacy in location-based mobile social applications. In Proceedings of the Eleventh Workshop on Mobile Computing Systems & Applications, pages 1-6. ACM, 2010.Search in Google Scholar

[39] B. Schilit, J. Hong, and M. Gruteser. Wireless location privacy protection. Computer, 36(12):135-137, 2003.Search in Google Scholar

[40] R. Shokri, G. Theodorakopoulos, J.-Y. Le Boudec, and J.- P. Hubaux. Quantifying location privacy. In Security and privacy (sp), 2011 ieee symposium on, pages 247-262. IEEE, 2011.Search in Google Scholar

[41] M. Siegler. Foodspotting is a location-based game that will make your mouth water. http://techcrunch.com/2010/03/04/foodspotting.Search in Google Scholar

[42] M. Veytsman. How I was able to track the location of any Tinder user. http://blog.includesecurity.com/2014/02/howi-was-able-to-track-location-of-any.html.Search in Google Scholar

[43] G. Wang, B. Wang, T. Wang, A. Nika, H. Zheng, and B. Y. Zhao. Whispers in the dark: Analysis of an anonymous social network. In IMC ’14 Proceedings of the 2014 Conference on Internet Measurement Conference, pages 137-150, New York, USA, 2014. ACM.Search in Google Scholar

[44] Z. Yang, C. Wilson, X. Wang, T. Gao, B. Y. Zhao, and Y. Dai. Uncovering social network sybils in the wild. ACM Transactions on Knowledge Discovery from Data (TKDD), 8(1):2, 2014.Search in Google Scholar

[45] G. Zhong, I. Goldberg, and U. Hengartner. Louis, lester and pierre: Three protocols for location privacy. In Privacy Enhancing Technologies, pages 62-76. Springer, 2007.Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo