A Multi-agent Based Method for Reconstructing Buckets in Encrypted Databases

Outsourcing databases to third parties demonstrates a trend for many enterprise users. A bucket-based storage method is proposed for this emerging scenario. However, the introduction of buckets brings out challenges in balancing query efficiency and data secrecy. By measuring the query efficiency on false hits and the data secrecy on entropy amounts, an optimization problem is formalized to find a set of buckets on a tradeoff between efficiency and secrecy. We propose a multi-agent based method to find an approximate solution to this problem. In our solving, each agent manages a bucket and always tries to decrease the number of false hits by moving out a managed element on local evaluations. These local behaviors are aggregated as a global trend to find a set of buckets with fewer false hits. We validate this method by conducting simulated experiments on range queries.