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.

Traditional reverse k-nearest neighbor (RkNN) query schemes typically assume that users are available online in real-time for interactive key reception, overlooking scenarios where users might be offline. Moreover, existing privacy-preserving RkNN query schemes primarily focus on user features or spatial data, neglecting the significance of user reputation values. To address these limitations, we propose a privacy-preserving resilient RkNN query scheme over encrypted outsourced multi-attribute data (PRRQ). Specifically, to mitigate the challenges posed by resilient online presence (i.e., non-real-time online) of users for interactive key reception, we incorporate a non-interactive key exchange (NIKE) protocol and the Diffie-Hellman two-party key exchange algorithm to propose a multi-party NIKE algorithm (2K-NIKE), facilitating non-interactive key reception for multiple users. Considering the privacy leakage issues, PRRQ encodes original multi-attribute data (i.e., spatial, feature, and reputation values) alongside query requests based on formalized criteria. Additionally, we integrate the proposed 2K-NIKE and the improved symmetric homomorphic encryption (iSHE) algorithms to encrypt them. Furthermore, catering to the requirements of ciphertext-based RkNN queries, we propose a private RkNN query eligibility-checking (PREC) algorithm and a private reputation-verifying (PRRV) algorithm, which validate the compliance of encrypted outsourced multi-attribute data with query requests. Security analysis demonstrates that PRRQ achieves simulation-based security under anhonest-but-curiousmodel. Experimental results show that PRRQ offers superior computational efficiency compared to comparative schemes.

Extensive schemes have been conducted on the development of efficient and privacy-preserving$k$NN query algorithms in data outsourcing scenarios. However, existing researches primarily address low-dimensional data, posing scalability challenges in higher dimensions. To tackle this issue, we propose an efficient and privacy-preserving$k$NN query scheme for outsourced high-dimensional data (EPPQ), emphasizing the complete lifecycle from secure dimensionality reduction of high-dimensional data to secure$k$NN query on the reduced-dimensional data. Specifically,in the secure dimensionality reduction phase: on the one hand, EPPQ integrates principal component analysis (PCA) for dimensionality reduction to minimize computational overhead. On the other hand, to address privacy concerns during the process of PCA, by incorporating differential privacy (DP), we propose the Privacy-Preserving Data Dimensionality Reduction Algorithm based on PCA (PDDRP).In the secure$k$NN query phase: for one thing, EPPQ facilitates the index of the reduced-dimensional data by k-d tree. To enhance index efficiency, we innovatively propose plaintexts-based distance calculation definitions (PDC definitions) and construct an efficient variant of k-d tree (Ek-d tree), for the first time. For another, the Paillier homomorphic encryption (PHE) technique is leveraged to safeguard privacy when outsourcing Ek-d tree to untrusted cloud servers. Additionally, for ciphertexts-based distance calculations and comparisons, we design the Secure Precomputed Distance protocol (SPCD) and Secure Comparison protocol (SCOM). Finally, we creatively present the Privacy-Preserving$k$NN Query Algorithm based on Ek-d tree (PKQKT) for efficient and secure$k$NN query. Comprehensive security analysis demonstrates that the EPPQ scheme meets the required security properties under thehonest-but-curiousmodel. Extensive experiments confirms that EPPQ achieves high computational efficiency and query accuracy.