Index-based, Encrypted Database Query

Data encryption is an important measure to ensure confidentiality of important data. It is a difficult problem that how to query the encrypt database data efficiently.To enhance query performance of the encrypted database, a new type of B+tree index is designed for it. It makes a single index node can hold any number of keyword by using a cipher-text block array to organize the encrypted keywords,thus breaking the limit on number of keywords in the index node by the encryption length. In the index node, keywords are encrypted and stored separately with pointers. So what a cipher-text block holds are all keywords or pointers. This can increase the effective rate of keywords in a cipher-text block, reduce the length of the keyword array. Reducing the length of the keyword array can speed up the query, lead to less decryption. To support the range query, a prior-pointer and a next-pointer are added in the leaf node, pointing to the adjacent front leaf node and the next adjacent leaf node, so from a leaf node it is easy to find all the front and all the back leaf nodes of it.To speed up search on the cipher-text block array of keywords, binary search algorithms are designed for single-value queries and range queries on cipher-text block array. Binary search algorithm for single-value queries on cipher-text block array is based on the characteristics of the cipher-text block array and regards a block cipher as a single value, but in the query process it must check all the values of the cipher-text block. This would reduce the amount of cipher-text block to be decrypt. Binary search algorithm for range queries on cipher-text block also regards a block cipher as a single value. But what the algorithm looks for on the leaf node is the boundary keyword that satisfies the query. The ultimate query results are the pointer corresponding to the boundary keyword and all the left (or right) pointers of it, and all the pointers in the leaf nodes on the left (or right) of the leaf node being search on. By the prior-pointers and the next-pointers in the leaf nodes, you can find all the leaf nodes satisfying the query. So scope queries on the encrypted database are realized, which contain operators such as<,≤,>,≥. Binary search algorithms on cipher-text block array solve problems in these situations that query value is less than the first keyword of a cipher-text block, more than the last keyword of a cipher-text block, between blocks and between the two adjacent leaf nodes. The algorithms also resole the problem that keywords have different semantics in different nodes such as the root node, branch nodes, leaf nodes. Meanwhile, by using this index, it can be easy to get the maximum, the minimum of all records.Simulation results show that block binary search on the cipher-text array need much less amount of decryption, and return the answer more quickly than sequential search.