Secure range query over encrypted data in outsourced environments

With the rapid development of cloud computing paradigm, data owners have the opportunity to outsource their databases and management tasks to the cloud. Due to privacy concerns, it is required for them to encrypt the databases prior to outsourcing. However, there are no existing techniques handling range queries in a fully secure way. Therefore, in this paper, we focus exactly on the secure processing of range queries over outsourced encrypted databases. To efficiently process secure range queries, the extraordinarily challenging task is how to perform fully secure range queries over encrypted data without the cloud ever decrypting the data. To address the challenge, we first propose a basic secure range queries algorithm which is not absolutely secure (i.e., leaking the privacy of access patterns and path patterns). To meet better security, we present a fully secure algorithm that preserves the privacy of the data, query, result, access patterns and path patterns. To improve the performance further, we also propose two schemes to accelerate query speed. At last, we empirically analyze and conduct a comprehensive performance evaluation using the real dataset to validate our ideas and the proposed secure algorithms.