Privately Querying Location-based Services with SybilQuery

Pravin Shankar, Vinod Ganapathy, Liviu Iftode.

Proceedings of the 11th International Conference on Ubiquitous Computing (Ubicomp 2009); pages 31-40; Orlando, Florida; September 30-October 3, 2009.

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-anonymity-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.

Paper: [ PDF ] (© ACM)
Slides: [ Powerpoint | PDF ]
DOI: [ 10.1145/1620545.1620550 ]

Papers page