A Method for Reducing False Hits in Querying Encrypted Databases

The emerging trend of outsourcing database to third parties motivates the research of protecting sensitive data from database service providers. The bucket-based method is one of the feasible methods to store those data encrypted. Since a bucket may contain many different attribute values, this method also introduces some false query results when performing queries over encrypted databases. Strategies are needed to balance the data secrecy and query efficiency. In this paper, we use the expected number of false hits in query results to measure the query efficiency and formulate the tradeoff between security and efficiency as an optimization problem. Constrained by a given range of the bucket set entropies, a local search based method is applied to regulate the elements between neighboring bucket pairs and reconstruct a new set of buckets with fewer false hits. We validate this method with some experiments on range queries. Experiment results show that it can decrease the number of false hits in two different range query behaviors.