From the November 2014 issue
Secure kNN Query Processing in Untrusted Cloud Environments
By Sunoh Choi, Gabriel Ghinita, Hyo-Sang Lim, and Elisa Bertino
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.
Editorials and Announcements
- Get Your Journals as eBooks for Free
- TKDE celebrates its 25th Anniversary. Editor-in-Chief Jian Pei says, "We are celebrating the 25th Anniversary of TKDE. Since its first issue in March 1989, TKDE has published 2,981 articles, and another 220 articles in the early access portal. With 898 submissions and 79 accepted articles in 2012, TKDE is now the premier journal in the broad and general fields of data management, data mining, and knowledge engineering. We thank all the authors, reviewers, and readers for their continuing support to TKDE. As always, we are eager to hear your ideas and suggestions, and will do our best to meet your expectations. With all your passions, contributions, and supports, TKDE is embracing the new era of big data and big data analytics. Happy birthday to TKDE!"
- eBooks of issues of TKDE can now be downloaded from the Computer Society Digital Library
- Editorial: State of the Transactions (January 2014)
- Editorial (August 2013)
- New EIC Editorial (Feb 2013)
- Outgoing EIC Editorial (Feb 2013)
- State of the Journal (Feb 2012)
- EIC Editorial (January 2011)
- Special Section on the International Conference on Data Engineering (June 2014)
- Special Section on the 27th International Conference on Data Engineering (ICDE 2011)(Oct 2012)
- Special Section on Keyword Search on Structured Data (Dec 2011)
- Cloud Data Management (Sept 2011)
- Special Section on the 26th International Conference on Data Engineering (Aug 2011)
Access recently published TKDE articles
Subscribe to the RSS feed of latest TKDE content added to the digital library.
Sign up for the Transactions Connection newsletter.
IEEE Transactions on Knowledge and Data Engineering (TKDE) is an archival journal published monthly designed to inform researchers, developers, managers, strategic planners, users, and others interested in state-of-the-art and state-of-the-practice activities in the knowledge and data engineering area.
Read the full scope of TKDE