LPSQ: Achieving Efficient and Privacy-Preserving Location-Point-Set Similarity Range Query for Cloud Computing

Location point set similarity range query aims to retrieve candidate point sets that are similar to the given point set in terms of location distribution patterns and geographical features, and it is vital in GIS (Geographic Information Systems), IoT (Internet of Things), and biometrics. Due to the economic and flexible advantages of cloud services, location data is frequently outsourced to cloud servers, which simultaneously increases the risk of privacy breaches. To address this, service providers choose to encrypt data before outsourcing. However, the existing schemes for similarity range query of encrypted location point sets have some problems, such as high computational complexity of measurements, which limit the query efficiency and security of schemes. To tackle these problems, this paper achieves the efficient and privacy-preserving location-point-set similarity range query for cloud computing (LPSQ). Firstly, we propose a lightweight similarity measurement called Geo-Jaccard similarity, to reduce the time complexity to O(n). Secondly, to enhance the efficiency of the scheme, we integrate the kd-tree with pivot point technology to construct a pkd-tree, and design a corresponding filtering and verification algorithm. Thirdly, to enhance the security of our scheme, we encrypt the pkd-tree using a mix of matrix encryption and SHE (Symmetric Homomorphic Encryption), and design a series of protocols under SHE, such as SHE batch minimum value calculation protocol, SHE division protocol, and the approximation algorithm for computing Jaccard similarity securely. Finally, we prove that the security of our proposed LPSQ achieves CPA (Chosen Plaintext Attack) security. Furthermore, we conduct experiments to assess the performance, and the results demonstrate that LPSQ achieves sublinear search efficiency, while Geo-Jaccard similarity proves effective for similarity range queries on location point sets.