CAP: A Context-aware Privacy Protection System For Location-based Services

Location Based Services (LBS) are information services that provide users with customized contents, such as the nearest restaurants/hotels/clinics, retrieved from a dedicated spatial database. They make use of technologies such as Global Positioning System (GPS), triangulation/triliteration etc. to get the geographical position of the user. Since the queries on spatial database include the user's current location, LBS may raise serious concerns on the user's location privacy. If disclosed, a user's location information may be misused in many ways by a malicious adversary who has access to the LBS server or even by the LBS provider. Therefore, our aim in this thesis is to provide an user with a system to protect her location privacy, without impeding the LBS.

In this thesis, we address issues related to privacy protection for location-based services (LBS) without trusted-third parties (e.g., anonymizers). There are two critical challenges to such a system. First, the degree of privacy protection and LBS accuracy depends on the context, such as population and road density, around a user's location e.g. for an user in rural area, we use more perturbation than for an user in downtown to achieve the same level of privacy protection and LBS accuracy. Second, location privacy may be breached through not only an LBS query, but also via the network traffic that carries the query payload, leading to a dual requirement on data privacy and communication anonymity. In order to address these challenges, we introduce CAP, a Context-Aware Privacy-preserving LBS system with integrated protection for data privacy and communication anonymity. For data privacy, we propose a projection-based location data perturbation algorithm, called Various-size-grid Hilbert Curve (VHC) - mapping, which provides universal guarantees on privacy protection and LBS accuracy for all locations with diverse context. VHC-mapping is designed to require minimal storage and computational cost. For communication anonymity, CAP uses a revised version of Tor. In this revised version, we address the issue of QoS degradation due to Tor's random routing protocols. By exploiting the dual requirement with data privacy, we propose a set of new routing algorithms with significantly enhanced QoS. We have implemented a prototype of CAP which can be readily integrated with an existing LBS. Our theoretical analysis and experimental results validate CAP's effectiveness on privacy protection, LBS accuracy, and communication QoS.