Outsourced Databases in the Cloud: A Privacy-Preserving Indexing Scheme

Abstract Cloud computing becomes a popular and successful paradigm for data outsourcing. Cloud computing has developed as an affordable and realistic alternative to in-house data centers. However, security and privacy concerns have arisen and are still a great barrier. To mitigate these concerns , several authors proposed to use Property-Preserving Encryption (PPE) schemes. PPE schemes enable storing and processing queries over encrypted data. But, such schemes inherently leak some information about plaintexts that could jeopardize data privacy. In this article, we address the crucial issue of protecting data privacy when performing queries on it in an untrusted cloud. We introduce new order-preserving indexing schemes that allow queries to be carried out efficiently through encrypted data. We consider a robust security model and improve security strength with a complementary order-obfuscating technique. The proposed indexing schemes preserve the expressiveness of state-of-the-art PPE schemes while at the same time offering stronger security protections compared to pre-used schemes. We provide formal proofs of the security of our schemes and prove that they meet standard notions of security against a strong adversary model. We theoretically evaluate and compare our schemes with current PPE schemes. Analytically, we show the superiority of the proposed schemes relative to on-the-shelf PPE schemes. Our comparison demonstrates some interesting insights concerning the overall security and efficiency .