An index-based secure query processing scheme for outsourced databases

This paper proposes an index-based approach for secure query processing. Due to the rapid proliferation of cloud computing services in diverse applications, such as database as a service (DBaaS), and encrypted database systems (EDBSs) have been gaining much attentions as a way to construct secure databases in DBaaS. However, most of the existing works suffer from poor performance when dealing with large data. Some works proposed index-based query processing schemes, but they have a privacy problem that the order of attribute values may be revealed from the index structure on the server. To this problem, we propose a novel secure index-based query processing scheme where the order of attribute values is not disclosed. In the scheme, the index is maintained in such a way that the structural information regarding the index and the values (or index entries) are maintained separately, and only the latter is stored in a cloud server. When searching, a client uses the structural information (without entries) to traverse the index by cooperating with cloud servers, thereby securing the order among the index entries. We prove that, in our scheme, the order among the index entries would not be disclosed even though the data and the query log are disclosed. In addition, our experimental results show that the proposed scheme significantly outperforms existing state-of-the-art schemes.