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. Much prior work has addressed the problem of protecting client privacy in such location-based queries using k-anonymity. In such schemes, the location-based server is unable to distinguish a querying client from a group of k clients. However, prior work on k-anonymity-based schemes has typically required the use of an anonymizer— a proxy that intercepts and modifies client queries so as to achieve k-anonymity. The centralized nature of anonymizers makes them a single point of failure. Moreover, in the presence of mobile clients, anonymizers must be implemented so as to avoid correlation attacks, where an adversary compromises client location using that client’s queries from multiple locations. Alternatives that eliminate the anonymizer either rely on the participation of k other peers, thus making the system reliant on these peers, or are based upon computationally-expensive cryptographic protocols that present scalability problems. 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 clientside 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.