Adaptive bucket formation in encrypted databases

As the mode of e-business is patterned widely, many small and medium enterprises need to rely on the database service provided by the third parties. Encryption techniques must be adopted to protect sensitive data from the service providers. A bucket-based storage technique addresses the scenarios with limit trust in database servers. However, when the buckets are constructed improperly, intruders could have a chance to guess the sensitive value distribution based on the bucket occurrences. In this paper, we propose a simple and adaptive method, named split and merge (SAM), to construct a set of buckets with balanced occurrences. The buckets with more occurrences are splitted in two parts and the neighbor bucket pairs with smaller occurrences are merged together. Some experiments are conducted to validate this method.