Privately querying location-based services with SybilQuery

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Privately querying location-based services with SybilQuery

Full text

Pdf (617 KB)

Source

ACM International Conference Proceeding Series archive
Proceedings of the 11th international conference on Ubiquitous computing table of contents

Orlando, Florida, USA

SESSION: Places & location table of contents

Pages 31-40

Year of Publication: 2009

ISBN:978-1-60558-431-7

Authors

Pravin Shankar	Rutgers University, Piscataway, NJ, USA
Vinod Ganapathy	Rutgers University, Piscataway, NJ, USA
Liviu Iftode	Rutgers University, Piscataway, NJ, USA

Sponsors

ACM: Association for Computing Machinery
SIGMOBILE: ACM Special Interest Group on Mobility of Systems, Users, Data and Computing
SIGCHI: ACM Special Interest Group on Computer-Human Interaction

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 41, Downloads (12 Months): 41, Citation Count: 0

Additional Information:

abstract references index terms

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1620545.1620550 What is a DOI?

ABSTRACT

To usefully query a location-based service, a mobile device must typically present its own location in its query to the server. This may not be acceptable to clients that wish to protect the privacy of their location. This paper presents the design and implementation of SybilQuery, a fully decentralized and autonomous k-anonymization-based scheme to privately query location-based services. SybilQuery is a client-side tool that generates k-1 Sybil queries for each query by the client. The location-based server is presented with a set of k queries and is unable to distinguish between the client's query and the Sybil queries, thereby achieving k-anonymity. We tested our implementation of SybilQuery on real mobility traces of approximately 500 cabs in the San Francisco Bay area. Our experiments show that SybilQuery can efficiently generate Sybil queries and that these queries are indistinguishable from real queries.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	B. Bamba, L. Liu, P. Pesti, and T. Wang. Supporting anonymous location queries in mobile environments with PrivacyGrid. In Proc. WWW, 2008.
	2	Cabspotting project. http://cabspotting.org/.
	3	D. Choffnes, J. Duch, D. Malmgren, R. Guierma, F. Bustamante, and L. Amaral. Swarmscreen: Privacy through plausible deniability in p2p systems. In Northwestern EECS Technical Report, 2009.
	4	C.-Y. Chow and M.F. Mokbel. Enabling private continuous queries for revealed user locations. In Proc. SSTD'07: Advances in Spatial and Temporal Databases, 2007.
	5	C.-Y. Chow, M.F. Mokbel, and X. Liu. A peer-to-peer spatial cloaking algorithm for anonymous location-based services. In Proc. GIS'06: ACM International Symposium on Advances in Geographic Information Systems, 2006.
	6	B. Cox, D. Evans, A. Filipi, J. Rowanhill, W. Hu, j. Davidson, J. Knight, A. Nguyen-Tuong, and J. Hiser. N-Variant systems: A secretless framework for security through diversity. In Proc. USENIX Security Symposium, 2006.
	7	F. Diggelen. Gnss accuracy: Lies, damn lies, and statistics. GPS World, 2007.
	8	M. Duckham and L. Kulik. A formal model of obfuscation and negotiation for location privacy. In Proc. Pervasive, pp. 152--170, 2005.
	9	C. Dwork. Differential privacy. In Proc. ICALP'06: Intl. Colloquium on Automata, Languages and Programming, 2006.
	10	EZPass: A pass on privacy? "http://www.nytimes.com/2005/07/17/magazine/17WWLN.html".
	11	EZPass records out cheaters in divorce court. "http://www.msnbc.msn.com/id/20216302".
	12	R. Finkel and J. Bentley. Quad trees: A data structure for retrieval on composite keys. Acta Informatica, 4(1):1--9, 1974.
	13	B. Gedik and L. Liu. Location privacy in mobile systems: A personalized anonymization model. In Proc. ICDCS, 2005.
	14	B. Gedik and L. Liu. Protecting location privacy with personalized k-anonymity: Architecture and algorithms. IEEE Transactions on Mobile Computing, 2007.
	15	G. Ghinita, P. Kalnis, A. Khoshgozaran, C. Shahabi, and K.-L. Tan. Private queries in location-based services: Anonymizers are not necessary. In Proc. ACM SIGMOD, 2008.
	16	G. Ghinita, P. Kalnis, and S. Skiadopoulos. Mobihide: A mobile peer-to-peer system for anonymous location-based queries. In Proc. SSTD'07: International Symposium on Spatial and Temporal Databases, 2007.
	17	G. Ghinita, P. Kalnis, and S. Skiadopoulos. PRIVE: Anonymous location-based queries in distributed mobile systems. In Proc. WWW, 2007.
	18	Google maps geo API. http://code.google.com/apis/maps/.
	19	M. Gruteser and D. Grunwald. Anonymous usage of location-based services through spatial and temporal cloaking. In Proc. Mobisys, 2003.
	20	K.H.Y. Yanagisawa, and T. Satoh. An anonymous communication technique using dummies for location-based services. In Proc IEEE International Conference on Pervasive Services, 2005.
	21	K.H.Y. Yanagisawa, and T. Satoh. Protection of location privacy using dummies for location-based services. In Proc ICDE Workshops, 2005.
	22	U. Hengartner. Hiding location information from location-based services. In Proc. International Workshop on Privacy-Aware Location-based Mobile Services (PALMS), 2007.
	23	B. Hoh and M. Gruteser. Location privacy through path confusion. In Proc. SecureComm, 2005.
	24	D. Howe and H. Nissenbaum. TrackMeNot: Resisting surveillance in Web search. On the Identity Trail: Privacy, Anonymity and Identity in a Networked Society (Oxford University Press), 2008.
	25	R.R.C.J. Meyerowitz. Realtime location privacy via mobility prediction: Creating confusion at crossroads. In Proc. HotMobile, 2009.
	26	P. Kalnis, G. Ghinita, K. Mouratidis, and D. Papadias. Preventing location-based identity inference in anonymous spatial queries. IEEE Transactions on Knowledge and Data Engineering, 19(12):1719--1733, 2007.
	27	J. Krumm. Realistic driving trips for location privacy. In Proc. Pervasive, 2009.
	28	J. Krumm and E. Horvitz. Predestination: Where do you want to go today? In IEEE Computer Magazine, vol. 40, no. 4, pp. 105--107, 2007.
	29	E. Kushilevitz and R. Ostrovsky. Replication is not needed: Single database, computationally-private information retrieval. In Proc. FOCS'97: IEEE Symposium on Foundations of Computer Science, 1997.
	30	N. Li, T. Li, and S. Venkatasubramanian. t-closeness: Privacy beyond k-anonymity and l-diversity. In Proc. ICDE, 2007.
	31	M.L. Liu, C.S. Jensen, X. Huang, and H. Lu. Spacetwist: Managing the tradeoffs among location privacy, query performance, and query accuracy in mobile services. In Proc ICDE, 2008.
	32	A. Machanavajjhala, J. Gehrke, D. Kifer, and M. Venkitasubramaniam. l-Diversity: Privacy beyond k-anonymity. In Proc. ICDE, 2006.
	33	A. Machanavajjhala, D. Kifer, J. Abowd, J. Gehrke, and L. Vilhuber. Privacy: Theory meets practice on the map. In Proc. ICDE, 2008.
	34	M.F. Mokbel, C.-Y. Chow, and W.G. Aref. The new Casper: Query processing for location services without compromising privacy. In Proc. VLDB, 2006.
	35	Microsoft multimap API. http://www.multimap.com/.
	36	NYC cabs strike over GPS system plans. http://www.engadget.com/2007/03/09/nyc-cab-drivers-say-no-thanks-to-gps-installation/.
	37	M.K. Reiter and A.D. Rubin. Crowds: Anonymity for Web transactions. ACM Transactions on Information and System Security, 1(1):66--92, 1998.
	38	F. Saint-Jean, A. Johnson, D. Boneh, and J. Feigenbaum. Private Web search. In Proc. WPES'07: ACM Workshop on Privacy in the Electronic Society, 2007.
	39	P. Samarati. Protecting respondents identities in microdata release. IEEE Transactions on Knowledge and Data Engineering, 13(6):1010--1027, 2001.
	40	P. Shankar, V. Ganapathy, and L. Iftode. Privately querying location-based services with sybilquery. In Rutgers University Technical Report DCS-TR-652, 2009.
	41	R. Sion and B. Carbunar. On the computational practicality of private information retrieval. In Proc. NDSS, 2007.
	42	L. Sweeney. k-anonymity: A model for protecting privacy. International Journal on Uncertainty, Fuzziness and Knowledge-based Systems, 10(5):557--570, 2002.
	43	Yahoo maps local search API. http://developer.yahoo.com/maps/.
	44	Yahoo! Local. http://traffic.yahoo.com/traffic/.
	45	G. Zhong and U. Hengartner. A distributed k-anonymity protocol for location privacy. In Proc. IEEE PerCom, 2009.