Secure kNN query processing in untrusted cloud environments

Sunoh Choi, Gabriel Ghinita, Hyo Sang Lim, Elisa Bertino

Research output: Contribution to journalArticlepeer-review

74 Citations (Scopus)

Abstract

Mobile devices with geo-positioning capabilities (e.g., GPS) enable users to access information that is relevant to their present location. Users are interested in querying about points of interest (POI) in their physical proximity, such as restaurants, cafes, ongoing events, etc. Entities specialized in various areas of interest (e.g., certain niche directions in arts, entertainment, travel) gather large amounts of geo-tagged data that appeal to subscribed users. Such data may be sensitive due to their contents. Furthermore, keeping such information up-to-date and relevant to the users is not an easy task, so the owners of such data sets will make the data accessible only to paying customers. Users send their current location as the query parameter, and wish to receive as result the nearest POIs, i.e., nearest-neighbors (NNs). But typical data owners do not have the technical means to support processing queries on a large scale, so they outsource data storage and querying to a cloud service provider. Many such cloud providers exist who offer powerful storage and computational infrastructures at low cost. However, cloud providers are not fully trusted, and typically behave in an honest-but-curious fashion. Specifically, they follow the protocol to answer queries correctly, but they also collect the locations of the POIs and the subscribers for other purposes. Leakage of POI locations can lead to privacy breaches as well as financial losses to the data owners, for whom the POI data set is an important source of revenue. Disclosure of user locations leads to privacy violations and may deter subscribers from using the service altogether. In this paper, we propose a family of techniques that allow processing of NN queries in an untrusted outsourced environment, while at the same time protecting both the POI and querying users' positions. Our techniques rely on mutable order preserving encoding (mOPE), the only secure order-preserving encryption method known to-date. We also provide performance optimizations to decrease the computational cost inherent to processing on encrypted data, and we consider the case of incrementally updating data sets. We present an extensive performance evaluation of our techniques to illustrate their viability in practice.

Original languageEnglish
Article number6722903
Pages (from-to)2818-2831
Number of pages14
JournalIEEE Transactions on Knowledge and Data Engineering
Volume26
Issue number11
DOIs
Publication statusPublished - Nov 2014
Externally publishedYes

Keywords

  • Location privacy
  • database outsourcing
  • mutable order preserving encoding
  • spatial databases

Fingerprint

Dive into the research topics of 'Secure kNN query processing in untrusted cloud environments'. Together they form a unique fingerprint.

Cite this