PMRK: Privacy-Preserving Multidimensional Range Query with Keyword Search over Spatial Data

With the intensification of mobile devices, vast amounts of spatial data have been outsourced to cloud servers to provide query services. However, existing privacy-preserving schemes for spatial data only support spatial range queries and keyword searches and do not scale well in the scenario of multidimensional range queries. To address the above challenges, we propose a privacy-preserving scheme for the multidimensional range query with keyword search over spatial data (PMRK). Specifically, based on the encoding technique, we design data comparison and text matching algorithms, which can convert range queries and keyword searches into Hadamard-product-based operations. To improve the search efficiency, we index the spatial data by R-tree and propose the range intersection algorithm to implement the multidimensional range query with keyword search on R-tree simultaneously. Furthermore, the homomorphic encryption and matrix encryption techniques are leveraged to design the intersection predicate encryption (IPE) and subset predicate encryption (SPE) schemes, which preserve the privacy of range queries and keyword searches. Then, we propose our PMRK scheme, which not only supports efficient and secure multidimensional range queries and keyword searches at the same time but also preserves the single-dimensional privacy for multidimensional queries, and the path pattern privacy of the R-tree. In addition, the security of IPE and SPE is formally proved, and the security of PMRK is analyzed. In the experimental part, the feasibility and efficiency of PMRK are demonstrated by conducting experiments on real data sets.