Efficient Privacy-Preserving and Verifiable Arbitrary Polygon Range Query in Cloud Computing

Geometric range queries are essential in location-based services, yet outsourcing spatial data to a cloud server raises privacy and integrity concerns. Existing schemes often rely on complex and heavy encryption, which degrades query efficiency and lacks robust result verification against malicious cloud behavior. To address these challenges, we propose a privacy-preserving and verifiable arbitrary polygon range query (PPVRQ) scheme in cloud computing. PPVRQ transforms geometric range queries into range intersection tests between Quadtree-based rectangular subspaces and the query polygon’s minimum bounding rectangle (MBR). By employing Enhanced Asymmetric Scalar Product-Preserving Encryption (EASPE), it enables the secure transformation of Euclidean distance calculations into inner product operations on encrypted data, allowing efficient query processing without decryption. Additionally, we integrate a lightweight hash-based verification mechanism to ensure the correctness and completeness of query results. Security analysis confirms that PPVRQ achieves semantic security under the IND-CPA model. Experimental results demonstrate that PPVRQ significantly enhances query efficiency and verification reliability, making it a practical solution for secure spatial data outsourcing.