Open Access Open Access  Restricted Access Subscription or Fee Access

Secure kNN Query Processing in Untrusted Cloud Environments

Devidas S. Thosar, Rajashree D. Thosar, Prashant J. Gadakh


Now days a Wireless devices which having geo-positioning facility like GPS enable users to give information about their current location. Users are interested in querying in their physical location like restaurants, college, home, etc. Such data may be important due to their information. Furthermore, storing such relevent information regularly to the users tedious task, so the author of such information will make the data access only to paying users. The users are send their proper location as the query parameter, and wish to accept as result the nearest position, i.e., nearest-neighbors (NNs). But actual data owners do not have the technical knowledge to support processed query on a large data, so they outsource information storage and querying to a main dataset. Many such cloud providers exist offer powerful storage and computational structures at less cost. However, such a dataset providers are not completely trusted, and typically behave in an cusial fashion. Specifically they uses the some rules to answer queries perfectly, but they also collect the locations of the users and the subscribers for other uses. Giving this information of locations can lead to security breaches and financial losses to the data provider, for whom the dataset is an important source of revenue. The importance of user locations leads to privacy and may refer subscribers from using the service altogether. In this paper, we propose a set of ideas that allow NN queries in an unsecured outsourced structure, while at the same time provide security to both the location and querying users’ positions. Our ideas focuses on only secure order-preserving encryption method which is known to-date. We also provide performance measurements to reduce the processing cost inherent to processing on secured data, and we consider the problem of incrementally updating these datasets. We present an extensive performance measurement of our ideas to illustrate their use in practice.


Location Privacy, Spatial Databases, Database Outsourcing, Mutable Order Preserving Encoding

Full Text:



Mark de Berg, Computational Geometry, Springer

W. K. Wong, David W. Cheung, Ben Kao, and Nikos Figure 8-3. Data Encryption Time Mamoulis, Secure kNN Computation on Encrypted Databases, SIGMOD’09

Haibo Hu, JianliangXu, ChushiRen, and Byron Choi, Processing Private Queries over Untrusted Data Cloud through Privacy Homomorphism, ICDE’11

HuiqiXu, ShuminGuo, and Keke Chen, Building Confidential and Efficient Query Services in the Cloud withRASP Data Perturbation, TKDE’12

Bin Yao, Feifei Li, and Xiaokui Xiao, Secure Nearest Neighbor Revisited, ICDE’13

Raluca Ada Popa, Frank H. Li, and NickolaiZeldovich, An Ideal-Security Protocol for Order-Preserving Encoding, IEEE S&P’13

Gabriel Ghinita, PanosKalnis, Ali Khoshgozaran, Cyrus Shahabi, and Kian-Lee Tan, Private Queries in Location Based Services: Anonymizers are not Necessary, SIGMOD’08

Gabriel Ghinita, PanosKalnis, Murat Kantarcioglu, and Elisa Bertino, A Hybrid Technique for Private Location- Based Queries with Database Protection, SSTD’09

Gabriel Ghinita, PanosKalnis, MuratKantarcioglu, and Elisa Bertino, Approximate and exact hybrid algorithms for private nearest-neighbor queries with database protection, Geoinformatica’11

Ali Khoshgozaran and Cyrus Shahabi, Blind Evaluation of Nearest Neighbor Queries Using Space Transformation to Preserve Location Privacy, SSTD’07

A. Boldyreva, N. Chenette, Y. Lee, and A. O’Neill, Order Preserving Symmetric Encryption, EuroCrypt’09

A. Boldyreva, N. Chenette, and A. O’Neill, Order_preserving Encryption Revisited: Improved Security Analysis and Alternative Solutions, Crypto’11

Jon Louis Bentley, Multidimensional Binary Search Trees used for Associative Searching, ACM Communications, 1975

Thomas Roos, Voronoi diagrams over dynamic scenes, Discrete Applied Mathematics, 1993.

Gruteser M. and Grunwald D., Anonymous usage of location-based services through spatial and temporal cloaking, MOBISYS’03

Gedik B. and Liu L., Location privacy in mobile systems: a personalized anonymization model, ICDCS’05

Mokbel M. F., Chow C. Y., and Aref W. G., The new Casper: query processing for location services without compromising privacy, VLDB’06

Kalnis P., Ghinita G., Mouratidis K., and Papadias D., Preserving location-based identity inference in anonymous spatial queries, TKDE’07

R. Agrawal, J. Kiernan. R. Srikant, and Y. Xu, Order preserving encryption for numeric data, SIGMOD’04


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.