Privacy-preserving query transformation and processing in location based service

Abstract

The increasing trend of embedding positioning capabilities (e.g., GPS) in mobile devices has created unprecedented opportunities for the widespread use of Location Based Services (LBS). Mobile users are able to formulate spatial queries, such as "find the closest restaurant to my current position". For such applications to succeed, privacy and confidentiality are essential. Commonly, privacy-enhancing techniques rely on encryption to safeguard communication channels, and on pseudonyms to protect user identities. Nevertheless, an LBS query contains the current location of the user, which may be mapped to the userb s identity through a variety of means, such as signal triangulation, or physical observation. Hiding the user location is a challenging task, and a primordial requirement for LBS privacy. This thesis presents a framework for private queries in location-based services. First, we study in depth the location privacy problem in the context of spatial K-anonymity (SKA), an extension of the K-anonymity paradigm, widely used for privacy preservation in relational databases. To enforce SKA, we adopt a three-tier architecture, with an Anonymizer Service (AS) that acts as an intermediary between the users and the LBS, and anonymizes queries by cloaking user locations. We identify the reciprocity property, a sufficient condition to guarantee privacy for a snapshot of user locations, and develop two SKA algorithms which provide a trade-off between privacy requirements and query processing overhead. We also devise algorithms to process range and nearest-neighbor anonymized queries at the LBS side. Next, we extend our results by showing how reciprocity can be effectively and efficiently enforced using hierarchical spatial indices, such as Quad-trees and R-trees. We also develop a stronger version of reciprocity: frequency-aware reciprocity, which addresses the scenario when an attacker possesses additional background knowledge about the relative frequencies of issuing queries among distinct users. Most existing work in LBS query privacy assumes a centralized AS, which must handle the frequent updates of user locations, as well as the overhead of anonymizing queries. Furthermore, the AS is a single-point-of-attack, and, if compromised, the privacy of all users is threatened. We address these limitations by devising a decentralized architecture for LBS anonymization: users organize themselves into a P2P network, and cooperate to anonymize queries. We propose two such P2P systems, which provide a trade-off between privacy requirements and scalability. Finally, we take a step further from the SKA paradigm, and propose a novel LBS privacy approach, based on Private Information Retrieval (PIR). PIR comprises of a two-party cryptography-based protocol that allows a client to retrieve the desired information from a server, without the server learning what information was requested. We show that PIR eliminates the need to trust a third-party anonymizer, as well as other users. Furthermore, since location information is encrypted (not just cloaked, as in the case of spatial K-anonymity), this method is resilient to any type of location-based attack. For instance, PIR-based privacy protects against correlation attacks in the case of private continuous queries (i.e., a user asks the same query from different locations at consecutive timestamps), a problem which has not been efficiently solved yet within the SKA paradigm. The PIR approach provides superior privacy, and incurs a reasonable overhead in practice.