Research Article
Tree-Based Multi-dimensional Range Search on Encrypted Data with Enhanced Privacy
@INPROCEEDINGS{10.1007/978-3-319-23829-6_26, author={Boyang Wang and Yantian Hou and Ming Li and Haitao Wang and Hui Li and Fenghua Li}, title={Tree-Based Multi-dimensional Range Search on Encrypted Data with Enhanced Privacy}, proceedings={International Conference on Security and Privacy in Communication Networks. 10th International ICST Conference, SecureComm 2014, Beijing, China, September 24-26, 2014, Revised Selected Papers, Part I}, proceedings_a={SECURECOMM}, year={2015}, month={11}, keywords={Multi-dimensional range search Encrypted data}, doi={10.1007/978-3-319-23829-6_26} }- Boyang Wang
Yantian Hou
Ming Li
Haitao Wang
Hui Li
Fenghua Li
Year: 2015
Tree-Based Multi-dimensional Range Search on Encrypted Data with Enhanced Privacy
SECURECOMM
Springer
DOI: 10.1007/978-3-319-23829-6_26
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 (conjunctive) range queries, have also been studied in several approaches to provide search functionalities over multi-dimensional data. However, current works supporting 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 encryption to support multi-dimensional range queries on encrypted data. Besides protecting data privacy, our proposed scheme is able to achieve faster-than-linear search, query privacy and single-dimensional privacy simultaneously compared to previous solutions. More specifically, we formally define the security of our proposed scheme, prove that it is selectively secure, and demonstrate its faster-than-linear efficiency with experiments over a real-world dataset.