Privacy-Preserving Queries over Outsourced Data with Access Pattern Protection

One of the concerns about database outsourcing is that the service provider may not be trustworthy. Besides protecting data against outsiders, it is necessary to hide sensitive information from the service provider. For single-server environments, data encryption is commonly used to protect data confidentiality. To use server computational resources for processing queries, data are encrypted in tuple-level. Indexing tags are computed and attached to the encrypted tuples such that the server can check if an encrypted tuple satisfies the query predicate without learning exact data values. However, with additional information of some time-based events, service providers can still infer information of the encrypted data through query access patterns if there are observed linkages between the access patterns and the time-based events. In this paper, we study the problem of information disclosure in such a scenario. We first illustrate how to launch the inference attack. Then, we formally define the problem and propose techniques for protecting access privacy. Instead of providing total privacy with a high overhead, our approach aims to lower the confidence of service providers´ inferences. Experiment results show that a high level of access privacy can be achieved with a reasonable overhead.