PMRK: Privacy-Preserving Multidimensional Range Query With Keyword Search Over Spatial Data

Xinqi Tu, Haiyong Bao*, Rongxing Lu, Cheng Huang, Hong Ning Dai

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

1 Citation (Scopus)


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 multi-dimensional 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 datasets.

Original languageEnglish
Pages (from-to)10464-10478
Number of pages15
JournalIEEE Internet of Things Journal
Issue number6
Early online date20 Oct 2023
Publication statusPublished - 15 Mar 2024

Scopus Subject Areas

  • Signal Processing
  • Information Systems
  • Hardware and Architecture
  • Computer Science Applications
  • Computer Networks and Communications

User-Defined Keywords

  • Keyword search
  • multidimensional range query
  • path pattern privacy
  • privacy-preserving
  • single-dimensional privacy


Dive into the research topics of 'PMRK: Privacy-Preserving Multidimensional Range Query With Keyword Search Over Spatial Data'. Together they form a unique fingerprint.

Cite this