Tree-based Multi-Dimensional Range Search on Encrypted Data with Enhanced Privacy

Abstract. With searchable encryption, a data user is able to perform meaningful search on encrypted data stored in the public cloud without revealing data privacy. Besides handling simple queries (e.g., keyword queries), complex search functions, such as multi-dimensional (conjunc-tive) range queries, have also been studied in several approaches to sup-port the search of multi-dimensional data. However, current works sup-porting multi-dimensional range queries either only achieve linear search complexity or reveal additional private information to the public cloud. In this paper, we propose a tree-based symmetric-key searchable encryp-tion to support multi-dimensional range queries on encrypted data. Be-sides protecting data privacy, our proposed scheme is able to achieve faster-than-linear search, query privacy and single-dimension privacy si-multaneously compared to previous solutions. More specifically, we for-mally define the security of our proposed scheme, prove that it is se-lectively secure, and demonstrate its efficiency with experiments over a real-world dataset.