Geometric range search on encrypted spatial data

Boyang Wang, Ming Li, Haitao Wang

Research output: Contribution to journalArticlepeer-review

66 Scopus citations


Geometric range search is a fundamental primitive for spatial data analysis in SQL and NoSQL databases. It has extensive applications in location-based services, computeraided design, and computational geometry. Due to the dramatic increase in data size, it is necessary for companies and organizations to outsource their spatial data sets to third-party cloud services (e.g., Amazon) in order to reduce storage and query processing costs, but, meanwhile, with the promise of no privacy leakage to the third party. Searchable encryption is a technique to perform meaningful queries on encrypted data without revealing privacy. However, geometric range search on spatial data has not been fully investigated nor supported by existing searchable encryption schemes. In this paper, we design a symmetric-key searchable encryption scheme that can support geometric range queries on encrypted spatial data. One of our major contributions is that our design is a general approach, which can support different types of geometric range queries. In other words, our design on encrypted data is independent from the shapes of geometric range queries. Moreover, we further extend our scheme with the additional use of tree structures to achieve search complexity that is faster than linear. We formally define and prove the security of our scheme with indistinguishability under selective chosen-plaintext attacks, and demonstrate the performance of our scheme with experiments in a real cloud platform (Amazon EC2).

Original languageEnglish (US)
Article number7347418
Pages (from-to)704-719
Number of pages16
JournalIEEE Transactions on Information Forensics and Security
Issue number4
StatePublished - Apr 1 2016
Externally publishedYes


  • Encrypted data
  • Geometric range search
  • Spatial data

ASJC Scopus subject areas

  • Safety, Risk, Reliability and Quality
  • Computer Networks and Communications


Dive into the research topics of 'Geometric range search on encrypted spatial data'. Together they form a unique fingerprint.

Cite this