Query processing in private data outsourcing using anonymization

We propose a model supporting privacy-preserving data manipulation for private data outsourcing. This builds on the model of anatomization, where identifying and sensitive information are separated, and linked only in groups such that the probability of a particular sensitive value belonging to a particular individual is below a threshold; the information needed to join the identifying and sensitive information is encrypted with a key known only to the client/data owner. By exposing data where possible, the server can perform value-added services such as data analysis while being unable to violate privacy constraints. We show how data can be queried in this model. The key contribution of this work is a relational query processor that minimizes the client-side computation while ensuring the server learns nothing violating the privacy constraints.