Secure and efficient range queries on outsourced databases using Rp-trees

We show how to execute range queries securely and efficiently on encrypted databases in the cloud. Current methods provide either security or efficiency, but not both. Many schemes even reveal the ordering of encrypted tuples, which, as we show, allows adversaries to estimate plaintext values accurately. We present the Rp-tree, a hierarchical encrypted index that may be securely placed in the cloud, and searched efficiently. It is based on a mechanism we design for encrypted halfspace range queries in Rd, using Asymmetric Scalar-product Preserving Encryption. Data owners can tune the Rp-tree parameters to achieve desired security-efficiency tradeoffs. We also present extensive experiments to evaluate Rp-tree performance. Our results show that Rp-tree queries are efficient on encrypted databases, and reveal far less information than competing methods.