Location Privacy:

The past few years have witnessed a dramatic growth in capabilities of cellphone devices as well as the same growth in public demand for using such services and features. Such growth and trend in technology is often not seamless. Recent concerns over how such services can jeopardize user's private information have coined a term, until recently unknown, location privacy. With the advent of GPS devices embedded in cellphones, and their growing use, several breaching of subscriber's privacy by stalking their locations have been reported and many researchers and organizations have raised the need to explore the threats associated with location-based services and misuse of users' private location information.

The concerns over protecting user's location while using location-based services have led to the discussion that the user has to compromise his privacy for the service because more accurate responses from location servers demand more accurate information about where the user is located. However, we believe it is possible to allow users to enjoy the same quality of service while not being worried about their private location information. 

In April 2007 we embarked on the new research topic of location privacy. We are studying two different approaches to satisfy significantly more stringent privacy guarantees as compared to the first generation approaches based on location cloaking or anonymity. Neither of our approaches are ad-hoc; on the contrary, the first approach, PULSE, is inspired by the work in the area of
encryption and the second, SPIRAL, builds upon the framework of Private Information Retrieval (PIR). Both of these research fields have been around for a long time enabling privacy protection but not yet fully exploited for location privacy.

PULSE, Private Queries Using Location Aware Space Encoding, utilizes space filling curves as one-way transformations to encode the locations of both user(s) and points of interest into an encrypted space and to evaluate a query in this transformed space. The transformed space maintains the distance properties of the original space and hence location queries can be resolved efficiently in the transformed space. At the same time, our transformation can be viewed as an encryption of the space with a one-way transformation function that allows fast computation of its inverse given some extra knowledge, termed trapdoor or transformation key. Subsequently, the client can encrypt the query using its key and the server performs the query in the encrypted space and returns back to client the encrypted answers for client's fast decryption.
Consequently, similar to conventional encryption schemes, we do not need any intermediator between the client and server to evaluate the spatial queries blindly. In addition, by standing on the shoulders of the encryption giants, we benefit from all the techniques developed in the past two decades for managing, maintaining, distributing and securing encryption keys.
 

SPIRAL, a Scalable Private Information Retrieval Approach to Location Privacy uses practical PIR techniques to retrieve the answers to the location queries without revealing the retrieved items to the server. The main challenge is to efficiently translate the location queries into a series of independent record retrievals (perhaps at the client side) to be able to use PIR at the server to retrieve the response records privately. Once this achieved, due to our utilization of PIR, there is no need for an intermediate anonymizer. Building on almost optimal hardware-based PIR protocols, SPIRAL achieves very high performance while guaranteeing user privacy in Location Based Services.
 

In collaboration with National University of Singapour's  Database Research Group, we have also designed a framework based on theoretical work on PIR to enable location privacy. As opposed to SPIRAL, utilizing computationally secure PIR protocols avoids the need to a secure-coprocessor at the cost of imposing more time-consuming query processing while enabling location-based queries. Read more in the Publications section.

	Research Agenda
	Our current research agenda is to Enable the blind evaluation of Range queries as well as the KNN queries in location based services. Enable the blind evaluation of Dynamic queries (i.e., private queries over public data) in location based services. Achieve the desirable privacy metrics such as A-anonymity and U-anonymity efficiently.
	webadmin: jafkhosh at usc dot edu This research has been funded in part by NSF grants IIS-0742811 and CNS-0831505 (CyberTrust). Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.