Title: Private Queries in Location Based Services: Anonymizers are not Necessary
       (to appear in Proc of SIGMOD 2008)

Speaker: Gabriel Ghinita, Research Fellow (http://www.comp.nus.edu.sg/~ghinitag)
         Dept. of Computer Science, National University of Singapore

Abstract:

Mobile devices equipped with positioning capabilities (e.g., GPS) can ask
location-dependent queries to Location Based Services (LBS). To protect privacy,
the user location must not be disclosed. Existing solutions utilize a trusted
anonymizer between the users and the LBS. This approach has several drawbacks:
(i) All users must trust the third party anonymizer, which is a single point of
attack. (ii) A large number of cooperating, trustworthy users is needed.
(iii) Privacy is guaranteed only for a single snapshot of user locations; users
are not protected against correlation attacks (e.g., history of user movement).

We propose a novel framework to support private location-dependent queries,
based on the theoretical work on Private Information Retrieval (PIR). Our framework
does not require a trusted third party, since privacy is achieved via cryptographic
techniques. Compared to existing work, our approach achieves stronger privacy for
snapshots of user locations; moreover, it is the first to provide provable privacy
guarantees against correlation attacks. We use our framework to implement approximate
and exact algorithms for nearest-neighbor search. We optimize query execution by
employing data mining techniques, which identify redundant computations. Contrary
to common belief, the experimental results suggest that PIR approaches incur
reasonable overhead and are applicable in practice.

Biodata:

Gabriel Ghinita is currently a research fellow with the Dept. of Computer Science,
National University of Singapore (NUS). From 2004 to 2008, he has pursued a PhD
degree in NUS (degree expected in May 2008). His PhD topic is “Privacy-Preserving
Query Transformation and Processing in Location Based Services”. Previous to joining
NUS, he has obtained a bachelor degree in Computer Science from the “Politehnica”
University of Bucharest, in 2003.

Gabriel's main research interests focus on data privacy, specifically: private
queries in location-based services, anonymization of trajectories, and
privacy-preserving publication of relational and transaction data. His broader
research interests include spatial databases, peer-to-peer systems and sensor networks.