Secure and Practical Group Nearest Neighbor Query for Location-Based Services in Cloud Computing
Open Access
- 25 September 2021
- journal article
- research article
- Published by Hindawi Limited in Security and Communication Networks
- Vol. 2021, 1-17
- https://doi.org/10.1155/2021/5686506
Abstract
Group nearest neighbor (GNN) query enables a group of location-based service (LBS) users to retrieve a point from point of interests (POIs) with the minimum aggregate distance to them. For resource constraints and privacy concerns, LBS provider outsources the encrypted POIs to a powerful cloud server. The encryption-and-outsourcing mechanism brings a challenge for the data utilization. However, as previous work from anonymity technique leaks all contents of POIs and returns an answer set with redundant communication cost, the LBS system cannot work properly with those privacy-preserving schemes. In this paper, we illustrate a secure group nearest neighbor query scheme, which is referred to as SecGNN. It supports the GNN query with LBS users and assures the data privacy and query privacy. Since SecGNN only achieves linear search complexity, an efficiency enhanced scheme (named Sec) is introduced by taking advantage of the KD-tree data structure. Specifically, we convert the GNN problem to the nearest neighbor problem for their centroid, which can be computed by anonymous veto network and Burmester–Desmedt conference key agreement protocols. Furthermore, the Sec scheme is introduced from the KD-tree data structure and a designed tool, which supports the computation of inner products over ciphertexts. Finally, we run experiments on a real-database and a random database to evaluate the performance of our SecGNN and Sec schemes. The experimental results show the high efficiency of our proposed schemes.Funding Information
- National Natural Science Foundation of China (61960206014, MMJJ20180110)
This publication has 21 references indexed in Scilit:
- Efficient and Privacy-Preserving Polygons Spatial Query Framework for Location-Based ServicesIEEE Internet of Things Journal, 2016
- Practical and secure nearest neighbor search on encrypted large-scale dataPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2016
- The Cloaked-Centroid protocol: location privacy protection for a group of users of location-based servicesKnowledge and Information Systems, 2014
- Location Oblivious Privacy Protection for Group Nearest Neighbor QueriesLecture Notes in Computer Science, 2014
- Preserving Location Privacy for a Group of UsersTurkish Journal of Electrical Engineering and Computer Sciences, 2013
- GLP: A cryptographic approach for group location privacyComputer Communications, 2012
- Supporting anonymous location queries in mobile environments with privacygridPublished by Association for Computing Machinery (ACM) ,2008
- Aggregate nearest neighbor queries in spatial databasesACM Transactions on Database Systems, 2005
- A Generalisation, a Simplification and Some Applications of Paillier's Probabilistic Public-Key SystemLecture Notes in Computer Science, 2001
- An improved algorithm for computing logarithms overGF(p)and its cryptographic significance (Corresp.)IEEE Transactions on Information Theory, 1978