research-article

Geosocial query with user-controlled privacy

Authors:

Sherman S. M. Chow,

Asma AloufiAuthors Info & Claims

WiSec '17: Proceedings of the 10th ACM Conference on Security and Privacy in Wireless and Mobile Networks

Pages 163 - 172

https://doi.org/10.1145/3098243.3098245

Published: 18 July 2017 Publication History

Abstract

Geosocial applications collect (and record) users' precise location data to perform proximity computations, such as notifying a user or triggering a service when a friend is within geographic proximity. With the growing popularity of mobile devices that have sophisticated localization capability it becomes more convenient and tempting to share location data. But the precise location data in plaintext not only exposes user's whereabouts but also mobility patterns that are sensitive and cannot be changed easily. This paper proposes cryptographic protocols on top of spatial cloaking to reduce the resolution of location and balance between data utility and privacy. Specifically we interest in the setting that allows users to send periodic updates of precise coordinates and define privacy preferences to control the granularity of the location, both in an encrypted format. Our system supports three kinds of user queries --- "Where is this user?", "Who is nearby?", and "How close is this user from another user?". Also, we develop a new algorithm to improve the multidimensional data access by reducing significant masking error. Our prototype and various performance evaluations on different platforms demonstrated that our system is practical.

References

[1]

Gilad Asharov, Abhishek Jain, Adriana López-Alt, Eran Tromer, Vinod Vaikuntanathan, and Daniel Wichs. 2012. Multiparty Computation with Low Communication, Computation and Interaction via Threshold FHE. In EUROCRYPT. Springer-Verlag.

Digital Library

[2]

Omer Barak, Gabriella Cohen, and Eran Toch. 2016. Anonymizing mobility data using semantic cloaking. Pervasive and Mobile Computing, Special Issue on Security and Privacy in Mobile Clouds 28 (2016), 102--112.

Digital Library

[3]

A.R. Beresford and F. Stajano. 2003. Location Privacy in Pervasive Computing. Pervasive Computing, IEEE 2, 1 (Jan 2003), 46--55.

Digital Library

[4]

Claudio Bettini and Daniele Riboni. 2015. Privacy Protection in Pervasive Systems: State of the Art and Technical Challenges. Pervasive and Mobile Computing 17, Part B (2015), 159 -- 174.

Digital Library

[5]

Joppe W. Bos, Kristin Lauter, Jake Loftus, and Michael Naehrig. 2013. Improved Security for a Ring-Based Fully Homomorphic Encryption Scheme. In Cryptography and Coding. LNCS, Vol. 8308. Springer Berlin Heidelberg, 45--64.

Digital Library

[6]

Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. 2012. (Leveled) Fully Homomorphic Encryption without Bootstrapping. In Innovations in Theoretical Computer Science (ITCS). 309--325.

Digital Library

[7]

Zvika Brakerski and Vinod Vaikuntanathan. 2011. Efficient Fully Homomorphic Encryption from (Standard) LWE. In FOCS. IEEE Computer Society, 97--106.

Digital Library

[8]

Jung Hee Cheon, Miran Kim, and Kristin Lauter. 2015. Homomorphic Computation of Edit Distance. In Workshop on Encrypted Computing and Applied Homomorphic Cryptography (WAHC). ACM, Isla Verde, Puerto Rico.

[9]

Sherman S. M. Chow, Jie-Han Lee, and Lakshminarayanan Subramanian. 2009. Two-Party Computation Model for Privacy-Preserving Queries over Distributed Databases. In Network and Distributed System Security Symposium (NDSS).

[10]

Sunny Consolvo, Ian E. Smith, Tara Matthews, Anthony LaMarca, Jason Tabert, and Pauline Powledge. 2005. Location Disclosure to Social Relations: Why, when, & What People Want to Share. In Human Factors in Computing Systems (CHI). ACM, New York, NY, USA, 81--90.

Digital Library

[11]

Cynthia Dwork. 2006. Differential Privacy. In ICALP (LNCS), Vol. 4052. Springer Verlag, Venice, Italy, 1--12.

Digital Library

[12]

Taher El Gamal. 1985. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. In CRYPTO. Springer-Verlag New York, Inc., Santa Barbara, California, USA, 10--18.

Digital Library

[13]

Junfeng Fan and Frederik Vercauteren. 2012. Somewhat Practical Fully Homomorphic Encryption. (2012).

[14]

Uriel Feige, Amos Fiat, and Adi Shamir. 1988. Zero-Knowledge Proofs of Identity. J. Cryptology 1, 2 (June 1988), 77--94.

Digital Library

[15]

Julien Freudiger, Maxim Raya, Márk Félegyházi, Panos Papadimitratos, and Jean-Pierre Hubaux. 2007. Mix-Zones for Location Privacy in Vehicular Networks. In Proceeding of Win-ITS'07. Vancouver, British Columbia.

[16]

Volker Gaede and Oliver Günther. 1998. Multidimensional Access Methods. ACM Comput. Surv. 30, 2 (June 1998), 170--231.

Digital Library

[17]

B Gedik, Kun-Lung Wu, P S Yu, and Ling Liu. 2006. Processing Moving Queries over Moving Objects using Motion-adaptive Indexes. IEEE Transactions on Knowledge and Data Engineering 18, 5 (2006), 651--668.

Digital Library

[18]

Craig Gentry, Shai Halevi, and Nigel P. Smart. 2015. Homomorphic Evaluation of the AES Circuit (Updated Implementation). In Cryptography ePrint Archive. LNCS, Vol. 7417. Springer Berlin Heidelberg, 850--867. Last Updated on 2015. Originally appeared in CRYPTO 2012.

Digital Library

[19]

Shai Halevi and Victor Shoup. 2014. Algorithms in HElib. In CRYPTO. Springer, 554--571.

[20]

Tanzima Hashem and Lars Kulik. 2011. "Don't trust anyone": Privacy Protection for Location-Based Services. Pervasive & Mobile Computing 7, 1 (2011), 44 -- 59.

Digital Library

[21]

Peizhao Hu, Tamalika Mukherjee, Alagu Valliappan, and Stanislaw Radziszowski. 2016. Evaluation of Homomorphic Primitives for Computations on Encrypted Data for CPS systems. In IEEE CPS Week Smart City Security and Privacy Workshop (SCSP-W). Vienna, Austria.

[22]

Peizhao Hu, Tamalika Mukherjee, Alagu Valliappan, and Stanislaw Radziszowski. 2016. Homomorphic Proximity Computation in Geosocial Networks. In BigSecurity an INFOCOM workshop.

[23]

Ali Khoshgozaran and Cyrus Shahabi. 2007. Blind Evaluation of Nearest Neighbor Queries Using Space Transformation to Preserve Location Privacy. In SSTD. Springer-Verlag, 239--257.

Digital Library

[24]

Ali Khoshgozaran and Cyrus Shahabi. 2009. Private Buddy Search: Enabling Private Spatial Queries in Social Networks. In Social Intelligence and Networking (SIN), Computational Sci and Engg. (CSE) - Vol. 04. IEEE Comp. Society, 166--173.

Digital Library

[25]

John Krumm. 2009. A Survey of Computational Location Privacy. Personal Ubiquitous Comput. 13, 6 (Aug. 2009), 391--399.

Digital Library

[26]

Tancrede Lepoint and Michael Naehrig. 2014. A Comparison of the Homomorphic Encryption Schemes FV and YASHE. In AfricaCrypt. Springer, 318--335.

[27]

Vadim Lyubashevsky, Chris Peikert, and Oded Regev. 2013. On Ideal Lattices and Learning with Errors over Rings. J. ACM 60, 6, Article 43 (Nov. 2013), 35 pages.

Digital Library

[28]

Sergio Mascetti, Dario Freni, Claudio Bettini, X. Sean Wang, and Sushil Jajodia. 2011. Privacy in Geo-social Networks: Proximity Notification with Untrusted Service Providers and Curious Buddies. The VLDB Journal 20, 4 (2011), 541--566.

Digital Library

[29]

Michael Naehrig, Kristin Lauter, and Vinod Vaikuntanathan. 2011. Can Homomorphic Encryption be Practical?. In Cloud Comp. Sec. Ws. (CCSW). 113--124.

Digital Library

[30]

Arvind Narayanan, Narendran Thiagarajan, Mugdha Lakhani, Michael Hamburg, and Dan Boneh. 2011. Location Privacy via Private Proximity Testing. In Network and Distributed System Security Symposium (NDSS).

[31]

Janus Dam Nielsen, Jakob Illeborg, and Michael Bladt Stausholm. 2012. Location Privacy via Actively Secure Private Proximity Testing. In PerCom Workshop. Lugano, Switzerland, 381--386.

[32]

Alexandra-Mihaela Olteanu, Kévin Huguenin, Reza Shokri, and Jean-Pierre Hubaux. 2014. Quantifying the Effect of Co-location Information on Location Privacy. Privacy Enhancing Technologies 8555, Chapter 10 (2014), 184--203.

[33]

Femi Olumofin, Piotr K Tysowski, Ian Goldberg, and Urs Hengartner. 2010. Achieving Efficient Query Privacy for Location Based Services. In Privacy Enhancing Technologies Symposium (PETS). Springer-Verlag, 93--110.

Digital Library

[34]

Tao Peng, Qin Liu, and Guojun Wang. 2013. Privacy Preserving for Location-Based Services Using Location Transformation. CSS 8300, Chap. 2 (2013), 14--28.

[35]

Krishna P. N. Puttaswamy, Shiyuan Wang, Troy Steinbauer, Divyakant Agrawal, Amr El Abbadi, Christopher Kruegel, and Ben Y. Zhao:. 2014. Preserving Location Privacy in Geosocial Applications. IEEE Trans. Mob. Comput. (2014), 159--173.

Digital Library

[36]

Gokay Saldamli, Richard Chow, Hongxia Jin, and Bart Knijnenburg. 2013. Private Proximity Testing with an Untrusted Server. In ACM WiSec. ACM, 113--118.

Digital Library

[37]

Joe Schwartz. 2012. Bing Maps Tile System. https://msdn.microsoft.com/en-us/library/bb259689.aspx. (2012).

[38]

Carmen Ruiz Vicente, Dario Freni, Claudio Bettini, and Christian S. Jensen. 2011. Location-Related Privacy in Geo-Social Networks. IEEE Internet Computing 15, 3 (2011), 20--27.

Digital Library

[39]

Boyang Wang, Ming Li, Sherman S. M. Chow, and Hui Li. 2014. A tale of two clouds: Computing on data encrypted under multiple keys. In IEEE Communications and Network Security (CNS). 337--345.

[40]

Tao Zhang, Sherman S. M. Chow, Zhe Zhou, and Ming Li. 2016. Privacy-Preserving Wi-Fi Fingerprinting Indoor Localization. In Advances in Information and Computer Security (IWSEC). 215--233.

[41]

Ge Zhong, Ian Goldberg, and Urs Hengartner. 2007. Louis, Lester and Pierre - Three Protocols for Location Privacy. In Privacy Enhancing Technologies. 62--76.

Digital Library

Cited By

Quan HWang BLi MLeontiadis I(2023)FastReach: A system for privacy-preserving reachability queries over location dataComputers & Security10.1016/j.cose.2023.103513135(103513)Online publication date: Dec-2023
https://doi.org/10.1016/j.cose.2023.103513
Aloufi AHu PSong YLauter K(2021)Computing Blindfolded on Data Homomorphically Encrypted under Multiple Keys: A SurveyACM Computing Surveys10.1145/347713954:9(1-37)Online publication date: 8-Oct-2021
https://dl.acm.org/doi/10.1145/3477139
Wang JDu MChow S(2020)Stargazing in the Dark: Secure Skyline Queries with SGXDatabase Systems for Advanced Applications10.1007/978-3-030-59419-0_20(322-338)Online publication date: 22-Sep-2020
https://doi.org/10.1007/978-3-030-59419-0_20
Show More Cited By

Recommendations

Privacy-preserving framework for geosocial applications

The paper deals with user privacy in geosocial applications. Geosocial applications have become very popular but can misuse user's private data and location. We propose a novel solution that prevents tracking and protects against personal identity and ...
Preserving Location Privacy in Geosocial Applications

Using geosocial applications, such as FourSquare, millions of people interact with their surroundings through their friends and their recommendations. Without adequate privacy protection, however, these systems can be easily misused, for example, to ...
Private geosocial networking
GIS '11: Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems

Location based social or geosocial networks (GSNs) have recently emerged as a natural combination of location based services with online social networks: users register their location and activities, share it with friends and achieve special status (...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

WiSec '17: Proceedings of the 10th ACM Conference on Security and Privacy in Wireless and Mobile Networks

July 2017

297 pages

ISBN:9781450350846

DOI:10.1145/3098243

General Chair:
Guevara Noubir
Northeastern University
,
Program Chairs:
Mauro Conti
University of Padua, Italy
,
Sneha Kumar Kasera
University of Utah

Copyright © 2017 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSAC: ACM Special Interest Group on Security, Audit, and Control
NSF: National Science Foundation
ACM: Association for Computing Machinery

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 July 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Funding Sources

Research Grants Council, Hong Kong
Research Grants Council Hong Kong

Conference

WiSec '17

Sponsor:

WiSec '17: 10th ACM Conference on Security & Privacy in Wireless and Mobile Networks

July 18 - 20, 2017

Massachusetts, Boston

Acceptance Rates

Overall Acceptance Rate 98 of 338 submissions, 29%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
173
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Quan HWang BLi MLeontiadis I(2023)FastReach: A system for privacy-preserving reachability queries over location dataComputers & Security10.1016/j.cose.2023.103513135(103513)Online publication date: Dec-2023
https://doi.org/10.1016/j.cose.2023.103513
Aloufi AHu PSong YLauter K(2021)Computing Blindfolded on Data Homomorphically Encrypted under Multiple Keys: A SurveyACM Computing Surveys10.1145/347713954:9(1-37)Online publication date: 8-Oct-2021
https://dl.acm.org/doi/10.1145/3477139
Wang JDu MChow S(2020)Stargazing in the Dark: Secure Skyline Queries with SGXDatabase Systems for Advanced Applications10.1007/978-3-030-59419-0_20(322-338)Online publication date: 22-Sep-2020
https://doi.org/10.1007/978-3-030-59419-0_20
Kounadi OResch BPetutschnig A(2018)Privacy Threats and Protection Recommendations for the Use of Geosocial Network Data in ResearchSocial Sciences10.3390/socsci71001917:10(191)Online publication date: 11-Oct-2018
https://doi.org/10.3390/socsci7100191
Pesara APatil VAtrey P(2018)Secure Computing of GPS Trajectory SimilarityProceedings of the 2nd ACM SIGSPATIAL Workshop on Recommendations for Location-based Services and Social Networks10.1145/3282825.3282832(1-7)Online publication date: 6-Nov-2018
https://dl.acm.org/doi/10.1145/3282825.3282832
Wang JChow S(2017)Secure Strategyproof Ascending-Price Spectrum Auction2017 IEEE Symposium on Privacy-Aware Computing (PAC)10.1109/PAC.2017.42(96-106)Online publication date: Aug-2017
https://doi.org/10.1109/PAC.2017.42

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents