A hybrid technique for private location-based queries with database protection

Gabriel Ghinita, Panos Kalnis, Murât Kantarcioǧlu, Elisa Bertino

Research output: Chapter in Book/Report/Conference proceedingConference contribution

19 Scopus citations


Mobile devices with global positioning capabilities allow users to retrieve points of interest (POI) in their proximity. To protect user privacy, it is important not to disclose exact user coordinates to un-trusted entities that provide location-based services. Currently, there are two main approaches to protect the location privacy of users: (i) hiding locations inside cloaking regions (CRs) and (ii) encrypting location data using private information retrieval (PIR) protocols. Previous work focused on finding good trade-offs between privacy and performance of user protection techniques, but disregarded the important issue of protecting the POI dataset D. For instance, location cloaking requires large-sized CRs, leading to excessive disclosure of POIs (O(|D|) in the worst case). PIR, on the other hand, reduces this bound to , but at the expense of high processing and communication overhead. We propose a hybrid, two-step approach to private location-based queries, which provides protection for both the users and the database. In the first step, user locations are generalized to coarse-grained CRs which provide strong privacy. Next, a PIR protocol is applied with respect to the obtained query CR. To protect excessive disclosure of POI locations, we devise a cryptographic protocol that privately evaluates whether a point is enclosed inside a rectangular region. We also introduce an algorithm to efficiently support PIR on dynamic POI sub-sets. Our method discloses O(1) POI, orders of magnitude fewer than CR- or PIR-based techniques. Experimental results show that the hybrid approach is scalable in practice, and clearly outperforms the pure-PIR approach in terms of computational and communication overhead. © 2009 Springer Berlin Heidelberg.
Original languageEnglish (US)
Title of host publicationAdvances in Spatial and Temporal Databases
PublisherSpringer Nature
Number of pages19
ISBN (Print)3642029817; 9783642029813
StatePublished - 2009

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'A hybrid technique for private location-based queries with database protection'. Together they form a unique fingerprint.

Cite this