Processing secure, verifiable and efficient SQL over outsourced database

Database as a Service (DBaaS) economically enables the customers with limited resources to outsource large-scale databases to the cloud. However, it becomes a very challenging problem that how to execute SQL on outsourced databases while protecting the confidentiality of outsourced databases at the same time. In this paper, we present a novel protocol to enable secure and efficient database outsourcing. First, we propose a new cloud database model by introducing computation service providers (CSPs), which can accommodate the conventional DBaaS model; the CSPs undertake most of the postprocessing and reconstruction burden for database query. Next, we design our database outsourcing protocol SecureDBS by leveraging a secret sharing mechanism and a novel tree-based order-preserving encryption (OPE) mechanism. The proposed protocol supports various SQL queries, including selection, update, insertion, and aggregate queries. Further, we present a mechanism to detect malicious behaviors of the cloud. Finally, we theoretically show that our protocol is correct, secure and efficient, and experimentally demonstrate that the protocol is efficient for practical usage.