Numerous encrypted database management systems (EDBMSs) were recently developed to address data confidentiality in case the database server is compromised. Data is encrypted before it is stored at a server and the private keys are kept away from the server. The challenge in the EDBMS development is that the server is not able to perform usual database operations on the encrypted data. Novel techniques were proposed to address this issue, but most studies focused on facilitating query processing in EDBMS while little attention was paid on indexing. A secure and effective indexing method for EDBMS has not been seen. In this paper, we develop an indexing mechanism called past results knowledge base (PRKB) for EDBMS. Unlike any traditional indexing method where the index is built o...[ Read more ]

Numerous encrypted database management systems (EDBMSs) were recently developed to address data confidentiality in case the database server is compromised. Data is encrypted before it is stored at a server and the private keys are kept away from the server. The challenge in the EDBMS development is that the server is not able to perform usual database operations on the encrypted data. Novel techniques were proposed to address this issue, but most studies focused on facilitating query processing in EDBMS while little attention was paid on indexing. A secure and effective indexing method for EDBMS has not been seen. In this paper, we develop an indexing mechanism called past results knowledge base (PRKB) for EDBMS. Unlike any traditional indexing method where the index is built on plain data, we extract and accumulate knowledge from range query results to form PRKB. PRKB is secure since it does not leak additional information to an attacker. EDBMS can use PRKB to boost the performance of range query processing. In our empirical studies, PRKB can reduce query processing cost by orders of magnitudes compared to the case that no indexing is used.